Path Inflation Review

This paper attempts to determine why Internet paths are frequently much
longer than necessary. The authors gather data on the topologies of 65
diverse ISPs and their interconnections by tracing packet hops from 42
geographically dispersed vantage points using PlanetLab. They deduce ISP
topologies by using new, indirect methods because ISPs are reluctant to
share proprietary topology maps and peering agreements.

The problem is analyzed at three levels: intra-domain, ISP peering, and
inter-domain. Topologies are extracted using BGP tables to distinguish IP
address spaces of different ISPs and confirmed by comparing the names of
routers with DNS records. It was assumed that the routing within an ISP is
weighted shortest path with some unknown set of edge weights, then the
collected data was fit to the topologies to determine those weights. The
inferred weights not only fit the observed paths well, they also predicted
paths between cities for which no data was collected.

The authors' main conclusions are:

1) Intra-domain traffic engineering was found to be common but minimally
responsible for path inflation. Investigation of paths beyond 50 ms
revealed that most are caused by load balancing across multiple
transcontinental links. The problem is most severe with Tier1 ISPs.
2) It was found that adjacent ISPs do cooperate to set up optimized peering
arrangements to avoid undesirable routes and to perform load balancing
across several peering links. Peering topology does not affect path
inflation significantly, however peering policies do make a significant
contribution to path inflation and cause excessively long paths. They found
that paths that use early-exit strategies are suboptimal.
3) For inter-domain traffic, most of the path inflation comes from using the
shortest AS-path as the distance metric.

Ultimately, the blame falls on BGP since it does not provide sufficient
information for co-operative ISPs to implement optimal routing decisions.
The authors express reservations about the ability to generalize their
results because their data is dependent on their choices of ISPs and vantage
points.
Received on Thu Nov 16 2006 - 08:23:29 EST