Article

Free access

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

Authors:

Mario Gerla,

Prasasth Palnati,

Simon WaltonAuthors Info & Claims

SIGCOMM '96: Conference proceedings on Applications, technologies, architectures, and protocols for computer communications

Pages 184 - 193

https://doi.org/10.1145/248156.248173

Published: 28 August 1996 Publication History

PDF eReader

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

[1]

N. Boden, D. Cohen, R. E. Felderman, A. E. Kulawik, C. L. Seitz, J. N. Seizovic, and W.-K. Su. Myrinet: A gigabit-per-second local-area network. IEEE Micro, 15(1), February 1995.

Digital Library

Google Scholar

[2]

R. Bagrodia, M. Gerla, B. Kwan, J. Martin, P. Prasasth, and S. Walton. Parallel simulation of a high-speed wormhole routing network. In Tenth ACM Workshop on Parallel and Distributed Simulation (PADS '96), Philadelphia, PA, May 1996.

Digital Library

Google Scholar

[3]

R. Bagrodia and Wen toh Liao. Maisie: A language for design of efficient discrete-event simulations. IEEE Transactions on Software Engineering, April 1994.

Digital Library

Google Scholar

[4]

W.J. Dally and C. L. Seitz. Deadlock-Free Message Routing in Multiprocessor Interconnection Networks. IEEE Transactions on Computers, C-36(5):547-553, May 1987.

Digital Library

Google Scholar

[5]

Sally Floyd, Van Jacobson, Steven McCanne, Ching-Gung Liu, and Lixia Zhang. A reliable multicast framework for lightweight sessions and application level framing. In Proceedings ACM SIGCOMM '95, Cambridge, MA, August 1995.

Digital Library

Google Scholar

[6]

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.

Google Scholar

[7]

Van Jacobson. Multimedia conferencing on the Internet. InACM SIGCOMM '94, August 1994. Tutorial 4.

Google Scholar

[8]

P. Kermani and L. Kleinrock. Virtual Cutthrough: A New Computer Communication Switching Technique. Computer Networks, 3(4):267-286, September 1979.

Google Scholar

[9]

L.M. Ni and P. K. McKinley. A Survey of Wormhole Routing Techniques in Direct Networks. IEEE Computer, 26(2):62-76, February 1993.

Digital Library

Google Scholar

[10]

P. Palnati, M. Gerla, and E. Leonardi. Deadlock-free routing in an optical interconnect for high-speed wormhole routing networks. In Prec. Int'l Conf. on Parallel and Distributed Systems (ICPADS '96), Tokyo, June 1996.

Digital Library

Google Scholar

[11]

S. Pakin, M. Lauria, and A. Chien. High performance messaging on workstations: Illinois Fast Messages (FM) for Myrinet. In Proceedings of Supercemputing '95, December 1995.

Digital Library

Google Scholar

[12]

Prasasth Palnati, Emilio Leonardi, and Mario Gerla. Bidirectional Shuffienet: A Multihop Topology for Backpressure Flow Control. In Prec. Int'l Conf. on Computer Communications and Networks (ICCCN '95), Las Vegas, September 1995.

Digital Library

Google Scholar

[13]

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.

Digital Library

Google Scholar

[14]

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.

Crossref

Google Scholar

Cited By

View all

Zhang XShin K(2010)DACProceedings of the 29th conference on Information communications10.5555/1833515.1833680(1064-1072)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833680
Bauer GBoyer VBranson JBrett ACano ECarboni ACiganek MCittolin SErhan SGigi DGlege FGomez-Reino RGulmini MMlot EGutleber JJacobs CKim JKlute MLipeles EPerez JMaron GMeijers FMeschi EMoser RMurray SOh AOrsini LPaus CPetrucci APieri MPollet LRacz ASakulin HSani MSchieferdecker PSchwick CSumorok KSuzuki ITsirigkas DVarela J(2007)CMS DAQ Event Builder Based on Gigabit Ethernet2007 15th IEEE-NPSS Real-Time Conference10.1109/RTC.2007.4382750(1-5)Online publication date: Apr-2007
https://doi.org/10.1109/RTC.2007.4382750
Bauer GBoyer VBranson JBrett ACano ECarboni ACiganek MCittolin SErhan SGigi DGlege FGomez-Reino RGulmini MMlot EGutleber JJacobs CKim JKlute MLipeles EPerez JMaron GMeijers FMeschi EMoser RMurray SOh AOrsini LPaus CPetrucci APieri MPollet LRacz ASakulin HSani MSchieferdecker PSchwick CSumorok KSuzuki ITsirigkas DVarela J(2007)Effects of Adaptive Wormhole Routing in Event Builder Networks2007 15th IEEE-NPSS Real-Time Conference10.1109/RTC.2007.4382749(1-7)Online publication date: Apr-2007
https://doi.org/10.1109/RTC.2007.4382749
Show More Cited By

Index Terms

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

Recommendations

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

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 ...
Experimental evaluation of TCP protocols for high-speed networks

In this paper, we present experimental results evaluating the performance of the scalable-TCP, HS-TCP, BIC-TCP, FAST-TCP, and H-TCP proposals in a series of benchmark tests. In summary, we find that both Scalable-TCP and FAST-TCP consistently exhibit ...
Multicasting at the Host Interface Level in Wormhole Networks
ICNP '98: Proceedings of the Sixth International Conference on Network Protocols

