This page contains some references, both theoretical and experimental using real traffic, on the application and evaluation of large deviation techniques, and in particular the many sources asymptotic and its related effective bandwidth definition, for traffic engineering in broadband networks.
It also describes and makes available the programs (executables) used for obtaining the results published in [CSS99, CSS98]. A description of the methods and usage of the tools is available in [CS00b,CS99].
Also available is an interface providing Web-based access to the tools.[CS00]
E-mail suggestions to vsiris "at" ics "dot" forth "dot" gr
Analysis of traffic measurements has shown that a large variety of traffic types exhibit a self-similar or fractal behavior. Such behavior can have implications on the performance of a link that mulitplexes such traffic. Hence, there is a need to understand the impact of the various time scales of traffic burstiness on the performance of a link and on its resource sharing capabilities. Moreover, problems in admission control, network resource dimensioning, and pricing can be simplified with the use of an accurate and unifying definition of resource usage.
Some specific questions in traffic engineering that we seek to answer are the following:
Traditional queueing theory based on elaborate traffic models cannot answer such questions in the context of large multi-service networks carrying traffic of different type. Our objective is to address the above questions and other problems in traffic engineering by applying, to real broadband traffic and a real networking environment, some powerful results from large deviations theory.
This work is based on the following definition of effective bandwidths of a source of type j given by Kelly [Kel96]:
where Xj[0,t] is the amount of workload produced by a source of type j in a time interval of length t. The above definition summarizes the statistical characteristics of a source over different time and space scales.
When used for the analysis of a link (multiplexer) that guarantees some level of performance or quality of service (QoS), the space and time parameters s, t characterize the context of the source, which includes the link resources (capacity and buffer), scheduling discipline, QoS, and traffic mix (percentage and characteristics of the different source types).
In this case, parameters s, t can be computed using the many sources asymptotic[CW96,BD95]:
where Q(Nc,Nb,Nn) is probability of overflow in a link with capacity Nc and buffer Nb which multiplexes Nn=N(n1, ... nJ) sources, with nj the percentage of sources of type j. We will refer to the last equation as the supinf formula.
At this point you're probably asking why there is a need for an effective bandwidth definition which takes into account the context of the source. Here's an answer.
Particular values of (s,t) can be taken to characterize the operating point of a link. Here's why.
We have implemented the numerical solution of the supinf when the source trace is in the form of aggregate statistics (number of bytes/cells) in fixed time intervals (epochs). A sample trace file looks like this
# epoch_in_msecs = 4065458...
In the above trace an epoch has duration 40 msec. In the first epoch ( 40 msec ) the source produces 65 cells, in the second ( 40-80 msec ) 4 cells, etc.
To numerical solve the supinf formula we replace the expectation in the effective bandwidth with the empirical estimate. Hence the effective bandwidth is estimated from traffic traces using the following equation:where T is the total duration of the trace (for simplicity we have assumed that it is an integer number of the time parameter t). Xj[(i-1)t,it] is the amount of work (e.g., number of cells) produced in the interval ((i-1)t,it].
The supinf formula involves two optimization procedures: the first consists of, for fixed t, a minimization with respect to s, and the second a maximization with respect to t.The minimization with respect to s (infs) can be solved numerically in an efficient manner by taking into account the convexity of the product s times the effective bandwidth, in s. In particular, for a specific value of t, the infs is found using a golden section search starting from an initial uncertainty interval which contains the minimum. The search procedure decreases the uncertainty interval in successive steps, and stops when the width of the uncertainty interval is less than some small number.The maximization with respect to t (supt) is found by linear searching a range of values for t, in steps equal to the epoch of the trace file (there is no general property that we can take advantage of to use a faster approach, as we did for the infs). The range of t that is searched is determined heuristically and depends, among others, on the buffer size: the extremizing value of t is larger for larger buffer sizes.
I have made available some typical values of s,t for MPEG-1 video, Internet WAN traffic, and a traffic mix of MPEG-1 video and voice traffic. There is also a FAQs for the s,t parameters
The executables for the msa tool, along with other traffic engineering related executables, are available here.There exists a man page, and a collection of frequently encountered problems.
We have started developing a WEB-based interface for our traffic analysis tools. A prelimenary version of the interface is available here.
A sample trace file (MPEG-1 compressed video of Star Wars) can be found here. The trace contains 40000 epochs, with each epoch having duration 40 msec. Note that the trace file MUST have the extension .tr
If you choose to download and use the software, I'ld appreciate if you send me an email at vsiris@ics.forth.gr, possibly with some of your results !
Theoretical backround
For more info: Vasilios Siris Tel: +30 2810 391726 Email: vsiris "at" ics "dot" forth "dot" gr
