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