From: Andrew Putnam (aputnam@cs.washington.edu)
Date: Tue Nov 02 2004 - 01:15:10 PST
Quantifying the Causes of Path Inflation
Neil Spring, Ratul Mahajan, Thomas Anderson
Summary: This paper seeks to determine the cause of previously
observed Internet path inflation. They determine the primary causes to
be inter-domain routing and ISP peering policies, and suggest that
technical rather than commercial barriers account for the sub-optimal
inter-domain routing.
Internet measurement techniques allow users to measure network
topologies, locations, and policies without enlisting the help of
network administrators. Using these techniques, the authors compare
optimal routing with the observed routing. The authors cite a previous
study that indicates geographical distance between network nodes is a
good indication of minimum network latency. By comparing the network
latency with the time required for a signal to travel from city A to
city B, the effectiveness of the path can be evaluated.
A key piece of information that is missing from the analysis is the
amount of traffic traversing the various links. While the Internet
measurement techniques can infer the presence of various paths, it is
difficult to determine the path bandwidth or utilization without the
help of the network administrator. Without this information, it is
difficult to determine whether or not the path inflation is a necessary
consequence of congested links. In the example case of Sprint and AT&T,
congestion appears to be the reason for the sub-optimal routing path.
There are a number of interesting findings presented in this paper.
First, intra-ISP routing is very close to optimal. It appears that with
a centralized authority, it is possible to come up with an optimal
configuration.
Another interesting finding is that two ISPs may behave differently
toward each other. This is odd in that one expects ISPs to treat each
other in the same manner. Instead, their analysis shows that some ISPs
are significantly nicer in terms of attempting to find optimal routes
for traffic entering other ISPs than the other ISP is at sending
traffic back the other direction. In particular, the ISP Telia follows
a late-exit policy for 13 peer ISPs, while only 4 ISPs follow a
late-exit policy toward Telia.
Perhaps the most interesting conclusion in the paper is that the
sub-optimal routes chosen for inter-domain traffic are motivated by the
fact that ISPs do not have enough information about network topologies
in other ISPs to make optimal routing decisions. I would expect that
ISPs would not route traffic for other ISPs without incentive to do so,
but is appears that ISPs still try, but fall short of optimal for
technical rather than commercial reasons.
The overall conclusion is the providing ISPs with better global
information will likely have the greatest effect in reducing Internet
path inflation.
This archive was generated by hypermail 2.1.6 : Tue Nov 02 2004 - 01:15:10 PST