Routers of the AS, Unite! Guaranteeing a Network Realizes Its Routing Policy

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.