Constraint-based geolocation of internet hosts

ABSTRACT

Geolocation of Internet hosts enables a new class of location-aware applications. Previous measurement-based approaches use reference hosts, called landmarks, with a well-known geographic location to provide the location estimation of a target host. This leads to a discrete space of answers, limiting the number of possible location estimates to the number of adopted landmarks. In contrast, we propose Constraint-Based Geolocation (CBG), which infers the geographic location of Internet hosts using multilateration with distance constraints to establish a continuous space of answers instead of a discrete one. However, to use multilateration in the Internet, the geographic distances from the landmarks to the target host have to be estimated based on delay measurements between these hosts. This is a challenging problem because the relationship between network delay and geographic distance in the Internet is perturbed by many factors, including queueing delays and the absence of great-circle paths between hosts. CBG accurately transforms delay measurements to geographic distance constraints, and then uses multilateration to infer the geolocation of the target host. Our experimental results show that CBG outperforms previous geolocation techniques. Moreover, in contrast to previous approaches, our method is able to assign a confidence region to each given location estimate. This allows a location-aware application to assess whether the location estimate is sufficiently accurate for its needs.

REFERENCES

• 1: [1] M. J. Freedman, M. Vutukuru, N. Feamster, and H. Balakrishnan, "Geographic locality of IP prefixes," in Proc. ACM Internet Measurement Conf. (IMC 2005), Berkeley, CA, Oct. 2005, pp. 153-158.
• 2: Artur Ziviani , Serge Fdida , José F. de Rezende , Otto Carlos M. B. Duarte, Improving the accuracy of measurement-based geographic location of internet hosts, Computer Networks and ISDN Systems, v.47 n.4, p.503-523, 15 March 2005 [doi>10.1016/j.comnet.2004.08.013]
• 3: 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
• 4: [4] P. Enge and P. Misra, "Special issue on global positioning system," Proc. IEEE, vol. 87, no. 1, pp. 3-15, Jan. 1999.
• 5: [5] S. Banerjee, T. G. Griffin, and M. Pias, "The interdomain connectivity of PlanetLab nodes," in Proc. Passive and Active Measurement Workshop (PAM 2004), Antibes Juan-les-Pins, France, Apr. 2004.
• 6: Lakshminarayanan Subramanian , Venkata N. Padmanabhan , Randy H. Katz, Geographic Properties of Internet Routing, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.243-259, June 10-15, 2002
• 7: [7] T. S. E. Ng and H. Zhang, "Predicting Internet network distance with coordinates-based approaches," in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 170-179.
• 8: Liying Tang , Mark Crovella, Virtual landmarks for the internet, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948223]
• 9: Frank Dabek , Russ Cox , Frans Kaashoek , Robert Morris, Vivaldi: a decentralized network coordinate system, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 10: [10] R. Percacci and A. Vespignani, "Scale-free behavior of the Internet global performance," Eur. Phys. J. B--Condensed Matter, vol. 32, no. 4, pp. 411-414, Apr. 2003.
• 11: [11] PlanetLab: An Open Platform for Developing, Deploying, and Accessing Planetary-Scale Services. 2002 [Online]. Available: http://www.planet-lab.org
• 12: C. Davis , P. Vixie , T. Goodwin , I. Dickinson, A Means for Expressing Location Information in the Domain Name System, RFC Editor, 1996
• 13: [13] IP Address to Latitude/Longitude. Univ. Illinois, Urbana-Champaign [Online]. Available: http://cello.cs.uiuc.edu/cgi-bin/slamm/ip2ll/.
• 14: [14] D. Moore, R. Periakaruppan, J. Donohoe, and K. Claffy, "Where in the world is netgeo.caida.org?," presented at the INET 2000 Conf., Yokohama, Japan, Jul. 2000.
• 15: [15] GeoURL. [Online]. Available: http://www.geourl.org/.
• 16: [16] Net World Map. [Online]. Available: http://www.networldmap.com/.
• 17: [17] GeoNetMap. Geobytes, Inc. [Online]. Available: http://www.geobytes. com/GeoNetMap.htm.
• 18: [18] GeoPoint. Quova Inc. [Online]. Available: http://www.quova.com/.
• 19: [19] GTrace. CAIDA [Online]. Available: http://www.caida.org/tools/visualization/gtrace/
• 20: [20] Sarangworld Traceroute Project. 2003 [Online].Available: http://www. sarangworld.com/TRACEROUTE/
• 21: [21] P. Bahl and V. N. Padmanabhan, "RADAR: An in-building RF-based user location and tracking system," in Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, Mar. 2000, pp. 775-784.
• 22: [22] A. Ziviani, S. Fdida, J. F. de Rezende, and O. C. M. B. Duarte, "Toward a measurement-based geographic location service," in Proc. Passive and Active Measurement Workshop (PAM 2004), Antibes Juan-les-Pins, France, Apr. 2004, pp. 43-52.
• 23: [23] C. J. Bovy, H. T. Mertodimedjo, G. Hooghiemstra, H. Uijterwaal, and P. van Mieghem, "Analysis of end-to-end delay measurements in Internet," in Proc. Passive and Active Measurement Workshop (PAM 2002), Fort Collins, CO, Mar. 2002.
• 24: [24] RIPE Test Traffic Measurements. 2000 [Online]. Available: http://www.ripe.net/ttm/
• 25: [25] NLANR Active Measurement Project. 1998 [Online]. Available: http:// watt.nlanr.net/.
• 26: 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]
• 27: [27] D. Krioukov, K. Fall, and X. Yang, "Compact routing on Internet-like graphs," in Proc. IEEE INFOCOM 2004, Hong Kong, Mar. 2004, pp. 209-219.
• 28: [28] H. Zheng, E. K. Lua, M. Pias, and T. G. Griffin, "Internet routing policies and round-trip-times," in Proc. Passive and Active Measurement Workshop (PAM 2005), Boston, MA, Mar. 2005, pp. 236-250.
• 29: [29] Geographic location/privacy (geopriv). IETF working group, 2003 [Online]. Available: http://www.ietf.org/html.charters/geo-priv-charter.html
• 30: [30] S.-H. Yook, H. Jeong, and A.-L. Barabási, "Modeling the Internet's large-scale topology," Proc. National Academy of Sciences (PNAS), vol. 99, pp. 13382-13386, Oct. 2002.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques; Design studies

Keywords:
delay measurement, geolocation, internet, multilateration, position measurement