Routers of the AS, Unite! Guaranteeing a Network Realizes Its Routing Policy
Report ID: TR-847-09Author: Wilfong, Gordon T. / Rexford, Jennifer / Zhang-Shen, Rui
Date: 2009-01-00
Pages: 14
Download Formats: |PDF|
Abstract:
We study how the many routers in an AS should cooperate to provably realize a single routing policy, a question that has remained unanswered despite years of experience with policy-based interdomain routing. The simplest solution is to distribute all interdomain routing information to every router, but this is not scalable. Instead, intra-AS route dissemination should ensure that every router learns a sufficient set of routes to make decisions that comply with the policy. Unfortunately, mismatches between today's routing policies and route-dissemination protocols can easily lead to protocol oscillations, traffic blackholes, and violations of business contracts. This paper presents a systematic study of the role of route dissemination in realizing an AS's policy. We begin by defining a policy as an AS-wide route preference plus a router-specific preference, and show that minimizing intra-AS route dissemination while provably satisfying the policy is NP-complete in general. Fortunately, polynomial-time algorithms exist for today's typical policies and other policies of similar structure. Our analysis shows that each router advertising a single best route, as in today's internal BGP (iBGP) protocol, is not sufficient to realize some common policies. Our proposed changes guarantee that policies will be realized correctly, can be implemented by router features available in the near future, and simplify the router configuration process.