What is TULIP
TULIP is a geolocation utility developed by National University of Sciences and Technology (NUST) School of Electrical Engineering and Computer Sciences (SEECS) and the Stanford Linear Accelerator Center (SLAC) Internet End-to-end Performance Monitoring (IEPM) project. TULIP's purpose is to geolocate a specified target host (identified by IP name or address) using ping RTT delay measurements to the target from reference landmark hosts whose positions are well known (see map or table). Knowing the speed of light in fibre or copper (roughly 0.6*c, we use 1ms. is equivalent to 100km), the minimum ping RTT measurement of 5 pings from each landmark site gives a rough estimate of the fibre + copper cable distance of the landmark from the target host. Lateration is applied on these distance estimates to estimate the position of the specified host on the globe. We are focusing on a platform agnostic, open non-proprietary tool (c.f. Traceware from Digital island or Edgescape from Akamai) that can be used to evaluate the effectiveness of this technique for hosts outside the U.S. and Europe specifically in less well developed countries.
Lateration
Lateration is the calculation of position information based on distance measurements. Calculating an object's position in two dimensions requires distance measurements from 3 non-collinear points (hence Trilateration). Multilateration computes the position of an object by measuring its distance from multiple reference positions. We use Multilateration following "Wireless Position Technologies and Applications" written by Alan Bensky, 2008, British library Cataloguing. The algorithm for multilateration was designed for Wireless Sensor Networks, with a little tweaking of parameters like Time of Arrival and distance based on wireless sensor location.
Also see Problem of Apollonius and Descartes Theorem for tangential circles.
Some Uses of Geolocation and TULIP
Geolocation:
- If one knows where a host is located then one can choose what content to send to the host, for example what language to use, what local services to recommend etc. Typically this does not demand accurate geographical locating, often determining the state or country is enough.
- It can be useful for security to pin-point the location of a suspicious host (assuming it has not blocked pings).
- It can be used to help determine from where to get a replicated service.
- Applications that try to draw maps of host locations, such as Visual Traceroute, require accurate locations of routers.
- By determining the geographical path data travels on, one can analyze the efficiency of a network. For example, determining tha route used between countries in Africa and even within countries in Africa, one can determine that traffic frequently goes via Europe or North America, vastly increasing the RTTs and using more expensive transcontinental links.
- It can be used to supplement or verify the information in databases such as Whois, DNS, Geo IP Tools and PingER.
- The pings from multiple landmarks can help identify hosts that have proxies. For example many web servers in developing countries have proxy web servers in N. America or Europe.
- Hosts can move. For example host names belonging to companies that are acquired can move to new locations, or hosts names that are associated with a show (e.g. SuperComputing) that moves to new locations can also move. Then there are hosts (e.g. laptops, PDAs) that are inherantly mobile.
- Projects such as Zooknic Internet Intelligence study the geography of the Intenet industry providing maps of the Internet domains in the world and their relations to economic growth.
- TULIP is being used in Phantom OS as a location estimation service for making self configuring sub-grids. Phantom OS is a Grid OS being developed at SEECS (formerly NIIT), Pakistan in collaboration with UWE, UK.
TULIP
- TULIP can also be used to make ping requests from multiple landmarks to see whether the target is accessible by ping from multiple sites. If it is accessible from many landmarks but not all, then:
- It is possible that the landmark is not working. To test this try other targets and see if they all fail from a given landmark.
- The target may be blocking ping access from some landmarks.
- There may be some network problems (e.g. routing) between the landmark and target. Reviewing the ping output may assist in determining whether the target host's name is known to the landmark.
- TULIP can show up anomalies, e.g. a host masquerading as another host. In this case multiple hosts may show up with inconsistent min-RTTs. For example we have seen a case where a registered mail server in Iran (Geo-IP Tools and traceroutes showed it in Teheran), yet the IP addrress had min-RTTs from US and Canadian landmarks that showed less than a few tens of ms.
- TULIP can help identify if a host is connected via a satellite link. In this case minimum RTT from most or all landmarks will be >~ 400 msec.
- TULIP can help identify hosts that are replicated. For example root name servers (e.g. 193.0.14.129) or servers (e.g. gfx1.hotmail.com, yahoo.com) with identical names or IP addresses that show up in many different regions. In this case the replicated host as seen from multiple landmarks will have impossibly short minimum RTTs that are less than the RTTs between the landmarks.
- By using the landmarks in the various regions, TULIP can be used to identify which regions have large RTTs to which regions. This may be used to identify where it would be advantageous to place a server in a region to reduce the RTTs and hence improve service. It may also be used to verify Service Level Agreements that involve RTTs.
Additional Location Techniques
There is no geographical tie between Internet architecture and geogrpahy. For example. unlike the phone system where phone numbers provide countries, areas and exchanges in areas, the Internet IP address is not designed to provide any location information. In fact, it needs to be understood that methods to derive location of Internet hosts were not originally designed for this. As mentioned previously, however, it can be important to know the location of a host. It is also very useful to have multiple ways to find the location of a host both since all methods ahve their problems, and also to look for agreements or discrepancies. The paper Distributed Traceroute Approach to Geographically Locating IP Devices investigates and evaluates existing (2003) methods and solutions. Basically there are three major ways of locating a host:
- By using databases such as whois, DNS, or location specific databases.
- By using traceroutes and extracting locations from router names.
- By using ping Round Trip Times.
When trying to map the topology of a traceroute onto a map of the world, such errors cause problems. For example a traceroute from Brazil to Costa Rica apparently (according to GeoIP Tools) goes to Florida then to Italy, back to Florida and then to Costa Rica. Actually it goes to Florida and then to Costa Rica. Hostip.info gets it right. Another example is a traceroute from Brazil to a Venezuelan (according to Geo IP Tools) node. Again the route according to Geo IP Tools goes via Italy and again HostIP.com gets it right. Geo IP Tools also shows the end host www.unerg.edu.ve in Venezuela while Hostip.info says its in the US. Other tests (RTT, Octant) make us believe it is in the US possibly Dallas (Octant) or Florida (TULIP). We are starting to compare Hostip with locations from the PingER database of known host, and see how well TULIP does for various regions (see for example TULIP estimates from Europe to PingER hosts).
Examples include:
- Databases:
- Shodan is a very useful search engine for network devices.
- Domain Name Services (DNS) may also help in locating a host. The DNS LOC (location) resource record is designed to make this data available. In addition the names of routers often contain their location (e.g. city) so a traceroute may help identify where a host is near. Examples include VisualRoute, NeoTrace and GTrace. See reference 1 for a comparison for the U.S. of the DNS method compared to ping RTTs and a cluster technique.
- Autonomous Systems (AS): Given an IP or host name you can use Fixed Orbits to find the relevant AS. Then using a table of AS number to name you can find out more about the AS (e.g. contacts, HQ site etc.) Another source for finding AS' is Team Cymru's whois database
- Whois databases: Examples of sites that provide information from such sources include: IP2location (max 20 requests per day unless sign up), Maxmind has a free downloadable GeoLite database that includes accuracy estimates, they also have an IPv6 database. AntiOnline, DNSstuff Geolocation, and Hostip.info. Unfortunately the information is often missing, inaccurate or stale. Also a large block of geographically disperded IP addresses may be assigend to a single entity and the Whois database may contain a single entry for all of them.
- Also see NetGeo from CAIDA, which though no longer maintained has many useful links. It has a database of previously successfully found hosts, if this fails it uses DNS, then a traceroute is performed with a WHOIS database lookup as a last resort. It is now a commercial product from NetGeo Inc..
- Geo IP Tool (also see the explanation) and IP-address.com display the location of a selected host/address using Google maps. Geo IP Tool uses a database and probably has the best overall coverage and accuracy. However, it often fails for routers. GeoBytes requires one to provide the IP address (not the name) which is a slight inconvenience. It provides lat/long as well as City, Country, population, currency etc.
- GeoTool this seems a promising new entry, it uses maxmind's database (see above).
- Networldmap determines geographical information by acquring location information from willing participants.
- Quova has a large (2.4 Billion addresses) database of IP addresses to locations that they can provide access to for organizations.
- Traceroute: Typically such methods use regular expressions to deduce the location of a router (e.g. a router with the name 500.Serial3-11.GW8.BOS1.ALTER.NET is using the Boston, US airport code (BOS) and is in the city of Boston, Massachussetts.)
- Visual TraceRoute Server: VisualRoute has limits on the number of tries (unless one subscribes). It uses both the router names and a knowledge base.
- Distributed Traceroute Approach to Geographically Locating IP Devices proposes a way of using traceroutes from multiple landmarks to a target host to locate the target.
- Round Trip Times: methods typically use the minimum RTT from several landmarks to the target host to triangulate the poistion of the target host.
- TULIP uses a Trilateration algorithm.
- Similar tools to TULIP are the Constraint Based Geolocation of Hosts2 and Octant from Cornell. Both of these foused on the technique, only worked in the U.S. and are longer providing a service.
If you need to find the latitude and longitude of a place whose location you can find on a map, then try the Latitude & Longitude finder. Latitude & Longitude finder 2. If you need to find the location ofd a knwon latitide and longitude then use Google Maps, latitude, Longitude Popup.
TULIP Landmarks
The details of landmarks is maintain in a MySQL database. Reflector has a function for easy viewing of these landmarks. The list of landmards and their detials can be seen by going here. The active landmarks are shown in green whereas the disabled ones are in red.
Landmark Maps
There are three type of landmarks i.e. PingER, PerfSONAR and PlanetLAB. Depending on the availablity of the landmarks, they can be either enabled or disabled for use in geolocation. The maps of the landmarks can be seen by going to the following links:
Enabled Landmarks Disabled LandmarksLandmark Laundering
The landmarks that are not responding should be disabled since otherwise reflector would have to wait for them to timeout and this would greatly increase the geolocation time. This process is carried out automatically by scripts running in trscrontab. This is documented here.