We have developed a new end-to-end available-bandwidth measurement tool: FEAT (Fish-Eye Available-bandwidth Tool). FEAT features a new dynamic pattern of probes called a Fisheye Stream.  One fisheye stream covers a range of packet probing rates. A fisheye stream consists of a focus region, where the probing rates are sampled more frequently and the number of packets used at each rate is larger. This creates a fisheye effect that the focus region enables an easily identified "turning point" for accurate measurements. When the dynamic available bandwidth is outside the region, the surrounding regions enable the tool to automatically "refocus". Fisheye streams offer several advantages over current probing schemes that are based on packet pairs, packet trains, or packet chirps. FEAT is also fast, nearly non-intrusive, and clock resolution insensitive. Experiments show that FEAT provides accurate estimations of the available bandwidth with low overhead compared to the existing techniques.

What is a Fisheye Stream?

The fisheye-stream measurement can be analogized as a fish-eye magnifier, where objects in the middle are shown in great details while objects in the surroundings are visible but not in great details. A fisheye stream consists of K packets of equal size that are sent at a changing rate from L (the lower bound) to U (the upper bound). Inside this range, there is an area called a focus region, where the avi-bw to be measured is most likely to be in this range. Around the center, packet instantaneous-rate sampling is more frequent. The number of packets at each sampling rate is larger. Outside the focus region, the rate sampling is less frequent; however, it still covers the range from L to U.

Why use a Fisheye Stream?

There are few observations in our experimental studies:

(1) The long-term stability and predictability of the Internet: Some previous studies show that the available bandwidth of an Internet path usually shows a certain degree of constancy within a few minutes or even hours.

(2) The fisheye stream is based on observations that the smaller the sample intervals around the turning point, the more accurately we can find the turning point.

(3) Tthe larger the number of packets at the same rate around the turn point, the more quickly the queue will be built up.

MRTG Internet path validation

Testbed validations and ns-2 simulations could verify the idea of a tool. However, there is no better approach than using actual network paths. Similar to Spruce, we validate FEAT with the help of the MRTG tool on network paths. Although the 5-minute resolution of the MRTG data is low, the MRTG tool is so far the most accurate way to validate the output of an avi-bw tool.

MRTG validation requires accesses to MRTG log data from all links of a path and the capacity of each link. We have collected MRTG data from 100+ routers in Lehigh campus and downloaded the freely available Abilene network MRTG logs. We have applied the MRTG test to several paths that traverse the Lehigh campus network. Our ongoing tests include paths from Berkeley, U. Northwestern, U. Florida to Lehigh. The initial Internet test shows positive results. However, extensive Internet testing is still an ongoing work and we expect the result in next few months. Our Internet validation will test the relative error, absolute errors as well as the agility of the tools over these selected Internet paths.

Qiang Wang, Liang Cheng. FEAT: Improving Accuracy in End-to-end Available Bandwidth Measurement, In Proceedings of the 2006 IEEE Global Telecommunications Conference (GLOBECOM 2006), San Francisco, CA, Nov. 27 -Dec.1, 2006.

Pathload: C. Dovrolis, P. Ramanathan, and D. Moore, What do packet dispersion techniques measure? in Proc. of IEEE INFOCOM, pp. 905-914, 2001. M. Jain and C. Dovrolis, Pathload: a measurement tool for end-to-end available bandwidth, in Proc. of PAM, pp. 14-25, March 2002.

IGI: N. Hu and P. Steenkiste, Evaluation and characterization of available bandwidth probing techniques, IEEE JSAC, Vol. 21, No. 6, 2003.

PathChirp:  V. Ribeiro, R. Riedi, R. Baraniuk, J. Navratil, and L. Cottrell, pathChirp: efficient available bandwidth estimation for network paths, in Proc. of Passive and Active Measurement Workshop, April 2003.

Spruce: J. Strauss, D. Katabi, and F. Kaashoek, A measurement study of available bandwidth estimation tools, in Proc. of 2003 ACM SIGCOMM Conf. on Internet Measurement, pp. 39-44, Oct. 2003.

Netest: G. Jin and B. Tierney, Netest: a tool to measure the maximum burst size, available bandwidth and achievable throughput, LBNL report #48350. G. Jin and B. L. Tierney, System capability effects on algorithms for network bandwidth measurement, in Proc. of ACM IMW ¡°2001, pp. 27-38, 2001.

PATHMON: D. Kiwior, J. Kingston, and A. Spratt, PATHMON: a methodology for determining available bandwidth over an unknown network, in Proc. of IEEE Sarnoff 2004 Symposium, pp. 27-30, April 26-27, 2004.

TOPP: B. Melander, M. Bjrkman, and P. Gunningberg, A new end-to-end probing and analysis method for estimating bandwidth bottlenecks, in Proc. of IEEE Globecom, pp. 415-420, 2000.

MRTG: Multi router traffic grapher. T. Oetiker, MRTG: the multi router traffic grapher, in Proc. of the 12th Conference on Systems Administration (LISA¡¯98), pp. 141-148, 1998.

Y. Zhang, N.G. Duffield, V. Paxson, and S. Shenker, On the constancy of Internet path properties, in Proc. of ACM SIGCOMM Internet Measurement Workshop 2001, pp. 197-211, 2001.

Emulab: Network Simulation Testbed.

Sally Floyd¡¯s Tools For Bandwidth Estimation page.

Nettimer: A tool for measuring bottleneck link bandwidth.

SPAND: Shared Passive Network Performance Discovery Environment Aware Adaptation.

Remulac: Resource Management under Language and Application Control

Remos: Resource Monitoring for Network-Aware Applications