Check out the new USENIX Web site.

USENIX Home . About USENIX . Events . membership . Publications . Students
IMC '05, 2005 Internet Measurement Conference — Abstract

Pp. 173–186 of the Proceedings

Multi-Hop Probing Asymptotics in Available Bandwidth Estimation: Stochastic Analysis

Xiliang Liu, City University of New York; Kaliappa Ravindran, City College of New York; Dmitri Loguinov, Texas A&M University

Abstract

This paper analyzes the asymptotic behavior of packet-train probing over a multi-hop network path $ \mathcal{P}$carrying arbitrarily routed bursty cross-traffic flows. We examine the statistical mean of the packet-train output dispersions and its relationship to the input dispersion. We call this relationship the response curve of path $ \mathcal{P}$. We show that the real response curve $ \mathcal{Z}$is tightly lower-bounded by its multi-hop fluid counterpart $ \mathcal{F}$, obtained when every cross-traffic flow on $ \mathcal{P}$is hypothetically replaced with a constant-rate fluid flow of the same average intensity and routing pattern. The real curve $ \mathcal{Z}$asymptotically approaches its fluid counterpart $ \mathcal{F}$as probing packet size or packet train length increases. Most existing measurement techniques are based upon the single-hop fluid curve $ \mathcal{S}$associated with the bottleneck link in $ \mathcal{P}$. We note that the curve $ \mathcal{S}$coincides with $ \mathcal{F}$in a certain large-dispersion input range, but falls below $ \mathcal{F}$in the remaining small-dispersion input ranges. As an implication of these findings, we show that bursty cross-traffic in multi-hop paths causes negative bias (asymptotic underestimation) to most existing techniques. This bias can be mitigated by reducing the deviation of $ \mathcal{Z}$from $ \mathcal{S}$using large packet size or long packet-trains. However, the bias is not completely removable for the techniques that use the portion of $ \mathcal{S}$that falls below $ \mathcal{F}$.

  • View the full text of this paper in HTML and PDF.
    The Proceedings are published as a collective work, © 2005 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.

  • If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.

?Need help? Use our Contacts page.

Last changed: 24 Oct. 2005 rc
IMC '05 Tech Sessions
IMC '05 Home
USENIX home