Discarte: a disjunctive internet cartographer

ABSTRACT

Internet topology discovery consists of inferring the inter-router connectivity ("links") and the mapping from IP addresses to routers ("alias resolution"). Current topology discovery techniques use TTL-limited "traceroute" probes to discover links and use direct router probing to resolve aliases. The often-ignored record route (RR) IP option provides a source of disparate topology data that could augment existing techniques, but it is difficult to properly align with traceroute-based topologies because router RR implementations are under-standardized. Correctly aligned RR and traceroute topologies have fewer false links, include anonymous and hidden routers, and discover aliases for routers that do not respond to direct probing. More accurate and feature-rich topologies benefit overlay construction and network diagnostics, modeling, and measurement.

We present DisCarte, a system for aligning and cross-validating RR and traceroute topology data using observed engineering practices DisCarte uses disjunctive logic programming (DLP), a logical inference and constraint solving technique, to intelligently merge RR and traceroute data. We demonstrate that the resultant topology is more accurate and complete than previous techniques by validating its internal consistency and by comparing to publicly-available topologies. We classify irregularities in router implementations and introduce a divide-and-conquer technique used to scale DLP to Internet-sized systems.

REFERENCES

• 1: Abilene router configurations. http://pea.grnoc.iu.edu/Abilene.
• 2: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 3: 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]
• 4: R. P. Bonica, D.-H. Gan, and D. C. Tappan. ICMP extensions for multiprotocol label switching. Internet Draft (work in progress): draft-ietf-mpls-icmp-05, 2006.
• 5: Francesco Calimeri , Wolfgang Faber , Gerald Pfeifer , Nicola Leone, Pruning Operators for Disjunctive Logic Programming Systems, Fundamenta Informaticae, v.71 n.2,3, p.183-214, February 2006
• 6: Personal e-mail from Cisco engineers.
• 7: k. claffy, T. E. Monk, and D. McRobb. Internet tomography. Nature, Web Matters, 1999. http://www.nature.com/nature/webmatters/tomog/tomog.html.
• 8: http://www.dbai.tuwien.ac.at/proj/dlv/examples/3col.
• 9: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 10: L. Gao and F. Wang. The extent of AS path inflation by routing policies. In IEEE GLOBECOM, vol. 3, 2002.
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: R. Govindan and H. Tangmunarunkit. Heuristics for Internet map discovery. In INFOCOM, 2000.
• 13: Graphviz. http://www.graphviz.org.
• 14: M. H. Gunes and K. Sarac. Analytical IP alias resolution. In IEEE International Conference on Communications (ICC), 2006.
• 15: Ningning Hu , Li (Erran) Li , Zhuoqing Morley Mao , Peter Steenkiste , Jia Wang, Locating internet bottlenecks: algorithms, measurements, and implications, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 16: C. Jin, Q. Chen, and S. Jamin. Inet: Internet topology generator. Tech. Rep. CSE-TR-433-00, University of Michigan, EECS dept., 2000. http://topology.eecs.umich.edu/inet/inet-2.0.pdf.
• 17: Ethan Katz-Bassett , John P. John , Arvind Krishnamurthy , David Wetherall , Thomas Anderson , Yatin Chawathe, Towards IP geolocation using delay and topology measurements, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177090]
• 18: A. Lakhina, J. Byers, M. Crovella, and P. Xie. Sampling biases in IP topology measurements. In INFOCOM, 2003.
• 19: Nicola Leone , Gerald Pfeifer , Wolfgang Faber , Thomas Eiter , Georg Gottlob , Simona Perri , Francesco Scarcello, The DLV system for knowledge representation and reasoning, ACM Transactions on Computational Logic (TOCL), v.7 n.3, p.499-562, July 2006 [doi>10.1145/1149114.1149117]
• 20: M. Litzkow, M. Livny, and M. Mutka. Condor: A hunter of idle workstations. In ICDCS, 1988.
• 21: Harsha Madhyastha , Tomas Isdal , Michael Piatek , Colin Dixon , Thomas Anderson , Arvind Krishnamurthy , Arun Venkataramani, iPlane: an information plane for distributed services, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.26-26, November 06-08, 2006, Seattle, WA
• 22: Priya Mahadevan , Dmitri Krioukov , Kevin Fall , Amin Vahdat, Systematic topology analysis and generation using degree correlations, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 23: Ratul Mahajan , Neil Spring , David Wetherall , Tom Anderson, Inferring link weights using end-to-end measurements, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637237]
• 24: 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]
• 25: Alberto Medina , Ibrahim Matta , John Byers, BRITE: A Flexible Generator of Internet Topologies, Boston University, Boston, MA, 2000
• 26: D. Meyer. University of Oregon Route Views project. http://www.routeviews.org/.
• 27: Akihiro Nakao , Larry Peterson , Andy Bavier, A routing underlay for overlay networks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863958]
• 28: Venkata N. Padmanabhan , Lili Qiu , Helen J. Wang, Passive network tomography using Bayesian inference, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637214]
• 29: Jean-Jacques Pansiot , Dominique Grad, On routes and multicast trees in the Internet, ACM SIGCOMM Computer Communication Review, v.28 n.1, p.41-50, Jan. 1998 [doi>10.1145/280549.280555]
• 30: 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]
• 31: Vern Paxson, Strategies for sound internet measurement, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028824]
• 32: L. Peterson, T. Anderson, D. Culler, and T. Roscoe. A blueprint for introducing disruptive technology into the Internet. In HotNets, 2002.
• 33: J. Postel, editor. Internet protocol. IETF RFC-791, 1981.
• 34: Francesco Ricca , Wolfgang Faber , Nicola Leone, A backjumping technique for disjunctive logic programming, AI Communications, v.19 n.2, p.155-172, January 2006
• 35: E. Rosen , A. Viswanathan , R. Callon, Multiprotocol Label Switching Architecture, RFC Editor, 2001
• 36: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 37: Rob Sherwood , Neil Spring, A platform for unobtrusive measurements on PlanetLab, Proceedings of the 3rd conference on USENIX Workshop on Real, Large Distributed Systems, p.2-2, November 05, 2006, Seattle, WA
• 38: Rob Sherwood , Neil Spring, Touring the internet in a TCP sidecar, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177093]
• 39: Neil Spring , Ratul Mahajan , Thomas Anderson, The causes of path inflation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863970]
• 40: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 41: Neil Spring , David Wetherall , Tom Anderson, Scriptroute: a public internet measurement facility, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.17-17, March 26-28, 2003, Seattle, WA
• 42: Jacob Strauss , Dina Katabi , Frans Kaashoek, A measurement study of available bandwidth estimation tools, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948211]
• 43: H. Tangmunarunkit, R. Govindan, and S. Shenker. Internet path inflation due to policy routing. In SPIE ITCOM Workshop on Scalability and Traffic Control in IP Networks, vol. 4526, 2001.
• 44: Renata Teixeira , Keith Marzullo , Stefan Savage , Geoffrey M. Voelker, In search of path diversity in ISP networks, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948247]
• 45: B. Yao, R. Viswanathan, F. Chang, and D. Waddington. Topology inference in the presence of anonymous routers. In INFOCOM, 2003.
• 46: E. W. Zegura, K. Calvert, and S. Bhattacharjee. How to model an internetwork. In INFOCOM, 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Experimentation, Measurement, Verification

Keywords:
alias resolution, discarte, disjunctive logic programming, network topology discovery, record route