Bamba Gueye
Mark Crovella
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.
- {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. Google Scholar
- {2} A. Ziviani, S. Fdida, J. F. de Rezende, and O. C. M. B. Duarte, "Improving the accuracy of measurement-based geographic location of Internet hosts," Comput. Netw., vol. 47, no. 4, pp. 503-523, Mar. 2005. Google Scholar
- {3} V. N. Padmanabhan and L. Subramanian, "An investigation of geographic mapping techniques for Internet hosts," in Proc. ACM SIGCOMM , San Diego, CA, Aug. 2001, pp. 173-185. Google Scholar
- {4} P. Enge and P. Misra, "Special issue on global positioning system," Proc. IEEE, vol. 87, no. 1, pp. 3-15, Jan. 1999.Google Scholar
- {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.Google Scholar
- {6} L. Subramanian, V. N. Padmanabhan, and R. Katz, "Geographic properties of Internet routing," in Proc. USENIX 2002, Monterey, CA, Jun. 2002, pp. 243-259. Google Scholar
- {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.Google Scholar
- {8} L. Tang and M. Crovella, "Virtual landmarks for the Internet," in ACM Internet Measurement Conf. 2003, Miami, FL, Oct. 2003, pp. 143-152. Google Scholar
- {9} F. Dabek, R. Cox, F. Kaashoek, and R. Morris, "Vivaldi: A decentralized network coordinate system," in Proc. ACM SIGCOMM 2004, Portland, OR, Aug. 2004, pp. 15-26. Google Scholar
- {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.Google Scholar
- {11} PlanetLab: An Open Platform for Developing, Deploying, and Accessing Planetary-Scale Services. 2002 {Online}. Available: http://www.planet-lab.orgGoogle Scholar
- {12} C. Davis, P. Vixie, T. Goodwin, and I. Dickinson, "A means for expressing location information in the domain name system," Internet RFC 1876, Jan. 1996. Google Scholar
- {13} IP Address to Latitude/Longitude. Univ. Illinois, Urbana-Champaign {Online}. Available: http://cello.cs.uiuc.edu/cgi-bin/slamm/ip2ll/.Google Scholar
- {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.Google Scholar
- {15} GeoURL. {Online}. Available: http://www.geourl.org/.Google Scholar
- {16} Net World Map. {Online}. Available: http://www.networldmap.com/.Google Scholar
- {17} GeoNetMap. Geobytes, Inc. {Online}. Available: http://www.geobytes. com/GeoNetMap.htm.Google Scholar
- {18} GeoPoint. Quova Inc. {Online}. Available: http://www.quova.com/.Google Scholar
- {19} GTrace. CAIDA {Online}. Available: http://www.caida.org/tools/visualization/gtrace/Google Scholar
- {20} Sarangworld Traceroute Project. 2003 {Online}.Available: http://www. sarangworld.com/TRACEROUTE/Google Scholar
- {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.Google Scholar
- {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.Google Scholar
- {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.Google Scholar
- {24} RIPE Test Traffic Measurements. 2000 {Online}. Available: http://www.ripe.net/ttm/Google Scholar
- {25} NLANR Active Measurement Project. 1998 {Online}. Available: http:// watt.nlanr.net/.Google Scholar
- {26} N. Spring, R. Mahajan, and T. Anderson, "Quantifying the causes of path inflation," in Proc. ACM SIGCOMM 2003, Karlsruhe, Germany, Aug. 2003, pp. 113-124. Google Scholar
- {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.Google Scholar
- {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. Google Scholar
- {29} Geographic location/privacy (geopriv). IETF working group, 2003 {Online}. Available: http://www.ietf.org/html.charters/geo-priv-charter.htmlGoogle Scholar
- {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.Google Scholar
Index Terms
- Constraint-based geolocation of internet hosts
Recommendations
Constraint-based geolocation of internet hosts
IMC '04: Proceedings of the 4th ACM SIGCOMM conference on Internet measurementGeolocation 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 ...
Leveraging buffering delay estimation for geolocation of internet hosts
NETWORKING'06: Proceedings of the 5th international IFIP-TC6 conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications SystemsGeolocation techniques aim at determining the geographic location of an Internet host based on its IP address. Currently, measurement-based geolocation techniques disregard the buffering delays that may be introduced at each hop along the path taken by ...
Assessing the geographic resolution of exhaustive tabulation for geolocating internet hosts
PAM'08: Proceedings of the 9th international conference on Passive and active network measurementGeolocation of Internet hosts relies mainly on exhaustive tabulation techniques. Those techniques consist in building a database, that keeps the mapping between IP blocks and a geographic location. Relying on a single location for a whole IP block ...
Reviews
Kipp Jones
Geolocation of devices has long been a topic of research, and using the network to help uncover these details is a specific area within the broader topic. There have been several efforts to use information on and about the Internet to help systematically determine the physical location of a given machine. The authors present new work in the area of Internet protocol geolocation based on end-to-end delay measurements, work that performs better than previous efforts, including those based on domain name system, traceroute, and ping. The authors present a constraint-based geolocation (CBG) approach that uses the additive delay error in end-to-end delay measurements to estimate a great-circle radius. Multiple great-circle radii from a number of landmarks are then used to perform multilateration to create an area of estimation within the intersection of all radii. The centroid of this enclosed polygon is then used as the estimated location, with the area of the polygon representing an estimate of accuracy. The bounding region is reduced by a distributed self-calibrating process, whereby each of the landmarks continuously adjusts its estimation delays and tunes the distance calculations based on changing conditions within the network. Based on tests in Western Europe, the US, and via PlanetLab, the authors show improved results and analyze the impact of various changes such as the number (and quality) of the landmarks chosen for the geolocation task. The median error for the tests in the US is below 100km, while those performed in Europe have a median below 25km. This is an improvement over the median of 150km for the US and 100km for Europe using methods such as GeoPing. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments