Stochastic analysis of packet-pair probing for network bandwidth estimation

In this paper, we perform a stochastic analysis of the packet-pair technique, which is a widely used method for estimating the network bandwidth in an end-to-end manner. There has been no explicit delay model of the packet-pair technique primarily because the stochastic behavior of a packet pair has not been fully understood. Our analysis is based on a novel insight that the transient analysis of the G/D/1 system can accurately describe the behavior of a packet pair, providing an explicit stochastic model. We first investigate a single-hop case and derive an analytical relationship between the input and the output probing gaps of a packet pair. Using this single-hop model, we provide a multi-hop model under an assumption of a single tight link. Our model shows the following two important features of the packet-pair technique: (i) The difference between the proposed model and the previous fluid model becomes significant when the input probing gap is around the characteristic value. (ii) The available bandwidth of any link after the tight link is not observable. We verify our model via ns-2 simulations and empirical results. We give a discussion on recent packet-pair models in relation to the proposed model and show that most of them can be regarded as special cases of the proposed model.