Traffic-Oblivious Network Routing for Guaranteed Network Performance

We describe a capacity efficient, robust, and traffic-oblivious routing strategy, called two-phase routing, that allows pre-configuration of the VPN such that all traffic patterns permissible within the network's natural ingress-egress capacity constraints can be routed with bandwidth guarantees. The scheme routes traffic in two phases - traffic entering the VPN is sent from the source to a set of intermediate nodes in predetermined split ratios that depend on the intermediate nodes, and then from the intermediate nodes to the final destination. (The traffic split ratios can be generalized to depend on the source and/or destination of traffic also.) A significant benefit of the described schemes is that the network can be configured for a completely static operation while providing service-level guarantees to widely varying VPN traffic. This is unlike previous approaches based on direct source-destination routing which need dynamic adaptation to changing traffic conditions in order to provide service-level guarantees.