Live TULIP

Live Tulip Visualization

Summary TULIP
(CBG Techniques only)

TULIP Summary Visualization

What is TULIP

TULIP is a web application being developed by the MAGGIE-NS team from the National University of Sciences and Technology (NUST) School of Electrical Engineering and Computer Sciences (SEECS) (formerly known as NIIT) 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. 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 (see Ref 1 for the error distance versus the number of probes) 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. There is a map and a table of the TULIP landmarks



Lateration back to top

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 back to top

Geolocation:

TULIP



Ways to Locate back to top

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: Databases may give the location of a host, in particular a router, as being the location of the owner's location rather than the location of the router itself. A couple of examples for hosts are www.seecs.edu.pk and www.hec.edu.pk which one would expect to be located in Islamabad since that is where ns.seecs.edu.pk is located, but are actually in Texas. Some examples for routers include GeoIP Tools locates address 4.68.116.16. in Kansas, whereas it has < 5ms minimum RTT from Liverpool and < 1ms (< 100km) from Rutherford Lab near Oxford in the UK. The router is in ASN 3356 which is Level 3 Communications, based in the U.S. It also locates mia2-fiu-1-us.mia.seabone.net as being in Europe (presumably since it is owned by a European ISP (Seabone) however it is in located in the US.

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:

If you want to find the great circle distance and know the latitude and longitude coordinates of the two ends then you can use the Movable Type Scripts web page. World Gazeteer provides access to data with lat/longs, cities, countries & populations ( download data). If you want to calculate it for yourself then see Deriving the Haversine Formula. You can also make a name server lookup for a host, or if you don't know the exact name tryDomainSurfer. There is also an Atlas of Cyberspace that provides maps and graphic representations of the geographies of the new electronic territories of the Internet, the World-Wide Web and other emerging Cyberspaces and the Corpex sponsored Cyber Geography Research.

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 finderLatitude & Longitude finder 2. If you need to find the location ofd a knwon latitide and longitude then use Google Maps, latitude, Longitude Popup.



Versions of TULIP back to top

We have developed two version of TULIP. The first (TULIP1) was developed to understand the feasability. The second (TULIP2) evolved from ideas and experiences encountered with TULIP1.

TULIP1:

TULIP1 is based on Java and Java Web Start must be installed on your system. The applet does all the work, it get the request for the target from the user, sends the requests to ping the target to the landmarks, gets the results back, amek the analysis and displays the rsults in graphical form. It requires a configuration file that provides the name and location of each landmark, the URLs for the ping and traceroutes. At SLAC this is kept at /afs/slac/www/comp/net/wan-mon/tulip/Sites.txt.

TULIP2

The user's browser accesses a form to make a request to locate a target. This is sent to tulip-viz.cgi at www-wanmon.slac.stanford.edu. It uses a Google visualization package to display a sortable table of the landmarks and their RTTs to the target. When it has gathered all the RTTs from the responding landmarks, it uses Google maps to display a map of the RTT circles used in the lateration and various location estimates for the target. The requests to the landmarks to ping the target are made by reflector.cgi running on www-wanmon.slac.stanford.edu. Having a central reflector enables more control over the requests and their impact, as well as keeping logs. It also enables us to use a single cookie to access PlanetLabs landmarks.

Landmarks back to top

For hosts in the world at large it is important to have landmarks that enable the host to sit within a triangle of landmarks 4,5. Thus we are very interested in getting more landmarks that cover the world. We also need thelatitude and longitude (lat/long) of each landmark. Most Internet hosts are located in developed countries of North America, Europe and East Asia. Thus we need landmarks to cover these areas. Many countries in the developing world do not have direct access to other nearby countries (see for example the Case Studies on S. Asia, Africa and Palestine) but go via Europe or the US. Thus the route is very indirect and extended so distances estimated by RTT will be too long. Thus we also need landmarks in such developing countries in particular those with a large Internet presence, e.g. countries with > 1 million connected Internet users (see Internet World Statistics). We have three main sources of landmarks:

