On the structure and application of BGP policy atoms

Yehuda Afek, Anat Bremler-Barr, Omer Ben-Shalom
Conferences & Workshops
Routing, Traffic Measurement


The notion of Internet Policy Atoms has been
recently introduced in [1], [2] as groups of prefixes sharing
a common BGP AS path at any Internet backbone router.
In this paper we further research these ’Atoms’. First we
offer a new method for computing the Internet policy atoms, and use the RIPE RIS database [6] to derive their structure.
Second, we show that atoms remain stable with only about
2-3% of prefixes changing their atom membership in eight
hour periods. We support the ’Atomic’ nature of the policy
atoms by showing BGP update and withdraw notifications
carry updates for complete atoms in over 70% of updates,
while the complete set of prefixes in an AS is carried in only 21% of updates. We track the locations where atoms are created (first different AS in the AS path going back from the common origin AS 1 ) showing 86% are split between the origin AS and it’s peers thus supporting the assumption that they are created by policies. Finally applying atoms to ”real life” applications we achieve a modest savings in BGP updates due to the low average prefix count in the atoms.

  author    = {Yehuda Afek and
               Omer Ben{-}Shalom and
               Anat Bremler{-}Barr},
  title     = {On the structure and application of {BGP} policy atoms},
  booktitle = {Proceedings of the 2nd {ACM} {SIGCOMM} Internet Measurement Workshop,
               {IMW} 2002, Marseille, France, November 6-8, 2002},
  pages     = {209--214},
  publisher = {{ACM}},
  year      = {2002},
  url       = {https://doi.org/10.1145/637201.637234},
  doi       = {10.1145/637201.637234},
  timestamp = {Tue, 06 Nov 2018 11:07:19 +0100},
  biburl    = {https://dblp.org/rec/conf/imc/AfekBB02.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}