The first complete system that is aimed at predicting Internet distance is
called IDMaps. IDMaps is
an infrastructural service in which special HOPS servers maintain a
virtual topology map of the Internet consisting of end hosts and
special hosts called Tracers. This virtual topology map is used to
predict Internet distance. For example, the distance between hosts A
and B is estimated as the distance between A and its nearest Tracer
T1, plus the distance between B and its nearest Tracer T2, plus the
shortest path distance from T1 to T2 over the Tracer virtual
topology. As the number of Tracers grow, the prediction accuracy of
IDMaps tends to improve. Designed as a client-server architecture
solution, end hosts can query HOPS servers to obtain network distance
predictions. An experimental IDMaps system has been deployed. Below
we highlight some key differences between IDMaps and GNP.
Client-server vs peer-to-peer architecture: GNP can be easily
integrated with peer-to-peer applications because GNP coordinates are
compact and can be distributedly computed and maintained by individual
end hosts. Distance computations are also easily handled by individual
end hosts. Compared with client-server based solutions, peer-to-peer
systems have potential advantages in scaling. Since there is no need
for shared servers, potential performance bottlenecks are eliminated,
especially when the system size scales up. Performance may also
improve as there is no need to endure the latency of communicating
with remote servers.
Prediction algorithm differences: In our Internet experiments,
we have found that GNP is much more accurate than IDMaps when a
light-weight infrastructure is deployed. The difference is actually
easy to explain. Consider the example below.
X and Y are infrastructure nodes, and A and B are two end hosts that
are very nearby. IDMaps' prediction method will give a pessimistic
distance prediction of (A,X)+(B,Y)+(X,Y). In contrast, with a
one-dimensional model, GNP will be able to perfectly predict the
distance between A and B. GNP performs better because it exploits the
relationships between the positions of Landmarks and end hosts rather
than depending on the exact topological locations of the
infrastructure nodes, thus it is highly accurate and robust.
Structured representation: The geometric coordinates of hosts
generated by GNP describe a simple and yet highly structured
representation of the complex Internet topology. Many algorithms can
then take advantage of this structure to perform topologically aware
operations on the Internet in a scalable fashion.
Back to GNP Home
