Olaf Maennel
Anja Feldmann
ABSTRACT
This paper examines the possibility of generating realistic routing tables of arbitrary size along with realistic BGP updates of arbitrary frequencies via an automated tool deployable in a small-scale test lab. Such a tool provides the necessary foundations to study such questions as: the limits of BGP scalability, the reasons behind routing instability, and the extent to which routing instability influences the forwarding performance of a router.We find that the answer is affirmative. In this paper we identify important characteristics/metrics of routing tables and updates which provide the foundation of the proposed BGP workload model. Based on the insights of an extensive characterization of BGP traffic according to such metrics as prefix length distributions, fanout, amount of nesting of routing table prefixes, AS path length, number and times between BGP update bursts and number and times between BGP session resets, etc., we introduce our prototype tool, rtg. rtg realizes the workload model and is capable of generating realistic BGP traffic. Through its flexibility and parameterization rtg enables us to study the sensibilities of test systems in a repeatable and consistent manner while still providing the possibility of capturing the different characteristics from different vantage points in the network.
- IXIA BGP Routing Protocol Emulation Software, 2002. http://www.ixiacom.com/.]]Google Scholar
- Chariot, 2002. http://www.netiq.com/products/chr/default.asp.]]Google Scholar
- TeraRouter Tester, 2002. http://www.netcomsystems.com/ solutions/products/applications/pdf/TeraRouting/index.htm.]]Google Scholar
- A. Krämer, "RIG, A BGP Routing Instability Generator," 2002. Diploma Thesis, ETH Z "urich. http://www.barman.ch/rig/.]]Google Scholar
- T. G. Griffin and G. Wilfong, "An analysis of BGP convergence properties," in Proc. ACM SIGCOMM, 1999.]] Google ScholarDigital Library
- A. Shaikh, R. Dube, and A. Varma, "Avoiding instability during graceful shutdown of OSPF," in Proc. IEEE INFOCOM, 2002.]]Google Scholar
- T. Griffin, "What is the Sound of One Route Flapping?," 2002. IPAM talk.]]Google Scholar
- B. Halabi, Internet Routing Architectures. Cisco Press, 1997.]] Google ScholarDigital Library
- J. W. Stewart, BGP4: Inter-Domain Routing in the Internet. Addison-Wesley, 1999.]] Google ScholarDigital Library
- C. Huitema, Routing in the Internet. Prentice Hall, 1999.]] Google ScholarDigital Library
- B. Chinoy, "Dynamics of Internet routing information," in Proc. ACM SIGCOMM, pp. 45--52, 1993.]] Google ScholarDigital Library
- R. Govindan and A. Reddy, "An analysis of Internet inter-domain topology and route stability," in Proc. IEEE INFOCOM, 1997.]] Google ScholarDigital Library
- K. Varadhan, R. Govindan, and D. Estrin, "Persistent route oscillations in inter-domain routing," tech. rep., 96-631, USC/ISI, 1996.]]Google Scholar
- C. Labovitz, R. Malan, and F. Jahanian, "Internet routing instability," IEEE/ACM Trans. Networking, vol. 6, no. 5, pp. 515--558, 1998.]] Google ScholarDigital Library
- C. Labovitz, R. Malan, and F. Jahanian, "Origins of Internet routing instability," in Proc. IEEE INFOCOM, 1999.]]Google ScholarCross Ref
- C. Labovitz, A. Ahuja, and F. Jahanian, "Experimental study of Internet stability and wide-area network failures," in Proc. International Symposium on Fault-Tolerant Computing, 1999.]] Google ScholarDigital Library
- C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian, "Delayed Internet routing convergence," in Proc. ACM SIGCOMM, 2000.]] Google ScholarDigital Library
- T. G. Griffin and B. J. Premore, "An experimental analysis of BGP convergence time," in Proc. International Conference on Network Protocols, 2001.]] Google ScholarDigital Library
- A. Shaikh, L. Kalampoukas, R. Dube, and A. Varma, "Routing stability in congested networks: Experimentation and analysis," in Proc. ACM SIGCOMM, 2000.]] Google ScholarDigital Library
- D. Chang, R. Govindan, and J. Heidemann, "An Empirical Study of Router Response to Large BGP Routing Table Load," tech. rep., USC/ISI, 2001.]]Google Scholar
- S. Ramachandra, Y. Rekhter, R. Fernando, J. Scudder, and E. Chen, "Graceful restart mechanism for BGP," 2001. Internet Draft (draft-ietf-idr-restart-05.txt).]]Google Scholar
- D. McPerson, V. Gill, D. Walton, and A. Retana, "BGP persistent route oscillation condition," 2001. Internet Draft (draft-ietf-idr-route-oscillation-01.txt).]] Google ScholarDigital Library
- H. Berkowitz, A. Retana, S. Hares, and P. Krishnaswamy, "Benchmarking methodology for basic BGP convergence," 2002. Internet Draft (draft-ietf-bmwg-bgpbas-01.txt).]]Google Scholar
- H. Berkowitz, A. Retana, S. Hares, P. Krishnaswamy, and M. Lepp, "Terminology for benchmarking external routing convergence measurements," 2002. Internet Draft (draft-ietf-bmwg-conterm-01.txt).]]Google Scholar
- NANOG: The North American Network Operators Group. http://www.nanog.org/.]]Google Scholar
- S. Hare, P. Krishnaswamy, M. Lepp, A. Retana, H. Berkowitz, and E. Davis, "BGP convergence measurement issues," 2001. IETF/bmwg talk.]]Google Scholar
- P. Barford and M. Crovella, "Generating Representative Web Workloads for Network and Server Performance Evaluation," in Proc. ACM SIGMETRICS, pp. 151--160, 1998.]] Google ScholarDigital Library
- P. Danzig, R. Caceres, D. Mitzel, and D. Estrin, "An empirical workload model for driving wide-area TCP/IP network simulations," IEEE/ACM Trans. Networking, vol. 3, no. 1, pp. 1--26, 1992.]]Google Scholar
- P. Danzig and S. Jamin, "tcplib: A Library of TCP Internetwork Traffic Characteristics," tech. rep., USC, 1991.]]Google Scholar
- C. Huitema, Routing in the Internet. Prentice Hall, 1995.]] Google ScholarDigital Library
- Y. Rekhter and T. Li, "A Border Gateway Protocol 4 (BGP-4)," 1995. RFC 1771.]] Google ScholarDigital Library
- C. Villamiyar, R. Chandra, and R. Govindan, "BGP route flap damping," 1998. RFC 2439.]] Google ScholarDigital Library
- C. Panigl, J. Schmitz, P. Smith, and C. Vistoli, "RIPE Routing-WG Recommendation for Coordinated Route-flap Damping Parameters ," 2001. http://www.ripe.net/ripe/docs/ripe-229.html.]]Google Scholar
- M. Musuvathi, S. Venkatachary, R. Wattenhofer, C. Labovitz, and A. Ahuja, "BGP-CT: A First Step Towards Fast Internet Fail-Over," in Microsoft Research Technical Report, 2000.]]Google Scholar
- G. Varghese, R. Govindan, R. Katz, and Z. Mao, "Route flap damping exacerbates Internet routing convergence," in Proc. ACM SIGCOMM, 2002.]] Google ScholarDigital Library
- M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law relationships of the Internet topology," in Proc. ACM SIGCOMM, 1999.]] Google ScholarDigital Library
- K. Calvert, M. Doar, and E. W. Zegura, "Modeling Internet topology," in IEEE Communication Magazine, 1997.]]Google Scholar
- L. Gao, "On inferring autonomous system relationships in the Internet," in Proc. IEEE Global Internet, 2000.]]Google Scholar
- L. Gao and J. Rexford, "Stable Internet routing without global coordination," in Proc. ACM SIGMETRICS, 2001.]] Google ScholarDigital Library
- B. Norton, "The art of peering: The peering playbook," 2002.]]Google Scholar
- "SSFNet, Scalable Simulation Framework." http://www.ssfnet.org/.]]Google Scholar
- O. Maennel and A. Feldmann, "BGPcharacter: Tool for processing and characterizing BGP data," February 2002. NANOG 24 talk.]]Google Scholar
- D. Wetherall, R. Mahajan, and T. Anderson, "Understanding BGP misconfigurations," in Proc. ACM SIGCOMM, 2002.]] Google ScholarDigital Library
- T. G. Griffin, F. B. Shepherd, and G. Wilfong, "Policy disputes in path vector protocols," in Proc. International Conference on Network Protocols, 1999.]] Google ScholarDigital Library
- A. Feldmann and S. Muthukrishnan, "Tradeoffs for packet classification," in Proc. IEEE INFOCOM, 2000.]]Google ScholarCross Ref
- W. Fang and L. Peterson, "Inter-AS traffic patterns and their implications," in Proc. IEEE Global Internet, 1999.]]Google Scholar
- H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger, "Network topology generators: Degree -based vs. structural," in Proc. ACM SIGCOMM, 2002.]] Google ScholarDigital Library
- B. Krishnamurthy and J. Rexford, Web Protocols and Practice. Addison-Wesley, 2001.]]Google Scholar
- RIPE's Routing Information Service Raw Data Page. http://data.ris.ripe.net/.]]Google Scholar
- SaarGate. http://www.saargate.de/.]]Google Scholar
- University of Oregon RouteViews project. http://www.routeviews.org/.]]Google Scholar
- Merit. http://www.merit.edu/.]]Google Scholar
- V. Fuller, T. Li., J. Yu, and K. Varadhan, "Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy," 1993. RFC 1519.]] Google ScholarDigital Library
- Light Reading, "The Internet Core Router Test," 2001.]]Google Scholar
- G. Huston, "Analyzing the Internet BGP routing table," in Internet Protocol Journal, 2001.]]Google Scholar
- A. Broido, E. Nemeth, and K. Claffy, "Internet Expansion, Refinement and Churn," in ETT, 2002.]]Google Scholar
- L. Subramanian, S. Agarwal, J. Rexford, and R. H. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in Proc. IEEE INFOCOM, 2002.]]Google ScholarCross Ref
- C. Labovitz, "Multithreaded routing toolkit," in Merit Technical Report to the National Science Foundation, 1996.]]Google Scholar
Index Terms
- Realistic BGP traffic for test labs
Recommendations
Realistic BGP traffic for test labs
Proceedings of the 2002 SIGCOMM conferenceThis paper examines the possibility of generating realistic routing tables of arbitrary size along with realistic BGP updates of arbitrary frequencies via an automated tool deployable in a small-scale test lab. Such a tool provides the necessary ...
Neighbor-specific BGP: more flexible routing policies while improving global stability
SIGMETRICS '09The Border Gateway Protocol (BGP) offers network administrators considerable flexibility in controlling how traffic flows through their networks. However, the interaction between routing policies in different Autonomous Systems (ASes) can lead to ...
Quantifying the BGP routes diversity inside a tier-1 network
NETWORKING'06: Proceedings of the 5th international IFIP-TC6 conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications SystemsMany large ISP networks today rely on route-reflection [1] to allow their iBGP to scale. Route-reflection was officially introduced to limit the number of iBGP sessions, compared to the $\frac{n\times(n-1)}{2}$ sessions required by an iBGP full-mesh. ...
Comments