Wormhole routing LANs are an effective solution for high-bandwidth, low-latency interconnects in distributed computing and cluster computing applications. Since a key property of conventional LANs, which is valuable for many distributed applications, is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGCOMM '96: Conference proceedings on Applications, technologies, architectures, and protocols for computer communications

August 1996

330 pages

ISBN:0897917901

DOI:10.1145/248156

Chairmen:
Deborah Estrin
Univ. of Southern California, Los Angeles
,
Sally Floyd
Lawrence Berkeley National Laboratory, Berkeley, CA
,
Craig Partridge
BBN Systems and Technologies
,
Editor:
Martha Steenstrup
BBN, USA

ACM SIGCOMM Computer Communication Review Volume 26, Issue 4
Oct. 1996
335 pages
ISSN:0146-4833
DOI:10.1145/248157
Editor:
Martha Steenstrup
BBN Corporation, Cambridge, MA
Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 August 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

COMM96

Sponsor:

SIGCOMM

COMM96: ACM SIGCOMM '96

August 28 - 30, 1996

California, Palo Alto, USA

Acceptance Rates

SIGCOMM '96 Paper Acceptance Rate 27 of 162 submissions, 17%;

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
545
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)3

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang XShin K(2010)DACProceedings of the 29th conference on Information communications10.5555/1833515.1833680(1064-1072)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833680
Bauer GBoyer VBranson JBrett ACano ECarboni ACiganek MCittolin SErhan SGigi DGlege FGomez-Reino RGulmini MMlot EGutleber JJacobs CKim JKlute MLipeles EPerez JMaron GMeijers FMeschi EMoser RMurray SOh AOrsini LPaus CPetrucci APieri MPollet LRacz ASakulin HSani MSchieferdecker PSchwick CSumorok KSuzuki ITsirigkas DVarela J(2007)CMS DAQ Event Builder Based on Gigabit Ethernet2007 15th IEEE-NPSS Real-Time Conference10.1109/RTC.2007.4382750(1-5)Online publication date: Apr-2007
https://doi.org/10.1109/RTC.2007.4382750
Bauer GBoyer VBranson JBrett ACano ECarboni ACiganek MCittolin SErhan SGigi DGlege FGomez-Reino RGulmini MMlot EGutleber JJacobs CKim JKlute MLipeles EPerez JMaron GMeijers FMeschi EMoser RMurray SOh AOrsini LPaus CPetrucci APieri MPollet LRacz ASakulin HSani MSchieferdecker PSchwick CSumorok KSuzuki ITsirigkas DVarela J(2007)Effects of Adaptive Wormhole Routing in Event Builder Networks2007 15th IEEE-NPSS Real-Time Conference10.1109/RTC.2007.4382749(1-7)Online publication date: Apr-2007
https://doi.org/10.1109/RTC.2007.4382749
Hoefler TLichei ARehm W(2007)Low-Overhead LogGP Parameter Assessment for Modern Interconnection Networks2007 IEEE International Parallel and Distributed Processing Symposium10.1109/IPDPS.2007.370593(1-8)Online publication date: Mar-2007
https://doi.org/10.1109/IPDPS.2007.370593
Hoefler TSiebert CRehm W(2007)A practically constant-time MPI Broadcast Algorithm for large-scale InfiniBand Clusters with Multicast2007 IEEE International Parallel and Distributed Processing Symposium10.1109/IPDPS.2007.370475(1-8)Online publication date: Mar-2007
https://doi.org/10.1109/IPDPS.2007.370475
Petrini FMoody AFernandez JFrachtenberg EPanda D(2006)NIC-based reduction algorithms for large-scale clustersInternational Journal of High Performance Computing and Networking10.1504/IJHPCN.2006.0106354:3/4(122-136)Online publication date: 1-Aug-2006
https://dl.acm.org/doi/10.1504/IJHPCN.2006.010635
Moody AFernandez JPetrini FPanda DMcGraw J(2003)Scalable NIC-based Reduction on Large-scale ClustersProceedings of the 2003 ACM/IEEE conference on Supercomputing10.1145/1048935.1050209Online publication date: 15-Nov-2003
https://dl.acm.org/doi/10.1145/1048935.1050209
Moh SYu CYoun HHan DLee BLee D(2001)A Fast Tree-Based Barrier Synchronization on Switch-Based Irregular NetworksHigh Performance Computing — HiPC 200010.1007/3-540-44467-X_24(273-282)Online publication date: 8-Jun-2001
https://doi.org/10.1007/3-540-44467-X_24
Bhoedjang RVerstoep KRühl TBal HHofman R(2000)Evaluating design alternatives for reliable communication on high-speed networksACM SIGOPS Operating Systems Review10.1145/384264.37900434:5(71-81)Online publication date: 12-Nov-2000
https://dl.acm.org/doi/10.1145/384264.379004
Bhoedjang RVerstoep KRühl TBal HHofman R(2000)Evaluating design alternatives for reliable communication on high-speed networksACM SIGARCH Computer Architecture News10.1145/378995.37900428:5(71-81)Online publication date: 12-Nov-2000
https://dl.acm.org/doi/10.1145/378995.379004
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

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

Experimental evaluation of TCP protocols for high-speed networks

Multicasting at the Host Interface Level in Wormhole Networks