A Queueing-Theoretic Foundation of Available Bandwidth Estimation: Single-Hop Analysis

Most existing available-bandwidth measurement techniques are justified using a constant-rate fluid cross-traffic model. To achieve a better understanding of the performance of current bandwidth measurement techniques in general traffic conditions, this paper presents a queueing-theoretic foundation of single-hop packet-train bandwidth estimation under bursty arrivals of discrete cross-traffic packets. We analyze the statistical mean of the packet-train output dispersion and its mathematical relationship to the input dispersion, which we call the probing-response curve. This analysis allows us to prove that the single-hop response curve in bursty cross-traffic deviates from that obtained under fluid cross traffic of the same average intensity and to demonstrate that this may lead to significant measurement bias in certain estimation techniques based on fluid models. We conclude the paper by showing, both analytically and experimentally, that the response-curve deviation vanishes as the packet-train length or probing packet size increases, where the vanishing rate is decided by the burstiness of cross-traffic.