research-article

Evolution of internet address space deaggregation: myths and reality

Authors:

Luca Cittadini,

Wolfgang Muhlbauer,

Pierre Francois,

Olaf MaennelAuthors Info & Claims

IEEE Journal on Selected Areas in Communications, Volume 28, Issue 8

Pages 1238 - 1249

https://doi.org/10.1109/JSAC.2010.101002

Published: 01 October 2010 Publication History

Abstract

Internet routing table size growth and BGP update churn are two prominent Internet scaling issues. There is widespread belief in a high and fast growing number of ASs that deaggregate prefixes, e.g., due to multi-homing and for the purpose of traffic engineering [1]. Moreover, researchers often blame specific classes of ASs for generating a disproportionate amount of BGP updates. Our primary objective is to challenge such widespread assumptions ("myths") and not solely to confirm previous findings [1]-[3]. Surprisingly, we find severe discrepancies between existing myths and reality. According to our results, there is no trend towards more aggressive prefix deaggregation or traffic engineering over time. With respect to update dynamics, we observe that deaggregated prefixes generally do not generate a disproportionate number of BGP updates, with respect to their share of the BGP routing table. On the other side, we observe much more widespread traffic engineering in the form of AS path prepending and scoped advertisements compared to previous studies [1]. Overall, our work gives a far more positive picture compared to the alarming discourses typically heard [1], [2], [4]: The impact of "bad guys" on routing table size growth and BGP churn has not changed for the worse in recent years. Rather, it increases at the same pace as the Internet itself.

References

[1]

X. Meng, Z. Xu, B. Zhang, G. Huston, S. Lu, and L. Zhang, "IPv4 Address Allocation and the BGP Routing Table Evolution," ACM CCR, vol. 35, no. 1, pp. 71-80, 2005.

Digital Library

[2]

G. Huston, "BGP Routing Table Analysis Reports," http://bgp.potaroo.net/.

[3]

T. Bu, L. Gao, and D. Towsley, "On Characterizing BGP Routing Table Growth," Computer Networks, vol. 45, no. 1, pp. 45-54, 2004.

Digital Library

[4]

T. Bates, P. Smith, and G. Huston, "CIDR Report," http://www. cidr-report.org/as2.0/.

[5]

C. Labovitz, G. Malan, and F. Jahanian, "Origins of Internet Routing Instability," in Proc. IEEE INFOCOM, 1999.

[6]

J. Li, M. Guidero, Z. Wu, E. Purpus, and T. Ehrenkranz, "BGP Routing Dynamics Revisited," ACM CCR, vol. 37, no. 2, pp. 5-16, 2007.

[7]

A. Feldmann, "Internet Clean-Slate Design: What and Why?," ACM CCR, vol. 37, no. 3, pp. 59-64, 2007.

Digital Library

[8]

"RIPE Routing Information Service," http://www.ripe.net/ris/.

[9]

"University of Oregon Route Views Project," http://www.routeviews. org/.

[10]

"Regional Internet Registries allocations statistics files," ftp://ftp.ripe. net/pub/stats.

[11]

K. Hubbard, M. Kosters, D. Conrad, D. Karrenberg, and J. Postel, "Internet Registry IP Allocation Guidelines," IETF RFC2050, 2000.

[12]

T. Hain, "A Pragmatic Report on IPv4 Address Space Consumption," The Internet Protocol Journal, vol. 8, no. 3, 2005.

[13]

Y. Rekhter and T. Li, "An Architecture for IP Address Allocation with CIDR," IETF RFC1518, September 1993.

[14]

V. Fuller, T. Li, J. Yu, and K. Varadhan, "Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy," IETF RFC1519, September 1993.

[15]

P. Smith, J. Martin, and R. Bush, "Use of Final /8," http://www.apnic. net/policy/proposals/prop-062-v002.html.

[16]

A. Dhamdhere and C. Dovrolis, "Ten Years in the Evolution of the Internet Ecosystem," in Proc. ACM IMC, 2008, pp. 183-196.

[17]

L. Subramanian, S. Agarwal, J. Rexford, and R. Katz, "Characterizing the Internet Hierarchy from Multiple Vantage Points," in Proc. IEEE INFOCOM, 2002.

[18]

F. Wang and L. Gao, "Inferring and Characterizing Internet Routing Policies," in Proc. ACM IMC, 2003.

[19]

G. Di Battista, M. Patrignani, and M. Pizzonia, "Computing the Types of the Relationships Between Autonomous Systems," in Proc. IEEE INFOCOM, 2003.

[20]

B. Donnet and O. Bonaventure, "On BGP Communities," SIGCOMM Comput. Commun. Rev., vol. 38, no. 2, 2008.

[21]

B. Quoitin, S. Uhlig, C. Pelsser, L. Swinnen, and O. Bonaventure, "Interdomain Traffic Engineering with BGP," IEEE Commun. Mag., 2003.

[22]

R. Oliveira, D. Pei, W. Willinger, B. Zhang, and L. Zhang, "In Search of the Elusive Ground Truth: The Internet's AS-level Connectivity Structure," in Proc. ACM SIGMETRICS, 2008.

Digital Library

[23]

B. Zhang R. Oliveira, R. Izhak-Ratzin and L. Zhang, "Measurement of Highly Active Prefixes in BGP," in Proc. IEEE GLOBECOM, 2005.

[24]

D. Jen, M. Meisel, H. Yan, D. Massey, L. Wang, B. Zhang, and L. Zhang, "Towards A New Internet Routing Architecture: Arguments for Separating Edges from Transit Core," in Proc. ACM Workshop on Hot Topics in Networks, 2008.

[25]

R. Chandra, P. Traina, and T. Li, "BGP Communities Attribute," IETF RFC1997, August 1996.

[26]

EU Framework Programme 7 Integrated Project, "Trilogy," http://www. nets-find.net.

[27]

NSF, "NeTS Initiative, Future Internet Design," http://www.nets-find. net.

[28]

"Global Environment for Network Innovations," http://www.geni.net/.

[29]

"Internet Research Task Force - Routing Research Group," http://tools. ietf.org/group/irtf/trac/wiki/RoutingResearchGroup.

[30]

"Cooperation for Internet Data Analysis (CAIDA)," http://caida.org/ research/topology.

[31]

G. Huston, "Analyzing the Internet BGP Routing Table," The Internet Protocol Journal, vol. 4, no. 1, 2002.

[32]

R. Oliviera, B. Zhang, and L. Zhang, "Observing the Evolution of Internet AS Topology," in Proc. ACM SIGCOMM, 2007.

[33]

Z. Xu, X. Meng, L. Zhang, S. Lu, and C. Wittbordt, "Impact of IPv4 Address Space Allocation Practice on BGP Routing Table Growth," in Proc. IEEE 18th Annual Workshop on Computer Communications (CCW), 2003.

[34]

B. Carpenter, "Observed Relationships between Size Measures of the Internet," ACM CCR, vol. 39, no. 2, pp. 5-12, 2009.

Digital Library

Cited By

Piraux MBarbette TRybowski NNavarre LAlfroy TPelsser CMichel FBonaventure O(2022)The multiple roles that IPv6 addresses can play in today's internetACM SIGCOMM Computer Communication Review10.1145/3561954.356195752:3(10-18)Online publication date: 6-Sep-2022
https://dl.acm.org/doi/10.1145/3561954.3561957
Sediqi KPrehn LGasser O(2022)Hyper-specific prefixesACM SIGCOMM Computer Communication Review10.1145/3544912.354491652:2(20-34)Online publication date: 20-Jun-2022
https://dl.acm.org/doi/10.1145/3544912.3544916
Du BTestart CFontugne RAkiwate GSnoeren Aclaffy kBarakat CPelsser CBenson TChoffnes D(2022)Mind your MANRSProceedings of the 22nd ACM Internet Measurement Conference10.1145/3517745.3561419(716-729)Online publication date: 25-Oct-2022
https://dl.acm.org/doi/10.1145/3517745.3561419
Show More Cited By

Evolution of internet address space deaggregation: myths and reality
1. Networks
  1. Network protocols
    1. Network layer protocols

Recommendations

