page 1  (22 pages)
2to next section

Expanding the text here will generate a large amount of data for your browser to display

An Analysis of Internet Inter-Domain Topology and Route Stability

Ramesh Govindan

USC/Information Sciences Institute
4676 Admiralty Way, Suite 1001
Marina del Rey, CA 90292-6695
Phone: +1 310{822{1511 (ext. 103)
Fax: +1 310{823{6714
govindan@isi.edu

Anoop Reddy

USC/Information Sciences Institute
4676 Admiralty Way, Suite 1001
Marina del Rey, CA 90292-6695
Phone: +1 310{822{1511 (ext. 742)
Fax: +1 310{823{6714
areddy@isi.edu

Abstract
The Internet routing fabric is partitioned into several domains. Each domain represents a region of the fabric administered by a single commercial entity. Over the past two years, the routing fabric has experienced significant growth. From more than a year's worth of inter-domain routing traces, we analyze the Internet inter-domain topology, its route stability behavior, and the effect of growth on these characteristics. Such an analysis is important because inter-domain routing provides the foundation for Internet wide-area communication.

Despite growth, the degree distribution and the diameter of the inter-domain topology have remained relatively unchanged. Furthermore, there exists a four-level hierarchy of Internet domains classified by degree. However, connectivity between domains is significantly non-hierarchical. Despite increased connectivity at higher levels in the topology, the distribution of paths to prefixes from the backbone remained relatively unchanged. There is evidence that both route availability and the mean time to unreachability have degraded with Internet growth.

Keywords: Internet, Inter-domain Routing, BGP, Topology, Route Stability.