More Web Proxy on the site http://driver.im/

article

STAR: a transparent spanning tree bridge protocol with alternate routing

Authors:

Whay Chiou Lee,

Klara NahrstedtAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 32, Issue 3

Pages 33 - 46

https://doi.org/10.1145/571697.571722

Published: 01 July 2002 Publication History

Abstract

With increasing demand for multimedia applications, local area network (LAN) technologies are rapidly being upgraded to provide support for quality of service (QoS). In a network that consists of an interconnection of multiple LANs via bridges, the QoS of a flow depends on the length of an end-to-end forwarding path. In the IEEE 802.1D standard for bridges, a spanning tree is built among the bridges for loop-free frame forwarding. Albeit simple, this approach does not support all-pair shortest paths. In this paper, we present a novel bridge protocol, the Spanning Tree Alternate Routing (STAR) Bridge Protocol, that attempts to find and forward frames over alternate paths that are provably shorter than their corresponding tree paths. Being backward compatible to IEEE 802.1D, our bridge protocol allows cost-effective performance enhancement of an existing extended LAN by incrementally replacing a few bridges in the extended LAN by the new STAR bridges. We develop a strategy to ascertain bridge locations for maximum performance gain. Our study shows that we can significantly improve the end-to-end performance when deploying our bridge protocol.

References

[1]

Data-Over-Cable Service Interface Specifications (DOCSIS).

[2]

Information technology - telecommunications and information exchange between systems - local an d metropolitan area networks - common specifications. Part 5: Remote Media Access Control (MAC) bridging, 1998.

[3]

Information technology - telecommunications and information exchange between systems - local and metropolitan area networks - common specifications. Part 3: Media Access Control (MAC) bridges, ISO/IEC 15802-3, ANSI/IEEE Std 802.1D, 1998.

[4]

E. Benhamou. Integrating Bridges and Routers in a Large Internetwork. IEEE Network Magazine, 2(1), Jan. 1988.

Digital Library

[5]

L. Bosack and C. Hedrick. Problems in Large LANs. IEEE Network Magazine, 2(1), Jan. 1988.

[6]

R. P. et al. Utilization of Redundant Links in Bridged Networks. U.S. Patent Number 5,150,360, Sept. 22, 1992.

[7]

R. Garcia, J. Duato, and J. Serrano. A New Transparent Bridge Protocol for LAN Internetworking Using Topologies with Active Loops. In International Conference on Parallel Processing, 1998.

Digital Library

[8]

J. Hart. Extending the IEEE 802.1 MAC Bridge Standard to Remote Bridges. IEEE Network Magazine, 2(1), Jan. 1988.

[9]

J. Hart. Distributed Load Sharing. U.S. Patent Number 4,811,337, Mar. 7, 1989.

[10]

T. Jeffree. Unifying Class of Service Provision in LANs - The Role of MAC Bridges. IEE Colloquium, 1999.

[11]

Y.-D. Lin and M. Gerla. Brouter: The Transparent Bridge with Shortest Path in Interconnected LANs. In LCN, 1991.

[12]

K. Lui and W. Lee. Spanning tree alternate routing bridge protocol. Technical report, Department of Computer Science, University of Illinois at Urbana-Champaign, Apr. 2001.

Digital Library

[13]

R. Perlman. Interconnections - Bridges, Routers, Switches, and Internetworking Protocols. Addison-Wesley, second edition, 1999.

Digital Library

[14]

R. Perlman, A. Harvey, and G. Varghese. Choosing the Appropriate ISO Layer for LAN Interconnection. IEEE Network Magazine, 2(1), Jan. 1988.

[15]

B. Rajagopalan and M. Faiman. Load Sharing and Shortest-Path Routing in Transparently Interconnected Local Area Networks. In INFOCOM, 1991.

[16]

T. Rodeheffer, C. Thekkath, and D. Anderson. SmartBridge: A Scalable Bridge Architecture. In SIGCOMM, 2000.

Digital Library

[17]

B. Rose. Home networks: a standards perspective. IEEE Communications Magazine, 39, Dec. 2001.

Digital Library

[18]

W. Seifert. Bridges and Routers. IEEE Network Magazine, 2(1), Jan. 1988.

Digital Library

[19]

M. Steenstrup. Routing in Communications Networks. Prentice-Hall, 1995.

Digital Library

[20]

T.-Y. Tai and M. Gerla. LAN Interconnection: A Transparent, Shortest-Path Approach. In ICC '91, 1991.

[21]

G. Varghese and R. Perlman. Transparent Interconnection of Incompatible Local Area Networks Using Bridges. IEEE Journal on Selected Areas in Communications, 8(1), Jan. 1990.

Digital Library

[22]

XILINK. FPGA Enabled Home Networking Technology Bridges - Connecting Disparate Technologies, Mar. 2001.

Cited By

