Packet-Pair Bandwidth Estimation: StochasticAnalysis of a Single Congested Node1Seong-ryong Kang,2Xiliang Liu,1Min Dai, and1Dmitri Loguinov1Texas A&M University, College Station, TX 77843, USA{skang, dmitri}@cs.tamu.edu, [email protected] University of New York, New York, NY 10016, [email protected]—In this paper, we examine the problem of estimatingthe capacity of bottleneck links and available bandwidth of end-to-end paths under non-negligible cross-traffic conditions. Wepresent a simple stochastic analysis of the problem in the contextof a single congested node and derive several results that allow theconstruction of asymptotically-accurate bandwidth estimators.We first develop a generic queuing model of an Internet routerand solve the estimation problem assuming renewal cross-trafficat the bottleneck link. Noticing that the renewal assumption onInternet flows is too strong, we investigate an alternative filteringsolution that asymptotically converges to the desired values ofthe bottleneck capacity and available bandwidth under arbitrary(including non-stationary) cross-traffic. This is one of the firstmethods that simultaneously estimates both types of bandwidthand is provably accurate. We finish the paper by discussing theimpossibility of a similar estimator for paths with two or morecongested routers.I. INTRODUCTIONBandwidth estimation has recently become an importantand mature area of Internet research [1], [2], [4], [5], [6],[7], [10], [11], [12], [14], [15], [16], [18], [19], [20], [21],[22], [23], [24], [25], [26], [27]. A typical goal of thesestudies is to understand the characteristics of Internet pathsand those of cross-traffic through a variety of end-to-endand/or router-assisted measurements. The proposed techniquesusually fall into two categories – those that estimate thebottleneck bandwidth [4], [5], [6], [12], [13] and those thatdeal with the available bandwidth [11], [19], [24], [26]. Recallthat the former bandwidth metric refers to the capacity of theslowest link of the path, while the latter is generally definedas the smallest average unused bandwidth among the routersof an end-to-end path.The majority of existing bottleneck-bandwidth estimationmethods are justified assuming no cross-traffic along the pathand are usually examined in simulations/experiments to showthat they can work under realistic network conditions [4],[5], [6], [7], [12]. With available bandwidth estimation, cross-traffic is essential and is usually taken into account in theanalysis; however, such analysis predominantly assumes a fluidmodel for all flows and implicitly requires that such models beaccurate in non-fluid cases. Simulations/experiments are againused to verify that the proposed methods are capable of dealingwith bursty conditions of real Internet cross-traffic [11], [19],[24], [26].To understand some of the reasons for the lack of stochas-tic modeling in this field, this paper studies a single-nodebandwidth measurement problem and derives a closed-formestimator for both capacity C and available bandwidth A =C − ¯r, where ¯r is the average rate of cross-traffic at the link.For an arbitrary cross-traffic arrival process r(t), we define¯r as the asymptotic time-average of r(t) and assume that itexists and is finite:¯r = limt→∞1ttZ0r(u)du < ∞. (1)Notice that the existence of (1) does not require stationarityof cross-traffic, nor does it impose any restrictions on the ar-rival of individual packets to the router. While other definitionsof available bandwidth A and the average cross-traffic rate ¯rare possible, we find that (1) serves our purpose well as itprovides a clean and mathematically tractable metric.The first half of the paper deals with bandwidth estimationunder i.i.d. renewal cross-traffic and the analysis of packet-pair/train methods. We first show that under certain conditionsand even the simplest i.i.d. cross-traffic, histogram-basedmethods commonly used in prior work (e.g., [5]) can be misledinto producing inaccurate estimates of C. We overcome thislimitation by developing an asymptotically accurate model forC; however, since this approach eventually requires ergodicityof cross-traffic, we later build another model that imposesmore restriction on the sampling process (using PASTA prin-ciples suggested in [26]), but allows cross-traffic to exhibitarbitrary characteristics.Unlike previous studies [26], we prove that the correspond-ing PASTA-based estimators converge to the correct values andshow that they can be used to simultaneously measure capacityC and available bandwidth A. To our knowledge, this is thefirst estimator that measures both C and A without congestingthe link, assumes non-negligible, non-fluid cross-traffic in thederivations, and applies to non-stationary r(t). Note that whilethis estimator can measure A over multiple links, its inherentpurpose is not to become another measurement tool or to workover multi-node paths, but rather to understand the associatedstochastic models and disseminate the knowledge obtained inthe process of writing this paper.We conclude the paper by discussing the impossibilityof building an asymptotically optimal estimator of both Cand A for a two-node case. While estimation of A maybe possible for multi-node paths, our results suggest thatprovably-convergent estimators of C do not exist in the contextof end-to-end measurement. Thus, the problem of deriving aprovably accurate estimator for a two-node case with arbitrarycross-traffic remains open; however, we hope that our initialwork in this direction will stimulate additional research andprompt others to prove/disprove this conjecture.II. STOCHASTIC QUEUING MODELIn this section, we build a simple model of a router thatintroduces random delay noise into the measurements of thereceiver and use it to study the performance of packet-pairbandwidth-sampling techniques. Note that we depart from thecommon assumption of negligible and/or fluid cross-traffic andspecifically aim to understand the effects of random queuingdelays on the bandwidth sampling process. First consider anunloaded router with no cross-traffic. The packet-pair mecha-nism is based on an observation that if two packets arrive at thebottleneck link with spacing x smaller than the transmissiondelay ∆ of the second packet over the link, their spacing afterthe link will be exactly ∆. In practice, however, packets fromother flows often queue between the two probe packets andincrease their