**A Stochastic Model for Topology Discovery of Tree Networks**

**Y. Azzana, INRIA Rocquencourt**
**Abstract:**

A model describing the discovery by means of traceroute of the topology an Internet access
network with a tree structure is proposed in this study. This model allows us to assess
the efficiency of traceroute procedures to determine the complete set of routers of the
network. Under some stochastic assumptions, explicit analytical expressions are obtained
for the mean number of routers discovered when a subset of the stations is used in the
traceroute procedure. Several tree architectures are then discussed when the total number
of routers gets large, and asymptotic expansions are derived. The results are compared
with real data obtained from measurements.