Besta MDomke JSchneider MKonieczny MGirolamo SSchneider TSingla AHoefler T(2021)High-Performance Routing With Multipathing and Path Diversity in Ethernet and HPC NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2020.303576132:4(943-959)Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1109/TPDS.2020.3035761
Besta MSchneider MKonieczny MCynk KHenriksson EDi Girolamo SSingla AHoefler TCuicchi CQualters IKramer W(2020)FatPathsProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.5555/3433701.3433736(1-18)Online publication date: 9-Nov-2020
https://dl.acm.org/doi/10.5555/3433701.3433736
Besta MSchneider MKonieczny MCynk KHenriksson EGirolamo SSingla AHoefler T(2020)FatPaths: Routing in Supercomputers and Data Centers when Shortest Paths Fall ShortSC20: International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC41405.2020.00031(1-18)Online publication date: Nov-2020
https://doi.org/10.1109/SC41405.2020.00031
Show More Cited By

Index Terms

STAR: a transparent spanning tree bridge protocol with alternate routing

Recommendations

On the construction of all shortest node-disjoint paths in star networks

An optimal construction of all shortest node-disjoint paths in a star network.High probability of the existence of disjoint shortest paths was shown.A sufficient condition for the existence of disjoint shortest paths was given. Node-disjoint paths have ...
A Routing and Broadcasting Scheme on Faulty Star Graphs

The authors present a routing algorithm that uses the depth first search approach combined with a backtracking technique to route messages on the star graph in the presence of faulty links. The algorithm is distributed and requires no global knowledge ...
One-to-many node-disjoint paths of hyper-star networks

In practice, it is important to construct node-disjoint paths in networks, because they can be used to increase the transmission rate and enhance the transmission reliability. The hyper-star networks HS(2n,n) were introduced to be a competitive model ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 32, Issue 3

July 2002

79 pages

ISSN:0146-4833

DOI:10.1145/571697

Issue’s Table of Contents

Copyright © 2002 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2002

Published in SIGCOMM-CCR Volume 32, Issue 3

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
707
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Besta MDomke JSchneider MKonieczny MGirolamo SSchneider TSingla AHoefler T(2021)High-Performance Routing With Multipathing and Path Diversity in Ethernet and HPC NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2020.303576132:4(943-959)Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1109/TPDS.2020.3035761
Besta MSchneider MKonieczny MCynk KHenriksson EDi Girolamo SSingla AHoefler TCuicchi CQualters IKramer W(2020)FatPathsProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.5555/3433701.3433736(1-18)Online publication date: 9-Nov-2020
https://dl.acm.org/doi/10.5555/3433701.3433736
Besta MSchneider MKonieczny MCynk KHenriksson EGirolamo SSingla AHoefler T(2020)FatPaths: Routing in Supercomputers and Data Centers when Shortest Paths Fall ShortSC20: International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC41405.2020.00031(1-18)Online publication date: Nov-2020
https://doi.org/10.1109/SC41405.2020.00031
Akbari NKhorsandi S(2018)A Thorough Performance Evaluation of L2 Non-Broadcast Network ProtocolsElectrical Engineering (ICEE), Iranian Conference on10.1109/ICEE.2018.8472602(1607-1612)Online publication date: May-2018
https://doi.org/10.1109/ICEE.2018.8472602
Chu HChen CWang P(2017)Uninterrupted Ethernet using failure‐adaptive spanning treesInternational Journal of Communication Systems10.1002/dac.329130:14Online publication date: 14-Feb-2017
https://doi.org/10.1002/dac.3291
Teo ZBirman KApthorpe NVan Renesse RKuksenkov V(2016)Treating software-defined networks like disk arrays2016 IEEE NetSoft Conference and Workshops (NetSoft)10.1109/NETSOFT.2016.7502467(361-366)Online publication date: Jun-2016
https://doi.org/10.1109/NETSOFT.2016.7502467
Luo ZSuh C(2016)An analytical model for evaluating spanning tree based layer 2 routing schemes2016 18th International Conference on Advanced Communication Technology (ICACT)10.1109/ICACT.2016.7423458(527-531)Online publication date: Jan-2016
https://doi.org/10.1109/ICACT.2016.7423458
Fornasa MStecca MMaresca MBaglietto P(2015)Bounded latency spanning tree reconfigurationComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2014.11.00476:C(259-274)Online publication date: 15-Jan-2015
https://dl.acm.org/doi/10.1016/j.comnet.2014.11.004
Faghani FMirjalily G(2015)Isolated Forwarding Strategy in Metro Ethernet NetworksJournal of Network and Systems Management10.1007/s10922-014-9305-923:3(539-566)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s10922-014-9305-9
Zhang JLiang MWang Z(2012)Multi-Priority Frame Forwarding in Tree-Based Routing EthernetJournal of Networks10.4304/jnw.7.9.1472-14787:9Online publication date: 1-Sep-2012
https://doi.org/10.4304/jnw.7.9.1472-1478
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents