Spatio-Temporal Modeling of BGP Routing Table Evolution
Article No.: 8, Pages 1 - 7
Abstract
Modeling the routing table growth is vital to the BGP operation. The temporal evolution of the routing table size has been researched to anticipate the memory limitation of BGP routers. However, route aggregation and compression techniques make it difficult to expect the actual memory size from the routing table size. Therefore, further evolution models focusing on the spatial routing table structure are required to evaluate the tolerance of these techniques to future routing table growth. In this paper, we create an evolution model focusing on spatio-temporal route changes using ten-year BGP routing table datasets. We categorize route variations into three types; new, fragmented, and vanished and then create a model for each type. We also demonstrate the characteristics of the model parameters in these ten years.
References
[1]
Bgp routing table analysis reports. http://bgp.potaroo.net/. Accessed: 2015-4-3.
[2]
Ris routing beacons. https://www.ripe.net/analyse/internet-measurements/routing-information-service-ris/ris-routing-beacons.
[3]
University of oregon route views archive project. http://archive.routeviews.org.
[4]
H. Asai and Y. Ohara. Poptrie: A compressed trie with population count for fast and scalable software IP routing table lookup. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, SIGCOMM 2015, London, United Kingdom, August 17-21, 2015, pages 57--70, 2015.
[5]
T. Bu, L. Gao, and D. Towsley. On characterizing bgp routing table growth. Comput. Netw., 45(1):45--54, May 2004.
[6]
L. Cittadini, W. MÃijhlbauer, S. Uhlig, R. Bush, P. FranÃğois, and O. Maennel. Evolution of internet address space deaggregation: Myths and reality. IEEE Journal on Selected Areas in Communications, 28(8):1238--1249, 2010.
[7]
A. Elmokashfi, A. Kvalbein, and C. Dovrolis. On the scalability of bgp: The roles of topology growth and update rate-limiting. In Proceedings of the 2008 ACM CoNEXT Conference, CoNEXT '08, pages 8:1--8:12, New York, NY, USA, 2008. ACM.
[8]
V. Fuller, T. Li, J. Yu, and K. Varadhan. Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy. RFC 1519 (Proposed Standard), Sept. 1993. Obsoleted by RFC 4632.
[9]
D. R. Jim Cowie, Chief Scientist. 512k ipv4 routes:the new normal.
[10]
C. Kalogiros, M. Bagnulo, and A. Kostopoulos. Understanding incentives for prefix aggregation in bgp. In Proceedings of the 2009 Workshop on Re-architecting the Internet, ReArch '09, pages 49--54, New York, NY, USA, 2009. ACM.
[11]
E. Karpilovsky and J. Rexford. Using forgetful routing to control bgp table size. In Proceedings of the 2006 ACM CoNEXT Conference, CoNEXT '06, pages 2:1--2:12, New York, NY, USA, 2006. ACM.
[12]
F. Le, G. G. Xie, and H. Zhang. On route aggregation. In Proceedings of the Seventh COnference on Emerging Networking EXperiments and Technologies, CoNEXT '11, pages 6:1--6:12, New York, NY, USA, 2011. ACM.
[13]
X. Meng, Z. Xu, B. Zhang, G. Huston, S. Lu, and L. Zhang. Ipv4 address allocation and the bgp routing table evolution. SIGCOMM Comput. Commun. Rev., 35(1):71--80, Jan. 2005.
[14]
T. P. Minka. Estimating a gamma distribution. http://research.microsoft.com/en-us/um/people/minka/papers/minka-gamma.pdf.
[15]
Z. A. Uzmi, M. Nebel, A. Tariq, S. Jawad, R. Chen, A. Shaikh, J. Wang, and P. Francis. Smalta: Practical and near-optimal fib aggregation. In Proceedings of the Seventh COnference on Emerging Networking EXperiments and Technologies, CoNEXT '11, pages 29:1--29:12, New York, NY, USA, 2011. ACM.
[16]
M. Zec, L. Rizzo, and M. Mikuc. Dxr: Towards a billion routing lookups per second in software. SIGCOMM Comput. Commun. Rev., 42(5):29--36, Sept. 2012.
[17]
X. Zhao, Y. Liu, L. Wang, and B. Zhang. On the Aggregatability of Router Forwarding Tables. In INFOCOM, 2010 Proceedings IEEE, pages 1--9, march 2010.
Index Terms
- Spatio-Temporal Modeling of BGP Routing Table Evolution
Recommendations
Identifying BGP routing table transfers
BGP routing updates collected by monitoring projects such as RouteViews and RIPE have been a vital source to our understanding of the global routing system. However the collected BGP data contains both the updates generated by actual route changes, and ...
Understanding slow BGP routing table transfers
IMC '09: Proceedings of the 9th ACM SIGCOMM conference on Internet measurementResearchers and network operators often say that BGP table transfers are slow. Despite this common knowledge, the reasons for slow BGP transfers are not well understood. This paper explains BGP table transfer delays by combining BGP messages collected ...
Identifying BGP routing table transfers
MineNet '05: Proceedings of the 2005 ACM SIGCOMM workshop on Mining network dataBGP routing updates collected by monitoring projects such as RouteViews and RIPE have been a vital source to our understanding of the global routing system. The updates logged by these monitoring projects are generated either by individual route changes,...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2017
52 pages
ISBN:9781450353328
DOI:10.1145/3095786
Copyright © 2017 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 June 2017
Check for updates
Author Tag
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
CFI'17
CFI'17: 12th International Conference on Future Internet Technologies
June 14 - 16, 2017
Fukuoka, Japan
Acceptance Rates
CFI'17 Paper Acceptance Rate 8 of 15 submissions, 53%;
Overall Acceptance Rate 29 of 55 submissions, 53%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 104Total Downloads
- Downloads (Last 12 months)6
- Downloads (Last 6 weeks)3
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in