NAME
msa - Numerically solves the supinf formula and computes the
effective bandwidth, for input from trace files.
This is for msa version 1.7.
The most recent software and manual can be found at [MSA].
SYNOPSIS
(0) msa [-help]
(1) msa data -eb s t
(2) msa data -bop B C N [-t t_start t_final t_step] [-log logfile]
(3) msa data -load | -load_br B C gamma [-t t_start t_final t_step]
[-log logfile]
(4) msa data -B | -B_br N C gamma [-t t_start t_final t_step]
[-log logfile]
(5) msa data -C | -C_br N B gamma [-t t_start t_final t_step]
[-log logfile]
where data = dataset |
-two dataset1 dataset2 perc2 |
-two dataset1 dataset2 -N2 n2 |
-three dataset1 dataset2 dataset3 perc2 perc3 |
DESCRIPTION
Implements the numerical solution of the supinf formula of the many
sources asymptotic [CW95], through which the s,t parameters and BOP
(Buffer Overflow Probability) are computed, and the calculation of
the related effective bandwidth definition [Kel96], for traffic from a
trace file. It has four basic functions: (1) computes effective
bandwidth for specific s,t, and traffic mix, (2) computes BOP and s, t
for specific capacity, buffer, number of sources, and traffic mix,
(3) computes maximum number of sources and s,t for specific capacity,
buffer, target BOP, and traffic mix, (4) computes minimum buffer
and s,t for specific capacity, number of sources, target BOP, and
traffic mix, and (5) computes the minimum capacity and s,t for
specific buffer, number of sources, target BOP, and traffic mix.
See [CSS99] for results with real traffic (MPEG-1 compressed video
and Internet WAN).
The traffic mix is defined by the variable data, and can contain one,
two, or three different types, each described from a trace file. In
the case of two or three data types, the percentage of the second or
second and third traffic types, respectively, is given. Finally, for
the case of two traffic types, we can fix the number of source of the
second type ("-two dataset1 dataset2 -N2 n2" option above).
Trace files have the extension ".tr" and contain the number of info
units (where one info unit can be e.g., 8 or 424 bits) in each
epoch. The duration of each epoch is defined in the first line of the
file. For example:
# epoch_in_msecs = 40.000000
65
4
5
8
6
6
10
...
or
# epoch_in_msecs = 200.000000
# bits_per_info_unit = 8.000000
328
0
176
375
187
64
128
...
For the first file, one epoch is defined to be 40 msec. Furthermore,
the number of bits per info unit equals the default value which is 424
(= 1 ATM cell). Hence, for the first file, in the first epoch (0-40
msec) the number of cells sent is 65, in the second (40-80 msec) 4,
in the third (80-120 msec) 5, etc. For the second file, in the first
epoch the number of bytes sent is 328, in the second 0, in the third
176, etc. The number of info units per epoch, as well as the duration
of the epoch and bits per info unit, are read as floating point
numbers.
(1) msa data -eb s t
Computes mean, peak, standard deviation, and eb(s,t) of a single
traffic stream for particular values of s (real) in kb^-1 and t
(integer) in epochs. The stream can be a "virtual" stream created
from two or three other streams.
EXAMPLE
The following command calculates the effective bandwidth
for the trace in "star2.tr", and for s=.01135 kb^-1 and t=0.16 sec
=4 epochs (since for the "star2.tr" trace one epoch equals 40 msec)
msa star2 -eb .01135 4
The above gives eb=0.30815 Mbps.
Note that the value of t (in epochs) MUST be an integer.
(2) msa data -bop B C N [-t t_start t_final t_step] [-log logfile]
Numerically solves supinf (computes s, t, and BOP) for given
buffer, capacity, number of sources, and traffic mix.
B is in info units of datafile, C in Mbps, N is number of streams,
t_* is in epochs.
The numerical solution of the supinf formula: sup_t inf_s (J) involves
calculating for a range of values of t (time parameter) the values of
inf_s(J). The latter is performed using a golden section search
starting from some initial uncertainty interval [s_a,s_b] which
contains the minimum value. 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 BOP is computed using many sources, many source + Bahadur-Rao
improvement, and many sources + Bahadur-Rao approximate improvement.
See [CSS99] for the details.
EXAMPLE
msa star2 -bop 351 149 400
Output tracks intermediate values of s, t, BOP, ... At the very
bottom you'll get something like:
------------------------------------------------------------
B=351 cells (=1.0 msec), C=149 Mbps
N=400, Load=0.70
BOP(many sources)=10^-7.64
BOP(many sources + b-r)=10^-8.86, BOP(many sources + b-r_approx)=10^-8.81
s=0.016532 kb^-1, t=1 epochs (=40.000 msec)
effective bandwidth=0.3153 Mbps
------------------------------------------------------------
Regarding the execution time, for an ULTRA-1 workstation (one
UltraSPARC processor at 170 Mhz running Solaris) the above command is
executed in approximately 14 seconds, while for a Sun SS-10 the
command is executed in approximately 63 seconds. For a workstation
with a Pentium III at 550 Mhz running FreeBSD 3.2, the time is
approximately 3.9 seconds.
The execution time depends on the range of t values (50 in the example)
that are searched and the number of epochs in the trace (40000 for
star2.tr). For comparison, the command:
msa bc_40msec_a -bop 85000 34 4000 -t 1 100 1
with bc_40msec_a.tr containing 175000 epochs is executed in
approximately 99 seconds on an ULTRA-1 and 32 seconds on a
a workstation with a Pentium III at 550 Mhz running FreeBSD 3.2
(3) msa data -load | -load_br B C gamma [-t t_start t_final t_step]
[-log logfile]
Finds the maximum load for given capacity, buffer, and traffic mix
such that BOP <= 10^-gamma. B is in info units of datafile, C in Mbps,
t_* in epochs, and traffic is determined from data.
To use the many sources asymptotic with the Bahadur-Rao improvement, use
-load_br instead of -load.
EXAMPLE
msa star2 -load 1405 149 7
Output tracks intermediate values of s, t, N, ...
At the bottom you'll get something like:
------------------------------------------------------------
B=1405 cells (=4.0 msec), C=149 Mbps
N=443, Load=0.78, BOP(many sources)=10^-7.01
s=0.015291 kb^-1, t=1 epochs (=40.000 msec)
effective bandwidth=0.3104 Mbps
------------------------------------------------------------
where N=443 is the maximum number of sources that can be multiplexed
such that the target overflow probability 10^-7 is satisfied. The load
(=N*mean_rate/C) is 0.78.
(4) msa data -B | -B_br N C gamma [-t t_start t_final t_step]
[-log logfile]
Finds the minimum buffer for given capacity, number of sources, and
traffic mix such that BOP <= 10^-gamma. B is in info units of
datafile, C in Mbps, t_* in epochs, and traffic is determined from data.
To use the many sources asymptotic with the Bahadur-Rao improvement, use
-B_br instead of -B.
(5) msa data -C | -C_br N B gamma [-t t_start t_final t_step]
[-log logfile]
Finds the minimum capacity for given buffer, number of sources,
and traffic mix such that BOP <= 10^-gamma. B is in info units of
datafile, C in Mbps, t_* in epochs, and traffic is determined from data.
To use the many sources asymptotic with the Bahadur-Rao improvement, use
-C_br instead of -C.
OPTIONS
-log logfile
Creates a file called log_file containing the intermediate values of
-inf_s(=sup_s), effective bandwidth, and I=-log10(BOP)/N for
the various values of t.
-t t_start t_final t_step
The program allows you to specify the range of values of t to
search. If these are not specified the program heuristically searches
a range of values of t. The heuristic works for the traces I have
used, but I cannot guarantee that it works for all traces. You can try
running msa without specifying the range of t values, then run it
specifying a wide range (say -t 1 1000 1) and see if you get the same
answer.
Typical values for s,t, and a list of frequently asked questions
for these variables can be found at [MSA].
REFERENCES
[CW95] C. Courcoubetis and R. Weber. Buffer overflow asymptotics for
a switch handling many traffic sources. Journal of Applied Probability,
vol.33, 1996.
[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.
[CSS99] C. Courcoubetis, V. A. Siris, and G. D. Stamoulis. Application
of the many sources asymptotic and effective bandwidths for traffic
engineering. To appear in Telecommunication Systems, 1999.
[MSA] V. A. Siris. Large deviation techniques for traffic engineering.
http://www.ics.forth.gr/netgroup/msa
NOTES/CHANGES
Send problems, questions, comments to Vasilios A. Siris, vsiris@ics.forth.gr
A second trace file format is supported:
# epoch_in_msecs = 40.000000
1 65
2 4
3 5
...
for traces in file with extension ".trace".
The option to specify bytes per info unit works with this format too.
IMPORTANT: do not use the extension .trace for files that include
only the number info units per epoch, since in this case only half
of the file will be read.
IMPORTANT: when using the two or three dataset option, be sure that
all files are of the same type (.tr or .trace), have the same
epoch_in_msecs, and the same number of bits per info units. Also note
that the number of epochs will be the smallest number of epochs.
May 20, 1998 - Vasilios A. Siris
Last update: November 21, 1999