IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 11, NO. 4, AUGUST 2003 537End-to-End Available Bandwidth: MeasurementMethodology, Dynamics, and RelationWith TCP ThroughputManish Jain and Constantinos Dovrolis, Member, IEEEAbstract—The available bandwidth (avail-bw) in a networkpath is of major importance in congestion control, streamingapplications, quality-of-service verification, server selection, andoverlay networks. We describe an end-to-end methodology, calledself-loading periodic streams (SLoPS), for measuring avail-bw.The basic idea in SLoPS is that the one-way delays of a periodicpacket stream show an increasing trend when the stream’s rateis higher than the avail-bw. We implemented SLoPS in a toolcalled pathload. The accuracy of the tool has been evaluatedwith both simulations and experiments over real-world Internetpaths. Pathload is nonintrusive, meaning that it does not causesignificant increases in the network utilization, delays, or losses.We used pathload to evaluate the variability (“dynamics”) of theavail-bw in internet paths. The avail-bw becomes significantlymore variable in heavily utilized paths, as well as in paths withlimited capacity (probably due to a lower degree of statisticalmultiplexing). We finally examine the relation between avail-bwand TCP throughput. A persistent TCP connection can be usedto roughly measure the avail-bw in a path, but TCP saturates thepath and increases significantly the path delays and jitter.Index Terms—Active probing, bottleneck bandwidth, bulktransfer capacity, network capacity, packet pair dispersion.I. INTRODUCTIONTHE CONCEPT of available bandwidth (avail-bw) hasbeen of central importance throughout the history ofpacket networks, in both research and practice. In the context oftransport protocols, the robust and efficient use of avail-bw hasalways been a major issue, including Jacobson’s TCP [9]. Theavail-bw is also a crucial parameter in capacity provisioning,routing and traffic engineering, quality-of-service (QoS) man-agement, streaming applications, server selection, and severalother areas.Researchers have been trying to create end-to-end measure-ment algorithms for avail-bw over the last 15 years. From Ke-shav’s packet pair [15] to Carter and Crovella’s cprobe [6],the objective was to measure end-to-end avail-bw accurately,quickly, and without affecting the traffic in the path, i.e., non-intrusively. What makes the measurement of avail-bw difficultManuscript received October 21, 2002; approved by IEEE/ACMTRANSACTIONS ON NETWORKING Editor J. Rexford. This work was supportedby the Scientific Discovery through Advanced Computing (SciDAC) Programof the Department of Energy under Award DE-FC02-01ER25467. This paperwas presented in part at the ACM SIGCOMM Conference, Pittsburgh, PA,August 2002.The authors are with the College of Computing, Georgia Instituteof Technology, Atlanta, GA 30332 USA (e-mail: [email protected];[email protected]).Digital Object Identifier 10.1109/TNET.2003.815304is, first, that there is no consensus on how to precisely define it,second, that it varies with time, and third, that it exhibits highvariability in a wide range of timescales.A. DefinitionsWe next definetheavail-bw in an intuitive butprecisemanner.The definition does not depend on higher level issues, such asthe transport protocol or the number of flows that can capturethe avail-bw in a path.A network pathis a sequence of store-and-forward linksthat transfer packets from a senderto a receiver .Weassume that the path is fixed and unique, i.e., no routing changesor multipath forwarding occur during the measurements. Eachlinkcan transmit data with a rate bits per second, whichis referred to as link capacity. Two throughput metrics that arecommonly associated withare the end-to-end capacity andavailable bandwidth. The capacity is defined as(1)and it is the maximum rate that the path can provide to a flow,when there is no other traffic in.Suppose that linktransmitted bits duringa time interval. The term , or simply, is the average utilization of link during ,with. Intuitively, the avail-bw of linkin can be definedasthefractionofthelink’s capacitythat has not been utilized during that interval, i.e.,(2)Extending this concept to the entire path, the end-to-endavail-bwduring is the minimum avail-bwamong all links in(3)Thus, the end-to-end avail-bw is defined as the maximum ratethat the path can provide to a flow, without reducing the rate ofthe rest of the traffic in.To avoid the term bottleneck link, which has been widely usedin the context of both capacity and avail-bw, we introduce twonew terms. The narrow link is the link with the minimum ca-pacity, and it determines the capacity of the path. The tight linkis the link with the minimum avail-bw, and it determines theavail-bw of the path.The parameterin (3) is the avail-bw averaging timescale.Ifwe consideras a stationary random process, the variance1063-6692/03$17.00 © 2003 IEEE538 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 11, NO. 4, AUGUST 2003of the process decreases as the averaging timescaleincreases. We note that if is self-similar, the variancedecreases slowly, in the sense that the decrease ofas increases is slower than the reciprocal of [19].B. Main ContributionsIn this paper, we present an original end-to-end avail-bwmeasurement methodology, called self-loading periodicstreams (SLoPS). The basic idea in SLoPS is that the one-waydelays of a periodic packet stream show an increasing trendwhen the stream’s rate is higher than the avail-bw. SLoPS hasbeen implemented in a measurement tool called pathload. Thetool has been verified experimentally, by comparing its resultswith MRTG utilization graphs for the path links [25]. Wehave also evaluated pathload in a controlled and reproducibleenvironment using NS simulations. The simulations show thatpathload reports a range that includes the average avail-bwin a wide range of load conditions and path configurations.The tool underestimates the avail-bw, however, when thepath includes several tight links. The pathload measurementsare nonintrusive, meaning that they do not cause significantincreases in the network utilization, delays, or losses. Pathloadis described in detail in [12]; here we describe the tool’s salientfeatures and show a few experimental and simulation results toevaluate the tool’s accuracy.An important feature of pathload is that, instead of reporting asingle figure for the average avail-bw in a time