From: T Scott Saponas (ssaponas@cs.washington.edu)
Date: Wed Nov 03 2004 - 07:59:19 PST
"Quantifying the Causes of Path Inflation" looks at the causes for some routing paths in the internet being much longer than what a direct link would be. They use a trace-driven approach to examine what actual ISPs do with traffic and try to see where paths get long and why. They looked at paths that stay within an ISP and ones that require an ISP to send traffic through another ISP. In looking at traffic inside one ISP they discovered that paths are mostly latency driven and result in relatively short paths. In the later case, it was discovered the interaction of ISPs could mostly be characterized in terms of early-exit and late-exit strategies. In early exist strategies (the seemingly natural approach) data exists one ISP and heads to the other ISP as soon as it can when the destination is in the second ISP. Late-exit describes when one ISP actually keeps it in their network until its relatively close to the destination then hands it over to the other ISP. The existence of late-exit suggests ISPs must share some topological information because otherwise the first ISP wouldn't know where to route the packets internally before handing them over. Late-exit can lead to longer paths because the second ISP could have a shorter path to the destination from an early-exit point than from the late-exit point plus the internal route of the first ISP to the late-exit point. Similarly in early-exit, the first ISP might have had a shorter route. So in either policy just the fact that ISPs don't know the whole topology of each others network prevents any one flow from necessarily traveling along the shortest path.
In the case study of ATT and Sprint in San Francisco, it was discovered that there is yet another way packets can be routed besides early-exit and late-exit. They found that to avoid a congested link between one ISP and another SIP sometimes an ISP will actually send data far away to inject it into the other ISPs network there. Like in the case of sending some San Francisco traffic through Seattle.
This work does a good job of inferring routing policies and their impact on path length. However, an obvious drawback is researchers couldn't actually get access to the insides of the various ISPs studied to see how different changes in policies might actually reduce path blow-up. It might be interesting in future work to simulate the topology of a bunch of ISPs using this trace-driven approach to discover the characteristics of ISPs. You could imagine simulating these topologies using a collection of virtual routers and independent agents (representing ISPs) giving the routers in their AS a collection of routing policies. Then one could show the possibilities of new policies that work among competitive networks to reduce path blow-up.
This archive was generated by hypermail 2.1.6 : Wed Nov 03 2004 - 07:59:28 PST