Understanding Route Redistribution
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.
Description
Proc. IEEE ICNP 2007 Conference, Beijing, China, October 2007. Best paper award. Also as Technical Report CMU-CS-07-122, April 2007.
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.Collections
Related items
Showing items related by title, author, creator and subject.
-
A validation metrics framework for safety-critical software-intensive systems
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 ... -
BLIP ON THE RADAR: SCHOOL SAFETY SYNERGY THROUGH EARLY WARNING AND INFORMATION SHARING
Dias, Bruno S. (Monterey, CA; Naval Postgraduate School, 2020-12);The traditional response to school violence by legislators and school districts has been mostly reactive. Scholars and existing research in the field of school safety and security recommend a critical safety and security ...