Implications of the topological properties of Internet traffic on traffic engineering
SAC '04: Proceedings of the 2004 ACM symposium on Applied computing

In this paper we study the behavior of Internet traffic on the AS-level topology and discuss its implications on interdomain traffic engineering. We rely on two notable interdomain traffic traces, the first is one month long and the other is one day ...
The impact of BGP dynamics on intra-domain traffic
SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems

Recent work in network traffic matrix estimation has focused on generating router-to-router or PoP-to-PoP (Point-of-Presence) traffic matrices within an ISP backbone from network link load data. However, these estimation techniques have not considered ...
The impact of BGP dynamics on intra-domain traffic

Recent work in network traffic matrix estimation has focused on generating router-to-router or PoP-to-PoP (Point-of-Presence) traffic matrices within an ISP backbone from network link load data. However, these estimation techniques have not considered ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Journal on Selected Areas in Communications

IEEE Journal on Selected Areas in Communications Volume 28, Issue 8

Special issue title on scaling the internet routing system: an interim report

October 2010

143 pages

ISSN:0733-8716

Issue’s Table of Contents

Copyright © 2010.

Publisher

IEEE Press

Publication History

Published: 01 October 2010

Revised: 19 March 2010

Received: 30 October 2009

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Piraux MBarbette TRybowski NNavarre LAlfroy TPelsser CMichel FBonaventure O(2022)The multiple roles that IPv6 addresses can play in today's internetACM SIGCOMM Computer Communication Review10.1145/3561954.356195752:3(10-18)Online publication date: 6-Sep-2022
https://dl.acm.org/doi/10.1145/3561954.3561957
Sediqi KPrehn LGasser O(2022)Hyper-specific prefixesACM SIGCOMM Computer Communication Review10.1145/3544912.354491652:2(20-34)Online publication date: 20-Jun-2022
https://dl.acm.org/doi/10.1145/3544912.3544916
Du BTestart CFontugne RAkiwate GSnoeren Aclaffy kBarakat CPelsser CBenson TChoffnes D(2022)Mind your MANRSProceedings of the 22nd ACM Internet Measurement Conference10.1145/3517745.3561419(716-729)Online publication date: 25-Oct-2022
https://dl.acm.org/doi/10.1145/3517745.3561419
Carpenter B(2021)A square law revisitedACM SIGCOMM Computer Communication Review10.1145/3477482.347749051:3(41-45)Online publication date: 23-Jul-2021
https://dl.acm.org/doi/10.1145/3477482.3477490
Ongkanchana PFontugne REsaki HSnijders JAben EFeamster NLutu A(2021)Hunting BGP zombies in the wildProceedings of the 2021 Applied Networking Research Workshop10.1145/3472305.3472315(1-7)Online publication date: 24-Jul-2021
https://dl.acm.org/doi/10.1145/3472305.3472315
Bienkowski MSarrar NSchmid SUhlig S(2018)Online Aggregation of the Forwarding Information BaseIEEE/ACM Transactions on Networking10.1109/TNET.2017.278741926:1(591-604)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1109/TNET.2017.2787419
Utsumi MAsai HEsaki H(2017)Spatio-Temporal Modeling of BGP Routing Table EvolutionProceedings of the 12th International Conference on Future Internet Technologies10.1145/3095786.3095794(1-7)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3095786.3095794
Bienkowski MMarcinkowski JPacut MSchmid SSpyra AScheideler CHajiaghayi M(2017)Online Tree CachingProceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3087556.3087558(329-338)Online publication date: 24-Jul-2017
https://dl.acm.org/doi/10.1145/3087556.3087558
Krenc TFeldmann AGill PHeidemann JByers JGovindan R(2016)BGP Prefix DelegationsProceedings of the 2016 Internet Measurement Conference10.1145/2987443.2987458(469-475)Online publication date: 14-Nov-2016
https://dl.acm.org/doi/10.1145/2987443.2987458
Sobrinho JVanbever LLe FSousa ARexford J(2016)Scaling the Internet Routing System Through Distributed Route AggregationIEEE/ACM Transactions on Networking10.1109/TNET.2016.252784224:6(3462-3476)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1109/TNET.2016.2527842
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents