| Abstract | The Internet consists of about 13,000 Autonomous Systems (AS’s) that exchange routing information using the BorderGateway Protocol (BGP). The operators of each AS must have control over the flow of traffic through their network
and between neighboring AS’s. However, BGP is a complicated, policy-based protocol that does not include any direct
support for traffic engineering. In previous work, we have demonstrated that network operators can adapt the flow of
traffic in an efficient and predictable fashion through careful adjustments to the BGP policies running on their edge
routers.
Nevertheless, many details of the BGP protocol and decision process make predicting the effects of these
policy changes difficult. In this paper, we describe a tool that predicts traffic flow at network exit points based on the
network topology, the import policy associated with each BGP session, and the routing advertisements received from
neighboring AS’s. We present a linear-time algorithm that computes a network-wide view of the best BGP routes for each
destination prefix given a static snapshot of the network state, without simulating the complex details of BGP message
passing. We describe how to construct this snapshot using the BGP routing tables and router configuration files available
from operational routers. We verify the accuracy of our algorithm by applying our tool to routing and configuration data
from AT&T’s commercial IP network. Our route prediction techniques help support the operation of large IP backbone
networks, where interdomain routing is an important aspect of traffic engineering.
|
