Efficient policy-based routing in the internet

Traditional Internet routing has focused on shortest-path routing where paths are chosen which minimize an additive weight function on a single, typically delay-related metric. The evolving topology control requirements of the Internet require the generalization of this model to satisfy functions on multiple metrics. The inclusion of multiple metrics in a routing computation is called policy-based routing. Policy-based routing supports traffic engineering by the computation of routes in the context of constraints on the traffic allowed over portions of an internet. Analogously, policy-based routing supports quality-of-service (QoS) by the computation of routes in the context of constraints on the paths specific traffic flows are allowed to use. Previous work on policy-based routing has focused on virtual-circuit-based solutions, and has resulted in computationally expensive algorithms. This paper presents a number of advances in the provision of policy-based routing services in networks and internetworks. A family of routing algorithms are presented for computing routes in the context of traffic-engineering constraints, quality-of-service constraints, and a combination of the two, which achieve new levels of computational efficiency. In addition, a forwarding architecture is presented that efficiently supports hop-by-hop forwarding in the context of multiple paths to each destination, which is desirable for policy-based routing.