STOCHASTIC MODEL FOR THE NUMBER OF TRAVERSED ROUTERS IN INTERNET
Piet Van Mieghem, Gerard Hooghiemstra and Remco van der Hofstad
Delft University of Technology, Information Technology and Systems
In a recent paper [1], we have proposed a model for the number of
traversed routers on the shortest path, further called in short 'the
hopcount', between two arbitrarily chosen sites of the Internet. The
resulting probability distribution for the hopcount in Internet is derived
from a random graph with size N (the unknown total number of routers) and
probability of a link between two nodes (routers) equal to p, such that Np
is a constant of the same order as the degree of a given router (the
average number of outgoing interfaces of a router). A statistical analysis
of the this model for the shortest path showed a remarkable good fit as
also is demonstrated in a companion paper [2].
The remarkable agreement with Internet measurements is surprising, not
because the model would be speculative, but, because it suggests a
desirable additional property of the hopcount in Internet, namely, almost
sure behaviour.
There are two different approaches to compute the probability
distribution function (pdf) of the hopcount of a path from A to B. Either
we fix the topology and vary the source and destination over all possible
couples or we choose a particular source and destination and let the
topology change over all possible graphs. The first approach suffers from
the fact that the paths are not independent because of overlap. Since the
influence of the correlation structure of this overlap on the hopcount is
a priori difficult to estimate, in simulations and computation, the second
approach had been followed.
However, the experimental trace-route measurements are all performed
on one fixed graph (the Internet graph) starting from one source (at Delft
University of Technology) to a finite number of randomly chosen
destinations (about 200). Hence to verify these measurements one should
fix *one* random graph of the class G_{p}(N), equip the links of this
graph with uniform or exponential weights and then choose one node as
source and (randomly) k destination nodes.
We will show in this contribution, with the help of the ergodic
theorem for stationary sequences, that the frequency of the hopcount from
our measurements can indeed be well approximated by the probabilities in
the random graph model proposed in [1]. Thus, we demonstrate the
applicability of that model in [1] to the Internet by illustrating that
the distribution possesses the remarkable property of almost sure
behaviour, which means that it features a high degree of robustness.
- P. Van Mieghem, G, Hooghiemstra and R. van der Hofstad, "A Scaling
Law for the hopcount in Internet",
http://wwwtvs.et.tudelft.nl/people/piet/telconference.html Submitted to
IEEE Transactions on Networking.
- F. Begtasevic and P. Van Mieghem, "Measurements of the Hopcount in
Internet", submitted to PAM2001.
|
