Testing the reachability of (new) address space

ABSTRACT

The Internet was originally designed to provide connectivity from every node to every other node. However, policies can impede this connectivity [1]. This is especially true for newly allocated address space. Some Internet Service Providers (ISPs) simply do not realize that the status of previously unallocated address space has changed, and they continue blocking that space. Therefore, it would be desirable to test whether filters block newly apportioned address space before it is allocated to ISPs and/or end users.

In this paper we present a methodology that aims to detect incorrectly configured filters, so that ISPs can be contacted and asked to update their router configurations. Our methodology is capable of detecting paths on which reachability is actually present but which are routed around an outdated filter configuration, as well as cases where a destination is inaccessible. To help narrowing down the most likely ASs that actually filter, we introduce a filtering likelihood index.

We apply our methodology on newly allocated address space and perform initial experiments on a large fraction of ISPs, covering over 80% of all Autonomous Systems (ASs).

REFERENCES

• 1: C. Labovitz and A. Ahuja, "Shining Light on Dark Internet Address Space," NANOG 23, 2001.
• 2: Mohit Lad , Dan Massey , Dan Pei , Yiguo Wu , Beichuan Zhang , Lixia Zhang, PHAS: a prefix hijack alert system, Proceedings of the 15th conference on USENIX Security Symposium, p.11-11, July 31-August 04, 2006, Vancouver, B.C., Canada
• 3: P. Boothe, J. Hiebert, and R. Bush, "How Prevalent is Prefix Hijacking on the Internet?," NANOG 36, February 2006.
• 4: Yan Chen , Adam Bargteil , David Bindel , Randy H. Katz , John Kubiatowicz, Quantifying Network Denial of Service: A Location Service Case Study, Proceedings of the Third International Conference on Information and Communications Security, p.340-351, November 13-16, 2001
• 5: Ratul Mahajan , David Wetherall , Tom Anderson, Understanding BGP misconfiguration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 6: "The Team Cymru Bogon Reference Page." http://www.cymru.com/Bogons/.
• 7: Nick Feamster , Jaeyeon Jung , Hari Balakrishnan, An empirical study of "bogon" route advertisements, ACM SIGCOMM Computer Communication Review, v.35 n.1, January 2005 [doi>10.1145/1052812.1052826]
• 8: G. Huston, "IPv4 Address Report," 2007. http://www.potaroo.net/tools/ipv4/index.html.
• 9: Z. Morley Mao , Randy Bush , Timothy G. Griffin , Matthew Roughan, BGP beacons, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948207]
• 10: American Registry for Internet Numbers. http://www.arin.net/.
• 11: "Planetlab." http://www.planet-lab.org/.
• 12: Brice Augustin , Xavier Cuvellier , Benjamin Orgogozo , Fabien Viger , Timur Friedman , Matthieu Latapy , Clémence Magnien , Renata Teixeira, Avoiding traceroute anomalies with Paris traceroute, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177100]
• 13: North American Network Operators Group. http://nanog.org/.
• 14: Zhuoqing Morley Mao , Jennifer Rexford , Jia Wang , Randy H. Katz, Towards an accurate AS-level traceroute tool, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863996]
• 15: Wolfgang Mühlbauer , Anja Feldmann , Olaf Maennel , Matthew Roughan , Steve Uhlig, Building an AS-topology model that captures route diversity, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 16: Cooperative Association for Data Analysis, "Skitter." http://www.caida.org/tools/measurement/skitter/.
• 17: Z. Mao, D. Johnson, J. Rexford, J. Wang, and R. Katz, "Scalable and accurate identification of AS-level forwarding paths," in Proc. IEEE INFOCOM, 2004.
• 18: R. Bush, T. Griffin, Z. M. Mao, E. Purpus, and D. Stutzbach, "Happy Packets - Initial Results," 2004. NANOG 31.
• 19: Vern Paxson, End-to-end routing behavior in the Internet, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.601-615, Oct. 1997 [doi>10.1109/90.649563]
• 20: T. G. Griffin Interdomain routing links. http://www.cl.cam.ac.uk/users/tgg22/interdomain/.
• 21: Craig Labovitz , G. Robert Malan , Farnam Jahanian, Internet routing instability, IEEE/ACM Transactions on Networking (TON), v.6 n.5, p.515-528, Oct. 1998 [doi>10.1109/90.731185]
• 22: Zhuoqing Morley Mao , Ramesh Govindan , George Varghese , Randy H. Katz, Route flap damping exacerbates internet routing convergence, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 23: T. G. Griffin and G. Huston, "BGP Wedgies," 2005. RFC 4264.
• 24: D. McPherson , V. Gill , D. Walton , A. Retana, Border Gateway Protocol (BGP) Persistent Route Oscillation Condition, RFC Editor, 2002
• 25: Anja Feldmann , Olaf Maennel , Z. Morley Mao , Arthur Berger , Bruce Maggs, Locating internet routing instabilities, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 26: RIPE's Routing Information Service. http://www.ripe.net/ris/.
• 27: University of Oregon RouteViews project. http://www.routeviews.org/.