Internet Path Selection

This paper uses several traces over various times to evaluate the
efficiency of Internet routing. The intuition is that because routing
is separated into a two stage hierarchy, where the motivation for
inter-AS routing is not necessarily performance-based, many paths can
be suboptimal. Because path optimality is a function of traffic,
determining the upper-bound for path selection quality can be
difficult to ascertain. Nevertheless, this paper selects a "best
path" metric by examining link characteristics of edges between nodes
over a long period of time.

I am somewhat torn by the results of this paper. On the one hand, it
is obvious there will be inefficiencies in routing, not only due to
physical constraints, but also due to economic constraints of peering
structures between autonomous systems. But on the other hand, there
is significant room for improvement.

For example, Figure 1 and 6: The CDF tells me that for approximately
50% of the nodes, the real route performed just as good or better than
the calculated "optimum". To me, that's not half bad. The graph
isn't symmetrical, but that tells me that on average the system as a
whole works pretty good.
Received on Thu Nov 03 2005 - 10:21:30 EST