Review: Quantifying the Causes of Path Inflation

Review: Quantifying the Causes of Path Inflation

Reviewer: Di Niu

This paper focuses on figuring out the various causes for path
inflation in the Internet -- end-to-end paths can be significantly
longer than necessary. Six possible causes of path inflation are
identified in the paper: topology and routing policy at three
different layers, i.e., in the selection of paths within an ISP, of
peering links to reach neighboring ISPs, and of the sequence of ISPs
used to reach more distant destinations. New methods are developed
to infer intra-domain routing policies and ISP peering policies
(which determine how ISPs exchange traffic with their neighbors).

One insight of the paper is that both paths taken and not taken
reveal information about the routing policy. For intra-domain paths,
the paper infers a set of edge weights that are consistent with the
paths obeserved in the trace data. Between neighboring ISPs, it
infers the use of early exit and various forms of cooperative routing
by focusing on whether the chosen paths depend on the ingress in the
upstream ISP, the egress in the downstream ISP, or both. These
results provide the first empirical data on ISP peering policies.

The main findings of the paper could be summarized as the following.
First, intra-domain traffic engineering is commonplace but has only a
minimal impact on path inflation. Second, contrary to popular belief,
there is significant cooperation between adjacent ISPs in the
Internet, to avoid particularly poor routes or load-balance traffic
across multiple peering links. Third, many paths that use early-exit
are inflated compared to a hypothetical optimal exit policy. Finally,
topology-insensitive load balancing can cause significant path
inflation.

The paper is original. The idea flows are very smooth, which makes it
relatively easy to digest the paper.
Received on Wed Nov 15 2006 - 22:37:30 EST