From Attila.Pasztor@ericsson.com Wed Dec 24 13:37:03 2003 Date: Wed, 15 Oct 2003 09:44:07 +0200 From: Attila Pasztor To: dovrolis@cc.gatech.edu Cc: d.veitch , Peter Haga Subject: BEst 2003 - Abstract: On Evaluating a New Class of Available Bandwidth Methods Title: On Evaluating a New Class of Available Bandwidth Methods Authors: Attila Pasztor, Darryl Veitch, Peter Haga Over the past few years a number of new available bandwidth estimation methods have been introduced which fit neither into the packet-pair category relying on the spacing effect of bottlenecks, nor into the category of "pathchar-like" one-packet based methods. Estimation methods of Melander et.al (TOPP) [1], Dovrolis et.al (SLoPS) [2] and Ribeiro et.al (pathChirp) [3] are examples in this new class. The link connecting these methods is their reliance on the interaction of probe and cross traffic, rather than relying purely on underlying network effects. Their approach is similar to Delphi's (Ribeiro et.al) [4] probing principle: they are based on sending packet trains with controlled inter-packet spacing. However the principles of the analysis performed, allowing estimates of available bandwidth independently (in most cases) from the knowledge of the bottleneck link rate, make them fundamentally different from the packet train based methods relying on the spacing effect. This is demonstrated by the fact that they are able to produce accurate results even in situations when a highly loaded high capacity link follows lightly loaded low capacity links, where the previously mentioned methods fail because of their assumption that the bottleneck link is the one limiting the available bandwidth. In the Ph.D. thesis "Accurate Active Measurement in the Internet and its Applications" [5] we proposed two new probe patterns, the chirp and the smoothed chirp (schirp), and a novel filtering approach to be used for available bandwidth estimation. Together they constitute a new member of this `interaction' class of methods. Currently we are working on comparing the methods in the interaction class, and developing our own further. We perform comparisons in simulations using traces of traffic collected from real networks as background traffic, which we modify in controlled ways. This approach has advantages in that many of the real complexities of traffic are preserved, however, given the spatio-temporal nature of the information carried by probes, and the difficulties in definition of `available bandwidth', a more controlled simulation methodology is also required. For the simulation of communication network protocols typically discrete event based simulation techniques are applied, as for example in the de facto standard TCP/IP simulation tool NS - The Network Simulator. This tool was used for example in the TCP based bandwidth measurement experiments of Lai and Baker. In this approach, simulation is used to emulate a real network including the functionality of network protocols. However our simulation requirements are somewhat different, less ambitious, but better suited to active probing where the focus is on what probes experience, and where the performance of methods is required to be insensitive to the nature of the cross-traffic. We developed a light-weight simulation package, "psim" [5], to help us efficiently investigate the main characteristics of the multiple hop network model [6]. Physically this model consists of a set of hops in series, a hop being a FIFO queue followed by a transmission link. The main task of such a tool is to generate detailed information corresponding to what would occur during an active probing experiment- both the observable, and the unobservable aspects. The inputs are the route configuration, the cross traffic entering the probed path at different hops, with adjustable TTL allowing cross traffic packets to leave the route at any downstream hop, and the probe stream injected into the network. The main output are the probe arrival times to the receiver at the end of the route. There is no need for routing and transport protocol simulation, the required outputs can be calculated exactly and rapidly using the recursion relations of queueing theory. Psim uses the same probe stream definition input format as our active probing senders, and produces the outputs compatible with those of our active probing monitors, allowing us to use the same analysis tools to process both simulation and real experimental results. Furthermore it supports the use of cross traffic traces collected from real networks as background traffic. A key capability of the simulator is that it provides (extensible) output statistics from each hop of the route, as if we were experimenting on a fully instrumented route, with monitors available at each hop. Thus the performance of methods can be tracked in great detail, instead of points of failure remaining essentially unknown. For example, we can use it to examine exactly when, on a probe by probe basis, the interaction of the cross traffic and probe obeys the assumptions of a given method (such as being in the same busy period at a given hop, but at no other), and when it doesn't, and why. In our presentation we will present the simulation and comparison methodology, as well as report preliminary results comparing methods in the interaction class. References: [1] B. Melander M. Bjorkman P. Gunningberg, "A new end-to-end probing and analysis method for estimating bandwidth bottlenecks," in Proc. GLOBECOM'00, San Francisco, Nov 2000. [2] M. Jain and C. Dovrolis, "End-to-end available bandwidth: measurement methodology, dynamics and relation with TCP throughput," in Proceedings of the 2002 ACM SIGCOMM conference, Pittsburgh, PA, August 2002, pp. 295-308. [3] V.Ribeiro, R.Riedi, R.Baraniuk, J.Navratil and Les Cottrell, "pathChirp: Efficient Available Bandwidth Estimation for Network Paths", Passive and Active Measurement Workshop 2003 [4] V. Ribeiro, M. Coates, R. Riedi, S. Sarvotham, B. Hendricks, and R. Baraniuk, "Multifractal crosstraffic estimation," in Proc. ITC Specialist Seminar, Monterey, USA, 2000. [5] Attila P'asztor, "Accurate Active Measurement in the Internet and its Applications" , Ph.D. thesis, The University of Melbourne, 2003, http://www.cubinlab.ee.mu.oz.au/~attila/pub/PhDfinal.pdf [6] Attila P'asztor and Darryl Veitch, "On the Scope of End-to-End Probing Methods," IEEE Communications Letters, vol. 6, no. 11, pp. 509-511, 2002.