Review: Quantifying Causes of Path Inflation

This paper examines the question of why certain Internet routing paths
can become extremely long. In particular, the paper investigates a
number of different factors affecting the inflation of paths: how paths
are selected within ISPs (intra-domain routing), how paths are selected
between ISPs (inter-domain routing), and the sequence of ISPs that
occur along a path between two end points.

The paper develops an original method for inferring intra-domain
routing policies and policies for selecting ISP peers on inter-domain
hops. This was done by first collecting traceroute data from a number
of PlanetLab vantage points. Then, the trace data was analyzed so that
the network topology could be extracted and policies could be inferred.

Inferring policy for intra-domain routing was done by assuming that
routing is done by using the shortest weighted paths with some unknown
set of edge weights. The authors infer these weights using the trace
data they collect and the topology that they extracted from it.

The paper also studies the impact of intra-domain routing policy by
measuring the inflation of least weight paths over shortest latency
paths. (The shortest latency path is a hypothetical one-hop direct link
between two points.) The results obtained show that the majority of
intra-domain paths are not inflated.

The paper goes on to study the peering factors and inter-domain factors
affecting route selection. These actual turn out to be the major
culprits of path inflation. Finally, the paper concludes that the main
reason for inter-domain path inflation has to do with BGP and poor or
nonexistant BGP policy controls.

Overall this was a good paper. Not only is solid evidence provided for
explaining why inter-domain routing is the main reason of path
inflation, but the authors go on to suggest a way for alleviating the
problem. This suggestion involves attaching geographic coordinates to
route advertisements in BGP. This will allow routes to be chosen that
have lower latency, since the geography of nodes tends to be a good way
of determining the latency of paths between nodes.
Received on Thu Nov 16 2006 - 01:59:22 EST