|
URL:
|
http://distcomp.ethz.ch/publications/INFOCOM01a.pdf
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.3022
|
|
Entry Date:
|
2002-12-23
|
|
Abstract:
|
This paper examines the role inter-domain topology and routing policy
play in the process of delayed Internet routing convergence. In recent
work, we showed that the Internet lacks effective inter-domain path
fail-over. Un-like circuit-switched networks which exhibit fail-over
on the order of mil-liseconds, we found Internet backbone routers may
take tens of minutes to reach a consistent view of the network
topology after a fault. In this paper, we expand on our earlier work
by exploring the impact of specific Inter-net provider policies and
topologies on the speed of routing convergence. Based on data from
the experimental injection and measurement of sev-eral hundred
thousand inter-domain routing faults, we show that the time for
end-to-end Internet convergence depends on the length of the longest
possible backup autonomous system path between a source and
destination node. We also demonstrate significant variation in the
convergence behav-iors of Internet service providers, with the larger
providers exhibiting the fastest convergence latencies. Finally, we
discuss possible modifications to BGP and provider routing policies
which if deployed, would improve inter-domain routing convergence.
|
|
Experiments:
|
Over a six month period the authors injected BGP faults into more than ten
geographically and topologically diverse providers. Passive observations
of the impact of these faults were made at an additional twenty ISP
default-free routing tables. Steady-state and convergence topologies were
inferred from update messages received at a passive RouteViews probe
machine. Finally, a survey about routing and peering policies was
performed, to which fifteen backbone providers of various sizes responded.
|
|
Results:
|
- The time complexity for Internet fail-over convergence is upper bounded by
30n seconds, where n is the length of the longest alternative ASPath
between the source and any destination autonomous system for a route.
- On average, routes from customers of larger ISPs exhibit faster convergence
than routes announced by customers of smaller Internet providers.
- Errant paths are frequently explored during delayed convergence. These
"vagabond" paths likely stem from misconfiguration or software bugs.
- The majority of default-free Internet routes exhibit multiple alternative
secondary paths. These paths often include several times the number of
associated BGP autonomous systems in the ASPath as the steady state paths
observed in routing table snapshots.
- Discusses a number of modifications to BGP which, if deployed, would
significantly improve inter-domain routing convergence.
|
|
References:
|
- Expands on:
- C. Labovitz, A. Ahuja, A Bose, and F. Jahanian, "Delayed Internet Routing Convergence," Proc. of the ACM SIGCOMM, August 2000.
- Complements:
- T. G. Griffin and G. Wilfong, "An Analysis of BGP Convergence Properties," Proc. ACM SIGCOMM, August 1999.
- K. Varadhan, R. Govindan, and D. Estrin. Persistent Route Oscillations in Inter-Domain Routing," Tech. Rep. USC CS TR 96-631, Department of Computer Science, University of Southern California, February 1996.
- Lixin Gao and J. Rexford, "Stable Internet Routing Without Global Coordination," Proc. of ACM SIGMETRICS, June 2000.
|