Show simple item record

dc.contributor.authorLe, F.
dc.contributor.authorZhang, H.
dc.contributor.authorXie, Geoffrey
dc.dateDecember 2008
dc.date.accessioned2013-08-01T21:11:08Z
dc.date.available2013-08-01T21:11:08Z
dc.date.issued2008-12
dc.identifier.urihttp://hdl.handle.net/10945/34780
dc.descriptionProc. ACM CoNEXT Conference, Madrid, Spain, December 2008.en_US
dc.descriptionThe article of record as published may be found at http://dx.doi.org/10.1145/1544012.1544021en_US
dc.description.abstractToday, a large body of research exists regarding the correctness 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 between 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, nondeterministic behaviors may occur because of their incorrect modeling of the dependencies between RS and RR. We identify the root cause for each of the instabilities and derive a configuration guideline as well as a functional model to eliminate them.Today, a large body of research exists regarding the correctness 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 between 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, nondeterministic behaviors may occur because of their incorrect modeling of the dependencies between RS and RR. We identify the root cause for each of the instabilities and derive a configuration guideline as well as a functional model to eliminate them.Today, a large body of research exists regarding the correctness 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 between 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, nondeterministic behaviors may occur because of their incorrect modeling of the dependencies between RS and RR. We identify the root cause for each of the instabilities and derive a configuration guideline as well as a functional model to eliminate them.en_US
dc.description.sponsorshipThis research was sponsored by the NSF under the 100x100 Clean Slate Project [1] (NSF-0331653), the 4D Project [2] (NSF-0520187), grants CNS-0520210, CNS-0721574, and a Graduate Research Fellowship.en_US
dc.rightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.en_US
dc.titleInstability Free Routing: Beyond One Protocol Instanceen_US
dc.contributor.departmentComputer Science (CS)
dc.description.funderThis research was sponsored by the NSF under the 100x100 Clean Slate Project [1] (NSF-0331653), the 4D Project [2] (NSF-0520187), grants CNS-0520210, CNS-0721574, and a Graduate Research Fellowship.en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record