Review - Quantifying the Causes of Path Inflation

Review of Quantifying the Causes of Path Inflation
by Ivan Hernández

The paper explores causes of path inflation -- end-to-end paths are
significantly longer than necessary. In order to know the reasons of
this anomaly, the authors performed a large trace-driven experiment,
the resulting dataset is really big and heterogeneous and comprehends
traces from the core of the Internet. With the collected dataset the
authors are able to extract the topology of the traversed networks and
to infer intra-domain routing policies and ISP peering policies. Then,
they analyse if these topology and policies increment the path
inflation.

The authors characterize the contribution of topology and policy to
path inflation in three component layers (1) Intra-domain, where the
main goal of traffic engineering is to spread the load evenly among
the links in the topology, but it may lead to longer
paths. Nevertheless, the analysis shows that 80% of the intra-domain
paths are not inflated at all. From this we have that intra-domain
inflation is not a significant problem. (2) ISP Peering, where path
inflation may result because packets may not be forwarded to a peering
point that optimizes latency -- use of policies such as
early-exit. The analysis show that the peering topology does not
inflate paths significantly. There are interesting results in the ISP
Peering. Most ISP do not use early-exit routes over 75% of the paths
were closer to the destination -- a characteristic of either late-exit
or load-balancing policy. The authors found that there is little
difference in latency between the early and late exit routing
strategies. On the other hand, the comparison of early-exit against
optimal-exit show that early-exit sometimes lead to highly inflated
paths. (3) Inter-domain, a path from a source AS to a destination AS
may traverse multiple intermediate ISPs. ISPs make routing policy
decisions that determine which paths are taken. This path selection is
constrained by business relationships that may forbid good paths that
exists in the topology. Surprisingly, the inter-domain routing
policies does not contribute significantly to additional path
inflation. On the other hand, most of the inflation comes from using
shortest AS-path as the distance metric. In summary, BGP is again the
bad and the ugly of the movie, because it does not propagate enough
information to enable an informed AS path selection, and therefore,
ISPs use minimum AS-hop count paths.

Although the analysis was based on a large and heterogeneous dataset,
there is no evidence that this is representative of the Internet
traffic. All the analysis are based on infers from the authors, there
is no actual information about either the topology, routing metrics,
or policies. Therefore, this results must be taken conservatively. On
the other hand, I found interesting that none of the papers take
advantage of statistical analysis in order to plan representative
measurements, just like in election, where it is enough to take a
representative sample to do predictions of the complete voting
population.
Received on Wed Nov 15 2006 - 23:27:21 EST