Quantifying the Causes of Path Inflation

Paper Review: Quantifying the Causes of Path Inflation

The paper focuses on Internet path inflation as a step in the goal of
determining the factors that affect Internet routes. By
characterizing the causes of path inflation, the authors hope to gain
knowledge about the design of networks, routing protocols and ISP
policies. In the past, this work was difficult as ISPs were unwilling
to share proprietary information, but advances in Internet topology
mapping and ISP policy inference has made it now possible. Their
study is based on trace-driven measurements.

Topology design and routing policy are the two major contributors to
path inflation and are subsequently accounted for in three component
layers, including the intra-domain, ISP peering and inter-domain. The
ISPs chosen in their study represent most of the large providers in
the Internet, which together comprise 40% of the globally routed IP
address space.

Using traceroute data along with BGP tables and DNS, the study first
identifies which ISP each router belongs to. The routers are
furthered mapped to geographical locations (point of presence) from
their DNS names. Their study focuses on path inflation between what
they refer to as important cities. Link latencies were computed using
geographic distance, which has shown to correlate well.

For path inflation due to intra-domain topology, an interesting result
was that path inflation was greatest in tier-1 ISPs which is somewhat
surprising at first glance. However, this is most likely due to the
high number of POPs in these ISPs making it difficult to connect all
pairs with a good set of links.

The topology of peering points was found not to have a significant
effect on path inflation. Early-exit in routing indicates a lack of
cooperation between ISPs. The study showed that there is in fact a
large amount of cooperation between ISPs.

Inter-domain routing was shown to have a significant impact on path
inflation with over one-half of the paths being longer than the
shortest paths. However, it was asserted that this path inflation was
not due to business-based policy but rather on using shortest AS-path
as the distance metric.

Some key observations:
- Policy has a greater effect on path inflation that topology at all
three component layers
- Inter-domain routing has a greater effect on path inflation than
intra-domain routing.
- Policy is affected by BGP as well as business arrangements.

The major conclusion of this work is that BGP is perhaps the leading
cause of path inflation in the Internet today.

One thing that quickly becomes evident when reading this paper is that
the work is very extensive. The authors have paid great attention to
detail and have attempted to cover all possibilities in their study.
Considering the inherent difficulty in their task, this is quite
impressive. Although their study was limited to their trace data,
their data set seems sufficiently large and thus their results are
indeed of value. The ability to infer routing policy and ISP topology
indicates a deep understanding of Internet technology and policy.
This paper is very interesting in that it shows Internet performance
is not only dependent on its technology, but also by the policies
which are based on business arrangements in ISPs. Furthermore, the
high occurrence of path inflation indicates a similar high level of
traffic engineering in ISPs.

-- Nadeem Abji
Received on Thu Nov 16 2006 - 01:45:55 EST