In search for an appropriate granularity to model routing policies

W Muhlbauer, SPWG Uhlig, B Fu, M Meulle, O Maennel

Research output: Contribution to journalArticleScientificpeer-review

10 Citations (Scopus)


Routing policies are typically partitioned into a few classes that capture the most common practices in use today[1]. Unfortunately, it is known that the reality of routing policies [2] and peering relationships is far more complex than those few cleasse [1,3]. We take the next step of searching for the appropiate granularity at which policies should be modeled. For this purpose, we study how and where to configure pre-prefix policies in an AS-level model of the INernet, such that the selected paths in the model are consistent with those observed in BGP data from mulitple vantage points. By comparing business relationships with per-prefix filters, we investigate the role and limitations of business relationships as a model for policies. We observe that popular locations for filtering correspond to balleys where no path shoulb be propagated according to inferred business relationships. This result reinforces the validity of the valley-free property used fro business relationships interference. However, given the sometimes large path diversity ASs have, business relationships do not contain enough information to devide which path will be chosen as the best. To model how individual ASs choose their best paths, we introduce a new abstraction: next-hop atoms. Next-hop atoms capture the fifferent sets of neighboring ASs adn AD uses for its best routes. We show that a large fraction of next-hop atoms correspond to per-neighbor path choices. A non-negligible fraction of path choices, however, correspond to hot-potato routing and tie-breaking within the BGP decision process, very detailed aspects of Internet routing.
Original languageUndefined/Unknown
Pages (from-to)145-156
Number of pages12
JournalComputer Communications Review
Issue number4
Publication statusPublished - 2007


  • academic journal papers
  • CWTS 0.75 <= JFIS < 2.00

Cite this