Understanding Route Redistribution
Loading...
Authors
Le, F.
Zhang, H.
Xie, Geoffrey
Subjects
Advisors
Date of Issue
2007-10
Date
October 2007
Publisher
Language
Abstract
Route redistribution (RR) has become an integral part of IP network design as the result of a growing need for disseminating certain routes across routing protocol boundaries. While RR is widely used and resembles BGP in several nontrivial aspects, surprisingly, the safety of RR has not been systematically studied by the networking community. This paper presents the first analytical model for understanding the effect of RR on network wide routing dynamics and evaluating the safety of a specific RR configuration. We first illustrate how easily inaccurate configurations of RR may cause severe routing instabilities, including route oscillations and persistent routing loops. At the same time, general observations regarding the root causes of these instabilities are provided. We then introduce a formal model based on the general observations to represent and study the safety of route redistribution. Using the model, we prove that given a RR configuration, determining whether the redistributions result in a cycle is NP-hard. Given this complexity, we present a sufficient condition, which can be checked in polynomial time with the proposed analytical model, for ensuring the safety of a RR configuration. Finally, the paper proposes potential changes to the current RR protocol to guarantee safety.
Type
Description
Proc. IEEE ICNP 2007 Conference, Beijing, China, October 2007. Best paper award. Also as Technical Report CMU-CS-07-122, April 2007.
Series/Report No
Department
Computer Science (CS)
Organization
Identifiers
NPS Report Number
Sponsors
This research was sponsored by the NSF under both NeTS Grant CNS-0520210 and a Graduate Research Fellowship.
Funder
This research was sponsored by the NSF under both NeTS Grant CNS-0520210 and a Graduate Research Fellowship.
Format
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.