Multicast in Wormhole-Switched Torus Networks Using Edge-Disjoint Spanning Trees |
| |
| Affiliation: | 1. Myricom Inc. 325 N. Santa Anita Avenue, Arcadia, California, 91006;2. School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, Georgia, 30332-0250;1. Department of Cardiovascular Medicine, Mayo Clinic, Rochester, MN;2. Division of Biomedical Statistics and Informatics, Mayo Clinic, Rochester, MN;3. Department of Laboratory Medicine and Pathology, Mayo Clinic, Rochester, MN;4. Department of Business Development, Mayo Clinic, Rochester, MN;5. Department of Internal Medicine, Mayo Clinic, Rochester, MN;6. Division of Nephrology and Hypertension, Mayo Clinic, Rochester, MN;7. AliveCor, Inc, San Francisco, CA;8. ZS Pharma, Inc, San Mateo, CA;9. University of California, Irvine, School of Medicine, Irvine, CA;1. University of the Free State, Faculty of Natural and Agricultural Sciences, Department of Computer Science and Informatics, P. O. Box 339, Bloemfontein, 9300, South Africa;2. Tshwane University of Technology, Faculty of Engineering and the Built Environment, Department of Electrical Engineering, Pretoria, South Africa;1. Department of Neurology, Ipswich Hospital NHS Trust, Ipswich, United Kingdom;2. School of Social and Community Medicine, University of Bristol, Bristol, United Kingdom;3. Institute of Neurological Sciences, Queen Elizabeth University Hospital, Glasgow, United Kingdom;4. Department of Neurology, Queen''s Medical Centre, Nottingham, United Kingdom;5. Department of Clinical Neurosciences, John van Geest Centre for Brain Repair, Cambridge, United Kingdom;6. Institute of Neuroscience, University of Newcastle, Newcastle upon Tyne, United Kingdom;7. Sobell Department of Motor Neuroscience, UCL Institute of Neurology, London, United Kingdom;8. Reta Lila Weston Laboratories, Department of Molecular Neuroscience, UCL Institute of Neurology, London, United Kingdom;9. Department of Clinical Neuroscience, UCL Institute of Neurology, London, United Kingdom;10. Institute of Psychological Medicine and Clinical Neurosciences, MRC Centre for Neuropsychiatric Genetics and Genomics, Cardiff University, Cardiff, United Kingdom;11. Department of Molecular Neuroscience, UCL Institute of Neurology, London, United Kingdom;1. Zachry Department of Civil Engineering, Texas A&M University, 3136 TAMU, College Station, TX, 77845, USA;2. Texas A&M AgriLife Research and Extension Center at El Paso, 1380 A&M Circle, El Paso, TX, 79927, USA;1. Muğla Sıtkı Koçman University Education and Research Hospital, Department of Anesthesiology and Reanimation, Muğla, Turkey;2. Yozgat Bozok University School of Medicine, Department of Anesthesiology and Reanimation, Yozgat, Turkey;3. Muğla Sıtkı Koçman University School of Medicine, Department of Internal Medicine, Division of Medical Oncology, Muğla, Turkey;4. Ankara Yıldırım Beyazıt University, School of Medicine, Department of Anesthesiology and Reanimation, Ankara, Turkey |
| |
| Abstract: | A tree-based multicast algorithm for wormhole-switched networks which makes use of multiple edge-disjoint spanning trees is presented. The disjoint spanning-tree multicast, or DSTM, algorithm provides deadlock-free multicast routing that is fully compatible with unicast. The application of the DSTM algorithm to 2-dimensional torus networks is considered. A family of constructions of two spanning trees in the torus is given along with a formal proof of their edge-disjointness. Two constructions from this family are selected and shown to produce diameters no greater than twice that of the torus. Flit-level simulation results are presented to show that DSTM outperforms the best single spanning tree multicast approach by up to a factor of two. The DSTM algorithm is also simulated for different spanning tree constructions. The results show that our novel tree construction is significantly better for multicast than those produced by a general tree construction method that applies to arbitrary-topology networks (J. Roskind and R. Tarjan, Math. Oper. Res.10 (Nov. 1985), 701–708). Finally, two approaches to providing single link fault tolerance with DSTM are presented and evaluated. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
