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

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*

- Motivation
- The theory
- and its application
- Some FAQs for the
,*s*parameters*t* - Software (executables)
- References

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?

where

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`,

In this case, parameters

where

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.

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:

where

The ` supinf` formula involves two
optimization procedures: the first consists of, for fixed

The minimization with respect to

The maximization with respect to

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

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 !

**[Kel96]**F.P. Kelly. ``Notes on effective bandwidths''. In Stochastic Networks: Theory and Applications (Editors F.P. Kelly, S. Zachary and I.B. Ziedins) Oxford University Press, 1996. 141-168.**[CW96]**C. Courcoubetis, R. Weber. ``Buffer Overflow Asymptotics for a Buffer Handling many Traffic Sources''.*Journal of Applied Probability*, vol. 33, 1996. [.ps.gz]**[CKW97]**C. Courcoubetis, F.P. Kelly, R. Weber. ``Measurement-based usage charges in communication networks ''. Statistical Laboratory Research Report 1997-19, University of Cambridge. To appear in Operations Research.**[BD95]**D.D. Botvich and N.G. Duffield. ``Large deviations, the shape of the loss curve, and economies of scale in large multiplexers''.*Queueing Systems*, 20:293-320, 1995.**[LM98]**L. Likhanov and R.R. Mazumdar. ``Cell loss asymptotics for buffers fed with a large number of independant stationary processes''. In*Proc. of IEEE INFOCOM'98*.**[Wis99]**D. Wischik. ``The output of a switch, or, effective bandwidths for networks''. To appear in Queueing Systems.

**[CS00b]**C. Courcoubetis and V.A. Siris. ``Procedures and tools for analysis of network traffic measurements''. Submitted, September 2000.**[CS00]**C. Courcoubetis and V.A. Siris. ``A web-based tool for advanced statistical analysis of network traffic measurements''. July 2000. [pdf, .ps.gz]**[CS99]**C. Courcoubetis and V.A. Siris. ``Measurement and analysis of real network traffic''. In Proc. of 7th Hellenic Conference on Informatics (HCI'99), Ioannina, Greece, August 1999. Available as ICS-FORTH TR-252 [pdf, .ps.gz]**[CSS99]**C. Courcoubetis, V.A. Siris, and G.D. Stamoulis. ``Application of the Many Sources Asymptotic and Effective Bandwidths to Traffic Engineering''.*Telecommunication Systems*, 12(2-3):167--191, 1999. [Abstract] Preprint: [pdf, .ps.gz, html]

**[CDS99]**C. Courcoubetis, A. Dimakis, and G.D. Stamoulis. `` Traffic Equivalence and Substitution in a Multiplexer''. In*Proc. of Infocom'99*, New York, USA, March 1999. [.ps.gz]**[CSS98]**C. Courcoubetis, V.A. Siris, and G.D. Stamoulis. ``Application and Evaluation of Large Deviation Techniques for Traffic Engineering in Broadband Networks''. In*Proc. of ACM SIGMETRICS '98/ PERFORMANCE '98*, Madison, Wisconsin, June 1998. Superseded by [CSS99] above.

**[Gib96]**R. Gibbens. ``Traffic characterisation and effective bandwidths for broadband network traces''. Statistical Laboratory Research Report 1996-9, University of Cambridge.

**[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.

ICS-FORTH

Email questions/problems to Vasilios A. Siris, vsiris "at" ics ``dot'' forth ``dot'' gr

Last updated: September 2000