The causes of path inflation

ABSTRACT

Researchers have shown that the Internet exhibits path inflation -- end-to-end paths can be significantly longer than necessary. We present a trace-driven study of 65 ISPs that characterizes the root causes of path inflation, namely topology and routing policy choices within an ISP, between pairs of ISPs, and across the global Internet. To do so, we develop and validate novel techniques to infer intra-domain and peering policies from end-to-end measurements. We provide the first measured characterization of ISP peering policies. In addition to "early-exit," we observe a significant degree of helpful non-early-exit, load-balancing, and other policies in use between peers. We find that traffic engineering (the explicit addition of policy constraints on top of topology constraints) is widespread in both intra- and inter-domain routing. However, intra-domain traffic engineering has minimal impact on path inflation, while peering policies and inter-domain routing lead to significant inflation. We argue that the underlying cause of inter-domain path inflation is the lack of BGP policy controls to provide convenient engineering of good paths across ISPs.

References

1. D. Anderson, H. Balakrishnan, M. F. Kaashoek, and R. Morris. Resilient overlay networks. In SOSP, 2002.
2. P. Barford, A. Bestavros, J. Byers, and M. Crovella. On the marginal utility of network topology measurements. In ACM SIGCOMM Internet Measurement Workshop, 2001.
3. S. Bhattacharyya, C. Diot, J. Jetcheva, and N. Taft. Pop-level and access-link-level traffic dynamics in a Tier-1 POP. In ACM SIGCOMM Internet Measurement Workshop, 2001.
4. A. Borning, B. Freeman-Benson, and M. Wilson. Constraint hierarchies. Lisp and Symbolic Computation, 5(3), 1992.
5. T. Bu and D. Towsley. On distinguishing between Internet power law topology generators. In IEEE INFOCOM, 2002.
6. H. Chang, et al. On inferring AS-level connectivity from BGP routing tables. Tech. Rep. UM-CSE-TR-454-02, University of Michigan, 2002.
7. k. claffy, T. E. Monk, and D. McRobb. Internet tomography. In Nature, 1999.
8. M. Dahlin, B. Chandra, L. Gao, and A. Nayate. End-to-end WAN service availability. In USITS, 2001.
9. M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the Internet topology. In ACM SIGCOMM, 1999.
10. A. Feldmann, et al. Netscope: Traffic engineering for IP networks. IEEE Network Magazine, 2000.
11. P. Francis, et al. IDMaps: A global Internet host distance estimation service. IEEE/ACM Transactions on Networking, 2001.
12. L. Gao. On inferring autonomous system relationships in the Internet. In IEEE Global Internet Symposium, 2000.
13. L. Gao and F. Wang. The extent of AS path inflation by routing policies. In IEEE Global Internet Symposium, 2002.
14. R. Govindan and V. Paxson. Estimating router ICMP generation delays. In Passive & Active Measurement (PAM), 2002.
15. R. Govindan and H. Tangmunarunkit. Heuristics for Internet map discovery. In IEEE INFOCOM, 2000.
16. G. Huston. BGP statistics. http://bgp.potaroo.net/rv-index.html.
17. A. Lakhina, J. Byers, M. Crovella, and P. Xie. Sampling biases in IP topology measurements. In IEEE INFOCOM, 2003.
18. R. Mahajan, N. Spring, D. Wetherall, and T. Anderson. Inferring link weights using end-to-end measurements. In ACM SIGCOMM Internet Measurement Workshop, 2002.
19. R. Mahajan, D. Wetherall, and T. Anderson. Understanding BGP misconfiguration. In ACM SIGCOMM, 2002.
20. D. Meyer. Routeviews project. http://www.routeviews.org.
21. K. G. Murty. Linear Programing. John Wiley & Sons, 1983.
22. V. N. Padmanabhan and L. Subramanian. An investigation of geographic mapping techniques for Internet hosts. In ACM SIGCOMM, 2001.
23. K. Papagiannaki, et al. Analysis of measured single-hop delay from an operational backbone network. In IEEE INFOCOM, 2002.
24. V. Paxson. End-to-end routing behavior in the Internet. In ACM SIGCOMM, 1997.
25. L. Peterson, T. Anderson, D. Culler, and T. Roscoe. A blueprint for introducing disruptive technology into the Internet. In HotNets-I, 2002.
26. S. Savage, et al. The end-to-end effects of Internet path selection. In ACM SIGCOMM, 1999.
27. N. Spring, R. Mahajan, and D. Wetherall. Measuring ISP topologies with Rocketfuel. In ACM SIGCOMM, 2002.
28. N. Spring, D. Wetherall, and T. Anderson. Scriptroute: A public Internet measurement facility. In USITS, 2003.
29. L. Subramanian, S. Agarwal, J. Rexford, and R. H. Katz. Characterizing the Internet hierarchy from multiple vantage points. In IEEE INFOCOM, 2002.
30. L. Subramanian, V. N. Padmanabhan, and R. H. Katz. Geographic properties of Internet routing. In USENIX Annual Technical Conference, 2002.
31. N. Taft, S. Bhattacharyya, J. Jetcheva, and C. Diot. Understanding traffic dynamics at a backbone POP. In SPIE ITCOM Workshop on Scalability and Traffic Control in IP Networks, 2001.
32. H. Tangmunarunkit, R. Govindan, and S. Shenker. Internet path inflation due to policy routing. In SPIE ITCom, 2001.
33. H. Tangmunarunkit, R. Govindan, S. Shenker, and D. Estrin. The impact of routing policy on Internet paths. In IEEE INFOCOM, 2001.
34. H. Tangmunarunkit, et al. Does AS size determine degree in AS topology? ACM Computer Communication Review, 2001.
35. H. Tangmunarunkit, et al. Network topology generators: Degree-based vs structural. In ACM SIGCOMM, 2002.

Index Terms

• Networks

  • Network architectures