Title :
The BEST challenge for next-generation Ethernet services
Author :
Risbood, Pankaj ; Swarup Acharya ; Bhawna Gupta
Author_Institution :
Integrated Networks Res. Dept., Lucent Technol. Bell Labs, USA
Abstract :
Service providers are starting to offer next-generation E-Line (point-to-point) and E-LAN (multipoint-to-multipoint) Ethernet services over their existing SONET/SDH networks. While Ethernet typically is "best-effort", these emerging services are expected to be "carrier-class" with strict bandwidth guarantees. Consequently, spanning tree creation, critical to any Ethernet network is fundamentally changed; each tree hop now needs to have sufficient capacity to meet the requisite bandwidth demands. In this paper, we introduce the bandwidth-endowed spanning tree (BEST) problem. Unlike the polynomial complexity of standard spanning tree algorithms, BEST is NP-complete, raising questions about the scalability of these services. We propose offline and online algorithms and study their performance using extensive simulations. We show that leveraging the Virtual Concatenation protocol (ITU-T G.707) is key to practical algorithms that are both effective and efficient. Inspite of the theoretical hardness, the online algorithms we propose are a good match to "optimal", offline integer programming benchmarks, demonstrating the viability of next-generation Ethernet services.
Keywords :
SONET; computational complexity; integer programming; optical fibre LAN; synchronous digital hierarchy; trees (mathematics); BEST challenge; E-LAN; ITU-T G.707; NP-complete; SONET-SDH network; bandwidth-endowed spanning tree; next-generation Ethernet service; online algorithm; optimal offline integer programming; polynomial complexity; virtual concatenation protocol; Bandwidth; Ethernet networks; Frame relay; Local area networks; Next generation networking; Polynomials; Protocols; SONET; Scalability; Virtual private networks;
Conference_Titel :
INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE
Print_ISBN :
0-7803-8968-9
DOI :
10.1109/INFCOM.2005.1498333