Realistic BGP traffic for test labs

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	IXIA BGP Routing Protocol Emulation Software, 2002. http://www.ixiacom.com/.
	2	Chariot, 2002. http://www.netiq.com/products/chr/default.asp.
	3	TeraRouter Tester, 2002. http://www.netcomsystems.com/ solutions/products/applications/pdf/TeraRouting/index.htm.
	4	A. Krämer, "RIG, A BGP Routing Instability Generator," 2002. Diploma Thesis, ETH Z "urich. http://www.barman.ch/rig/.
	5	Timothy G. Griffin , Gordon Wilfong, An analysis of BGP convergence properties, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.277-288, August 30-September 03, 1999, Cambridge, Massachusetts, United States
	6	A. Shaikh, R. Dube, and A. Varma, "Avoiding instability during graceful shutdown of OSPF," in Proc. IEEE INFOCOM, 2002.
	7	T. Griffin, "What is the Sound of One Route Flapping?," 2002. IPAM talk.
	8	Bassam Halabi, Internet Routing Architectures, Cisco Press, 1997
	9	John W. Stewart, III, BGP4: Inter-Domain Routing in the Internet, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
	10	Christian Huitema, Routing in the Internet, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
	11	Bilal Chinoy, Dynamics of internet routing information, Conference proceedings on Communications architectures, protocols and applications, p.45-52, September 13-17, 1993, San Francisco, California, United States
	12	R. Govindan , A. Reddy, An Analysis of Internet Inter-Domain Topology and Route Stability, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.850, April 09-11, 1997
	13	K. Varadhan, R. Govindan, and D. Estrin, "Persistent route oscillations in inter-domain routing," tech. rep., 96-631, USC/ISI, 1996.
	14	Craig Labovitz , G. Robert Malan , Farnam Jahanian, Internet routing instability, IEEE/ACM Transactions on Networking (TON), v.6 n.5, p.515-528, Oct. 1998 [doi>10.1109/90.731185]
	15	C. Labovitz, R. Malan, and F. Jahanian, "Origins of Internet routing instability," in Proc. IEEE INFOCOM, 1999.
	16	Craig Labovitz , Abha Ahuja , Farnam Jahanian, Experimental Study of Internet Stability and Backbone Failures, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.278, June 15-18, 1999
	17	Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.175-187, August 28-September 01, 2000, Stockholm, Sweden
	18	B. Premore, An Experimental Analysis of BGP Convergence Time, Proceedings of the Ninth International Conference on Network Protocols, p.53, November 11-14, 2001
	19	Aman Shaikh , Anujan Varma , Lampros Kalampoukas , Rohit Dube, Routing stability in congested networks: experimentation and analysis, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.163-174, August 28-September 01, 2000, Stockholm, Sweden
	20	D. Chang, R. Govindan, and J. Heidemann, "An Empirical Study of Router Response to Large BGP Routing Table Load," tech. rep., USC/ISI, 2001.
	21	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).
	22	D. McPerson, V. Gill, D. Walton, and A. Retana, "BGP persistent route oscillation condition," 2001. Internet Draft (draft-ietf-idr-route-oscillation-01.txt).
	23	H. Berkowitz, A. Retana, S. Hares, and P. Krishnaswamy, "Benchmarking methodology for basic BGP convergence," 2002. Internet Draft (draft-ietf-bmwg-bgpbas-01.txt).
	24	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).
	25	NANOG: The North American Network Operators Group. http://www.nanog.org/.
	26	S. Hare, P. Krishnaswamy, M. Lepp, A. Retana, H. Berkowitz, and E. Davis, "BGP convergence measurement issues," 2001. IETF/bmwg talk.
	27	Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States
	28	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.
	29	P. Danzig and S. Jamin, "tcplib: A Library of TCP Internetwork Traffic Characteristics," tech. rep., USC, 1991.
	30	Christian Huitema, Routing in the Internet, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
	31	Y. Rekhter and T. Li, "A Border Gateway Protocol 4 (BGP-4)," 1995. RFC 1771.
	32	C. Villamiyar, R. Chandra, and R. Govindan, "BGP route flap damping," 1998. RFC 2439.
	33	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.
	34	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.
	35	Zhuoqing Morley Mao , Ramesh Govindan , George Varghese , Randy H. Katz, Route flap damping exacerbates internet routing convergence, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
	36	Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
	37	K. Calvert, M. Doar, and E. W. Zegura, "Modeling Internet topology," in IEEE Communication Magazine, 1997.
	38	L. Gao, "On inferring autonomous system relationships in the Internet," in Proc. IEEE Global Internet, 2000.
	39	Lixin Gao , Jennifer Rexford, Stable Internet routing without global coordination, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.307-317, June 18-21, 2000, Santa Clara, California, United States
	40	B. Norton, "The art of peering: The peering playbook," 2002.
	41	"SSFNet, Scalable Simulation Framework." http://www.ssfnet.org/.
	42	O. Maennel and A. Feldmann, "BGPcharacter: Tool for processing and characterizing BGP data," February 2002. NANOG 24 talk.
	43	Ratul Mahajan , David Wetherall , Tom Anderson, Understanding BGP misconfiguration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
	44	Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, Policy Disputes in Path-Vector Protocols, Proceedings of the Seventh Annual International Conference on Network Protocols, p.21, October 31-November 03, 1999
	45	A. Feldmann and S. Muthukrishnan, "Tradeoffs for packet classification," in Proc. IEEE INFOCOM, 2000.
	46	W. Fang and L. Peterson, "Inter-AS traffic patterns and their implications," in Proc. IEEE Global Internet, 1999.
	47	Hongsuda Tangmunarunkit , Ramesh Govindan , Sugih Jamin , Scott Shenker , Walter Willinger, Network topology generators: degree-based vs. structural, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
	48	B. Krishnamurthy and J. Rexford, Web Protocols and Practice. Addison-Wesley, 2001.
	49	RIPE's Routing Information Service Raw Data Page. http://data.ris.ripe.net/.
	50	SaarGate. http://www.saargate.de/.
	51	University of Oregon RouteViews project. http://www.routeviews.org/.
	52	Merit. http://www.merit.edu/.
	53	V. Fuller, T. Li., J. Yu, and K. Varadhan, "Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy," 1993. RFC 1519.
	54	Light Reading, "The Internet Core Router Test," 2001.
	55	G. Huston, "Analyzing the Internet BGP routing table," in Internet Protocol Journal, 2001.
	56	A. Broido, E. Nemeth, and K. Claffy, "Internet Expansion, Refinement and Churn," in ETT, 2002.
	57	L. Subramanian, S. Agarwal, J. Rexford, and R. H. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in Proc. IEEE INFOCOM, 2002.
	58	C. Labovitz, "Multithreaded routing toolkit," in Merit Technical Report to the National Science Foundation, 1996.