AuthorsS. Reinemo and T. Skeie
EditorsI. Andonovic and J. Thompson
TitleEffective Shortest Path Routing for Gigabit Ethernet
AfilliationCommunication Systems, Communication Systems
Publication TypeProceedings, refereed
Year of Publication2007
Conference NameProceedings of the IEEE International Conference on Communications 2007
Date PublishedJune
PublisherIEEE Communications Society
ISBN Number1-4244-0353-7

Since its invention at Xerox PARC in 1973, Ethernet technology has proven to be both robust and adaptable. Through several evolutionary steps Ethernet has become an almost ubiquitous communication technology, spanning from local area networking through high performance backplane interconnects (a recent initiative) to metropolitan networking. However, an obstacle still remains for Ethernet to effectively make inroads in application areas such as interconnection and backbone networks. Ethernet's native routing algorithm, the Spanning Tree Protocol, becomes a major performance and utilization bottleneck when network connectivity increases. Since the Spanning Tree Protocol avoids deadlocks and infinitely looping packets by turning any topology into tree, it leaves a large portion of links unused and thus wastes bandwidth. In this paper we address this weakness by proposing a new routing algorithm which achieves the same goals as the Spanning Tree Protocol, but without disabling any links or prohibiting any turns, and at the same time guaranteeing shortest path routing. Through the use of layered routing we show how to improve performance with respect to both the Spanning Tree Protocol and a more recent proposal called Tree-Based Turn-Prohibition. Extensive simulations show that we are able to increase throughput by a factor of more than 3.5 compared to the Spanning Tree Protocol and a factor of 1.8 compared to Tree-Based Turn-Prohibition. Our concept relies on features introduced in IEEE standards 802.1Q, 802.1D and 802.3x, as well as changes currently discussed in IEEE task forces. We also discuss backwards compatibility toghether with the changes necessary for enabling layered shortest path routing in Ethernet.

Citation KeyReinemo.2006.4