CapProbe a Simple and Accurate Capacity Estimation Technique

Rohit Kapoor, Ling-Jyh Chen, Alok Nandan, Mario Gerla, M. Y. Sanadidi

UCLA Computer Science Department, Los Angeles, CA 90095, USA

{rohitk, cclljj, alok, gerla, medy}@cs.ucla.edu

ABSTRACT

The problem of estimating the capacity of an Internet path is one of fundamental importance. Due to the multitude of potential applications, a large number of solutions have been proposed and evaluated. The proposed solutions so far have been successful in partially addressing the problem, but have suffered from being slow, obtrusive or inaccurate. In this work, we evaluate CapProbe, a low-cost and accurate end-to-end capacity estimation scheme that relies on packet dispersion techniques as well as end-to-end delays. The key observation that enabled the development of CapProbe is that both compression and expansion of packet pair dispersion are the result of queuing due to cross-traffic. By filtering out queuing effects from packet pair samples, CapProbe is able to estimate capacity accurately in most environments, with minimal processing and probing traffic overhead. In fact, the storage and processing requirements of CapProbe are orders of magnitude smaller than most of the previously proposed schemes. We tested CapProbe through simulation, Internet, Internet2 and wireless experiments. We found that CapProbe error percentage in capacity estimation was within 10% in almost all cases, and within 5% in most cases.

Categories and Subject Descriptors

C.4 [Performance of Systems]: Measurement Techniques, Modeling Techniques, and Performance Attributes.

General Terms

Algorithms, Measurement, Performance, Design.

Keywords

Capacity Estimation, Packet Pair, Delay, Dispersion.

1. INTRODUCTION

A fundamental problem in the area of computer network measurements is determining the capacity of an Internet path in an end-to-end, non-disruptive and accurate manner. The capacity of a path is defined as the minimum physical bandwidth of all links comprising the path. The link with the minimum physical bandwidth has been called the narrow link. Capacity is clearly different from the available bandwidth, which is the minimum of the unused capacities among the links of a path. While the capacity is fixed for a path, the available bandwidth is time varying. Our focus in this paper is on measuring the capacity of a

Copyright is held by the author/owner(s).

SIGMETRICS/Performance'04, June 12-16, 2004, New York, NY, USA. ACM 1-58113-6-1/04/0006.

path.

The aim of this work is to develop an end-to-end capacity estimation approach that relies only upon packet statistics obtained at connection end-points to generate accurate capacity estimates quickly and unobtrusively, both for wired and wireless links. Towards this end, we present in this paper CapProbe, an end-to-end capacity estimation approach that is simple, not based on heuristics, unobtrusive, quick and extremely accurate across a range of system parameters.

In this study, we performed simulations, Internet and Internet2 measurement results showing that CapProbe is accurate in almost all environments, yet exhibits the properties of being unobtrusive and quick. Compared with previously proposed schemes, CapProbe is orders of magnitude simpler, both in terms of processing overhead and the amount of traffic injected into the network. Another novelty with respect to previously proposed estimation schemes is the use of CapProbe in noisy wireless environments. Here again CapProbe estimates very fast and accurately.

2. Packet Pair Technique

The basic Packet Pair algorithm [4] relies on the fact that if two packets sent back-to-back are queued next to each other at the narrow link, they will exit the link with ”dispersion” T given by:

T = L / B,

where L is the size of the second packet, and B is the bandwidth of the narrow link.

If the two packets have the same size, their transmission delays are the same. This means that after the narrow link, a dispersion of T will be maintained between the packets even if faster links are traversed downstream of the narrow link. This is shown in Fig 1.

Figure 1:

The narrow link capacity can then be calculated as: B = L / T The Packet Pair algorithm assumes that the packets will queue next to each other at the narrow link. As we discuss in Section 3, the presence of cross-traffic can invalidate this assumption.

3. CapProbe

The proposed approach, CapProbe, employs and extends the packet pair technique. Previous researchers [2] have noted that capacity estimates resulting from packet pair dispersion can be inaccurate due to compression or expansion of dispersion induced by cross traffic. CapProbe relies on filtering such distortion using packet delays and is based on a simple and fundamental observation: Both compression and expansion of narrow link induced dispersion result from queuing of the packet pair due to cross traffic. CapProbe, thus, combines dispersion and delay measures to filter out packet pair samples “distorted” by cross-traffic.

