Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Characterizing the Internet Hierarchy from Multiple Vantage Points

Lakshminarayanan Subramanian, Sharad Agarwal, Jennifer Rexford and Randy H. Katz

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-01-1151
August 2001

http://www.eecs.berkeley.edu/Pubs/TechRpts/2001/CSD-01-1151.pdf

The delivery of IP traffic through the Internet depends on the complex interactions between thousands of Autonomous Systems (ASes) that exchange routing information using the Border Gateway Protocol (BGP). This paper investigates the topological structure of the Internet in terms of customer-provider and peer-peer relationships between ASes, as manifested in BGP routing policies. We describe a technique for inferring AS relationships by exploiting partial views of the AS graph available from different vantage points. Next we apply the technique to a collection of ten BGP routing tables to infer the relationships between neighboring ASes. Based on these results, we analyze the hierarchical structure of the Internet and propose a five-level classification of ASes. Our analysis differs from previous characterization studies by focusing on the commercial relationships between ASes rather than simply the connectivity between the nodes.


BibTeX citation:

@techreport{Subramanian:CSD-01-1151,
    Author = {Subramanian, Lakshminarayanan and Agarwal, Sharad and Rexford, Jennifer and Katz, Randy H.},
    Title = {Characterizing the Internet Hierarchy from Multiple Vantage Points},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2001},
    Month = {Aug},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2001/5263.html},
    Number = {UCB/CSD-01-1151},
    Abstract = {The delivery of IP traffic through the Internet depends on the complex interactions between thousands of Autonomous Systems (ASes) that exchange routing information using the Border Gateway Protocol (BGP). This paper investigates the topological structure of the Internet in terms of customer-provider and peer-peer relationships between ASes, as manifested in BGP routing policies. We describe a technique for inferring AS relationships by exploiting partial views of the AS graph available from different vantage points. Next we apply the technique to a collection of ten BGP routing tables to infer the relationships between neighboring ASes. Based on these results, we analyze the hierarchical structure of the Internet and propose a five-level classification of ASes. Our analysis differs from previous characterization studies by focusing on the commercial relationships between ASes rather than simply the connectivity between the nodes.}
}

EndNote citation:

%0 Report
%A Subramanian, Lakshminarayanan
%A Agarwal, Sharad
%A Rexford, Jennifer
%A Katz, Randy H.
%T Characterizing the Internet Hierarchy from Multiple Vantage Points
%I EECS Department, University of California, Berkeley
%D 2001
%@ UCB/CSD-01-1151
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2001/5263.html
%F Subramanian:CSD-01-1151