URL: http://www.icir.org/vern/imw-2002/imw2002-papers/151.ps.gz
http://www.icir.org/vern/imw-2002/slides/151-slides.pdf
http://citeseer.nj.nec.com/afek02structure.html Entry Date: 2003-01-14 Abstract: 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) 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. Datasets: RIPE database for thirteen peers. Snapshots were used, and results were verified using update records from RIPE. Results:

• Validates notion of BGP policy atoms introduced by Broido and Claffy. Of the AS links where atoms are created, about 85% are between the origin AS and an AS it peers with, which, according to the authors, supports the hypothesis that atoms are the result of Internet policies rather than network faults.
• Atoms are relatively stable considering prefix update rate. Only 2-3% of prefixes change atom membership in 8 hours.
• Proposes a slightly different definition for atoms.
• Validates stability of computation of BGP policy atoms used by Broido and Claffy.
• Tests the ability to use atoms to save in BGP update traffic. 75% of updates contain a complete atom, whereas only 20% of updates contain complete AS prefix sets. Also provides an example of how atoms might enhance BGP efficiency.
• However, ignores issues with AS sets and multi-origin ASes.

References: Expands on:

• Andre Broido, kc claffy, "Analysis of RouteViews BGP data: policy atoms," in Proceedings of NRDM Workshop Santa Barbara, May 2001.
• Andre Broido, kc claffy, "Complexity of global routing policies," in Proc. IMA Special Workshop: Mathematical Opportunities in Large-Scale Network Dynamics, August 2001.