Stable Policy Routing with Provider Independence

Nick Feamster, Ramesh Johari & Hari Balakrishnan

Problem Statement

The Internet's routing infrastructure is made up of thousands of independently operated networks that cooperate to exchange global reachability information using an interdomain routing protocol, the Border Gateway Protocol, Version 4 (BGP) [4]. This cooperation occurs in a landscape where these independent networks, or Autonomous Systems (ASes), compete to provide Internet service. BGP facilitates this "competitive cooperation" by enabling network operators to express routing policies that are consistent with desired economic, business, and performance goals.

Ranking and filtering are two orthogonal mechanisms that network operators use to implement their policies. Ranking determines the route to a destination that should be used, given several available routes. It allows an AS the freedom to specify preferences over multiple candidate paths to a destination (e.g., specifying a primary and a backup path). ASes should be able to operate autonomously, retaining ranking independence; i.e., the ability to specify rankings independently of the rankings of other ASes. Ranking independence enables ASes to specify rankings without coordinating with one another or revealing their rankings to other ASes.

Filtering allows an operator to selectively advertise (or export) routes to some ASes, and hide routes from other ASes. Filtering allows an AS to control which neighboring ASes can send traffic over its infrastructure, because advertising routes to a neighboring AS is an implicit agreement to carry traffic for that AS. To empower flexible business contracts, an AS should always retain autonomy over its decision to advertise routes to its neighbors; i.e., the routing protocol should not mandate any filtering restrictions.

The combination of ranking independence and unrestricted filtering forms the cornerstone of interdomain routing, and has, in large part, been the reason for the success of BGP over the past decade. However, the ability to specify highly expressive policies comes at considerable cost to system robustness: as has been observed by Varadhan et al.and Griffin et al., among others, if ASes are not subject to any constraints on the rankings that they can specify, BGP may oscillate forever [3,5].

Figure 1: Instability can arise when ASes independently specify rankings [3,5]. Each circle represents an AS. AS 0 is the destination. The listing of paths beside each node denotes a ranking over paths.

Example:  Consider Figure 1 [3,5]. ASes 1, 2, and 3 each prefer the indirect path through their neighboring AS in the clockwise direction over the direct path to the destination, 0. All other paths are filtered. This configuration has no stable path assignment (i.e., a path assignment from which no node would deviate). For example, consider the path assignment (10, 210,30); in this case, AS 1 has a better path available to it, 130, so it switches paths. This switch causes the path (2 1 0) to break, causing AS 2 to switch to its second choice, path (2 0). The resulting path assignment, (130, 20, 30), is a permutation of the original path assignment: this time, AS 3 has the path 320 available, so it switches. This oscillation continues forever.

In light of this discovery, a natural question to ask is: "What are the necessary and sufficient conditions that guarantee global routing stability?" This question is rather broad, because these conditions depend on various modeling decisions: the details of the routing protocol, restrictions on filtering, and whether ASes retain policy independence. This paper studies how the rankings allowed by a routing protocol must be restricted to guarantee global routing stability, assuming that ASes (1) retain ranking independence and (2) face no restrictions on filtering. This question is important for two reasons. First, both ranking independence and unrestricted filtering reflect realities of how ASes specify policies today. Second, answering this question will deepen our understanding of stability of policy-based routing protocols, complementing earlier results by Varadhan et al. [5], Griffin et al. [3], and Gao and Rexford [2].

Results

Our work makes three main contributions. First, we show that rankings based solely on the immediate next-hop AS en route to the destination may never reach a stable path assignment from an arbitrary initial state; i.e., next-hop rankings, which are common in practice, are not safe. Moreover, under unrestricted filtering, a routing system with next-hop rankings may have no stable path assignment. In addition to their operational implications, these results are also somewhat surprising, because next-hop rankings with no route filtering always have one stable path assignment [1]. We also observe that although rankings based on a globally consistent weighting of paths are safe under filtering, even minor generalizations of the weighting function compromise safety.

Second, we define a dispute ring, a special case of the "dispute wheel" (a group of nodes whose rankings have a particular form) of Griffin et al.[3], and show that any routing system that has a dispute ring is not safe under filtering. Using the dispute wheel concept, Griffin et al.showed a sufficient condition for safety, proving that if a routing system is unsafe then it must have a dispute wheel. In contrast, to our knowledge, our result is the first known necessary condition for safety under filtering.

Third, we show that under ranking independence and unrestricted filtering, the set of allowable rankings that guarantee safety is effectively ranking based on (weighted) shortest paths. We prove that any routing system that permits paths of length n+2 to be ranked over paths of length n can have a dispute ring, and is thus unsafe under filtering. We also prove that any routing system that permits paths of length n+1 to be ranked over paths of length n can have a dispute wheel. In summary, our results indicate that stable policy routing with provider independence (i.e., ranking independence and unrestricted filtering) requires tight constraints on rankings.

Conclusion

Our findings may be interpreted in several ways. The optimist will note that checking a set of rankings to ensure safety is trivial, because all it requires is that BGP routers modify the decision process to consult a route's "local preference" attribute only after considering its AS path length. The pessimist, however, will note that guaranteeing safe routing, preserving ranking independence, and allowing unrestricted filtering, requires constraints that may be too strong to permit sufficient ranking expressiveness, since it effectively precludes an AS from ranking longer paths over shorter ones. In either case, our results suggest that stable interdomain routing protocols face a fundamental tradeoff between the expressiveness and independence of an AS's policies.

References

[1] Joan Feigenbaum, Rahul Sami, and Scott Shenker. Mechanism design for policy routing. In ACM Symposium on Principles of Distributed Computing, pages 11-20, 2004.

[2] L. Gao and J. Rexford. Stable Internet routing without global coordination. IEEE/ACM Trans. Networking, 9(6):681-692, December 2001.

[3] Timothy Griffin, F. Bruce Shepherd, and Gordon Wilfong. The stable paths problem and interdomain routing. IEEE/ACM Trans. Networking, 10(1):232-243, 2002.

[4] Y. Rekhter and T. Li. A Border Gateway Protocol. RFC 1771, March 1995.

[5] K. Varadhan, R. Govindan, and D. Estrin. Persistent route oscillations in inter-domain routing. Technical Report 96-631, USC/ISI, February 1996.

Footnote

1. A full version of this paper appears in ACM SIGCOMM, August 2005.