Abstract-This paper examines the network interdomain rout-
ing information exchanged between backbone service providers
at the major U.S. public Internet exchange points. Internet rout-
ing instability, or the rapid fluctuation of network reachability
information, is an important problem currently facing the In-
ternet engineering community. High levels of network instability
can lead to packet loss, increased network latency and time to
convergence. At the extreme, high levels of routing instability
have led to the loss of internal connectivity in wide-area, national
networks. In this paper, we describe several unexpected trends
in routing instability, and examine a number of anomalies and
pathologies observed in the exchange of inter-domain routing
information. The analysis in this paper is based on data collected
from BGP routing messages generated by border routers at five
of the Internet cores public exchange points during a nine month
period. We show that the volume of these routing updates is
several orders of magnitude more than expected and that the
majority of this routing information is redundant, or pathological.
Furthermore, our analysis reveals several unexpected trends and
ill-behaved systematic properties in Internet routing. We finally
posit a number of explanations for these anomalies and evaluate
their potential impact on the Internet infrastructure.
Index Terms-Communication system, communication system
routing, computer network, Internet, routing, stability.
|