TULIP

From MAGGIE

Jump to: navigation, search

Contents

[edit] What is TULIP? - Shahryar Khan, Faran Javed

TULIP ~ Trilateration Utility for Locating IP Addresses

It is a Java application being developed by the MAGGIE-NS team from the National University of Sciences and Technology (NUST) Institute of Information Technology ((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 fiber or copper (roughly 0.6*c, we use 1ms. is equivalent to 100km), the minimum ping RTT measurement 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.

[edit] Current Challenges

  • Currently having problems while resolving IP's from DNS. In case of replicas I don't know which IP to pick up and ping. Are you referring to "Some IP names and addresses actually refer to multiple hosts in very different locations. An example are some of the Internet's root name servers. Such hosts will appear to be close to multiple locations, so TULIP will be confused." as documented in the TULIP web page. If you get multiple IP addresses from a single name then you have two choices either tell the user to be more selective (and why) or try and locate them all. Les recommends the first.

Note: The DNS name is resolved at the Client-End (Where TULIP is running). Not at the landmark.

  • There Seems to be a problem with the location of DoE landmard recently added by Dr. Les. Les has fixed this, the longitude was missing a minus sign (-)

[edit] Progress

  • (Sunday, 17 June 2007 - 10:16 PM Pak Time):
Alpha for Pakistan improved from 20 to 42. (Using Landmark Alpha Tests)
  • (Saturday, 16 June 2007 - 8:52 PM Pak Time):
Alpha Optimization Using PingER Historical Data has been implemented.
  • If the distance between sites is greater than 0.0 and minRTT is 0.000 due to some reason. Than tulip will ignore any such data.
Scripts to edit Sites.txt have been implemented and integrated.
  • (Friday, 11 May 2007 - 9:21 PM Pak Time):
Investigating possible landmarks.
Planning the procedure for refining alpha values using PingER historical data
Studying the sigcomm paper.
  • (Friday, 11 May 2007 - 9:16 PM Pak Time):
SiteList can be updated from TULIP client.
Other implementation Bugs have also been removed.
TULIP is using Gal-Peters Projection NOT mercator projection.
  • (Tuesday, 24 April 2007 - 11:30 AM Pak Time):
The iterative correction algorithm has been completely implemented, debugged & tested. The updated version of TULIP is available at NIIT & SLAC site. Now I (Faran) will proceed with the tests. Three types of tests will be conducted.
  • Simple Tri-lateration with modified alpha
  • Iterative correction with modified alpha
  • Iterative correction with alpha = 100
  • After applying Iterative correction location results with modified alpha and alpha = 100 are almost same in most cases.
  • (Friday, 20 April 2007 - 01:00 PM Pak Time):
Sir Umar created account for me(Faran) on maggie2.
  • (Wednesday, 18 April 2007 - 11:23 PM Pak Time):
Perl scripts for TULIP config file managment are complete. These will be deployed on maggie server at NIIT. After testing and debugging these can be deployed on the SLAC server later.
  • (Sunday, 15 April 2007 - 11:19 PM Pak Time):
The second Visualization screen in TULIP titled "Locate using iterative correction" is now using modified alpha values. The decrease in the amount of overestimation is clear. Also the circles now complement each other and tend to focus at a point. This is a proof of the correctness of the modified alpha values. Now applying iterative correction on these distance measurments should increase the accuracy greatly. I (Les) tried it with www.dl.ac.uk (near Liverpool in the North of England). The nearby landmarks (in UK and Europe) did a pretty good job. The long distance network (e.g. in US, India) did a poor job. This is what one would want. We cannot expect hosts a long distance from the target to get a good estimate. So as Faran says it looks better.
  • (Monday, 09 April 2007 - 8:11 PM Pak Time):
Formatted output tables available at File >> View Landmark Config File. It is password protected because disclosing the ping and tracesite URL's might trigger some security issues we discussed before. For the same reason Faran has removed the ping and trace URL's from the main ping and trace tables. The raw output page is still working. To see raw output please double click on an entry in the ping or trace table. This looks good and well enough protected (Les).
  • (Sunday, 08 April 2007 - 7:17 AM Pak Time):
Site.txt file with adjusted alpha values hosted at http://maggie.niit.edu.pk/newwebsite/tulip/Sites.txt. Currently it is quite uneasy to observe the configuration file. Faran will provide a GUI that will parse the text file and show formatted output in tables.
  • (Wednesday, 04 April 2007 - 4:26 PM Pak Time):
As per the meeting during Dr. Les Cottrell's Visit to Pakistan we decided on figuring out the best number of ping packets to be sent to each host to get best value of RTT. the scrip has been written and results are available at : http://maggie.niit.edu.pk/newwebsite/tulip/BestPingPakcetsNum.zip.
  • No curve or pattern as expected was observed. To make the number of pings report usable ideally one needs much more coverage and would also need to find the minimum ping ever. One probably has roughly the approximate "minimum ping ever" using the pingtable.pl results from the various monitors for say a recent month or 180 days. Then one needs to measure minimum ping RTTs as a function of number of pings for many pairs (i.e. the pingtable.pl pairs) as you have been doing and come up with some cumulative distribution statistics (#pairs within n% of the minimum ping ever) of difference in the min-RTT say 5, 10, 20, and infinite (minimum ping ever) pings. This may vary depending on monitoring site, region etc. This could be an analysis project in itself and could be worthy of publication if done well. It might be something you want to spin off to a student who is interested in analysis, since I think it is non trivial and worthy of some detailed effort.
  • Looking at the graphs of min_rtt vs # pings, they are pretty but we need to summarize them. What is interesting is whether and how much improvement we get by increasing the number of pings (and the dispersion in the "improvement"). Ideally the grpahs would look like the NIIT-LUMS graphs, i.e. an exponential fall off and by the time one gets to 5 pings there is little improvement in going to 4 times as many pings (20). However, things are not that simple in real life. For example if one looks at NIIT-GIKI then the improvement going 5 to 20 pings is about min_RTT = 125:20ms, however going to 19 pings there is no improvement min_RTT=125:235ms. Thus one also needs the scatter of the improvement. One might define the dispersion as the standard deviation (or inter-quartile range) of the improvement going imp(5:10), imp(5:11)... imp( 5:20) where the numbers are the number of pings and imp(5:15) is the improvement in the min_rtt comparing 5 with 15 pings. I suspect NIIT-MIT is more typical of the min_RTT vs # pings. I also suspect the plot shapes may depend on regions and congestion between NIIT (or the landmark) and the region and may also depend on the landmark. This will all need some thought on how to present/aggregate the results in a useful fashion.
  • (Wednesday, 04 April 2007 - 3:39 AM Pak Time):
Adding a new column to the configuration file that contains modified value of alpha. The stable version of the config file will be uploaded after debugging & testing.
  • (Thursday, 29 March 2007 - 2:20 AM Pak Time):
Implementation, testing, and analysis of results of the iterative location approach.

[edit] Applicability

  • 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 NIIT, Pakistan in collaboration with UWE, UK. Les has added this to the TULIP web page at SLAC.

[edit] Landmark Issues

[edit] Recent Research

April 2, 2008

North America

In North America there are about 52 speednet sites. In the two of our tests we used 80 landmarks across different North American regions, the first test using TULIP1 (With only PingER landmarks) and second using TULIP2 (using both PingER and Planetlab landmarks), upon comparison revealed obvious improvements. Our observation shows that Chicago_UnitedStates_PL is the most frequently used North American landmark. When PingER is used for comparison again Chicago_UnitedStates_PL is found to have highest frequency followed by NewYork_UnitedStates_PL having second highest frequency.

Detailed reports can be found here:

1) Excel Comparison Sheet & Landmark Frequency Analysis 2) PingER Results Comparison

Europe

Europe also has 52 speednet sites. When results of TULIP1 and TULIP2 were compared significant improvements were noticed. For the tests in Europe we have 8 PingER and 48 Planetlab landmarks.

Detail reports can be found here:

1)Initial test results & Excel Comparison Sheet

