Network-Wide Prediction of BGP Routes

This paper presents provably correct algorithms for computing the outcome of the BGP route-selection process for each router in a network, without simulating the complex details of BGP message passing. The algorithms require only static inputs that can be easily obtained from the routers: The BGP routes learned from neighboring domains, the import policies configured on the BGP sessions, and the internal topology. Solving the problem would be easy if the route-selection process were deterministic and every router received all candidate BGP routes.