Network-wide load balancing routing with performance guarantees

As wide-area network connectivity becomes commoditized, network service providers are offering premium services that generate higher revenues by supporting performance sensitive traffic (such as voice, multimedia, and online trading). An emerging example is a virtual private network path with quality of service (QoS) guarantees, or QVPN. The main technical challenge in offering the QVPN service is how to allocate a physical route for each QVPN so as to maximize the total number of QVPNs that a given physical network infrastructure can support simultaneously. We make the case that the key to addressing this challenge is to maintain network-wide load balance when selecting QVPN routes. By ensuring that different parts of the network are evenly loaded, no single critical link will tend to become a bottleneck resource. This paper describes a Link Criticality Based Routing (LCBR) algorithm, which achieves high network resource utilization efficiency while supporting QVPNs with end-to-end delay and bandwidth guarantees. In addition, LCBR can select primary and backup routes for each QVPN simultaneously to support fast recovery from node or link failures. Using a simple yet effective metric that accurately quantifies network-wide load balance, LCBR significantly improves the total number of supported QVPNs when compared to state-of-the-art traffic engineering approaches.