Multicasting protocols for high-speed, wormhole-routing local area networks

ABSTRACT

Wormhole routing LANs are emerging as an effective solution for high-bandwidth, low-latency interconnects in distributed computing and cluster computing applications. An important example is the 640 Mb/s crossbar-based Myrinet. A key property of conventional LANs, which is valuable for many distributed applications, is transparent, reliable network-level multicast. It is desirable to retain this property also in wormhole LANs. Unfortunately, efficient, reliable multicasting in wormhole LANs is problematic because of the potential for deadlocks. As a consequence, current multicasting implementations typically consist of repeated unicast or assume a priori buffer reservations. These solutions, however, tend to increase latency and do not scale well.In this paper we address the problem of providing transparent, reliable, efficient network level multicasting in the wormhole LAN. We describe several protocols for achieving deadlock-free, reliable multicasting using restricted routing and fast buffer reservation techniques. Tradeoffs involving complexity and performance of various solutions are discussed, and are illustrated using simulation. A simple multicast implementation for Myrinet has been carried out, and experimental results are presented.

REFERENCES

• BCF+95: Nanette J. Boden , Danny Cohen , Robert E. Felderman , Alan E. Kulawik , Charles L. Seitz , Jakov N. Seizovic , Wen-King Su, Myrinet: A Gigabit-per-Second Local Area Network, IEEE Micro, v.15 n.1, p.29-36, February 1995 [doi>10.1109/40.342015]
• BGK+96: Rajive Bagrodia , Yu-an Chen , Mario Gerla , Bruce Kwan , Jay Martin , Prasasth Palnati , Simon Walton, Parallel simulation of a high-speed wormhole routing network, Proceedings of the tenth workshop on Parallel and distributed simulation, p.47-56, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• BtL94: R. L. Bagrodia , Wen-Toh Liao, Maisie: A Language for the Design of Efficient Discrete-Event Simulations, IEEE Transactions on Software Engineering, v.20 n.4, p.225-238, April 1994 [doi>10.1109/32.277572]
• DS87: W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• FJM+95: Sally Floyd , Van Jacobson , Steve McCanne , Ching-Gung Liu , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.342-356, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• fST94: Institute for Simulation and Training. Standard for Distributed Interactive Simulation- Application protocols (Draft IEEE standard). Technical Report IST-CR-94-50, University of Central Florida, Orlando, March 1994.
• Jac94: Van Jacobson. Multimedia conferencing on the Internet. InACM SIGCOMM '94, August 1994. Tutorial 4.
• KK79: P. Kermani and L. Kleinrock. Virtual Cutthrough: A New Computer Communication Switching Technique. Computer Networks, 3(4):267-286, September 1979.
• NM93: Lionel M. Ni , Philip K. McKinley, A Survey of Wormhole Routing Techniques in Direct Networks, Computer, v.26 n.2, p.62-76, February 1993 [doi>10.1109/2.191995]
• PGL96: P. Palnati , M. Gerla , E. Leonardi, Deadlock-free routing in an optical interconnect for high-speed wormhole routing networks, Proceedings of the 1996 International Conference on Parallel and Distributed Systems, p.256, June 03-06, 1996
• PLC95: Scott Pakin , Mario Lauria , Andrew Chien, High performance messaging on workstations: Illinois fast messages (FM) for Myrinet, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.55-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224360]
• PLG95: Bidirectional shufflenet: a multihop topology for backpressure flow control, Proceedings of the 4th International Conference on Computer Communications and Networks, p.74, September 20-23, 1995
• SBB+91: M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, T. L. Rodeheffer, E. H. Satterthwaite, and C. P. Thacker. Autonet: A High-Speed, Self-Configuring Local Area Network Using Point-to-Point Links. IEEE Journal on Selected Areas in Communications, 9(8):1318-35, October 1991.
• VLB96: K. Verstoep, K. Langendoen, and H. Bal. Efficient reliable multicast on Myrinet. Technical Report IR-399, Department of Mathematics and Computer Science, Vrije Universiteit, Amsterdam, January 1996.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Performance, Reliability