OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editor: Richard A. Linke
  • Vol. 5, Iss. 2 — Feb. 1, 2006
  • pp: 122–144

Scalable, distributed cycle-breaking algorithms for gigabit Ethernet backbones

Francesco De Pellegrini, David Starobinski, Mark G. Karpovsky, and Lev B. Levitin  »View Author Affiliations


Journal of Optical Networking, Vol. 5, Issue 2, pp. 122-144 (2006)
http://dx.doi.org/10.1364/JON.5.000122


View Full Text Article

Acrobat PDF (612 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

Feature Issue on Optical Ethernet (OE)

Ethernet networks rely on the so-called spanning-tree protocol (IEEE 802.1d) to break cycles, thereby avoiding the possibility of infinitely circulating packets and deadlocks. This protocol imposes a severe penalty on the performance and scalability of large gigabit Ethernet backbones since it makes inefficient use of fibers and may lead to bottlenecks. We propose a significantly more scalable cycle-breaking approach based on the theory of turn prohibition. Specifically, we introduce, analyze, and evaluate an algorithm called tree-based turn prohibition (TBTP). We show that this polynomial-time algorithm maintains backward compatibility with the IEEE 802.1d standard and never prohibits more than half the turns in the network for any given graph and any given spanning tree. We further introduce a distributed version of the algorithm that nodes in the network can run asynchronously. Through extensive simulations on a variety of graph topologies, we show that the TBTP algorithm can lead to an order of magnitude improvement over the spanning-tree protocol with respect to throughput and end-of-end delay metrics. In addition, we propose and evaluate heuristics to determine the replacement order of legacy switches that results in the fastest performance improvement.

© 2006 Optical Society of America

OCIS Codes
(060.4250) Fiber optics and optical communications : Networks
(060.4510) Fiber optics and optical communications : Optical communications

ToC Category:
Optical Ethernet

History
Original Manuscript: August 28, 2005
Revised Manuscript: November 23, 2005
Manuscript Accepted: December 24, 2005
Published: February 1, 2006

Virtual Issues
Optical Ethernet (2005) Journal of Optical Networking

Citation
Francesco De Pellegrini, David Starobinski, Mark G. Karpovsky, and Lev B. Levitin, "Scalable, distributed cycle-breaking algorithms for gigabit Ethernet backbones," J. Opt. Netw. 5, 122-144 (2006)
http://www.opticsinfobase.org/jocn/abstract.cfm?URI=jon-5-2-122

You do not have subscription access to this journal. Citation lists with outbound citation links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Log in to access OSA Member Subscription

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Log in to access OSA Member Subscription

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited