Understanding Route Redistribution
MetadataShow full item record
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.
Proc. IEEE ICNP 2007 Conference, Beijing, China, October 2007. Best paper award. Also as Technical Report CMU-CS-07-122, April 2007.
RightsThis 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.
Showing items related by title, author, creator and subject.
Cruickshank, Kristian John. (Monterey, California. Naval Postgraduate School, 2009-03);Validation of safety-critical software requirements is a difficult and frequently misunderstood task. It answers the question of "are we building the right product?" and is essential to Software Engineering. However, ...
Applying systems thinking to law enforcement safety: recommendation for a comprehensive safety management framework DeBoard, Maggie A. (Monterey, California: Naval Postgraduate School, 2015-12);Each year, approximately 100,000 police officers experience work-related occupational injuries, and more than 100 are killed on the job, in training accidents, routine operations, and emergency response. Many of these ...
Papakonstantinou, Nikolaos; Bossuyt, Douglas L. Van; Linnosmaa, Joonas; Hale, Britta; O’Halloran, Bryan (ASME, 2021);Designing complex, socio-technical, cyber-physical systems has become increasingly challenging in recent years. Interdependencies between engineering domains can lead to emergent behavior that is difficult to predict and ...