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)

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



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

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

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)

Sort:  Author  |  Year  |  Journal  |  Reset


  1. H. Frazier and H. Johnson, "Gigabit Ethernet: from 100to1,000 Mbps," IEEE Inter. Comput. 3(1), 24-31 (1999).
  2. H. Frazier, "The 802.3z gigabit Ethernet standard," IEEE Netw. 12(3), 6-7 (1998).
  3. D. Clark, "Are ATM, gigabit Ethernet ready for prime time?" IEEE Comput. 31(5), 11-13 (1998).
  4. W. Noureddine and F. Tobagi, "Selective backpressure in switched Ethernet LANs," in Global Telecommunications Conference (IEEE, 1999), pp. 1256-1263.
  5. R. Perlman, Interconnections (Addison-Wesley, 2000).
  6. M. Karol, S. Golestani, and D. Lee, "Prevention of deadlocks and livelocks in lossless backpressured packet networks," in Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE, 2000), pp. 1333-1342.
  7. J. Duato, "A necessary and sufficient condition for deadlock-free routing in cut-through and store-and-forward networks," IEEE Trans. Parallel Distrib. Syst. 7, 841-854 (1996).
  8. M. Soha and R. Perlman, "Comparison of two LAN bridge approaches," IEEE Netw. 2(1), 37-48 (1988).
  9. "Metro Ethernet networks--a technical overview," Metro Ethernet Forum White Paper, 2002-2004. Available online at http://www.metroethernetforum.org/.
  10. L. Bosack and C. Hedrick, "Problems in large LANs," IEEE Netw. 2(1), 52-56 (1988).
  11. G. Ibanez, A. Garcia, and A. Azcorra, "Alternative multiple spanning tree protocols (AMSTP) for optical Ethernet backbones," in 29th Annual IEEE International Conference on Local Computer Networks (IEEE, 2004), pp. 744-751.
  12. S. Sharma, K. Gopalan, S. Nanda, and T. C. Chiueh, "Viking: a multi-spanning-tree Ethernet architecture for metropolitan area and cluster networks," in Twenty-third Annual Joint Conference of the IEEE Computer and Communications Society (IEEE, 2004), pp. 2283-2294.
  13. D. Starobinski, M. Karpovsky, and L. Zakrevski, "Application of network calculus to general topologies using turn-prohibition," IEEE/ACM Trans. Netw. 11, 411-421 (2003).
  14. L. Levitin and M. Karpovsky, "Deadlock prevention in networks modeled as weighted graphs," in Proceedings of Eighth International Conference on Information Networks, Systems and Technologies, ICINSAT 2002 (2002), pp. 482-487.
  15. C. Glass and L. Ni, "The turn model for adaptive routing," J. ACM 41, 874-902 (1994).
  16. M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, and T. L. Rodeheffer, "Autonet: a high-speed, self-configuring local area network using point-to-point links," IEEE J. Sel. Areas Commun. 9, 1318-1335 (1991).
  17. R. Perlman, "An algorithm for distributed computation of a spanning tree in an extended LAN," in Proceedings of Ninth ACM Data Communications Symposium (ACM Press, 1985), pp. 44-53 .
  18. A. Myers, T. Ng, and H. Zhang, "Rethinking the service model: scaling Ethernet to a million nodes," in Proceedings of HotNets III (ACM Press, 2004).
  19. J. Hart, "Extending the IEEE 802.1 MAC bridge standard to remote bridges," IEEE Netw. 2(1), 10-15 (1988).
  20. R. Perlman, W. Hawe, and A. Lauck, "Utilization of redundant links in bridged networks," U.S. patent 5,150,360 (22 September 1992).
  21. K. Lui, W. C. Lee, and K. Nahrstedt, "STAR: a transparent spanning tree bridge protocol with alternate routing," ACM SIGCOMM Comput. Commun. Rev. 32(3), 33-46 (2002).
  22. T. L. Rodeheffer, C. Thekkath, and D. Anderson, "SmartBridge: a scalable bridge architecture," in Proceedings of ACM SIGCOMM 2000 (ACM Press, 2000), pp. 205-216.
  23. F. de Pellegrini, D. Starobinski, M. Karpovsky, and L. Levitin, "Scalable cycle-breaking algorithms for gigabit Ethernet backbones," in 29th Annual IEEE International Conference on Local Computer Networks (IEEE, 2004), pp.2175-2184.
  24. J. Echague, M. Prieto, J. Villadangos, and V. Cholvi, "A distributed algorithm to provide QoS by avoiding cycles in routes," Lect. Notes Comput. Sci. 3266, 224-236 (2004).
  25. T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms (McGraw-Hill, 1990).
  26. M. Fidler and G. Einhoff, "Routing in turn-prohibition based feed-forward networks," Lect. Notes Comput. Sci. 3042, 1168-1179 (2004).
  27. The Network Simulator-ns-2 is available online at http://www.isi.edu/nsnam/ns/.
  28. Boston University Representative Topology Generator-BRITE is available online at http://www.cs.bu.edu/brite/.
  29. A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," Science 286, 509-512 (1999).

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited