Inferring link weights using end-to-end measurements

ABSTRACT

We describe a novel constraint-based approach to approximate ISP link weights using only end-to-end measurements. Common routing protocols such as OSPF and IS-IS choose least-cost paths using link weights, so inferred weights provide a simple, concise, and useful model of intradomain routing. Our approach extends router-level ISP maps, which include only connectivity, with link weights that are consistent with routing. Our inferred weights agree well with observed routing: while our inferred weights fully characterize the set of shortest paths between 84--99% of the router-pairs, alternative models based on hop count and latency do so for only 47--81% of the pairs.

REFERENCES

• 1: M. Berkelaar. lp_solve: linear programming code. ftp://ftp.ics. ele.tue.nl/pub/lp_solve/.
• 2: Alan Borning , Bjorn Freeman-Benson , Molly Wilson, Constraint hierarchies, Lisp and Symbolic Computation, v.5 n.3, p.223-270, Sept. 1992 [doi>10.1007/BF01807506]
• 3: Hal Burch , Bill Cheswick, Mapping the Internet, Computer, v.32 n.4, p.97-98,102, April 1999 [doi>10.1109/2.755008]
• 4: D. Burton , Ph. L. Toint, On an instance of the inverse shortest paths problem, Mathematical Programming: Series A and B, v.53 n.1, p.45-61, Jan. 6, 1992 [doi>10.1007/BF01585693]
• 5: Robert Carter , Mark Crovella, Measuring Bottleneck Link Speed in Packet-Switched Networks, Boston University, Boston, MA, 1996
• 6: k. claffy, T. E. Monk, and D. McRobb. Internet tomography. In Nature, January 1999.
• 7: 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
• 8: S.P. Fekete, W. Hochstättler, S. Kromberg, and C. Moll. The complexity of an inverse shortest path problem. Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, 49, 1999.
• 9: B. Fortz and M. Thorup. Internet traffic engineering by optimizing OSPF weights. In IEEE INFOCOM, 2000.
• 10: L. Gao. On inferring autonomous system relationships in the Internet. In IEEE Global lnternet Symposium, 2000.
• 11: R. Govindan and H. Tangmunarunkit. Heuristics for Internet map discovery. In IEEE INFOCOM, 2000.
• 12: V. Jacohson. Pathchar. ftp://ftp.ee.lbl.gov/pathchar.
• 13: V. Jacobson. Traceroute. ftp://ftp.ee.lbl.gov/traceroute.tar.Z.
• 14: K. Lai and M. Baker. Nettimer: A tool for measuring bottleneck link bandwidth. In USITS, 2001.
• 15: K.G. Murty. Linear Programing. John Wiley & Sons, 1983.
• 16: Venkata N. Padmanabhan , Lakshminarayanan Subramanian, An investigation of geographic mapping techniques for internet hosts, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.173-185, August 2001, San Diego, California, United States
• 17: R. Rastogi, Y. Beribart, M. Garofalakis, and A. Kumar. Optimal configuration of OSPF aggregates. In IEEE INFOCOM, 2002.
• 18: 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
• 19: 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
• 20: L. Subrmanian, S. Agarwal, J. Rexford, and R. H. Katz. Characterizing the Internet hierarchy from multiple vantage points. In IEEE INFOCOM, 2002.
• 21: Hongsuda Tangmunarunkit , Ramesh Govindan , Sugih Jamin , Scott Shenker , Walter Willinger, Network topology generators: degree-based vs. structural, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 22: H. Tangmunarunkit, R. Govindan, and S. Shenker. Internet path inflation due to policy routing. In SPIE lTCom, 2001.
• 23: Y. Wang, Z. Wang, and L. Zhang. Internet traffic engineering without full mesh overlaying. In IEEE INFOCOM, 2001.
• 24: R. Wunderling. SoPlex: The sequential object-oriented simplex class library, http://www.zib.de/Optimization/Software/Soplex/ soplex.php.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management; Network monitoring
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

General Terms:
Management, Measurement, Performance