| Abstract | This paper presents a provably correct model that computes the out-come of the BGP decision process for each router in a single AS,
without simulating the complex details of BGP message passing.
The model requires only static inputs that can be easily obtained
from the routers: the set of candidate routes to a destination (and
the routers in the AS at which they were learned), import policies
and other session-level parameters, and internal topology. We pro-
pose algorithms for computing route selection under four different
network configurations: with the MED attribute compared across
all routes, and compared only across routes from the same neigh-
boring AS; and with a “full mesh” internal BGP (iBGP) topology
versus an iBGP topology that uses a scalability technique called
“route reflection”. For each scenario, we derive general properties
of the routes that routers ultimately select, present an efficient al-
gorithm for computing the outcome of BGP route selection, and
prove the algorithm’s correctness. Studying the general properties
and computational overhead of modeling the route selection pro-
cess in each of these cases provides insights into the unnecessary
complexity introduced by the MED attribute and route reflection;
we use these insights to propose improvements to BGP that achieve
the same goals as MED and route reflection without introducing the
negative side effects of these features. We have implemented some
of the algorithms from this paper in a prototype and have shown
them to be efficient and accurate enough for many traffic engineer-
ing tasks.
|
