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 AmericaPDF Article