CapProbe: A Simple and Accurate Capacity Estimation Technique

CapProbe: A Simple and Accurate Capacity Estimation Technique

Rohit Kapoor, Ling-Jyh Chen, Li Lao, Mario Gerla, M. Y. Sanadidi

SIGCOMM 2004

Summary:

Active capacity estimation techniques have previously been derived from one of two measurements: overall delay of packet probes, or dispersion (i.e., the separation imposed upon two packets by a narrow link) of packet probes. CapProbe combines the two methods in a novel manner: packet dispersion measurements provide the basis for capacity calculations, while delay measurements are used to filter out inaccurate estimations. Dispersion measurements can support accurate capacity estimations only insofar as packets do not suffer from cross-traffic interference, which can occur in one of two ways:

· cross-traffic packets delay the first of a pair of probes after it has crossed a narrow link, thus reducing measured dispersal times and producing capacity over-estimations

· cross-traffic packets delay the second of a pair of probes anywhere during the procedure, thus expanding the measured dispersal times and producing capacity under-estimations

For this reason, the CapProbe algorithm performs a number of probe measurements (between 40 and 100), using overall delay times to filter out inaccurate samples which have obviously incurred some sort of cross-traffic delay.

To reduce the probability of cross-traffic delay, probe packets should be as small as possible; however, packets which are too small may result in inaccurate measurements due to operating system clock granularity issues. As well, samples that do not satisfy the minimum delay sum condition, which states that the minimum aggregate delay of a probe sample should equal the minimum sum of the two smallest individual probe delays, are filtered out.

CapProbe’s probability for convergence on an accurate capacity estimation was determined for a number of topology models both analytically and experimentally. For all models, it was found that CapProbe is most effective when cross-traffic packet sizes are large. In particular, 40 byte packets (common as TCP Acks) and unmanaged UDP flows can severely decrease the performance of CapProbe by causing cross-traffic delays.

Finally, CapProbe was compared to alternative active capacity estimation techniques such as pathrate and pathchar. Pathrate, which is much closer to CapProbe in nature, produced approximately similar results but often took orders of magnitude units of time more than did CapProbe.

Discussion:

· CapProbe estimations can be applied explicitly in overlay systems, or could potentially be used to provide general ‘underlay’ service to all high level systems

· CapProbe could undermine its own success: By allowing applications (for example overlay systems) to make use of high proportions of available bandwidth (a good thing), CapProbe’s efficiency/accuracy will decrease as the likelihood of cross-traffic induced delays will increase

· CapProbe performance high enough that it could be used in dynamic, on-line ways

· CapProbe measures the capacity of the narrowest link in a route—this will often be the ‘last mile’ hop, as it was in the presented experimental data; the utility of ‘last mile’ characteristics may not be as high as the utility of arbitrary link characteristics

· The paper does not mention how exactly network synchronization was effected for the measurement of overall delays (although these overall delay measurements need be only consistent relative to each other, as their actual accuracy has no impact on capacity calculations)

· The paper mentions problems in accurately measuring dispersion with small probe packet sizes, citing operating system granularity issues, but does not explicate the matter