2009 · 14 citations · 36 references
ComputingComputer ScienceComputer SystemsComputer NetworksDistributed SystemsInterconnection NetworksInternet Protocol SuiteInternet RoutingNetwork ProtocolsRoutingRouting AlgorithmsRouting ProtocolsConvergenceConvergence TimeExplorationInterdomain RoutingPath ExplorationRouting MetricsRouting PoliciesTimer Design
The behavior of routing protocols during convergence is critical as it impacts end-to-end performance. Network convergence is particularly important in BGP, the current interdomain routing protocol. In order to decrease the amount of exchanged routing messages and transient routes, BGP routers rely on MRAI timers and route flap damping. These timers are intended to limit the exchange of transient routing messages. In practice, these timers have been shown to be partly ineffective at improving convergence, making it even slower in some situations.In this paper, we propose to add a timer mechanism to routing protocols, that enforces an ordering of the routing messages such that path exploration is drastically reduced while controlling convergence time. Our approach is based on known results in generalized path algorithms and endomorphism semi-rings. Our timers, called MRPC (metrics and routing policies compliant), are set independently by each router and depend only on the metrics of the routes received by the router as well as the routing policies of the router. No sharing of information about routing policies between neighboring ASs is required by our solution. Similarly to the case of routing policies that may lead to BGP convergence problems, arbitrary routing policies can also make it impossible to enforce an ordering of the messages that will prevent path exploration to occur. We explain under which conditions path exploration can be avoided with our timers, and provide simulations to understand how they compare to MRAI.
36
IEEE Transactions on Communications
J.B. Haseler · Electronics and Power · 1985 · 632 citations
Delayed Internet routing convergence
Craig Labovitz, Abha Ahuja, Abhijit Bose et al. · ACM SIGCOMM Computer Communication Review · 2000 · 492 citations · Full text
The end-to-end effects of Internet path selection
Stefan Savage, Andy Collins, Eric Hoffman et al. · 1999 · 474 citations