Packet switching in banyan networks

ABSTRACT

This paper presents a formal scheme for addressing base and apex nodes in SW-banyan networks. This scheme is used for routing packets in the network. Packet-switching, in conjunction with the the circuit-switch mode of operation, offers a very flexible and powerful mechanism for interprocess communication in the multiprocessor architectures based on the banyan networks. Finally, a fault-tolerent scheme for re-routing the packets in the network is presented, in case the packet encounters a faulty node in its path.

REFERENCES

• 1: L. Rodney Goke , G. J. Lipovski, Banyan networks for partitioning multiprocessor systems, Proceedings of the 1st annual symposium on Computer architecture, p.21-28, December 09-11, 1973
• 2: Lipovski, G.J, Tripathi, A., "A Varistructure Array Processor", Proceedings of the Parallel Processing Conference, 1977.
• 3: Anderesen Steinar, "Looping Algorithm Extended to Base 2t Rearrangeable Switching Networks", IEEE Tr. on Communication, October 1977, pp. 1057-1063.
• 4: Wu, C., Feng, T., "Routing Technique for Class of Multistages Interconnection Networks", 1978 Conference on Parallel Processing, pp. 197-205.
• 5: Lawrie, D.H., "Access and Alignment of Data in Array Processor", IEEE Transactions on Computers, vol. c-24, no.12, Dec.1975, pp.1145-1155.
• 6: Stone, H.S., "Parallel Processing with Perfect Shuffle", IEEE Trans. on Computers, vol. c-20, pp153-161, Feb.1971.
• 7: Benes, V.E., "Mathematical Theory of Connecting Networks and Telephone Traffic", Academic Press, 1965.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Design, Performance, Verification