Large Deviation Techniques for Traffic Engineering

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

Contents:

Motivation

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:

  • How is the loss probability (or probability of traffic exceeding some maximum delay) affected by the traffic mix (percentage and characteristics of the multiplexed traffic types) and the link resources (capacity and buffer)?
  • For a link with some amount of resources (capacity and buffer), what combinations of traffic sources can be accepted, while still ensuring the target quality of service?
  • What is the effect of traffic control mechanisms, such as traffic shaping and priority scheduling, on a link's multiplexing capability and the amount of resources used by a bursty source?
  • Measurement platforms enable the collection of detailed packet level traces on high speed links. Such traces can lead to a huge amount of data. Can one collect a smaller amount of traffic statistics, such as the amount of traffic in time periods of equal length, that nevertheless contains all the necessary information for performance analysis? What is the sufficient time granularity (length of the measurement period) of such measurements?

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.

The theory

This work is based on the following definition of effective bandwidths of a source of type j given by Kelly [Kel96]:

effective bandwidth

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]:

supinf

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.

and its application

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 = 40
65
4
5
8
...

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:
empirical estimate of effective bandwidth
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

Software (executables)

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 !

References

Theoretical backround

Application and experimental results

Related

  • [CLW94] G.L. Choudhury, D.M. Lucantoni, and W. Whitt. "On the effectiveness of effective bandwidths for admission control in ATM networks". In Proc. of ITC-14, 1994.
  • [Kni97]E. Knightly. "Second moment resource allocation in multi-service networks". In Proc. of ACM Sigmetrics'97, 1997.

For more info: Vasilios Siris Tel: +30 2810 391726 Email: vsiris "at" ics "dot" forth "dot" gr

© Copyright 2007 FOUNDATION FOR RESEARCH & TECHNOLOGY - HELLAS, All rights reserved.