Constraint-based geolocation of internet hosts

ABSTRACT

Geolocation of Internet hosts enables a diverse and interesting 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, thus establishing a continuous space of answers instead of a discrete one. 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 the previous measurement-based 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: NLANR Active Measurement Project. http://amp.nlanr.net/active/.
• 2: 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. of the Passive and Active Measurement Workshop - PAM'2002, Fort Collins, CO, USA, Mar. 2002.
• 3: K. Claffy. Internet measurement: myths about Internet data. Talk at NANOG24 Meeting, Feb. 2002. http://www.caida.org/outreach/presentations/Myths2002/.
• 4: C. Davis, P. Vixie, T. Goowin, and I. Dickinson. A means for expressing location information in the domain name system. Internet RFC 1876, Jan. 1996.
• 5: P. Enge and P. Misra. Special issue on global positioning system. Proceedings of the IEEE, 87(1):3--15, Jan. 1999.
• 6: D. Moore, R. Periakaruppan, J. Donohoe, and K. Claffy. Where in the world is netgeo.caida.org? In Proc. of the INET'2000, Yokohama, Japan, July 2000.
• 7: 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
• 8: R. Percacci and A. Vespignani. Scale-free behavior of the Internet global performance. The European Physical Journal B - Condensed Matter, 32(4):411--414, Apr. 2003.
• 9: RIPE Test Traffic Measurements. http://www.ripe.net/ttm/.
• 10: University of Illinois at Urbana-Champaign. IP Address to Latitude/Longitude. http://cello.cs.uiuc.edu/cgi-bin/slamm/ip2ll/.
• 11: S. van Langen, X. Zhou, and P. van Mieghem. On the estimation of Internet distances using landmarks. In Proc. of the International Conference on Next Generation Teletraffic and Wired/Wireless Advanced Networking -- NEW2AN'04, St. Petersburg, Russia, Feb. 2004.
• 12: S.-H. Yook, H. Jeong, and A.-L. Barabási. Modeling the Internet's large-scale topology. Proc. of the National Academy of Sciences (PNAS), 99:13382--13386, Oct. 2002.
• 13: A. Ziviani, S. Fdida, J. F. de Rezende, and O. C. M. B. Duarte. Demographic placement for Internet host location. In Proc. of the IEEE GLOBECOM'2003, San Francisco, CA, USA, Dec. 2003.
• 14: A. Ziviani, S. Fdida, J. F. de Rezende, and O. C. M. B. Duarte. Toward a measurement-based geographic location service. In Proc. of the Passive and Active Measurement Workshop - PAM'2004, Lecture Notes in Computer Science (LNCS) 3015, pages 43--52, Antibes Juan-les-Pins, France, Apr. 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Measurement

Keywords:
delay measurements, geolocation, multilateration