The Probe Gap Model can Underestimate theAvailable Bandwidth of Multihop PathsLi LaoGoogle Inc.Santa Monica, [email protected] DovrolisGeorgia TechAtlanta, [email protected]. SanadidiUCLALos Angeles, [email protected] Prob e Gap Model (PGM) was proposed as a lightweightand fast available bandwidth estimation method. Measure-ment tools such as Delphi and Spruce are based on PGM.Compared to estimation methods that require multiple iter-ations with different probing rates, PGM uses a single prob-ing rate and it infers the available bandwidth from a directrelation between the input and output rates of measurementpacket pairs. An imp ortant assumption behind the PGMmo del is that the measured path has a single bottlenecklink that determines the available bandwidth of the end-to-end path. In this letter, we show that, even though PGMis accurate in the case of a single queue, it cannot estimatethe available bandwidth of multi-hop paths, even if there isa single bottleneck in the path. Whether PGM is accurateor not depends on the routing of cross traffic relative to themeasurement traffic. PGM is accurate when the cross trafficfollows the same path with the measurement traffic. In thegeneral case, however, PGM can significantly underestimatethe available bandwidth of an end-to-end path.Categories and Subject DescriptorsC.2.3 [Computer-Communication Networks]: NetworkOp erations—Network MonitoringGeneral TermsPerformance, VerificationKeywordsNetwork capacity, available bandwidth, packet pair disper-sion, Probe Gap Model1. INTRODUCTIONThe problem of end-to-end available bandwidth estima-tion has received significant research interest [1, 2, 5, 6, 7,8, 10]. The available bandwidth of a link is defined as theaverage residual (or spare) capacity of that link. The linkwith the minimum available bandwidth in a network pathis called the tight link of the path, whereas the link withthe minimum capacity is called the narrow link. The end-to-end available bandwidth of a network path is equal to theavailable bandwidth of the tight link.Existing available bandwidth estimation techniques canb e grouped into two classes [3]. The first is the Probe RateModel (PRM), also known as Iterative Probing. In PRM,packet pairs (or packet trains) are sent at different rates,while the receiver observes the relation between the inputand output probing rates. When the output rate is lowerthan the input rate, the probing rate is higher than theavailable bandwidth. PRM tools can use this fact to “con-verge” into a range within which the available bandwidthvaries, adjusting the input probing rate.The second class is the Probe Gap Model (PGM), alsoknown as Direct Probing. In PGM, packet pairs (or packettrains) are sent to the path at a single rate. This probingrate is set to the capacity of the tight link, and so it is largerthan (or equal to) the available bandwidth of the path. Themain component of PGM is a mathematical relation b etweenthe input and output rates of a probing packet pair, undera fluid traffic model, based on which PGM tools such asDelphi [7] or Spruce [10] estimate the end-to-end availablebandwidth. Even though that relation has been derivedfor a single queue mo del, it has been claimed that PGM isalso accurate in multi-hop paths as long as there is a singlebottleneck [10].In this letter, we focus on the accuracy of the PGM method,and of Spruce in particular, in multi-hop paths. We showthat in general, even if there is a single b ottleneck in thepath, PGM tools provably underestimate the end-to-end avail-able bandwidth. Specifically, whether PGM is accurate or notdepends on the routing of cross traffic relative to the mea-surement traffic. PGM is accurate when the cross trafficfollows the same path with the measurement traffic. In thegeneral case, however, PGM can significantly underestimatethe available bandwidth of an end-to-end path.The rest of this letter is organized as follows. In Section 2,we provide some relevant background. Then, in Section 3,we evaluate the accuracy of PGM mathematically, first at asingle-hop path and then at a two-hop path. The analysisof the latter shows that PGM/Spruce are not accurate inthe general case. Simulation results confirm the analysis inSection 4. We conclude in Section 5.2. BACKGROUNDIn PGM, it is assumed that the tight link is the samewith the narrow link, referred simply as bottleneck. Fur-ther, PGM assumes that the capacity C of the bottleneckis known in advance. Spruce relies on probing packet pairs,but the PGM method could also be implemented with packettrains.1PGM is based on the relationship b etween the in-1The duration of the packet trains (determined by the num-ber and size of the probing packets in the train) correspondsto the averaging timescale over which the available band-width is defined. The variance of the available bandwidthterarrival (also referred to as dispersion) of probing packetsat the input and output of the measured path. Specifically,if the size of the probing packets is L and the packet pairis sent to the path at the rate of the bottleneck capacityC, the input dispersion of the packet pair is ∆in= L/C.According to PGM and Spruce, the available bandwidth Acan be estimated from the measured dispersion ∆outof thepacket pair at the receiver, as follows:ASpruce= C1 −∆out− ∆in∆in(1)In the next section, we show that this is equal to the avail-able bandwidth, under a fluid traffic model, of a single-queue. We also show, however, that ASprucecan be lessthan the available bandwidth of a multi-hop path, even ifthere is a single bottleneck.PRM also assumes a single tight link, but it does notpresume knowledge of that link’s capacity, and it do es notassume that the narrow link is the same with the tight link.Instead, it relies on iterative probing at various rates basedon the following simple observation. When the probing rateis higher than the available bandwidth, the tight link be-comes saturated and a queue builds up. The receiver candetect that the tight link is saturated because the delays ofsuccessive probing packets increase, or equivalently, becausethe probing rate at the receiver is less than the probing rateat the sender. The receiver can then estimate the avail-able bandwidth as the minimum probing rate that does notsaturate the tight link. Tools such as TOPP [6], Pathload[2], PathChirp [8], IGI and PTR [1] are all based on varia-tions of PRM. We clarify that the PRM