Accession Number : ADA527961


Title :   Instability Free Routing: Beyond One Protocol Instance


Descriptive Note : Conference paper


Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA


Personal Author(s) : Le, Franck ; Xie, Geoffrey G ; Zhang, Hui


Full Text : http://www.dtic.mil/dtic/tr/fulltext/u2/a527961.pdf


Report Date : Dec 2008


Pagination or Media Count : 13


Abstract : 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.


Descriptors :   *ROUTING , *INSTABILITY , *COMMUNICATIONS PROTOCOLS , COMPUTER NETWORKS , COMMUNICATIONS NETWORKS , COMPUTER ARCHITECTURE , SYMPOSIA


Subject Categories : Computer Programming and Software
      Computer Systems Management and Standards


Distribution Statement : APPROVED FOR PUBLIC RELEASE