More specifically, whenever an incorrect value of capacity is estimated, the sum of the delays of the packet pair packets, which we call the delay sum, includes cross-traffic induced queuing delay. This delay sum is clearly larger than the delay sum of a packet pair sample in which both packets do not suffer cross-traffic induced queuing. We refer to this delay sum, which does not include any cross-traffic queuing delay, as the minimum delay sum. The dispersion of such a packet pair sample is not distorted by cross-traffic and will reflect the correct capacity.

Thus, assuming that at least one packet pair sample goes through without cross-traffic interference, we get a sample that measures the correct capacity and the delay sum of whose packets is equal to the minimum delay sum. This sample can easily be identified since its delay sum will be the minimum among delay sums of all packet pair samples.

Using the above observation, we present a new capacity estimation technique, CapProbe, which is based on the association of increased queuing delay (resulting from cross-traffic) with capacity estimation errors as discussed earlier. CapProbe calculates the delay sum for all packet pair samples. The dispersion measured from the sample corresponding to the minimum of all these delay sums reflects the narrow link capacity!!

It is easy to see that CapProbe is extremely efficient in the use of resources. In fact, CapProbe needs to perform only one addition and one comparison operation per packet pair sample. Compared to some of the previous schemes, this represents an order of magnitude reduction in workload. The storage space required is also minimal. Only two values, the current minimum delay sum and its corresponding dispersion, need to be stored.

CapProbe is based on the assumption that at least one packet pair sample with the minimum delay sum is obtained. In a network such as the Internet in which the traffic intensity varies due to reactive TCP flows, there is very high likelihood of obtaining one or more of the desired samples. In fact, in our experiments, we found very few cases that are deprived of such samples. The cases in which these samples may not be obtained correspond to a highly congested (almost 100% congested), UDP-predominant (i.e., non-reactive) network.

4. Evaluation

We evaluated CapProbe using analysis, simulation, and Internet measurement methods. An analytic evaluation assuming Poisson

cross traffic was also performed to determine the expected number of samples required for accurate estimation. As it is difficult to analyze the case of long range dependent traffic, we used simulation experiments instead. A CapProbe testbed was created, and experiments on Internet, Internet2, and wireless links were carried out. From measurement results, we found CapProbe to be highly accurate in almost all cases. Specifically, the error percentage of CapProbe in capacity estimation was within 10% in almost all cases, and within 5% in most cases. CapProbe was also found to be accurate over wireless links.

5. CONCLUSIONS

The contribution of this work is the evaluation of CapProbe, a new technique to estimate the capacity of an Internet path. CapProbe is based on the simple and fundamental observation that a packet pair dispersion reflecting incorrect capacity always involves queuing of the packet pair. This technique combines packet pair dispersion and delay measurements resulting in a simple and accurate end-to-end method to estimate capacity. The strength of CapProbe is based on its simplicity (e.g., relative to other schemes such as pathchar [3], pathrate [1], packet tailgating [5]) and robustness. In fact, for an accurate estimate, it suffices that a single Packet Pair sample involving no cross-traffic induced queuing delay is obtained. Obtaining such a sample in today’s Internet, dominated by reactive (TCP) flows, is a practical certainty. Only extremely intense non-reactive cross-traffic can prevent the outcome of one such sample.

For the future, we are working towards enhancing the accuracy of CapProbe in the face of intensive CBR traffic. We are also looking at various applications of CapProbe in congestion and streaming control, and in overlay network optimization.

6. REFERENCES

[1] Dovrolis, C., Ramanathan, P., and Moore, D. Packet

dispersion techniques and capacity estimation submitted to IEEE/ACM Transactions of Networking. [2] Dovrolis, C., Ramanathan, P., and Moore, D. What do packet

dispersion techniques measure? In Proceedings of IEEE Infocom'01 (Anchorage, Alaska, April 22-26, 2001). IEEE, vol. 2, 22-26. [3] Jacobson, V. Pathchar: A tool to infer characteristics of

Internet paths, ftp://ftp.ee.lbl.gov/pathchar/ [4] Keshav, S. A control-theoretic approach to flow control. In

Proceedings of the SIGCOMM (SIGCOMM’91) (Zurich, Switzerland, Sept. 3-6, 1991). ACM Press, New York, NY, 1991, 3-15. [5] Lai, K., and Baker, M. Measuring Link Bandwidth Using a

Deterministic Model of Packet Delay, In Proceedings of the SIGCOMM (SIGCOMM’00) (Stockholm, Sweden, Aug. 28 – Sept. 01, 2000). ACM Press, New York, NY, 2000, 283-294.