URL: http://nms.lcs.mit.edu/6.829-f03/ps/ps2/lakshmi-mvp.pdf Entry Date: 2002-11-4 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 characterization differs from previous studies by focusing on the commercial relationships between ASes rather than simply the connectivity between the nodes. Datasets: 'bgp paths' data of 9 April 2001 from:
AS 1755 (Ebone)
AS 2548 (MAE-West)
AS 2516 (KDDI Japan)
AS 6893 (Cable and Wireless)

'show ip bgp' data of 18 April 2001 and 1 May 2001 from:
AS 1 (Genuity)
AS 1740 (CERFnet)
AS 3549 (Globalcrossing)
AS 3582 (Oregon RouteViews)
AS 3967 (Exodus Comm.)
AS 4197 (Global Online Japan)
AS 5388 (Energis Squared)
AS 7018 (AT&T)
AS 8220 (COLT Internet)
AS 8709 (Exodus, Europe)
Results:

• Presents a heuristic algorithm for inferring AS relationships (customer/provider and peer-peer relationships) from partial views of the AS graph from multiple vantage points.
• Presents a heuristic algorithm for dividing the Internet hierarchy into layers based on AS relationships (customer/provider and peer-peer relationships) and node connectivity.
• Based on the application of these algorithms to the Internet, proposes a five-level classification of ASes (similar to tiers). However:
  • Inferences are based on only ten vantage points.
  • The Oregon RouteViews table is treated as a single vantage point, rather than treating each AS participating in RouteViews as a vantage point.

Notes: According to the authors, their approach differs from Gao's for inferring relationships among ASes as follows. Gao constructs paths consisting of AS links, and then uses node degree to establish the point which divides the path into customer-provider links and provider-customer links. Instead, the authors use a ranking algorithm which ranks ASes along AS paths, and then apply heuristics to the ranks to determine customers, providers and peers.

According to the authors, their approach differs from Govindan and Reddy's for grouping ASes into classes, in that Govindan and Reddy use node degree to do this, whereas the authors use the provider/customer and peer-peer relationships. References:

• Complements:
  • L. Gao, "On inferring autonomous system relationships in the Internet," in Proc. IEEE INFOCOM, November 2000.
  • R. Govindan and A. Reddy, "An Analysis of Inter-Domain Topology and Route Stability," in Proc. IEEE INFOCOM 1997.
• Other references:
  • G. Huston, "Interconnection, Peering, and Settlements," in Proc. International Networking Conference (INET), June 1999
  • C. Alaettinoglu, "Scalable router configuration for the Internet," in Proc. IEEE IC3N, October 1996.