Temporal Delay Tomography

Multicast-based network tomography enables inference of average loss rates and delay distributions of internal network links from end-to-end measurements of multicast probes. Recent work showed that this method, based on correlating observations of multicast receivers, also supports the inference of temporal loss characteristics of network links. In this paper, we show that temporal characteristics can, in fact, be estimated even for link delay processes. Knowledge of temporal delay characteristics has applications for delay sensitive services such as VoIP as well as for characterizing the queueing behavior of bottleneck links. By assuming mutually independent, but arbitrary link delay processes, we develop estimators which can infer, in addition to delay distributions, the probabilities of arbitrary patterns of delay, means and full distributions of delay-run periods at chosen delay levels, for each link in the multicast tree. By applying the recently proposed principle of subtree-partitioning, the estimator is made scalable to multicast trees of large degree. Estimation error and convergence rates are evaluated using simulations.