The authors propose a simple table-free routing technique for the IEEE 802.6 Distributed Queue Dual Bus (DQDB). It offers the simplicity of high-speed packet switching, such as Batcher-Bayan, techniques to metropolitan-area networks. As in high-speed packet switching networks, it consists of a number of stages. A so-called self-routing technique routes a packet from one end to the other without table processing. By checking only one bit in the routing tag of a message at each stage, a switch knows to which switch the message is to be routed in the next stage. The proposed technique is similar to the knockout switch. However, instead of performing switching in a small area, it covers a much wider (metropolitan) area. Therefore, the technique becomes distributed. The proposed routing technique can be extended to cover a service of point-to-multipoint communications, something which is essential for B-ISDN, while maintaining much of its simplicity. Various issues of sequential delivery, replication, and label management are addressed. A novel technique for simplifying topologies is presented.>

Even though IEEE 802.6 can cover longer distances than those of local area networks (LANs), it is limited by unfairness in terms of average access delay. The effect of distance on average access delay is analyzed based on homogeneous assumptions, and a technique to extend 802.6 over a wider area is proposed. The technique makes possible simplification of topology for wide area networks (WANs), which in turn simplifies routing and network management tasks.>

Designing concurrent systems has been shown to be difficult due to state explosion problems. A synthesis technique using Petri nets is proposed to tackle the problem. A set of rules has been proposed to guide designers incrementally expanding Petri nets under design while maintaining the logical correctness. These rules cover the semantics of concurrency, exclusiveness, cyclicity, and interactions.>

The authors present a procedure for computing the cycle time of concurrent systems modeled by a restricted class of Petri nets, i.e. decision-free and safe persistent nets. The procedure is based on formulating the cycle time computation as a minimal cost-to-time ratio cycle problem. The result is an efficient algorithm with a computational complexity of O(n/sup 3/log/sub 2/ n). By using an example with a stochastic counterpart, it is shown that the results are consistent with those obtained by more complex Markov analysis.>

Petri net is a powerful model for analyzing communication protocols because they share many common properties. Currently, protocol analysis suffers the state explosion problem especially for error-recoverable protocols and multi-party protocols. Protocol synthesis relieves this problem by generating new and complicated protocols from simple subsets of the protocol models. Reduction analysis provides theoretical ground for correct synthesis or expansion. Thus, reduction is a very important research area. In this paper, we present a general Petri net reduction algorithm that reduces the number of states while preserving all desirable and undesirable properties. To the best of our knowledge, this is the first general Petri net reduction algorithm for protocol analysis. We first present and extend Dong's [DON 83] definition of WBMs to include more subnets as WBMs. To render the reductions automated, a new concept of simple well-behaved modules (SWBMs) is introduced. Recursively performing reductions of SWBMs, complicated WBMs can be reduced. A main program is written to implement this recursive procedure. The problem is then reduced to finding conditions for SWBMs. We do this by progressing from simpler SWBMs to more complicated ones, i.e., from single-arc ones to multi-arcs ones. Finally, we demonstrate the usefulness of this algorithm by applying it to the state exploration in protocol synthesis. Other applications such as error detection, performance evaluation, and software engineering will be discussed in future.

We have developed a correct, general, and efficient procedure of synthesizing two-party error-recoverable protocols for noisy channels where messages could be lost, corrupted, and/or missequenced. The state explosion problem has been tackled by synthesizing the error-recoverable protocol (ERP) from its noiseless local entity model using certain rules. This reduction arises from the approaches of local modeling and elaboration. We expect that these two approaches will also play a major role in tackling the complexity problems in designing multi-party protocols. Measures of efficiency and functionality improvements have been discussed.