Currently (May 2007) we have landmarks in about 30 countries (see map), so we have a way to go.



Securityback to top

The SLAC traceroute/landmark server that is frequently used by landmarks servers: rejects attempts to traceroute to a broadcast address; does not allow a remote host name to be greater than 255 characters to prevent buffer overflow attempts; does not allow a remote host in a different domain to do a traceroute to a host within the same domain as the web server; limits the maximum number of traceroute processes running in the server to reduce the chance of a denial of service request; starts the traceroute after 3 hops if the client/browser and server are in different domains in order to hide internal routing information from outsiders.\; has a blacklist of sites that are blocked.

The use of a central reflector to manage all the requests enables us to provide a single IP address that landmarks can enable access from, while disabling requests from other hosts.

A major concern is that the target is pinged simultaneously from multiple landmarks. This can look like a scan of multiple hosts when the target host responds to the ping requests. It can also look like a denial of service attack, especially for hosts with limited available bandwdth, such as are found in developing countries. We thus limit the number of pings from a landmark to a target to 5. We are also looking at tiering the landmarks. The top tier will enable us to locate the region of the world and then the second tier can be used to find the location in that region. This reduces the number of landmarks used and divides them in time into two or more sets. We are thus studying using tiering to tier the N. American and European hosts.

TULIP only allows one copy of the client to be running on a client host. TULIP also hides the URLs used for the landmarks to reduce the possibility of people gleaning the URLs for a denial of service attack. Editing the landmark URL's requires a password known only to the developers.

We have also considered whether the knowledge that a machine and possibly the usual owner can be accurately located may violate some privacy issue. This may require us to add some fuzz to results. So far this has not been done.



Log back to top

There is a centralized log of < 100 Mbytes, with time stamped records of all requests, the requesting host (client), the target, landmark, result (RTT, loss), errors etc. The log is truncated to the last 20% of the records when it reaches its maximum size. This is analyzed for response time of landmarks, abusing clients, and types of failures.


Problems with TULIP back to top



Development and More Information back to top

Development is at School of Electrical Engineering and Computer Sciences (SEECS, formerly known as NIIT), National University of Sciences and Technology (NUST), Pakistan and SLAC by Qasim Bilal Lone (SEECS and SLAC), Shahryar Khan (SEECS and SLAC) and Les Cottrell (SLAC). More information may be found at:

Acknowledgements back to top

We gratefully acknowledge the cooperation of the landmark sites, in particular PlanetLab, and those installing the SLAC reverse traceroute/ping server in developing regions (not Australia, N. America, Europe, Japan) of the world where there are fewer landmarks. These include:

References back to top

For documentation of work on TULIP see The TULIP Wiki.
  1.  "An Investigation of Geographic Mapping Techniques for Internet Hosts", N. N. Padmanabhan and L. Subramanian, 
  2. "Constraint-Based Geolocation of Internet Hosts", B. Gueye, M. Crovella, A. Ziviani, S. Fdida .(2004) 
  3. "Constraint-Based Geolocation of Internet Hosts", B. Gueye, M. Crovella, A. Ziviani, S. Fdida .(December 2006) 
  4.  "An Empirical Evaluation of Landmark Placement. on Internet Coordinate Schemes." Sridhar Srinivasan. Ellen Zegura. 
  5.  "Geometric Exploration of the Landmark Selection. Problem." Liying Tang and Mark Crovella 
  6. Geolocation Software 
  7. Geolocation
  8. Chapter 7 "Time of Arrival and Time Difference of Arrival", from Wireless Positioning Technologies and Applications, by Alan bensky
  9. Solving Passive Mulrtilateration Equations using Bancroft's Algorithm", M Geyer, A Daskaladis,
  10. Probabailistic Model of Triangulation, Xiaoyun Li, David K Hunter.