Interesting Observations

During the analysis, for a speednet site, an interesting observation is made. The initial test conducted on 2nd January, 2008 to locate ' www.g3pcs.com ' having IP address 208.109.181.237, the responding landmarks for triangulation were Eugene_UnitedStates_PL taking 12.5ms, Seattle_UnitedStates_PL 15.2ms and TRIUMF_Vancouver 19.1 ms. Speed database showed that the site was in Ephrata, WA (Latitude: 47.32 Longitude: -119.55), which despite of having some error distance made us believe results to be correct because Eugene, Seattle and Vancouver are close to Ephrata.

Later, on 4th March, 2008 new tests revealed three different sites responding with min RTT. They were SanDiego_UnitedStates_PL that took 13.337ms, LosAngeles_UnitedStates_PL 13.696ms and Riverside_UnitedStates_PL 14.342ms locating target somewhere in California State. This is quite interesting to notice as it makes us believe that the target site has moved between the first test and second test. GeoIpTool has been used to locate it and it showed this site to be present at Scottsdale, Arizonan (Latitude: 33.6 Longitude -111.89). A Planet Lab landmark is present in Phoenix, Arizona but it did not respond. If the Landmark near Phoenix had responded we have had obvious better results. Though a landmark in Tuscon, AZ responded with 23ms.

The observations mentioned lead us to conclude that this site: www.g3pcs.com, has moved between 2nd January, 2008 and 4th March, 2008. Hostip.info and geobytes.com says the host is in Brooklyn, NY which is obviously wrong. The whois information from (www.ip-lookup.net) suggests the site is in Scottsdale, AZ which we think is correct. Here is the whois information:


OrgName: GoDaddy.com, Inc. OrgID: GODAD Address: 14455 N Hayden Road Address: Suite 226 City: Scottsdale StateProv: AZ PostalCode: 85260 Country: US



  • DoE_HQ,Germantown_Maryland is no longer responding. The host is not responding to pings (Sunday, 08 April 2007 - 7:02 AM Pak Time). It is responding to pings from SLAC (Monday, 09 April 2007 - 8:52 AM Pacific Time).
  • Dublin,Ireland is no longer using Get method. Faran will write a script for getting result from landmarks using Post method (Sunday, 08 April 2007 - 6:40 AM Pak Time)
  • Ciudad_Juarez,Mexico is no longer responding. The host is not responding to pings (Sunday, 08 April 2007 - 6:35 AM Pak Time). Les sent email to them (Monday, 09 April 2007 - 8:52 AM Pacific Time). Should be working again (Wednesday, 11 April 2007).
  • UMichigan,AnnArbor_USA gate01.grid.umich.edu is no longer responding. The host is not responding to pings (Sunday, 08 April 2007 - 6:22 AM Pak Time). Les sent email to Shawn McKee, it has been fixed but needs a new URL http://gate01.aglt2.org/cgi-bin/traceroute.pl (Monday, 09 April 2007 - 8:52 AM Pacific Time).
  • Still awaiting response from Dr. Farooq & Dr. Hiroki Suguri for the Japan landmark. Faran will visit Dr. Farooq on Monday 09 April 2007 (Sunday, 08 April 2007 - 5:27 AM Pak Time)
Retrieved from "http://maggie2.niit.edu.pk/wiki/index.php/TULIP"
Personal tools