Shahryar Khan and Les Cottrell
Purpose
<span style="color: #000000">The purpose of this study is to investigate the effectiveness of tiering</span> for TULIP
(i.e we have a set of primary landmarks tier0 which will narrow down the target location to being in a particular region*[1] and then a denser set of secondary tier1 landmarks in the discovered region that can be used to get more accurate results). The use of tiering should enable us to reduce the network traffic (number of landmarks pinging a target) while retaining the accuracy of using all landmarks.
Currently we are looking into two regions where we hope to use tiering, i.e. North America and Europe. The choice of these two regions is since we have a relatively large number of landmarks in these regions. Landmarks in all other regions will be considered as tier0. Thus TULIP will try and locate targets in two passes. The first just uses tier0 landmarks. If the target then appears to be in North America or Europe, then a second pass is made using all the landmarks in that region, otherwise the target is determined from the first pass. The purpose of the current study is to determine whether tiering is effective and how it should be used.
North America
We selected 4 landmarks in North America for our study( SLAC, BNL, Ampath-Florida,TRIUMF-Canada). They were chosen to be reliable and to roughly be located close to the 4 corners of the region. We pinged a set of known geographical target sites in the US, Canada and Mexico. The coordinates of the sites were obtained from the PingER database. We also calculated the physical distances between the target sites and the landmarks. The figure below shows the distribution. It appeared that all hosts were within 80ms of one another of the 4 monitors and 98.84% are within 70ms.
Here are graphs of data seen from four landmarks
As we can see from the first graph that some sites are replicated (e.g. DNS root name servers, Yahoo) and we ignore them in our results. It is also seen that some values for Mexico are aberrant for example min rtt >200 for a Mexican site from Florida. So it is a good idea not to include Mexico in this region. This region will therefore comprise of Canada and US only.
The above graph shows how alpha varies with distance. Using a single alpha may fail for small RTTs (distances). This is probably since the min_RTT is dependent on router delays and where networks peer, so the routes may be very different from the Great Circle Distance (GCD), and the min_RTT may be only partially dependent on distance.
Looking at the graph above of Alpha vs min_RTT from SLAC it appears there are two regimes separated at ~8ms. Above 8ms alpha is ~ 50km/ms, below it is more variable closer to ~10km/ms
We also calculated median alpha from SLAC which is ~ 46.5km/ms and IQR ~15.6km/ms or IQR/Median~ 33% or ~ +-16%
Faran uses the maximum alpha value in order to avoid underestimation which is ~ 62.98 km/ms in our case. Also Faran calculates alpha based on PingER historical data to all the world regions and in this study we only used the North American PingER sites.
Europe
Conclusion
|
References
[1] A region may be different then a geographical region