Provisioning Networks to Support Fast Restoration with QoS Guarantees for Real Time Traffic

Network QoS is essential for supporting real time interactive services such as VoIP. Such services require guarantees on the minimum bandwidth and also demand low end to end latency, jitter and packet losses. In the differentiated services framework this is done by marking packets to receive a particular (preferential) forwarding treatment, or per-hop behavior, at each network node. This per hop forwarding treatment at each node may however be ineffective in providing the delay and jitter guarantees unless bounds are also imposed on the number of hops in the end to end paths Given that data networks are prone to failures, hop bounds on routing paths must also be maintained even subsequent to network failures. In addition fast recovery from failures is needed to keep packet losses to a minimum for real time interactive services such as VoIP. Recently it has been shown that MPLS fast (local) reroute combined with pre-provisioning of protection capacities and bypass tunnels enables fast restoration for data networks. However these schemes lack any guarantees on the number of hops for the bypass tunnels used for carrying re-routed traffic subsequent to network failures. In this paper we design efficient schemes for pre-provisioning protection capacities to support fast restoration that also satisfy hop constraints even for the re-routed traffic. We show that the underlying optimization problem is NP hard and design almost best possible approximation algorithms for it. Our simulation, on some standard core networks, show that our algorithms work well in practice as well.