Dynamic Routing of Restorable Bandwidth Guaranteed Tunnels Using Aggregated Network Resource Usage Information

This paper presents a new algorithm for routing bandwidth guaranteed label switched paths (LSPs) in Multi-Protocol Label Switched (MPLS) networks. The emerging MPLS standard will provide the capability to set-up explicitly routed LSPs with bandwidth guarantees. Service providers can use these LSPs as components of an IP Virtual Private Network (VPN) service with the band width guarantees used to satisfy customer service-level agreements (SLAs). The envisaged use of explicit routing is for traffic engineering since the prevalent shortest path routing is insufficient for this purpose. Since LSP routing requests are likely to arrive one-by-one, it is not practical to use offline path selection algorithms because they require a priori knowledge of all LSPs to be routed. Instead, on-line algorithms that handle requests arriving one-by-one and that satisfy as many potential future demands as possible are needed. The newly developed algorithm for MPLS routing is an on-line algorithm and is based on the idea that a newly routed LSP must follow a route that does not "interfere too much" with a route that may be critical to satisfy a future demand. We show that this problem is NP-hard.