On Inferring and Characterizing Internet Routing Policies

Border Gateway Protocol allows Autonomous Systems (ASs) to apply diverse routing policies for selecting routes and for propagating reachability information to other ASs. Al- though a signicant number of studies have been focused on the Internet topology, little is known about what routing policies network operators employ to congure their net- works. In this paper, we infer and characterize routing poli- cies employed in the Internet. We nd that routes learned from customers are preferred over those from peers and providers, and those from peers are typically preferred over those from providers. We present an algorithm for infer- ring and characterizing export policies. We show that ASs announce their prexes to a selected subset of providers. The main reasons behind the selective announcement are the trac engineering strategy for controlling incoming trac. The impact of these routing policies might be signicant. For example, many Tier-1 ASs reach their (direct or indi- rect) customers via their peers instead of customers. Fur- thermore, the selective announcement routing policies imply that there are much less available paths in the Internet than shown in the AS connectivity graph. We hope that our nd- ings will caution network operators in choosing the selective announcement routing policy for trac engineering. Finally, we study export policies to peers and nd that ASs tend to announce all of their prexes to other peers. To the best of our knowledge, this is the rst study on systematically understanding routing policies applied in the Internet