| This thesis presents a theoretical foundation for packet-train available bandwidth estimation in its most general settings. In the first half of our work, we analyze the asymptotic behavior of packet-train probing in a single-hop network path carrying bursty cross-traffic. We examine the asymptotic average of the packet-train output dispersions and its relationship to the input dispersion. We call this relationship the response curve of the network path. We show that the real response curve is provably different from that obtained under fluid cross-traffic models in prior work. This difference, which we refer to as response deviation, is one of the previously unknown factors that can cause measurement bias in available bandwidth estimation. We show both analytically and experimentally that the response deviation and its consequent measurement bias vanish as the packet-train length or probing packet size increases and that the vanishing rate is decided by the burstiness of cross-traffic.; In the second part of this thesis, we analyze the asymptotic behavior of packet-train probing over a multi-hop network path P carrying arbitrarily routed bursty cross-traffic flows. We show that the response curve Z is tightly lower-bounded by its multi-hop fluid counterpart F , obtained when every cross-traffic flow on P is hypothetically replaced with a constant-rate fluid traffic flow of the same average intensity and routing pattern. The real curve Z asymptotically approaches its fluid counterpart F as probing packet size or packet train length increases. As an implication of these findings, we show that bursty cross-traffic in multi-hop paths causes negative bias to most existing techniques. This bias can be mitigated using long packet-trains. However, the bias is not completely removable for the techniques that use the portion of the single-hop fluid model that differs from F .; Through our probing analysis, we have achieved a clear understanding of both the validity and the inadequacy of current techniques, and provided a guideline for their further improvements. |
