Relationship Between ASes: It’s Complicated

A Review on Inferring Autonomous System Relationships in the Internet

On Inferring Autonomous System Relationships in the Internet[1], written by Lixin Gao, formalizes a way to infer the relationship among autonomous systems in the internet.

Motivation
Since interconnectivity does not imply reachability among autonomous systems [1], there’s a need to visualize the AS relationships which are normally contractual commercial agreements to improve the topology of AS.

Summary

The paper can be summarized [2] by the following:

The relationship between a pair of ASes are customer-provider, provider-customer, peer-peer and sibling-sibling where a sibling relationship is mutual transit.

	Own Routes |	Customer’s Routes |	Sibling’s Route |	Provider’s Route |	Peer’s Route
Exporting to a Provider	X	X	X
Exporting to a Customer	X	X	X	X	X
Exporting to a Peer	X	X	X
Exporting to a Sibling	X	X	X	X	X

The author includes valley-free property which states that after traversing a provider-to-customer or peer-to-peer edge, the AS path cannot traverse a customer-to-provider or peer-to-peer edge. Provided that all ASes set their policies in accordance to the table above, any path is valley-free.

We can infer that:

• Peer-to-peer edge between top provider and one of its neighbors only
• If the top provider has sibling-to-sibling relationship with one of its neighbors, then it has a peer-to-peer relationship with the other neighbor
• We use the heuristic that peer-to-peer edge is between the top provider and its neighboring AS that has a higher degree because such edges are between ASes of comparable sizes
• We also use the heuristic that the degrees of two peers do not differ significantly – ASes having peer-to-peer relationship do not differ by more than R times

Margin Error
Since this is a mathematical inference, there’s room for errors. The author stated possible reasons of unconfrimed relationships – (1) router configuration typo (2) misconfiguration of small ISPs (3) unusual AS relationships and (4) inaccuracy of the heuristic in the algorithm

Conclusion
This algorithm is very useful that it became as of the bases in the papers such as [3]. hWith what I’ve seen in the Google result, this has been an accepted truth to determine the relationship among autonomous systems.

[1] Lixin Gao, “Inferring Autonomous System Relationships in the Internet”
[2] http://www.cs.fsu.edu/~xyuan/cis6930/lect6_as_relation.ppt
[3] Anja Feldmann et al, “A Methodology for Estimating Interdomain Web Traffic Demand”,
http://www.imconf.net/imc-2004/papers/p322-feldmann.pdf

Possibly Related Posts:

• Look Up! It’s a Chord!
• Chord-ially Inviting
• Internalizing Interdomain Internet Routing
• Fly, DARPA, Fly!
• Does The End Justify The Means?