Abstract
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
PDF ArticleMore Like This
Sarvesh Bidkar, Ashwin Gumaste, Puneet Ghodasara, Annirudha Kushwaha, Jianping Wang, and Arun Somani
J. Opt. Commun. Netw. 7(5) 445-460 (2015)
Mohammad Nurujjaman, Samir Sebbah, Chadi Assi, and Martin Maier
J. Opt. Commun. Netw. 4(12) 967-977 (2012)
Xiaomin Chen and Admela Jukan
J. Opt. Commun. Netw. 4(3) 248-258 (2012)