An analysis model on nonblocking multirate broadcast networks

ABSTRACT

Designing efficient interconnection networks with powerful connecting capability remains a key issue to parallel and distributed computing systems. Many progresses have been made in nonblocking broadcast networks which can realize all one-to-many connections between any network input port and a set of output ports without any disturbance (that is, rearrangement) of other existing connections. However, all results obtained so far for broadcast networks are for the circuit switching or single rate communication model. Meanwhile, there have been growing interests in large networks operated in a packet switching manner. This type of network can be modeled as a multirate network wherein a single link can be shared by multiple connections with arbitrary data rate. Previous work has been done on the blocking behavior of multirate one-to-one connection or permutation networks. However, yet very little is known about the behavior of multirate one-to-many connection or broadcast networks. In this paper, we will determine nonblocking conditions for v(m,n1,r1,n2,r2) networks under which any multirate broadcast connection request from a network input port to a set of network output ports can be satisfied without any disturbance of the existing connection in the network. Our results show that more general multirate broadcast networks can be constructed in the same order of hardware complexity as the best available single rate nonblocking broadcast networks. Our proofs for the theorems also imply an efficient routing algorithm for such networks. Multirate broadcast networks can provide strong support for parallel and distributed computing systems which require to broadcast multirate data in a random-access environment.

REFERENCES

• 1: H.S. Stone, "Parallel proces~ng with the perfect shut fie," 1EEE Trans. Computers, vol. C-20, pp. 153-161, 1971.
• 2: L. Bhuyan and D. Agrawal, "General hypercube and hyperbus structures for a computer network," 1EEE Trans. Computers, vol. C-33, pp. 323-333, 1984.
• 3: T. Feng, "A survey of interconnection networks," Computers, vol. 14, pp. 12-27, Dec. 1981.
• 4: V.E. Benes, "Heu~stic remarks and mathematical problems regarding the theory of sw~ching systems," The Bell System Technical Journa~ vol. 41, pp.1201- 1247, 1962.
• 5: Abraham Waksman, A Permutation Network, Journal of the ACM (JACM), v.15 n.1, p.159-163, Jan. 1968 [doi>10.1145/321439.321449]
• 6: C. Clos, "A study of non-blocking swRchiing networks," The Bell System Technical Journal, vol. 32, pp. 406- 424, 1953.
• 7: D. Cantor, "On nonblocking switching networks," Ne~ works, vol. 2, pp. 367-377, 1972.
• 8: F.K. H wang and A. J ajszczyk, "On nonblocking multN connection networks," 1EEE Trans. Communica~ons, vol. COM-34, pp. 1038-1041, 1986.
• 9: J.S. Turner, "PracficM wid~sense nonblocking gene~ alized connectors," Washington University Computer Science Research Repor~88-2~ 1988.
• 10: Paul Feldman , Joel Friedman , Nicholas Pippengers, Wide-sense nonblocking networks, SIAM Journal on Discrete Mathematics, v.1 n.2, p.158-173, May 1988 [doi>10.1137/0401018]
• 11: Yuanyuan Yang , Gerald M. Masson, Nonblocking Broadcast Switching Networks, IEEE Transactions on Computers, v.40 n.9, p.1005-1015, September 1991 [doi>10.1109/12.83662]
• 12: Riccardo Melen , Jonathan S. Turner, Nonblocking multirate networks, SIAM Journal on Computing, v.18 n.2, p.301-313, April 1989 [doi>10.1137/0218021]
• 13: Shun-Ping Chung , Keith W. Ross, On nonblocking multirate interconnection networks, SIAM Journal on Computing, v.20 n.4, p.726-736, Aug. 1991 [doi>10.1137/0220046]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Design, Theory, Verification

Keywords:
broadcast, interconnection networks, multirate traffic, nonblocking, packet switching