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.

1. 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.
2. F. Begtasevic and P. Van Mieghem, "Measurements of the Hopcount in Internet", submitted to PAM2001.