PDF《Instability Free Routing: Beyond》

Instability Free Routing: Beyond One Protocol Instance Franck Le Carnegie Mellon University franckle@cmu.

edu Geoffrey G. Xie Naval Postgraduate School xie@nps.edu Hui Zhang Carnegie Mellon University hzhang@cs.cmu.edu ABSTRACT Today, a large body of research exists regarding the correct- ness of routing protocols. However, many reported global disruptions of Internet connectivity, e.g., inter-AS persistent loops, cannot be explained by looking at a single routing protocol at a time. In fact, these anomalies have long been suspected in the operator community to be caused by the interactions between routing protocols. The interactions be- tween protocol instances are governed by two procedures at the border routers: route selection (RS) ranks routes from different protocol instances;

and route redistribution (RR) exchanges routes between protocol instances. Prior studies hypothesized that RR may be responsible for a portion of the observed anomalies. In this paper, we provide analytical and experimental results to link RS, RR, and their interplay to anomalies discovered in operational networks. We show that RS by itself can cause route oscillations and loops, and that in all Cisco, Quagga, and XORP implementations, non- deterministic behaviors may occur because of their incor- rect modeling of the dependencies between RS and RR. We identify the root cause for each of the instabilities and de- rive a con?guration guideline as well as a functional model to eliminate them. 1. INTRODUCTION One of the primary goals of a network is to ensure the proper delivery of packets to the intended destinations. Rout- ing protocols play an essential role toward that objective. They disseminate routing information and allow routers to compute their forwarding tables. Because of their impor- tance, a large body of research has been devoted to the cor- rectness of routing protocols. However, existing analytical frameworks as well as empir- 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 pro?t or commercial advantage and that copies bear this notice and the full citation on the ?rst page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior speci?c permission and/or a fee. ACM CoNEXT 2008, December 10-12, 2008, Madrid, SPAIN Copyright

2008 ACM 978-1-60558-210-8/08/0012 ...$5.00. ical studies for understanding routing dynamics concentrate on one routing protocol at a time, most notably BGP [22], [33], [19], [6], [18], [16]. The reality is that a large num- ber of the reported disruptions of Internet connectivity, such as the ones listed below, cannot be easily explained by the misbehavior of a single routing protocol. Persistent forwarding loops: Several studies [31], [34] have reported the existence of persistent forwarding loops within an AS or across multiple networks. The discoveries of inter-AS routing loops were surprising given the fact that BGP has been speci?cally designed to avert the formation of such loops via checking the AS PATH attribute. Those stud- ies [31], [34] conjectured that the interactions between static routes and BGP may have originated the inter-AS loops. Our own discussions with operators reveal that the operational community also views the interactions between BGP and IGPs as a possible root cause of this problem: the injec- tion of routes from BGP into IGP, and then re-injection of the same routes from IGP back into BGP at another location will reset the AS PATH attribute and render the BGP'