Home

fulltext - DiVA Portal

1. higher protocol layers channel buffer with finite size protocol higher layers t Tae J input flow output flow source off source on z Es modulation server high server low Figure 1 1 Fluid flow model of a wireless link Influence of transmission quality on server capacity a A channel has states of different quality Gilbert Elliott model which causes the effective channel bit rate to vary over time If the channel is bad queuing delays and perhaps even data loss become worse Tur 93 Kim 98 Fie 00b Figure 1 1 shows the corresponding scenario b A base station or a mobile terminal does not succeed in reserving time slots for a GPRS packet to be sent This means that the channel is temporarily unavailable and the packet has to be queued Also in this case queuing delays and the risk for data loss grow A question to be answered in this context would be how to dimension a buffer in order to reduce the loss ratio below a desired level Kim 98 Fie 00b c The capacity that is available for a certain traffic stream varies because there is priority traffic sharing the same link that is able to use as much capacity as it needs temporarily A typical situation at the edge of the network is the competition between voice and data traffic for time slots in GSM GPRS cells where data traffic has to take the left over from voice traffic But also inside the core network simi
2. Parameters for the command line calculation program Page 2 4 Ssrctypel Source type for group 1 1 CBR Constant bit rate 2 VBR 2 state Variable bit l cbr rate 2 vbr2 Number ofsourcesofgroup1 of sources of group 1 20 Source low data rate for group 1 IV O auto set to O for CBR 2 Source high data rate for group 1 1 For CBR gt 0 0 2 For VBR 2 state 2 gt 8x01 N oao dto ie NN he io Source low to high transition rate auto set to 0 for CBR Source high to low transition rate auto set to 0 for CBR Source type for group 2 1 CBR Constant bit rate 2 VBR 2 state Variable bit cbr rate vbr2 Source low data rate for group 2 auto set to 0 for CBR Source high data rate for group 2 1 For CBR gt 0 0 2 For VBR 2 state 2 gt r02 file D man param htm Parameters for the command line calculation program he ba O Ur N Source low to high transition rate auto set to O for CBR 0 Source high to low transition rate auto set to O for CBR 0 2 Ssrctype3 Source type for group 3 1 CBR Constant bit rate 2 VBR 2 state Variable bit l cbr rate 2 vbr2 n3 Number of sources of group 3 20 r03 Source low data rate for group 3 he Ur c N N N N auto set to O for CBR r13 Source high data rate for group 3 1 For CBR 2 For VBR 2 state N n N V V c Ww Ww Source low to high
3. Research Report 3 00 KARLSEKRONA RONNE BY Modeling and Analysis of Wireless Network Segments with aid of Teletraffic Fluid Flow Models by Markus Fiedler Department of Telecommunications ISSN 1103 1581 and Signal Processing ISRN HKR RES 00 5 SE University of Karlskrona Ronneby S 372 25 Ronneby Sweden Modeling and Analysis of Wireless Network Segments with aid of Teletraffic Fluid Flow Models by Markus Fiedler ISSN 1103 1581 ISRN HKR RES 00 5 SE Copyright O 2000 by Markus Fiedler All rights reserved Printed by Psilander Grafiska Karlskrona 2000 Research Report Modeling and Analysis of Wireless Network Segments with aid of Teletraffic Fluid Flow Models Markus Fiedler University of Karlskrona Ronneby Dept of Telecommunications and Signal Processing IT S S 371 79 Karlskrona markus fiedler its hk r se 990615 993011 Sponsored by T Nova Deutsche Telekom AG Technologiezentrum Am Kavalleriesand 3 D 64295 Darmstadt German title Modellierung und Analyse drahtloser Netzsegmente mit Hilfe verkehrstheoretischer FluB Modelle Abstract The fluid flow model is used to model variable server and link rates as they appear in mobile channels due to fading bit error recovery and failed channel reservations Assuming a Gilbert Elliott model for the channel the influence of transmission quality on network Quality of Ser vice QoS might be studied Thus the fluid flow model assumes the role of a mod
4. The original calculation program ffc that has been developed between 1995 and 1997 has been designed as a very universal tool based on the following requirements e The program should be able to carry out a whole set of complicated and time intensive calculations such as the iterative determination of required capacity of a CBR link for a changing population of sources with possibly different QoS requirements e The program should allow to step into intermediate calculation results e g to make it possible to search for numerical problems e The program should enable the user to carry out different function in a very flexible way e The program should make it easy to include new functions e The program should be able to operate in batch mode with input output redirection from to files To be able to cope with these partly contradicting requirements the functions of the program about one hundred are called via commands in a way that is known from most line oriented tools e g ftp or gnuplot Thus the program has a command oriented user interface Be fore carrying out the corresponding functionality each function checks whether all the required objects exist thus making the program robust w r t user faults For developing purposes this concept has proven to be very useful However for data production purposes such a command oriented interface is a kind of second best solution Experience has shown that the need for different inpu
5. low and one high state both with exponential duration The state diagram shown in Figure 2 2 captures the way a source of this kind contributes to the total input rate R t The source parameters are as follows 1 Input rate in source low state Le given in data units per time unit 2 Input rate in source high state h also given in data units per time unit 3 Transition rate from source low state to source high state XY given in reciprocal time units 4 Transition rate from source high state to source low state W also given in reciprocal time units A special case is the on off source Such a source is inactive off during its low phase i e I A 0 and active on during its high phase From the parameters we obtain a couple of other parameters The mean duration of a low high phase is given by A and u respectively The mean cycle time for a source is given as 1 1 Fa Ti a uF A Q 1 1 which means that on average one low and one high phase pass during time q Further more we define the source high activity factor the term in brackets is omitted for on off sources aF A 2 2 AS 14 CHAPTER 2 THE FLUID FLOW MODEL Figure 2 3 State diagram for a group of A VBR 2 state sources The number of the state b indicates how many sources are in the high state which represents the state pro
6. under load state element lt 0 equilibrium state element 0 over load state element gt 0 e The number of overload states int RPMUXC no_ol_states 34 CHAPTER 4 FLUID FLOW ANALYSIS AND ITS IMPLEMENTATION All these objects are defined within class RPMUXC ff_c h and may be displayed by corre sponding functions ff_c_io cc In the case of the buffer less fluid flow model the state probabilities determine the probability that the buffer is full 4 32 Thus if loss probabilities are to be calculated we might proceed to section 4 6 7 while the probability of saturation might be determined at once section 4 8 1 4 4 System of differential equations The distribution of the buffer content F x with Fs x Pr X lt x state s 4 7 is the solution of the system of differential equations D Fiy M F x 4 8 with the boundary conditions that the buffer is never full in under load states F K Ts Vesta lt 0 4 9 and never empty in over load states F 0 0 Ys d gt 0 4 10 The solution of 4 8 4 10 is given by E ay K 0 exp zqx 4 11 The determination of the sets of eigenvalues z and corresponding eigenvectors is dis cussed in the next section 4 5 while sections 4 6 and 4 7 deal with the determination of the coefficients ay K and ag c respectively 4 5 Eigensystem Transformation of 4 8 leads to an eigenvalue vector problem z D M 0 Yq 4 12 The set of eigenvalues
7. 53 54 APPENDIX List of files for building the executables executable code file standard version ff_imatr h ff_ivect h ff_matr h ff_vect h ff_sbase h ff_s1r h ff_s2ir h ff_s2mmr h ff_s2oor h ff_cmdiln cc ff_main cc fflmain cc ff_imatr cc ff_ivect cc ff_matr cc ff_vect cc ff_sbase cc ff_slr cc Ffis2ir ce ffls2ir cc ff_s2mmr cc ff1s2mmr cc ff_s200r cc ff1s2o0or cc long double vers fflcmdln Remarks J J JV calculation class RPMUXC J J definition of constants v v v v v vV v v v v vV vV v v v mM E AAA S 4 So A AA A L lt Re Se S eee A SS AA maretie Y Y S S sakeak kassasse A A y integer index matrix class IMATRIX integer index vector class IVECTOR matrix class MATRIX vector class VECTOR source server base class RPbaseC CBR source server class NRPC VBR on off source server class NIRPC VBR high low source server class NMMRPC VBR Poisson test class ooIRPC XC I O routines XC state space and eigensystem XC build system of equations XC build system of equations XC solve system of equations XC distribution of buffer content XC Grade Quality of Service XC required capacity XC proportional required capacity XC CAC regions main program for command line version main program for interactive version main program for interactive version integer index matri
8. Servers Page 1 1 Servers 14 A group of servers contains servers with similar characteristics and is defined by choosing a server type CBR default or VBR 2 state from the corresponding type list 15 The number of servers n has to be set The minimal value is 1 which is assumed by default A non numerical value throws error 25 while a value smaller than 1 leads to error 26 16 For VBR 2 state servers the server rate for the server low state has to be given the default is O If the entered value is non numerical or negative errors 27 or 28 are thrown In the case of CBR servers an entered value will be ignored 17 The server rate for the server high state is needed for both server types This value has to be larger than O for CBR servers and larger than the server low data rate for VBR 2 state servers otherwise error 30 is issued while a non numerical input leads to error 29 18 The transition rate between server low and server high state A has to be specified for VBR 2 state servers for CBR servers this value is ignored The default value of 0 is not suitable for VBR 2 state servers If the value is non numerical or non positive errors 31 or 32 are issued 19 The transition rate between server high and server low state u is treated in the same way as described under 18 the error codes for non numerical or non positive values are 33 or 34 respectively back file D man servers htm Ou
9. default Probability that a unit of information gets lost due to buffer overflow The loss probability can either be related to all sources or to single groups of similar sources o Overflow probability of buffer threshold Probability that the buffer content exceeds a given threshold 2 Fluid flow model The choice of the fluid flow model determines the size of the buffer and thus the speed memory requirements and stability of the calculations Not each model is suited for each QoS parameter There is no loss in a system in a system with infinite buffer and the probability of saturation is independent of the existence of a buffer The standard cases for each parameter are marked by M while additional possibilities are marked with Y Arrows describe how the remaining cases are translated into the standard cases Model Prob of Loss Overflow prob saturation B meme buffer eS 3 Buffer size The buffer size needs to be specified for the finite buffer case In the buffer less case this value will be set to 0 In the infinite buffer case it will be internally set to 1e 307 which is a symbol for infinity In the buffered case a negative buffer size will be set to 0 which is followed by a warning However a non numerical input throws error 3 The following three parameters enable users to specify a ranges of buffer related parameters for which the calculations are to be carried out so called thresholds Inside the calculation prog
10. transition rate auto set to 0 for CBR Source high to low transition rate auto set to 0 for CBR N Sservtype Server s type 1 CBR Constant bit rate 2 VBR 2 state Variable bit l cbr rate 2 vbr2 r0s Server low data rate an N N 00 eee N W N No auto set to O for CBR GF SI T TTF F AT eee file D man param htm Y av ihe O UI E Parameters for the command line calculation program Page 4 4 18 24 30 r1s Server high data rate 1 For CBR 1 gt 0 0 2 For VBR 2 state 2 gt r0s 19 25 31 Sls Server low to high transition rate auto set to 0 for CBR 20 26 32 Sus Server high to low transition rate auto set to 0 for CBR 21 27 33 Sout ftype Output file type 1 New Excel compatible file 2 Append to Excel compatible file 22 28 34 Sout fname Output file name 1 8 characters automatically truncated to 8 characters ending x1s will be attached automatically file D man param htm Web compute server configuration Page 1 1 Web Compute Server Configuration The compute server which carries out the calculation program should be set up as a web server This web server should have e the ability to carry out CGI files a time out setting that allows for keeping connections open until the calculation program is finished rights for nobody to execute programs write files Perl installed a C runtime library not needed i
11. z4 may be obtained from the characteristic equation det z D M 0 4 13 and the set of eigenvectors from solving the system of equations D M 0 vq 4 14 Unfortunately this method implies serious numerical problems Therefore we use special prop erties of the eigensystem Zy Oy 4 5 EIGENSYSTEM 35 an Punderoad state a 30 o o equilibrium state Jac RO o A Ee strongest positive Gr dy 1 mar d max o 7 Table 4 3 Eigenvalue assignment buffered model 4 5 1 Properties of the eigenvalues The following properties are very important for the treatment of the eigenvalues e Due to the time reversability of the processes under consideration the eigenvalues are real e There is always an eigenvalue 0 e There are as many negative eigenvalues as there are over load states e The number of positive eigenvalues is given by the number of under load states minus one e Originally the analysis could not be carried out if equilibrium states occurred Ani 82 However we are able to treat equilibrium states in the same way as over or under load states due to lim zs Foo 4 15 ds gt gt 0 There are as many unspecified eigenvalues as there are equilibrium states Due to the latter properties we may assign the eigenvalues to states at least in a formal way as shown by Table 4 3 After calculation the eigenvalues are stored in VECTOR RPMUXC eval_v For this assignment it is
12. 0 8 so that the capacity becomes we Mbit s Considering peak rate allocation the link server is over booked by 100 We shall study the effect of link breakdown on the buffer content distribution G x We assume that the availability is lowered from a 100 toa 99 9 thus raising the offered load slightly to 0 8008 The investigations are carried out for different numbers of connections n and as before for different mean cycle time ratios between servers and sources T Tt Table 5 1 shows some quite interesting results which consist in overflow probabilities of a buffer threshold size of 15 mean bursts for different numbers of VPs and different link capaci ties If the link is fully available we observe that queuing becomes less as the number of VPs rises Such a behavior reflects multiplexing gain that becomes the larger the more connections share a common link If the link s availability sinks to 99 9 and the mean cycle times of sources and servers are matched the changes of the overflow probability are marginal as ex pected However if the mean cycle time of the link rises in comparison to that of the sources i e if the link changes more slowly between up and down queuing becomes much more critical and worse for larger numbers of VPs Already for a mean cycle time of the link that is ten times as long as that for one source the trend that the QoS becomes better for a larger number of VPs as known
13. 471 484 1999 C H Lam and T T Lee Fluid flow models with state dependent service rate Com mun Statist Stochastic Models 13 3 547 576 1997 D Mitra Stochastic theory of a fluid flow model of producers and consumers cou pled by a buffer Advances in Applied Probability 20 646 676 1988 R Nagarajan J F Kurose and D Towsley Approximations techniques for com puting packet loss in finite buffered voice multiplexers IEEE JSAC 9 3 368 377 1991 V Ramaswami Matrix analytic methods for stochastic fluid flows Proc ITC 16 Edinburgh 1999 pp 1019 1030 W R W Scheinhardt Markov modulated and Feedback Fluid Queues Ph D thesis University of Twente The Netherlands 1998 T Stern and A Elwalid Analysis of separable markov modulated rate models for information handling systems Advances in Applied Probability 23 105 139 1991 R Tucker Accurate method for analysis of a packet speech multiplexer with limited delay IEEE Transactions on Communications 36 4 479 483 1988 W Turin and M M Sondhi Modeling error sources in digital channels JEEE JSAC 11 3 340 347 1993 T Yang and D H K Tsang A novel approach to estimating the cell loss probability in an ATM multiplexer loaded with homogeneous on off sources IEEE Transac tions on Communications 43 1 117 126 1995 Appendix 1 List of files for building the executables 2 Installation 3 Configuration 4 Web pages and user manual
14. The following configuration settings might be necessary e Apache server in file access conf set permission to execute CGI add lt Directory Options FollowsSymLinks ExecCGI AllowOverride None lt Directory gt allow directory add modify lt Directory WWwW_home_directory gt Options ExecCGI Includes AllowOverride None lt Directory gt allow hosts to contact add order allow deny allow from host in file httpd conf set suitable time out modify Timeout max calculation time e Enable PostScript in file in ffcout cgi and ffcoutl cgil set psenable 1 set gnubin gnuplot_binary Disable PostScript in file in ffcout cgi and ffcoutl cgi set psenable 0 e General in file in ffcout cgi and ffcoutl cgi set calcbin calculation_binary set WWW home directory Swwwroot http Server_address WWW_home modify the links in the HTML pages in directory man to http Server_address WWW_home man file htm set rights such that user nobody may read write in and execute WWW_home_directory read and execute the files in WWW_home_directory only if the long double version of the calculation program is available Manual for the Fluid Flow Calculator Page 1 1 Manual for the Fluid Flow Calculator Important e Usage e Units Stepping through the program e Quality of Service related parameters and thresholds Sources Servers Output
15. U R Krieger The fluid flow model with variable server capacity COST 257 temporary document 257TD 00 18 M Fiedler and U R Krieger The impact of varying channel capacity on the qual ity of advanced data services in PCS networks To appear at 12th ITC Specialist Seminar on Mobile Systems and Mobility Lillehammer March 22 24 2000 R Gu rin H Ahmadi and M Naghshineh Equivalent capacity and its application to bandwidth allocation in high speed networks IEEE Journal on Selected Areas in Communications 9 7 968 981 1991 J G Kim and M Krunz Effective bandwith in wireless ATM networks Proc MO BICOM 98 Dallas 1998 pp 233 241 L Kosten Stochastic theory of a multi entry buffer Delft Progress Report Series F 1 10 18 1974 51 52 Kos 84 Kon 94 Kro 99 Lam 97 Mit 88 Nag 91 Ram 99 Sch 98 Ste 91 Tuc 88 Tur 93 Yan 95 BIBLIOGRAPHY L Kosten Stochastic theory of data handling systems with groups of multiple sources Proc of IFIP WG 7 3 TC 6 International Symposium on the Performance of Computer Communication Systems Ziirich 1984 pp 321 331 K P Kontovasilis and N M Mitrou Bursty traffic modelling and efficient analysis algorithms via fluid flow models for ATM IBCN Annals of Operations Research 49 279 323 1994 D P Kroese and V F Nicola Efficient estimation of overflow probabilities in queues with breakdowns Performance Evaluation 36 37
16. all back file D man securadm htm
17. all the fields to their default values If the user clicks on the button the variable names and their values are passed to the CGI script via its command line Further information on the usage of this form and especially on the meaning of the different parameters might be obtained from the manual pages see appendix which may be reached directly via a link from the HTML page containing the form 3 3 2 CGI script ffcout cgi The CGI script that is called from the HTML form gets its input parameters via command line arguments Then e it checks the input and issues error messages or warnings e it starts the calculation program ff_cmd1n if the input data did not contain any obvious errors e on success it issues a link to an Excel compatible data file that the user may download and displays that file 26 CHAPTER 3 THE FLUID FLOW CALCULATOR e it produces a gnuplot control file and starts gnuplot to write a PostScript file if the user has chosen that option and if there is enough data to produce a picture e it issues links to the desired PostScript picture and the corresponding gnuplot control file The error messages and warnings reported by the script are also mentioned in the user manual There is no link back to the form page to prevent its entries from being deleted when the user should want to make some corrections To go back the button of the browser has to be used 3 3 3 The original interactive calculation program ffc
18. cases are treated by the function int RPMUXC create_full_v int outp en f _c_xd cc that writes the result to VECTOR RPMUXC full_v ff_c h 4 7 Coefficients for infinite buffer For infinite buffer the linear system of equations looks different The condition 4 9 now reads lim Fs x Vs d lt 0 4 33 x gt 00 This has special consequences for the coefficients that are described in the next subsection 42 CHAPTER 4 FLUID FLOW ANALYSIS AND ITS IMPLEMENTATION E E Eon peo 7 Table 4 5 Properties of the coefficients for finite buffer 4 7 1 Properties of the coefficients Compared to the buffered case see Table 4 4 the properties of the coefficients have changed Table 4 5 The positive coefficients that belong to the unstable eigenvalues have to become zero This in turn leads to the coefficient ay 1 The only coefficients that have to be determined are those for the over load states the corresponding system of equations reads Y ag o ys Vs ds gt 0 4 34 q d gt 0 For only one group of VBR 2 state sources or servers Ani 82 presented a very elegant closed form solution which unfortunately cannot be translated to the general case 4 7 2 Deletion of critical states As the equations 4 33 for the under load states are not needed due to the vanishing co efficients we cannot get numerical over or underflow from exponential functions contain ing the eigenvalues Thus th
19. in int NMMRPC evaluate_evec in a modi fied way that is described in Fie 97 After having been computed for each group separately the sub eigenvectors are joined together 4 22 by the function int RPMUXC evaluate_a_evec int chk_en int part en int outp_en ff_c_es cc The eigenvectors are stored in the matrix MATRIX RPMUXC evec_m ff_c h 4 5 5 Numerical problems For large groups the computation of 4 29 is numerically critical The binomial coefficients may lead to numerical overflow while the powers of the residua may lead to numerical under flow This problem may be solved in two ways 1 By calculating the product in 4 29 in a logarithmic way ff s2mmr cc this option is chosen automatically per group if the its number of sources servers exceeds FF_EVEC_N_B ff_const h or the probability that one source server is in the high state becomes less than FF_EVEC_N_B ff_const h This logarithmic calculation is much slower than the standard calculation about factor 10 4 6 COEFFICIENTS FOR FINITE BUFFER 39 Table 4 4 Properties of the coefficients for finite buffer 2 By calculating the product in 4 29 with help of long double variables ff1s2mmr cc This leads to a drastic improvement of the numerical stability of the whole fluid flow analysis but long double variables may not be used with each C compiler Therefore a sepa
20. int RPMUXC get_no_states ff _ c h The command line calculation program ff_cmdln cc issues a warning if the state space becomes larger than a predefined value WARN_NO_STATES 4 3 State transitions probabilities and drift values The state transitions are captured in the generator matrix M whose entries msg represent the transition rate from state g to state s The generator matrix for the whole systems of sources and servers is composed out of those for groups of sources M and servers M by using Kronecker algebra M M 0 oMPeM 4 1 The infinitesimal generator for a group of n CBR sources servers is given by the neutral element of the Kronecker addition M 0 4 2 while for a group of n VBR 2 state sources servers it becomes nA uw 0 dan 0 mh w 1h p Que sb M 0 D r 2 A p s 0 4 3 0 0 0 Xo nyw 4 3 STATE TRANSITIONS PROBABILITIES AND DRIFT VALUES 33 The generator matrix determines the behavior of the state probabilities which in the stationary case reads M 1 0 4 4 The state probability vector may also be composed from the vectors of the groups by using Kronecker algebra Ter k OT 4 5 However we use closed formulae 2 6 and 2 14 to determine the state probabili ties If desired the generator matrix M might be displayed by using the function void RPMUXC show_generator MATR_OUTP matr_outp ff_c_io cc where the enumeration type MATR_OUTP ff_const h determines
21. ject parameters as described in section 4 1 3 These eigenvalues are implemented as virtual inline functions e for CBR sources or servers in double NRPC cakt ff_slr cc e for VBR 2 state sources or servers in double NMMRPC cakt f f_s2mmr cc which may be called via the source pointer array rbp Before doing that the num ber of high sources has to be set in the source objects via the function int RPbaseC set_a_state int k_inp ff_sbase h the same applies for the eigenvalue void RPbaseC set_a_eval double z_inp ff_sbase h 4 5 3 Numerical search for eigenvalues Based on the eigenvalues of the inverse problem the search for an eigenvalue zg is carried out by int RPMUXC eval_srch int i int chk_en int trace en int outp_en ff_c_es cc with a relative deviation defined by FF_ZS_TOL usually 10 gt For trace_en 1 the search process might be observed The sign function in 4 19 and 4 21 is not a problem because the sign of the eigenvalue is known in advance Eigenvalues that are as signed to under load states are searched between O and while eigenvalues that are assigned to over load states are searched between co and 0 The search itself is interval based First an interval z z is determined that includes z which is the case if the left hand side of 4 17 has different sign for z and z respectively The interval is halved and the sub interval is chosen that contains z This procedure is co
22. negative buffer size Specify a non negative lower threshold Specify a lower threshold that is smaller or equal to the buffer size Specify an upper threshold that is smaller or equal to the buffer size Specify an upper threshold that is not smaller than the lower threshold Specify the number of VBR 2 state sources and servers so that the product of the sums of their numbers and one is not larger than WARN_NO_STATES in ff_cmdln cc usually 1000 Warnings Page 2 2 back file D man warnings htm Number of states Page 1 1 Number of states Time and memory requirements as well as the numerical stability of the calculation program depend heavily on the size of the state space This section discusses how this size is calculated The number of states for a CBR sources is given by v 1 and for nt VBR 2 state sources by e vt n 1 1 1 The total number of source states becomes ev Il v The same applies for n CBR servers ev l or n VBR 2 state servers ev n l Thus the size of the state space becomes e v v vy A warning is issued if v exceeds the predefined value WARN_NO_STATES in ff_cmdln cc Based on experience this value has been set to 1000 However this value represents a kind of weak limit especially with regard to numerical stability Important note For one group of VBR 2 state sources or servers the size of the state space should be e less than about 200 for the standard calculation p
23. not be underestimated How do we cope with this problem One possibility consists of adapting the buffer size in a way that a desired loss probability is not surpassed Figure 5 2 shows the required buffer size for a loss probability of 107 as a function of the mean cycle time ratio for the case 0 9 Compared to a fast varying channel a slow varying channel implies a need of up to ten times as much buffer space 45 46 CHAPTER 5 RESULTS PLoss 10 gt 10 10 102 107 10 10 102 10 Figure 5 1 Loss probability versus the mean cycle time ratio buffer size mean burst size 6 0 5 0 4 0 K 3 0 2 0 1 0 0 0 10 10 10 10 105 10 10 10 10 tic Figure 5 2 Required buffer size to achieve a loss probability of 10 versus the mean cycle time ratio server high activity factor a 0 9 5 2 LINK BREAKDOWN 47 yi G 15 mean bursts w t P n 50 n 100 ny 150 Too 155 10 1 60 10 7 2 08 x10 70 999 Tf 168x109 178107 2 31 x 10 0999 TO 1 77 x10 2 60 x 10 7 6 64 x 10 7 0 999 100 3 51 10 126x107 197107 Table 5 1 Overflow probability of buffer threshold 15 x mean burst length 5 2 Link breakdown The second example looks at the following scenario An ATM link carries n virtual paths VP with on off behavior acitvity factor a 0 4 and peak bit rate h 1 Mbit s The VPs may share the full link capacity among themselves The offered load is fixed to A
24. sizes and equivalent bandwidths used for capacity dimensioning appear Gu 91 Elw 93 Kon 94 et al e 1995 Yang et al admit numerical problems for quite small systems Yan 95 e 1997 Fiedler and Voos identify sources for the numerical problems Fie 97 Fie 99 e 1998 Kim and Krunz use the fluid flow model in a mobile environment Kim 98 e 1999 Kroese and Nicola use the fluid flow model for a simulation study of breakdowns in queues Kro 99 Ramaswami presents matrix geometric methods for fluid queues with infinite buffer Ram 99 Even today the numerical side of the fluid flow model has a bad reputation However the work Fie 97 Fie 99 on which this project is based shows that 1t is possible to overcome the corresponding difficulties 11 12 CHAPTER 2 THE FLUID FLOW MODEL e quality of the channel e capacity allocation input flow RT t e buffer content capacity R7 t Figure 2 1 Fluid flow model of a multiplexer 2 2 Multiplexer Model The fluid flow model of a multiplexer is shown in Figure 2 1 It takes a couple of influences on its capacity into account All information streams are modeled by streams of fluid from sources to sinks At the entrance of the buffer fluids are superimposed if more than one source exists or is active In the general case both total input rate R t and total service rate R t are random processes whose properties are basically described in sections 2 3 to 2 7
25. source low to source high has occurred A non positive transition rate from source low to source high has occurred Page 2 4 Choose a non negative integer Choose a non negative integer that is less or equal than parameter 7 do not select QoS for unspecified source types 9 15 Choose either cbr or vbr2 21 10 16 Choose a positive integer 22 10 16 2D Choose a positive integer Choose a non negative number 11 17 11 17 Choose a non negative number DHE as 12 18 Choose a non negative number 12 18 Choose a data rate that is higher than parameter 1 1 17 24 or choose CBR property 13 19 Choose a positive number 13 19 Choose a positive number i i i E i i i i i N N N N Error codes N N Transition rate not a number N Ow Positive transition rate required Unknown server type N n Number of servers not a number N oN Positive number of servers required Server rate not a number N 00 Non negative server rate required N NO Server rate not a number Server rate larger than required W he Transition rate not a number OW N Positive transition rate required w N N S Y ES file D man errcodes htm A non numeric specification of the transition rate from source high to source low has occurred A non positive transition rate from source low to source high has occu
26. the second last column refer to the position of the parameter in the command line call of the calculation program The positions that the corresponding parameters have depend on the number of source types Unknown QoS An invalid Quality of Choose either satu loss or Service QoS specification over has occurred E model An invalid fluid flow model Choose either inf fin or ee aa has occurred bls Buffer size not a A non numeric buffer size Choose a non negative number specification has occurred number Lower threshold A non numeric lower Choose a non negative not a number threshold specification has number occurred Upper threshold A non numeric upper not a number threshold specification has occurred Choose a non negative number Threshold step not A non numeric threshold a number step specification has occurred Positive step A non positive threshold required step has occurred Number of groups A non numeric of sources not an specification of the number integer of groups of sources has occurred negative character Choose a non negative number Choose a real valued number Choose a positive integer No groups of A non positive number of sources defined groups of sources has occurred Choose a positive integer specify groups of sources in ascending order without gaps 10 Too many groups of A number of groups of sources present sources has occurred that is larger than the int
27. the context of the fluid flow model 2 9 1 Probability of saturation The probability of saturation describes the probability that the total input rate exceeds the total server rate Pe Pik gt R a 2 20 seso This probability is a measure for the share of over load states that may lead to a degradation of QoS no matter how the buffer is able to handle this So from the model s point of view the buffered models need not be considered Furthermore this parameter does not reflect the viewpoint of different groups 2 9 2 Loss probability The individual loss probability for group i describes the probability that a fluid particle that is belonging to this group gets lost PLoss i 2 21 20 CHAPTER 2 THE FLUID FLOW MODEL where the loss rate is given in 2 17 For the total loss probability we obtain 1 PLoss EE y us ds 2 22 mM seso which is a weighted mean of the individual loss probabilities E mi PLoss L m Pross i 2 23 i 1 In the buffer less case the probabilities that the buffer is full in over load states s S ue merely needs to be replaced by the corresponding state probabilities my i e the loss probabili ties are described by closed formulae 2 9 3 Overflow probability of a buffer threshold The overflow probability of a buffer threshold x is described by the value of the complementary buffer content distribution G x Observe that G x gt K 0 which means that only the bu
28. the link in a statistical manner Under ideal conditions the capacity allocation might be reduced from peak rate allocation to a little bit more than mean rate allocation However this multiplexing gain is not achievable for constant bit rate CBR traffic for which peak and mean bit rate are the same Of course the fluid flow model is able to deal with this quite simple case The main aspect which the fluid flow model is able to model is addressed by the following question What happens if the arrival bit rate to a traffic concentrator or multiplexer or to a simple buffer temporarily exceeds the service rate Such situations might be due to 1 A varying input rate that might temporarily become higher than the output rate due to VBR input traffic streams 2 A varying output rate that might temporarily become lower than the peak requirement of input traffic streams Situation 1 is typical for the exploitation of multiplexing gain both at the edge and inside the core network The fluid flow model might help to dimension network links in a way to allocate as little capacity as possible while maintaining the desired Quality of Service QoS thus max imizing the gain from operating that link In connection to wireless network segments we are especially interested in situation 2 which may arise in the following scenarios 8 CHAPTER 1 INTRODUCTION Base station transmission Mobile terminal 4 mobile terminal errors base station
29. the same sources the command line version uses a subset of ffc s functions and source files This concept enables an advanced user to carry out much more detailed analysis by using the large set of commands that ffc offers based on the same source files i e under fully identical circumstances The corresponding list of source files is to be found in the appendix The parameters needed for calling ff_cmdln are to be found in the HTML user manual The calculation program will check each parameter and exit on error with a detailed error message error or at least issue a warning if some parameter value had to be adjusted This kind of error handling dominates the source code but makes the program safe for batch processing The corresponding error codes are also documented in the HTML user manual 3 4 Output format The output format has been chosen to be as general as possible The data file that may be imported into MS Excel may as well be used for producing PostScript pictures with help of the public domain software gnuplot The structure of this file and the steps that are necessary to import the file into Excel are also described in in the HTML user manual The ending x1s leads to an automatic call of MS Excel on Windows PCs when the user clicks on the link to download the file The same applies for the PostScript file name ending ps if a PostScript viewer e g Ghost View has been installed on the corresponding PC In the latter case a gr
30. the way how the matrix is shown The drift values d 2 16 are captured in the second matrix the diagonal drift matrix D This matrix might be composed out of group related rate matrices which reflect the rate contribution positive for sources negative for servers to each state 2 7 by Kronecker algebra D R 0R 6 R 4 6 If a constant capacity value RPMUXC Cg is specified the right hand side of 4 6 has to be completed with CI where I is a unity matrix of suitable size Matrix D might be displayed by using the function void RPMUXC show_drift MATR_OUTP matr_outp The determination of the set of states with their probabilities and drift values is carried out by the function int RPMUXC create_all_states int outp_en ff_c_io cc where outp en 0 suppresses the screen output of the results Summarized this function creates e A matrix of integers IMATRIX RPMUXC i_state_m containing the indexes of the states of the groups s7 Vi and s that contribute to state s e The vector of state probabilities VECTOR RPMUXC t_state_pr_v e A matrix MATRIX i_cratem ff_c h containing in column 0 the drift values for each state s row if the constant capacity value double RPMUXC Cg is zero in column i the bit rate contributions of source r7 gt 0 and server r7 lt 0 groups to each state s row e A load vector of integers IVECTOR RPMUXC load_v whose elements indicate which state is an
31. within the core network itself A user friendly contemporary and flexible computing environment has been created that is based on a web compute server concept thus providing a well known graphical user interface and multi user facilities The same calculation program might be used via the graphical user interface and for batch processing Great effort has been put into the numerical stabilization of the calculations The fluid flow analysis has been described together with its implementation thus enabling programmers to get a better idea on how analysis and implementation get together Two case studies reveal how important the consideration of a variable server rate is and how dangerous a slowly varying server capacity might become for Quality of Service QoS In the latter case even the well known law that multiplexing gain is rising together with the number of connections does not hold anymore The case studies reveal a strong dependency between results and system parameters Here pa rameters of realistic systems should be used to study the problems of varying server rates for practical systems As the fluid flow model presents a unifying framework for network wide QoS combinations of network elements and links should be considered as well More com plicated source and server models than the VBR 2 state model with exponentially distributed phases should be taken into account which implies the need to develop numerically stabilized al
32. PTER 4 FLUID FLOW ANALYSIS AND ITS IMPLEMENTATION 1 exp z K lt FF_EZK_OL typically 107300 for over load states 2 exp z K gt FF_EZK_UL typically 10739 for under load states This happens by setting the corresponding element of IVECTOR RPMUXC eq_used ff c h to 0 Equilibrium states are marked the same way by the function int RPMUXC delete_worst_states int outp_en double ezk_ol double ezk_ul ff c_eq cc The number of used equations is contained in int RPMUXC no_used ff_c h 4 6 3 The system of equations The system of equations 4 9 4 10 is put together by the function int RPMUXC create_equ_loss int out ff_c_eq cc from the matrix of eigenvectors evec_m e the vector of eigenvalues eval_v the buffer size Kg the vector of state probabilities t_st ate_pr_v based on the information contained in the flag vector eq_used Equation s is created only if el ement s of eg_used is not zero The system is stored in MATRIX RPMUXC eq_syst ff_c h that has no_used rows equations and no_used 1 columns where the last column contains the right hand sides of 4 9f 4 6 4 Solution of the system The solution of the system of equations is carried out by the function int RPMUXC solve_eqsyst int outp_en This function operates mainly on the matrix eq_syst by using the function VECTOR MATRIX solve ffmatr cc thereby changing eq_syst By default the Gauss elimination method with complete pivot
33. The index stands for the fact that a source adds fluid to the buffer while a server takes away fluid from the buffer index Before we begin to look at the description of the source characteristics and the source parame ters we have to discuss the role of data and time units One of the advantages of the fluid flow model consists in the fact that data and time units might be freely chosen Of course the same data and time units have to be used throughout the whole model The units of input and server rates have to be matched and there are also connections to transition rates and the buffer size K Thus the user has the freedom to choose units but has the responsibility to stick to them This issue is discussed in the manual pages see appendix 2 3 Source modeling 2 3 1 Groups of sources Sources that have the same parameters may be grouped The affiliation of a source to a certain group is expressed by the index i The advantage of grouping will become obvious later when it comes to the size of the overall state space v The number of groups is denoted by g We shall look at the superposition of several groups of sources and servers in section 2 6 2 3 SOURCE MODELING 13 Figure 2 2 State diagram for one VBR 2 state source State O refers to the source low state with bit rate while state 1 refers to the source high state with bit rate h 2 3 2 VBR 2 state sources A VBR 2 state source has one
34. aph showing the QoS on the y axis with logarithmic scale and the thresholds on the X axis might be displayed in the browser window without any further user interaction as it is required in Excel Furthermore the PostScript file may be used for slides or documents see Figures 5 3 and 5 4 28 CHAPTER 3 THE FLUID FLOW CALCULATOR 3 5 Long double versions The programs ffc and ff_cmdln get into numerical trouble 1f the number of VBR 2 state servers or sources within one group becomes about 200 or even less for OT or gt 17 This problem which is the most critical numerical issue for fluid flow analysis is also referred to in section 4 5 5 while Fie 97 contains a detailed discussion To be able to extend the limits to about 500 VBR 2 state servers sources a set of files is provided that uses the long double data type The disadvantages of this approach consist in e loss of portability e slow down of the calculations The set of files provided for this case consist in HTML file ffcalcl htm CGI script ffcoutl cgi command line calculation program ff1lcmdln interactive calculation program ffcl The corresponding table in the appendix shows that there are merely some files being affected by this new data type Chapter 4 Fluid flow analysis and its implementation This part of the report is devoted to fluid flow mathematics and how it is connected to the command line calculation program In the following the c
35. bability for the high on state The smaller a becomes the shorter the high phases get on average compared to the mean cycle time If 17 and a are preferred to characterize the behavior of a source the following equations might be applied 1 at 2 3 o o 2 4 C oF af The superposition of ni VBR 2 state independent sources within a group leads to a state dia gram representing a Markov chain with vt n 1 2 5 states as it is shown in Figure 2 3 The state probabilities t are binomially distributed i e nj st nt st mis OD a t 26 1 The input rate of the whole group of sources in state s is given by eE n 5 US tsi hy 2 7 and the mean input rate by 14 p m nt Li 2 8 1 1 uF AT which in the on off case becomes mi ni at he 2 9 2 4 CBR SOURCES 15 2 4 CBR sources CBR sources are somehow a special case of VBR 2 state sources either the low state is never assumed 7 or both states have the same input rate 1 h Thus the contribution of a CBR source to the total input rate R t is completely described by the constant a a x 1 input rate in source high state h given in data units per time unit Independently of the number of sources in the group the state space has the size of one VS 2 10 This state occurs with probability 1 2 5 Server modeling The modeling of the servers that
36. ch is called drift D t R t R t 2 15 The drift depends on the state in which sources and servers are Thus it takes on the values dy r r7 Vs 2 16 Depending on the drift we may observe one of the behaviors described in the next subsections 2 7 BUFFER MODELING 17 2 7 1 Positive drift and over load states If the drift is positive ds gt 0 i e the total input rate exceeds the total service rate in state s the buffer content rises by AX d AT during the time AT as long as the buffer does not get full not full Therefore all states that have positive drift constitute the set of over load states S Once the buffer gets full the drift describes the total loss rate i e during AT the amount of fluid AX gets lost Loss and its distribution is discussed more detailed in subsection 2 7 4 2 7 2 Zero drift and equilibrium states Zero drift ds 0 i e matched total input and service rate freezes the level of buffer content as long as this state is kept The corresponding states constitute the set of equilibrium states S No loss happens 2 7 3 Negative drift and under load states If the drift is negative d lt 0 i e the total server rate exceeds the total input rate in state s the buffer content either diminishes by AX during AT or it remains zero Such states are to be found within the set of under load states 5 and do not lead to any loss at all 2 7 4 Loss and its distribution We have seen
37. contribute to the total server rate R7 t is basically the same as for the corresponding sources To avoid repetitions we use a fully symmetrical notation 1 e we apply the same definitions as before and exchange the index by the index Moreover we restrict ourselves to one group of servers of the same kind i e we may omit the index i 2 5 1 VBR 2 state server The server parameters are as follows 1 Server rate in server low state I given in data units per time unit 2 Server rate in server high state h also given in data units per time unit 3 Transition rate from server low state to server high state given in reciprocal time units 4 Transition rate from server high state to server low state u also given in reciprocal time units Instead of A and u the mean cycle time for a source T and the state probability for the high state a may be used for example Especially the mean cycle time gives an impression on how fast a server changes states compared to a source The connection with the Gilbert Elliott model may been seen as follows In the Gilbert Elliott model a channel has at least two states one bad and one good state see Tur 93 Kim 98 and Figure 2 1 While the channel is fully available when it is good it looses a part or even the whole of its capacity in the bad state which is mainly due to bit errors as a result of diff
38. dd_src in the case of sources double r0 double r1 double 1 double u ff_c_io cc The parameters are given in Table 4 1 The units of the numbers are discussed in chapter 2 and in the HTML user manual The function does not ask for the number of the group because groups are joined succes sively to the source pointer array RPbaseC RPMUXC rbp ff_c h The class RPbaseC ff_sbase h is the base class from which all kinds of sources are deducted Therefore com mon source related functions are declared virtual Each of the classes e class NRPC ff_slr h for CBR sources e class NMMRPC ff_s2mmr h for VBR 2 state sources e class NIRPC ff _s2ir h for VBR on off sources not used in _cmdln e class ooIRPC ff_s200r h test class for a Poisson fluid arrival process not used in ff _cmdln implements its own version of corresponding function that is even accessible via the base class pointer This concept makes it possible to use different types of sources side by side based on the same infrastructure The numbering of sources begins with 1 i e rbp 1 is the first pointer pointing to a source object The number of source objects is limited by FF_MAX_NO_TYPES ff_ const h Source parameters are shown by the function void RPMUXC show_src int ff_c_io ccl where the parameter specifies the group of sources 4 1 3 Servers object Already in section 2 7 5 it has been outlined that from the fluid f
39. e function int RPMUXC delete_worst_states int outp_en double ezk_ol double ezk_ul ff_c eq cc is not necessary for infinite buffer 4 7 3 The system of equations The system of equations 4 10 is composed by the function int RPMUXC create_equ_delay int out ff_c eq cc from e the matrix of eigenvectors evec_n e the vector of eigenvalues eval_v e the vector of state probabilities t_state_pr_v and is stored in MATRIX RPMUXC eq_syst ff_c h that has no_ol_states rows equa tions and no_ol_states 1 columns Again the flag vector eq_used is used to indicate which states contribute 4 8 QUALITY OF SERVICE RELATED PARAMETERS 43 4 7 4 Solution of the system The solution of the system of equations is carried out by the same function as in the finite buffer case As the system of equations in the infinite buffer case is smaller than in the buffered case the solution needs less time whereas the numerical stability is about the same Fie 97 Fie 99 Again the result is stored in the vector solut_v 4 7 5 Assignment of the coefficients The coefficient vector coeff_v is produced from solut_v based on eg_used as described be fore with the only difference that element zero is set to one 4 8 Quality of Service related parameters 4 8 1 Probability of saturation The probability of saturation 2 20 are obtained from the function double RPMUXC sat_prob int outp_en ff_c_go c The function uses the vector of state p
40. ear systems of equations output of type VECTOR e IMATRIX ff_imatr h cc matrix of integer numbers mostly used for indexing purposes Such objects might as well be used outside the fluid flow context The only additional file they require is the file f_const h that contains definitions of some constants 4 2 General functions 4 2 1 User input verification The following functions adapt the functionality delivered by standard C functions to our specific needs 32 CHAPTER 4 FLUID FLOW ANALYSIS AND ITS IMPLEMENTATION e check_for_int char str checks whether str represents an integer return code 0 Floating points and characters are not accepted error code 1 e check_for_double char str checks whether str represents a floating point num ber return code 0 Characters are not accepted error code 1 4 2 2 Load calculation Calculation of the offered load is performed by the function double RPMUXC At f _c_io cc Within this function sources and servers that are referenced via the same ar ray Of base class pointers have to be treated differently because they contribute in different ways c f 2 18 Furthermore a constant server rate Cg that is not used at all in ff cmd1n but which might be used in ffc has to be taken care of 4 2 3 Size of the state space The size of the state space 2 13 is automatically determined once a new source or server group is added The corresponding value is returned by
41. el that might be used for dimensioning and performance evaluation both at the edge and inside a network We present a user friendly contemporary flexible fast and numerically stabilized computing environment for the fluid flow model with a well known user interface that is able to handle multiple users and that might be used as well for batch processing We discuss two case studies that emphasize the crucial impact of the relationship between server and source dynamics on QoS Keywords Fluid flow model variable server capacity Gilbert Elliott model performance anal ysis QoS software engineering numerical methods Acknowledgement The help of Dipl Ing Holger Voos Institute of Process Automation Universitat Kaiserslautern Germany is gratefully acknowledged This work gained a lot from the fruitful discussions dur ing his visit in Karlskrona in August 1999 Contents 1 Introduction T 2 The Fluid Flow Model 11 A o OI A A IA 11 22 Multiplexer Model ose ee e eee 12 2 3 SOURCE modelne ad ARANA A a A or hae eed 12 2 0 0 Groups OL SOUTCES a s oea a pua e dea ap a a a a a a a 12 2 3 2 VBR 2 state sources ess rr ch A A ae 13 24 CBR SOECES 25 255 84420554404 ars rr 13 2 9 Server mod lihg sea roid 4d oA ee daa a a 15 250 VBR 2 MESE 6 4 5 45 4443 65434 24 844 23 be 15 23 2 CBR A 16 2 6 Superposition of sources and servers o oo aer eee BS 16 2 BUE LIDIA o sasaa e a ee Gee ee RAR Ge Re Go RL a GG 16 2 7 1 Positive drif
42. erent influences e g a temporarily bad signal to noise ratio 16 CHAPTER 2 THE FLUID FLOW MODEL 2 5 2 CBR server A CBR server has been the standard for fluid flow analysis for a long time It is fully described by the 1 server rate in server high state h given in data units per time unit 2 6 Superposition of sources and servers All the source states for group i are collected in the column vector 5 Out of these vector the source state vector for all groups is composed by using Kronecker algebra PEN DN 2 11 This is a kind of formal composition where the symbol between the group related states points out that the corresponding states occur together To capture all states of the system the server state vector is joined in the same way The result is the state vector for the whole system Sos 2 12 For the size of the overall state space we obtain the expression v v v V vi 2 13 Il l Assuming independence the state probabilities are given in closed form For the vector element s in which the groups of sources are in the states st nee se and the servers are in the state s we obtain 8 Ts n r 2 14 i l 2 7 Buffer modeling The buffer may be modeled as a funnel or a bucket with a hole representing the outgoing link that is fed by one or more sources Its content X t depends on the balance between the total input rate R7 t and total server rate R t whi
43. ernal limit in ff_cmdln exe Choose a positive integer that is less or equal than FF_MAX_NO_TYPES in ff_const h DO KEELE E CA E file D man errcodes htm Error codes Group for QoS not an integer 12 Group for QoS does not exist Ow Unknown source type Number of sources not an integer Positive number of sources required Input rate not a number Nn 17 Non negative input rate required he 00 Input rate not a number Input rate larger than required Transition rate not a number N Positive transition rate required N Re Re Re Re Re o an Eh Rh file D man errcodes htm A non numeric specification of the type for which the QoS loss probability should be determined has occurred The group of sources whose QoS should be calculated does not exist An invalid source type characterization has occurred A non numeric specification of the number of sources has occurred A negative number of sources has been given A non numeric specification of the source low state input rate has occurred A negative input rate for the source low state has occurred A non numeric specification of the source high state input rate has occurred A data rate for the source high state has been specified that is not larger than the input rate for the source low state A non numeric specification of the transition rate from
44. f linked statically the program gnuplot if PostScript pictures are desired back file D man websconf htm Security and admininstrative issues Page 1 1 Security and administrative issues e To hinder third parties to use this software the web server should be an Intranet server e To improve security put an HTML page at the beginning that calls ffcalc html and that asks for a user name and a password Each user could get his account to store his or her files on the web compute server e After having been computed and produced the files are not deleted from the server automatically This is a kind of backup e g to enable people to just get a file back if they would have deleted it from their local disk by accident instead of carrying out the corresponding calculation once more or to be able to append data to a given file But there are also implicit dangers with this approach o Files that are not needed any more have to be taken away manually or by executing a special script to beware the web compute server to run out of disk space Different accounts for different users might ease this task Each user might be given access to a special script to clean up his her directory o Two or more people might try to write onto the same file at the same time especially when the default filename is used Possibilities to circumvent that problem consist in assigning directories to the users or in simply not providing any default file name at
45. f sources in group 2 file D man excelgnu htm Output analysis with Excel and gnuplot J 10 J 10 h2 Source high input rate for group 2 K 11 K 11 la2 Source low to high transition rate for group 2 0 for CBR sources L 12 L 12 mu2 Source high to low transition rate for group 2 0 for CBR sources M 13 n3 Number of sources in group 3 N 14 13 Source low input rate for group 3 O 15 h3 Source high input rate for group 3 P 16 la3 Source low to high transition rate for group 3 0 for CBR sources Q 17 mu3 Source high to low transition rate for group 3 0 for CBR sources M 13 R 18 Number of servers Server low service rate Server high service rate K 11 P 16 U 21 L 12 Q 17 Server high to low transition rate 0 for CBR sources Server low to high transition rate 0 for CBR sources Buffer size M 13 R 18 bufsize N 14 S 19 X 24 thresh Threshold size buffer size for loss prob buffer less model For help on how to edit the gnuplot control file please use gnuplot s own help facilities back file D man excelgnu htm Page 2 2 Error codes Page 1 4 Error codes All of the numbered errors listed below are discovered by the calculation program ff_cmdIn exe Besides that there are some errors also reported by the CGI script that calls ff_cmdIn exe but often with a shorter error message the texts in brackets are omitted The parameter numbers in
46. ffered models are of interest The parameter does not take the different views by different groups of sources into account Chapter 3 The Fluid Flow Calculator This chapter describes the basic software concepts while implementation details like class at tributes and methods are mentioned in chapter 4 Details about the use of the software may also be found in the user s manual web pages which are to be found in the appendix Most self written tools suffer from the lack of a Graphical User Interface GUI that makes 1t possible to use the tool in an intuitive way Mostly such tools offer very little flexibility with regard to data in and output and sometimes the user is forced to learn a vast amount of cryptic commands or even to modify source code to get the desired functionality So first we shall look at some important aspects of the GUI and how this affects the overall software concepts Later we will focus on the very heart the C calculation program 3 1 Graphical User Interface GUI 3 1 1 Requirements 1 The GUI should make it easy to use the calculation program 2 The GUI should use elements and a functionality that the user is familiar with 3 The GUI should be platform independent while keeping its functionality 4 The GUI should use current technology which makes it easier to maintain the interface and to adapt it to forthcoming developments 5 The GUI should not affect the performance of the calculation pro
47. file Output analysis with Excel and gnuplot Problems Error codes Load Warnings Number of states Strange Quality of Service Miscellaneous Software components Parameters for the command line calculation program Web compute server configuration Security and administrative issues file D man index htm Usage Page 1 1 Usage Please fill in the Fluid Flow Calculator form and adjust the values to your own needs Before choosing numeric values please fix your data and time units Please observe that by using merely default values the calculation program will terminate on error e The Reset button clears the user input i e shows the default values e The Start button sends the data to the calculation program and starts it Depending on the size of the system this calculation program may take a while to execute Thank you for your patience Upon reception of errors or warnings or if results seem to be strange please consult the problem pages By using the back button of your browser you can get back to your input and modify it without having to fill in the whole form again If you however prefer that please use the Reset button The files that are produced may be downloaded by clicking on the corresponding links They stay on the server until e they are overwritten by files with same names e they are removed by the administrator of the web computeserver back file D man usage
48. from the 100 CBR link case does not hold anymore If we raise the mean cycle time of the link once more by factor ten this trend is completely inverted We may summarize our observations as follows For links that change their state much slower than VPs 1 heavy queuing occurs 2 the multiplexing gain sinks if the number of connections rises While the first result is underlined by figures 5 3 and 5 4 unchanged PostScript output from the program the last result may have significant impact on the dimensioning of systems if reliability comes into the game 48 CHAPTER 5 RESULTS 1 0e 01 T T T 1 0e 02 1 0e 03 1 0e 04 1 0e 05 1 0e 06 1 0e 07 Complementary distribution function 1 0e 08 1 0e 09 1 0e 10 l L L 0 10 Buffer threshold x Figure 5 3 Overflow probabilities versus buffer threshold size in mean burst lengths for 150 connections and 100 link availability 1 0e 01 T T T 1 0e 02 gt 4 Complementary distribution function 1 0e 03 L L L 0 10 Buffer threshold x Figure 5 4 Overflow probabilities versus buffer threshold size in mean burst lengths for 150 connections and 99 9 link availability mean cycle time of the link 100 mean cycle times of a VP Chapter 6 Summary and outlook In this project the fluid flow model has been applied successfully to model variable server rates as they appear in mobile environments at the edge of the networks but also
49. gorithms The list of scenarios presented in the introduction gives only a vague notion about the very many problems that the fluid flow model might be applied to in the future Let s con tinue 49 50 CHAPTER 6 SUMMARY AND OUTLOOK Bibliography Ani 82 Elw 93 Elw 94 Fie 97 Fie 98 Fie 99 Fie 00a Fie 00b Gu 91 Kim 98 Kos 74 D Anick D Mitra and M M Sondhi Stochastic theory of a data handling system with multiple sources The Bell System Technical Journal 61 8 1871 1894 1982 A I Elwalid and D Mitra Effective bandwitdh of general Markovian traffic sources and admission control of high speed networks IEEE ACM Transactions on Net working 1 3 329 343 1993 A I Elwalid and D Mitra Statistical multiplexing with loss priorities in rate based congestion control of high speed networks IEEE Transactions on Communications 42 12 2989 3002 1994 M Fiedler and H Voos Fluid flow Modellierung von ATM Multiplexern Mathema tische Grundlagen und numerische L sungsmethoden Miinchen Utz 1997 ISBN 3 89675 251 0 M Fiedler and H Voos Erforderliche Kapazit t beim Multiplexen von ATM Verbindungen Ph D thesis Universit t des Saarlandes Saarbr cken 1998 M nchen Utz 1998 ISBN 3 89675 385 1 M Fiedler and H Voos How to win the numerical battle against the finite buffer stochastic fluid flow model COST 257 temporary document 257TD 99 38 M Fiedler and
50. gram 6 The GUI should make it easy to integrate manual and help functions 21 22 CHAPTER 3 THE FLUID FLOW CALCULATOR 3 1 2 Alternatives 1 Microsoft MS Windows specific solution Visual Basic e g As the MS Windows based PC has the leading position among the end user computers most people are acquainted with MS GUIs However the GUI specific part of the code is mostly not portable even between different versions of the MS Windows OS A re compilation of the DLL files is necessary which often comes along with the need to adapt or rewrite parts of the code As a new Windows release appears on average each second to third year this could imply a lot of adaptation work in the future Another disadvantage is the need for embedding the GUI functions into the code which could affect the speed of a calculation in a negative way 2 X Windows based solution X is a quite widespread standard for GUIs but mostly within the UNIX LINUX environment Therefore this solution does not seem to be feasible for Windows based PCs and thus neither for the whole project 3 HyperText Markup Language HTML based solution Here a browser window is used as GUI As HTML is designed to work independently of the OS a browser based solution should work quite independently of the underlying OS Windows LINUX UNIX and others as long as the current standards are supported Moreover this solution allows for a full separation of GUI and calculation pro
51. gram in the sense of a client server solution which will be discussed in the next section 3 2 The web compute server concept The web compute server concept represents a client server solution that is e flexible e simple to handle e almost independent of the underlying operating systems e capable of separating calculation and GUI tasks e multi user friendly 3 2 1 The server The notion of the concept already shows that the role of the server is two fold 1 The main task for the server is to be a compute server 1 e to execute the calculation program in a fast and reliable way Thus a powerful computer is needed e g with UNIX or LINUX operating system 3 2 THE WEB COMPUTE SERVER CONCEPT 23 2 The other task consists in providing communication facilities between the calculation program and its users To achieve this the compute server has to become an Intra or Internet web server Observe that the task of being a web server is restricted in 1 executing scripts 2 sending their HTML output back to the clients 3 starting programs and 4 making the files produced by those programs accessible to the user To be able to do that the following web server configurations have to be set e The server should be enabled to execute Common Gateway Interface CGI scripts e The timeout variable should be set in a way that the web server is patient enough to wait for calculations to complete e User nobody that act
52. he default setting is an average QoS for all source types The selection of a group that has not been defined before see 7 throws error 12 8 The number of sources ni within each defined group has to be set The minimal value is 0 which is assumed by default A non numerical value throws error 14 while a negative value throws error 15 9 For VBR 2 state sources the input rate for the source low state Le has to be given the default is 0 If the entered value is non numerical or negative errors 16 or 17 are thrown In the case of CBR sources an entered value will be ignored 10 The input rate for the source high state he is needed for both source types This value has to be larger than O for CBR sources and larger than the source low data rate for VBR 2 state sources otherwise error 19 is issued while a non numerical input leads to error 18 11 The transition rate from the source low to the source high state oe has to be specified for VBR 2 state sources for CBR sources this value is ignored The default value of 0 is not suitable for VBR 2 state sources If the value is non numerical or non positive errors 20 or 21 are issued file D man sources htm Sources Page 2 2 12 The transition rate from the source high to the source low state pr is treated in the same way as described under 12 the error codes for on numerical or non positive values are 22 or 23 respectively back file D man sources htm
53. he states very much 2 9 QUALITY OF SERVICE RELATED PARAMETERS 19 2 8 4 Buffer less model This model is obtained by passing the buffer size to the limit zero K 0 which implies that the buffer looses its buffering capability so that loss happens almost directly after the system has entered an overload state Such a behavior is typical for systems with very low transition rates 1 e systems that change states very slowly compared to the dynamics of the buffer In this limit the probabilities that the buffer is full in overload states are identical to the state probabilities for the overload states themselves The fact that state probabilities are given in closed form c f 2 6 and 2 14 makes the analysis fast and numerically stable On the other hand the cpdf G x cannot be considered anymore Also in this system the load is not limited neither in theory nor in the implementation 2 9 Quality of Service related parameters Before looking at the Quality of Service QoS related parameters we have to point out a very basic condition that prevents the fluid flow model from delivering zero values The minimal total server rate has to be smaller than the maximal total source rate If this is not the case the buffer is never able to fill and no loss will ever happen The fact that even systems of CBR sources and servers with matched rates i e 100 load do not fulfill this criterion underline the importance of the VBR property in
54. htm Units Units Page 1 1 Due to the broad range of applications for the fluid flow model it would not be sensible to predefine data and time units Therefore this specification has been left to the user completely The following table shows the ways in which parameters are affected by the chosen data and time units Buffer size K Data unit thresholds Data rates Data units time units Transition rates 1 time units However for VBR 2 state sources and servers there are some principle relationships between some of the parameters that deserve special attention e The mean burst duration is given by the corresponding reciprocal transition rate e The mean cycle time is the total mean burst duration for both states t 1 1 1 e The mean burst size mean amount of information within a burst is given by the product of the mean burst duration and the corresponding data rate e Especially for on off sources 0 the buffer size K might be related to the mean burst size in the on state by a factor k back file D man units htm K xh yu Quality of service related parameters and thresholds Page 1 2 Quality of Service related parameters and thresholds Quality of service QoS The desired output of the calculation has to be specified One of the following parameters has to be chosen from a list o Probability of saturation Probability that the input rate exceed the service rate o Loss probability
55. ing is set as solution procedure c f define FF_SOLV_M GAUSS_T ff_const h because it has shown up to be the numerically most versatile of all the methods implemented in ff_matr cc Fie 97 Fie 99 The result is stored in the VECTOR RPMUXC solut_v ff _c h which in most cases merely contains the subset of non vanishing coefficients due to the fact that some equations had to be left out c f subsection 4 6 2 4 7 COEFFICIENTS FOR INFINITE BUFFER 41 4 6 5 Assignment of the coefficients With the flag vector eq_used the coefficient vector VECTOR RPMUXC coeff_v ff_c h is created from the solution vector solut_v which is performed by the function int RPMUXC solut_2_coeff_v int outp_en ff_c_eq cc If element s of eq_used had been marked with 0 then coefficient s of coeff_v will also be set to zero 4 6 6 Regeneration of the flag vector If the buffer size is changed then the procedure has to be carried out from step 4 6 2 a re construction of the eigensystem is not necessary The flag vector eq used has to be prepared for new marking of critical states by calling the function int RPMUXC regen_eq_used ft cues cc 4 6 7 The probabilities of full buffer After the coefficients aj K have been determined the probabilities that the buffer gets full in over load state s are given by uy m lim F x 4 30 ad a dq K 0 exp ZqK 4 31 For the buffer less model this reduces to U Ts 4 32 Both
56. ings that are also issued by the CGI script are marked accordingly Model with infinite buffer set QoS Overflow probability over has been used with the buffer less model b1 s Buffered model set QoS Loss probability loss has been used with the model with infinite buffer inf Buffer less model set QoS Probability of saturation satu has been used with the model with finite buffer fin or infinite buffer inf Buffer size set to 0 A negative buffer size has been given Lower threshold set to A negative lower threshold 0 size has been given A lower threshold that is larger than the buffer size has occurred Lower threshold set to buffer size Upper threshold set to buffer size An upper threshold that is larger than the buffer size has occurred Upper threshold set to lower threshold An upper threshold that is smaller than the lower threshold has occurred Large state space states A large state space occurred which may lead to long execution times and numerical instabilities j 10 16 22 28 file D man warnings htm Specify fluid flow model with finite fin or infinite inf buffer together with the overflow probability over Specify buffer less model b1s or model with finite buffer fin together with the loss probability loss It suffices to specify the buffer less model b1 s together with the probability of saturation loss Specify a non
57. lar problems might arise With the introduction of QoS concepts to Internet such questions will surely gain more and more significance within the next years d In AAL 2 there exists the possibility of adapting the coding to network load conditions When the content of a network buffer reaches certain levels one or two of the least sig nificant bits are thrown away In principle this is a virtual increase of capacity which is controlled by the buffer content to keep the queue from growing This measure is typical for carrying mobile conversations over an ATM core network Lam 97 e Traffic shaping e g according to the Leaky Bucket algorithm aims at improving the uti lization of the network by making traffic patterns more useful for statistical multiplexing The shaper itself is modeled as a buffer with variable capacity which is controlled either by feedback from the network ABR or by local feedback from a token pool Shaping usually happens at the edge of the network Sch 98 f Network reliability problems e g link breakdown is an issue for network dimensioning and control both at the edge and inside the network Kro 99 All this shows the outstanding role of the fluid flow model for end to end networking because it provides a unifying framework for network performance evaluation On this background the research project that is described in this report aims at providing a user friendly and numerically stable tool for carryi
58. low model point of view servers are nothing else than sources with negative rates Thus we might use the same kind of objects both for sources and servers However there are some differences e The cell rates of servers are negative e The program relies on r0 lt r1 4 2 GENERAL FUNCTIONS 31 Parameter Symbol cup Bither NR for CBR or NYMR for VBR Pote servers n r 1 negative source low bit rate for one server NMMR only Server high to server low transition rate NMMR only server low to server high transition rate NMMR only Table 4 2 Parameters of the call of function RPMUXC add_src in the case of servers This is reflected in Table 4 2 Throughout the program servers are treated as sources with some exceptions e g in load and loss probability calculations Within the program servers are recognized by their absolutely seen non positive peak rate n r1 By default function parameters that are not explained explicitly in the following should be set to 0 4 1 4 General objects There are some general kinds of objects being used almost everywhere in the program e VECTOR ff_vect h cc vector of floating point numbers based on data type double e IVECTOR ff_ivect h cc vector of integer numbers mostly used for indexing purposes e MATRIX ff matr h cc matrix of floating point numbers based on data type double which includes methods for solving lin
59. mely high This case has been studied extensively in literature because it allows for certain simplifications of the analysis However infinite buffer sizes are impossible in practice The goal of the analysis consists in finding the complementary probability distribution function of the buffer content cpdf G x Pr X gt x A buffer content of x is henceforth called buffer threshold For one group of VBR 2 state sources and a CBR server there exists a very elegant method Ani 82 which unfortunately cannot be used for the general case of different groups in combination with VBR 2 state servers The offered load has to be limited to A lt 1 or A lt 1 if all sources and servers are of the CBR type 2 8 3 Model with finite buffer This is the most general case 0 lt K lt which at the same time is hardest to analyze It is hardly dealt with in literature due to effort and numerical problems For a group i of on off sources the buffer size may be given in k mean burst sizes h Ka 2 19 As the analysis of this model mostly focuses on loss related parameters the most interesting outcomes are the probabilities that the buffer is full in overload states us For buffer thresh olds x lt K it might be interesting to look at the cpdf G x to get an idea on how delays are distributed Essentially the offered load is not limited but the mainstream in the analysis relies on A lt 1 which simplifies the handling of t
60. n checks for errors reported by the calculation program and if no error has occurred displays the link to the Excel file that has been produced by the calculation program If the user has chosen the respective option in the HTML form and if there have at least two QoS values been calculated the script e produces control code for gnuplot file D man software htm Software components Page 2 2 e starts gnuplot to produce a PostScript file e and issues links to the gnuplot control file and to the PostScript file The output of this script in invisible as long as the calculation program is being carried out The names of the variables are adapted to those being used within the calculation program ff _ cmdln fflcmdln C calculation program ff_cmdln fflemdin This very central program receives its parameters via arguments on the command line either from the GUI via the CGI script or directly by the user when calling the program from a shell provided by the operating system This approach has an important advantage The same program might be used for different kinds of scenarios i e for interactive use via a GUI as well as for batch processes The long double version of the program 1cemd1n is numerically more stable especially for large numbers of sources or servers within one group 200 500 As the data type Long double needs a special library to be built from this version may not be built on all computers Furtherm
61. n rate s Define groups of sources in the order 1 2 3 without gaps Use buffered models and an upper threshold buffer size that is at least one threshold step larger than the lower threshold back file D man errcodes htm Load Page 1 1 Load For the buffered fluid flow models the offered load has to be limited below 100 This section explains how the load is calculated The variables are explained in the source and server section respectively For a group i of n CBR sources the mean data rate is given by and for a group of VBR 2 state sources by m n MU th ht A The mean data rate of all sources becomes m om Similar definitions apply to the n servers Here the mean service rate for CBR servers is given by m n h and for VBR 2 state servers by man WETANE WN The offered load A is the ratio of the mean data rate of all sources and the mean service rate A m m If this value is larger or equal than one the buffered fluid flow models cannot be used anymore In that case an error code is issued that reflects the rounded load in percent while loads greater than or equal 200 are not reported explicitly back file D man load htm Warnings Page 1 2 Warnings In some cases user input has to be corrected or modified The user will be notified about that by warnings while or after the calculation program is or has been carried out The warnings are generally unnumbered Warn
62. n the number of parameters gt 99 Load too high error code load in 100 199 from 200 on no further distinction Please assign source groups consecutively Not enough data for PostScript picture A non numeric specification of the transition rate from server high to server low has occurred A non positive transition rate from server low to server high has occurred A kind of output has been chosen that is not supported Depending on the number of source types the number of parameters is given by 22 28 34 The mean arrival rate is higher than the mean service rate which is critical for the fluid flow models with finite and infinite buffer There are gaps in the assignment of groups e g group 1 and 3 are defined but not group 2 The thresholds have been chosen automatically in a way that there would be only one point in the picture Page 4 4 Choose a positive transition rate Choose a positive transition rate Choose x1s for an Excel table or xla for appending to an Excel table Check whether the set of parameters is complete Reduce the load by decreasing the number of sources the source data rate s the source low to high transition rate s the server high to low transition rate or by increasing the number of servers the server data rate s the server low to high transition rate the source high to low transitio
63. ng fluid flow analysis Section 2 glances at fluid flow history and describes the fluid flow modeling of sources buffer and server Some general aspects of the analysis and its aims are discussed and the notation that is used through out the project is defined Section 3 explains basic and innovative concepts that have been used for implementing the fluid flow analysis e g the web compute server concept Section 4 de scribes both the main steps in fluid flow analysis and the software objects attributes and meth ods functions to carry them out Section 5 presents two case studies one which deals with scenarios a and b Fie 00b and another one that shows quite interesting results for scenario f Fie 00a Section 6 summarizes the project and gives an outlook on future work it is followed by the bibliography and the appendix that contains some details on the software that has been developed 10 CHAPTER 1 INTRODUCTION Chapter 2 The Fluid Flow Model 2 1 History This subsection mentions some important milestones in fluid flow analysis that are important in the context of this project e 1960 s The fluid flow model appears within manufacturing Mit 88 e 1974 1988 Pioneering work happens within communications Kos 74 Ani 82 Kos 84 Tuc 88 Ste 91 e 1988 Mitra studies a manufacturing system with more than one server i e variable server capacity Mit 88 e 1990 1995 Many approximations e g based on infinite buffer
64. nt ev_out_en int outp_en and int RPMUXC eval_srch int i int chk_en int trace en int outp en ff_c_es cc The only parameter that is no control parameter is i which denotes the current state 4 5 2 The inverse eigenvalue problem The inverse eigenvalue problem to 4 12 reads gt 1 gt Yq Zq Pg r m Qg 4 16 q with g Yalza Y Yislza Y Zq 9 4 17 i l The latter formula might be used to determine the eigenvalues z numerically due to the fact that the formulae for y zq are given in closed form Observe that the value 0 on the right hand side of 4 17 has to be replaced by a constant capacity value C if RPMUXC Cg should be used The eigenvalues of the inverse problem are given e for a group of CBR sources as Ya A 4 18 e fora group of VBR 2 state sources out of which k sources are high in state q as 1 Wila nb s n ahi zali A 4 sign zq 2k nj 1 40 ui 24h zal AF qu 4 19 e for a group of CBR servers as Y a W 4 20 e for a group of VBR 2 state servers out of which k servers are high in state q as 1 Yq Ra nl Zgh zq A p 224 sign zg 2k n 4A pr zgh7 zl A u P 4 21 4 5 EIGENSYSTEM 37 For sources and servers the corresponding eigenvalues 4 18 and 4 20 or 4 19 and 4 21 differ by their sign However this is happening automatically when we assign the source ob
65. ntinued until the desired precision has been reached 4 5 4 Determination of the eigenvectors Once an eigenvalue has been calculated the corresponding eigenvector may be computed which is composed of sub eigenvectors for each group 67 861 867 4 22 All the eigenvectors are normalized in the following way 4 23 The eigenvector for zo 0 is given by the vector of the state probabilities Go 1 4 24 while in the limit d 0 the eigenvector that comes along with indeterminate eigenvalues equilibrium states becomes a unit vector in q direction lim y 2 4 25 Zig Depending on the type of sources or servers the eigenvectors are given as follows 38 CHAPTER 4 FLUID FLOW ANALYSIS AND ITS IMPLEMENTATION e For a CBR source or server group we obtain 0 1 4 26 which is implemented in the virtual function int NRPC evaluate evec e For a VBR 2 state source or server group we have to use the eigenvector generating function approach described in Ani 82 Fie 97 Together with the two residua that look little different for sources and servers 1 res 1 2 24 qe taa Hy 4AT pt AF u PE 4 27 1 res y 2 Zq h Sag St 4 4A7 u ur reir 4 28 and with g sources servers out of n being in the high state in state q the components k of the sub eigenvectors are given in closed form vin E E e lei a However formula 4 29 is implemented
66. o that the user may decide whether s he wants to download it After the Excel file has been produced and if are at least two data lines in the corresponding file a gnuplot control file under the same name but with the different extension gnu will be written by the CGI script By using this file gnuplot will produce a PostScript picture under the same name with the extension ps In that picture the x axis will show the threshold value while the y axis represents the QoS parameter under study The user will be able to download both files By corresponding settings in the operating system or in the browser a PostScript viewer e g ghostview might be started automatically b New file The same as a but without the PostScript picture c Append to file One or more new rows are attached to a file even if this file has been empty before There is no check whether the file already exists The new rows are attached without a header line in the beginning It is up to the user to make sure that the number of groups of sources is not changed while s he appends to a certain file because otherwise the number of columns will change and thus some columns will change their meaning The file is also displayed The latter option c is not offered in a PostScript variant because most probably 1t will be used to file D man output htm Page 1 2 Output file Page 2 2 study the influence of other parameters than a buffer threshold Howeve
67. onstant and one parameter is raised then the QoS should either sink or rise but not alternate back file D man strange htm Software components Page 1 2 Software components The names given in brackets are used to invoke the numerically more stable but slower long double version of the calculation program that may not be available on each server HTML form ffcalc htm ffcalcl htm This file is called in a browser and delivers the Graphical User Interface GUI for the calculation program ff_cmdln ff1cmdln It consists of a FORM that is filled in by the user and either reset or sent away via standard input POST method to the CGI script ffcout cgi ffcoutl cgil The element that are used in this form are the following e Select The user may select an item from a list e Input of type text The user may type in text or numbers e Input of type radio The user may choose between different possibilities All the elements are preset with default values CGI script ffcout cgi This file represents the interface between the GUI and the calculation program f f_cmdin ff 1cmdln It is programmed in the script language Perl and receives the data from the GUI i e the HTML form ffcalc html corrects minor inconsistencies determines the number of source groups checks for obvious input errors fixes the set of input parameters and starts the calculation program starts the calculation program and waits for its executio
68. ore it is much slower than cmdiln The total number of parameters and their role depend on the number of groups of sources They are listed on a special page On Windows PCs the name of the executables should be trailed by exe back file D man software htm Parameters for the command line calculation program Page 1 4 Parameters for the command line calculation program The following table gives an overview over the parameters that f_cmdln or its long double version ff 1cmd1n has to be called with together with a specification of values that are supported The internal variable name in the Perl seript is also given The number of the respective parameter varies according to the chosen number of groups of sources User defined values of parameters that are set automatically in certain cases are mostly ignored a par a par ee name Role Valid entries a grp grp a grp Sqostype Quality of Service parameter Prob of saturation Loss probability Overflow prob of buffer threshold 2 2 2 f fmodel Fluid flow model 1 with infinite buffer 2 with finite buffer 3 buffer less 3 3 3 Sbufsize Buffer size automatically set to 1e307 in the infinite buffer case which stands as a symbol for infinity Number of groups of sources 8 8 8 Slosstype QoS loss that might be observed 1 individually for a certain 1 gt 0 group 2 0 2 for all groups auto set to 0 for file D man param htm
69. orresponding source code files are givenin The C software components are described in C notation which is symbolized by typewriter typesetting The notation of variables deviates to some extent from the no tation in the theoretical part 4 1 Objects 4 1 1 Calculation object The main object is the calculation object of class RPMUXC that comprises the source and server objects and all the necessary settings functions matrices and vectors needed to carry out the fluid flow analysis The class is defined in the header file ff c h and handled in ff cmd1n cc via the pointer MPtr The fluid flow model is set with the function int RPMUXC set_model char ff c io cc while the setting might be read with FF_MODE RPMUXC get_model ff_c h FF_MODE rep resents an enumeration type ff_c h The function void RPMUXC show_model prints out information about the model The buffer size is set with void RPMUXC set_Kg ff_c h and delivered by double RPMUXC get_Kg ff_c h 4 1 2 Sources object After the parameters for a group of sources have been read and checked to be error free the corresponding group is created by calling int RPMUXC add_src SRC_TYP typ int n 29 30 CHAPTER 4 FLUID FLOW ANALYSIS AND ITS IMPLEMENTATION Symbol Either NR for CBR or NMMR for VBR 2 state sources source high to source low transition rate NMMR only Table 4 1 Parameters of the call of function RPMUXC a
70. pace 2 cerraron rac ba ara 32 4 3 State transitions probabilities and drift values 32 44 System of differential equations ooa o 34 4 5 Eige systemM 24624024 Ho do ee eRe Se eee LE REESE 34 4 5 1 Properties of the eigenvalues 428 he ese eee ee 390 4 35 4 5 2 The inverse eigenvalue problem gg e 40 a4 Ge aie amp die eae 36 4 5 3 Numerical search for eigenvalues soc wk eg aie ae 37 4 5 4 Determination of the eigenvectors 4 5 44 24 Ge a 46 4 a e 37 4 5 5 Numerical problems i soc ocs neose amp ow varoa pa Se 38 4 6 Coefficients for finite buffer cde aod po Be eed e aa 39 4 6 1 Properties of the coefficients ro aa He Hd RA 39 4 6 2 Deletion of critical states usa da es a 39 4 6 3 The system of equations 22 2 sc seek eee eee td bere 2 40 4 6 4 Solution of the system 21 2 eo ee en Gees a 40 4 6 5 Assignment of the coefficients ooo ed a a 41 4 6 6 Regeneration of the flag vector ooa nas ma nds 41 4 6 7 The probabilities of full buffer 2 2 42542 252562 bh 22 4 4 7 Coefficients for infinite buffer es rela bn RS Oe A Be 41 4 7 1 Properties of the coefficients 20 1 E a bs 42 4 7 2 Deletion of critical states 3 acusar ade oe 42 4 7 3 The system of equations Vs ei 42 AJA Solution of the system 4 oaaae 43 4 7 5 Assignment of the coefficients uc 43 4 8 Quality of Service related parameters o 43 4 8 1 P
71. r a gnuplot control file that has downloaded might easily be modified to account for the parameters of interest back file D man output htm Output analysis with Excel and gnuplot Page 1 2 Output analysis with Excel and gnuplot Downloading of the Excel compatible data file on a Windows PC with Explorer on it causes Excel to start automatically within the browser window and the data file is displayed Important If a data file is reproduced on the server by choosing the same file name Excel might not be willing to show the new contents If this happens a new file name should be chosen e To assign columns o Mark at least the first column of the table o Choose Data gt Text to columns o Click on Finish e To fix column widths automatically o Mark the whole table o Choose Format gt Column gt AutoFit Selection e To produce a diagram Quality of service versus threshold o Mark the last two data columns o Choose Insert gt Chart o The most suitable chart format is XY Scatter The following table shows the layout of the Excel table for one two and three groups of sources both with Excel specific character and numerical column notions as needed for gnuplot p 1 p 2 e 3 Text in file Description header ao la1 Source low to high transition rate for group 1 0 for CBR sources mui Source high to low transition rate for group 1 0 for CBR sources Ha H 8 gt NN umber o
72. ram buffer related thresholds are the only parameters whose change does not enforce a complete reconstruction of the eigensystem Moreover QoS is often plotted versus buffer threshold sizes Therefore these parameters seem natural to a loop inside the calculation program The thresholds have different meanings for different fluid flow models and QoS parameters file D man gosthres htm Quality of service related parameters and thresholds Page 2 2 e Buffer less model Only one buffer related threshold is possible the buffer size 0 e Model with finite buffer o Loss probability A range of buffer sizes might be given for which loss probabilities are computed The range is upper bounded by the buffer size specification in 3 o Overflow probability of buffer threshold Buffer threshold values between 0 and the buffer size specified in 3 might be given for which the values of the complementary density function will be computed e Infinite buffer model o Overflow probability of buffer threshold Any non negative buffer threshold might be given for which the values of the complementary density function will be computed The range of thresholds is specified by 4 lower threshold minimal value default 0 this value is lower bounded by 0 and upper bounded by the upper threshold 5 upper threshold maximal value default 0 this value is lower bounded by the lower threshold and upper bounded by the buffer size 6
73. rate source code file f1s2mmr cc implements this case This long double calculation is even much slower about factor 100 compared to the standard calculation therefore it should only be used if the number of sources servers in one group exceeds 200 which is of course no hard limit but also influenced by a The difference in terms of stability are shown in Fie 97 4 6 Coefficients for finite buffer After the eigenvalues and eigenvectors have been determined the coefficients of the solution have to be calculated by solving the linear system of equations given by 4 9 and 4 10 4 6 1 Properties of the coefficients Some properties of the coefficients belonging to eigenvalues z and eigenvectors are listed in Table 4 4 The positive coefficients that belong to the unstable eigenvalues force 4 9 Fur thermore and together with 4 25 it becomes obvious that equilibrium states do not contribute to the solution at all 4 6 2 Deletion of critical states Due to 4 15 states with almost vanishing drift may cause 1 numerical underflow if the drift is slightly negative 2 numerical overflow if the drift is slightly positive The first problem may but the second problem does affect the solution procedure the numeri cal calculations collapse From Table 4 4 we know that the contribution of states with vanishing drift becomes arbitrarily small Therefore we mark all states that may not be used due to 40 CHA
74. rating system or hardware The typical end user system consists in a Windows PC 3 2 3 HTML based solutions An HTML based solution might use different technologies 1 Java client server solution A local Java applet or a Java script that is embedded in HTML page allows for interaction with the user and communicates with a Java application on the server that interacts with the C calculation program The calculation program should not be written in Java because this would lead to a dramatic slow down of the calcula tions Moreover some browsers still have problems with executing Java 2 Java client C socket solution Here the Java client communicates directly with the C calculation program via a socket which is the only difference to scenario 1 3 CGI Common Gateway Interface solution A local FORM that is embedded in a HTML document receives data from the user and activates a script batch shell or Perl e g on the server that calls the calculation program and sends HTML related output back to the client e g links to files that have been produced The advantage of scenario 2 consists in enabling the user to communicate with the calculation program in an interactive way However for standard applications such an interaction is not needed the next section contains a discussion of this topic Due to its universality and simplicity scenario 3 has been chosen The HTML code and the CGI script are easy to understand and modify F
75. robabilities t_state_pr_v and the flag vector load_v 4 8 2 Loss probability Based on the vector of probabilities that the buffer is full in different states full_v the function double RPMUXC loss_prob int type int part_en int inp rep int outp_en ff_c_go cc delivers e the individual loss probability 2 21 for a certain group of sources by specifying type number of the group e the total loss probability 2 22 by specifying type 0 e an error message and the value 0 if type refers to a server group This function uses the drift rate matrix i_crate_m and the flag vector 1oad_v 44 CHAPTER 4 FLUID FLOW ANALYSIS AND ITS IMPLEMENTATION 4 8 3 Overflow probability of a buffer threshold From 4 11 and 4 23 we obtain the complementary distribution function of the buffer content e fora finite buffer 0 lt x lt K as 1 Y ag K explzgx 4 35 e for an infinite buffer together with Table 4 5 as Y ay eo explz X 4 36 qeES This is carried out by the function double RPMUXC compl_distrib_total double x ff_c xd h that needs the vector of eigenvalues eval_v and the coefficient vector coeff_v Observe that the function does not perform any check on the value x for being reasonable Chapter 5 Results 5 1 Channel fading The first example considers one channel in a mobile environment that becomes partly unavail able due to channel fading or the correction of errors We assume that due to such une
76. robability of saturation 6 26ee 0 eed ri 43 48 2 Loss probability s seca raderat aa dies ee b S bee vd 43 4 8 3 Overflow probability of a buffer threshold 44 5 Results 45 Sl Channel radins Da o E AE oe A RS RS 45 5 2 da AE 47 6 CONTENTS 6 Summary and outlook 49 Bibliography 51 Appendix 53 List of files for building the executables 2 02 4 eee ee alee sta a Hee Re 54 Installation so 3 aS 6 eS Ges AAA AAA AAA 33 Confisuration 3 8445464244 8496438488234 848 a a aa as 56 Web pages and user manual sore e Ge 56 Chapter 1 Introduction The fluid flow model is a model that captures all kinds of effects that originate from time variable bit rates in all kinds of networks Its importance in communications came up at the same time as the Asynchronous Transfer Mode ATM was invented ATM offers an outstanding possibility to allocate network resources in a very flexible way and combining advantages of circuit and packet switched networks Especially for connection oriented traffic that exhibits variable bit rate VBR ATM is able to cope with so called over booking a link carrying a certain number of connections does not necessarily need to provide the total peak cell rate of all connections because each single connection does not need to use its full share of the link all of the time Indeed such a multiplexing gain is a very natural thing for packet switched networks especially when the packets share
77. rogram f_cmdln e less than about 500 for the long double version of the calculation program 1cmdin back file D man nostates htm Strange Quality of Service QoS Page 1 1 Strange Quality of Service QoS On the first glance strange QoS means e negative probabilities e probabilities larger than one e values that always stay zero Such values may appear in the buffered fluid flow models especially if e the number of sources and servers become large which leads to a large state space e the number of sources of one group or servers reaches the magnitude of 200 or 500 for the long double variant a large finite buffer size occurs e the lowest service rate is still larger or equal to the highest data rate from the sources In the case of one or more CBR servers the latter is called peak rate allocation To find out about the weak borders for numerical stability please e reduce the number of sources and or servers e reduce the buffer size e reduce the server rate s so that the total input rate has the chance to exceed the server rate Sometimes a strange QoS is not obvious Therefore it is recommended to countercheck critical results with fluid flow simulations or numerical integrations of the differential equations Typical hints that a system gets into numerical trouble are e Small variation of input parameters lead to large QoS variations e Trends are not unique If all other parameters remain c
78. rred An invalid server type characterization has occurred A non numeric specification of the number of servers has occurred A negative number of servers has been given A non numeric specification of the server low state data rate has occurred A negative data rate for the server low state has occurred A non numeric specification of the server high state data rate has occurred A data rate for the high state has been specified that 1s not larger than the data rate for the server low state A non numeric specification of the transition rate from server low to server high has occurred A non positive transition rate from server low to server high has occurred ee eee 14 20 14 20 NS y D A 15 21 16 22 16 22 17 23 17 23 18 24 18 24 30 19 25 31 19 25 31 w NN Se v Y N 2 a ed a 92 Page 3 4 Choose a positive number Choose a positive number Choose either cbr or vbr2 Choose a positive integer Choose a positive integer Choose a non negative number Choose a non negative number Choose a non negative number Choose a data rate that is higher than parameter 17 23 30 or choose the CBR property Choose a positive transition rate Choose a positive transition rate Error codes 33 Transition rate not a number 34 Positive transition rate required 35 Type of output not available 36 Error i
79. t and over load states 212 264 24224624244 17 2 7 2 Zero drift and equilibrium states d p 0 2 4 desea Ge es 17 2 7 3 Negative drift and under load states 17 2 7 4 Loss and its distribution 44 8 amp 5 aa RA a ORS a oe 17 2 7 5 The roles of sources and servers 2 224 ee add bv SRLS EES EX 17 2 8 Model variants and load conditions o 18 281 LCoaddefnition ss s g e AREA HY 18 2 8 2 Model with infinite buffer 2 cra eae See gk ee 18 2 8 3 Model with finite buffer 2 4 2 2 2446542863546 344084 18 2 8 4 Buffer less model 2 9 Quality of Service related parameters 2 9 1 The Fluid Flow Calculator 3 1 Graphical User Interface GUI 3 1 1 3 1 2 Alternatives 3 2 The web compute server concept 3 2 1 3 2 2 The clients 3 2 3 HTML based solutions 3 3 Software components 3al 3 3 2 CGI script ffcout cgi 3 3 3 The original interactive calculation program ffc 3 3 4 The command line calculation program ff cmdln 3 4 Output format 3 5 Long double versions Fluid flow analysis and its implementation 4 1 Objects 4 1 1 4 1 2 4 1 3 4 1 4 4 2 General functions 4 2 1 4 2 2 Load calculation Probability of saturation 2 9 2 Loss probability 2 9 3 Overflow probability of a buffer threshold HTML form page ffcalc htm Calculation object Sources object General objects User input verification CONTENTS CONTENTS 5 42 3 Size of the state s
80. t files for each new calcula tion series and the need for editing all these files imply a lot of effort as well as possibilities to introduce erroneous values As the program has been designed primarily for human interaction the call from a batch file with erroneous input files could result in program instability and large amounts of useless data on the harddrive The files from which ffc is to be built are listed in the appendix 3 4 OUTPUT FORMAT 27 3 3 4 The command line calculation program ff_cmd1n Both the specific disadvantages of the command line user interface for batch jobs and the ob servation that certain popular paths exist along which such a program is used led to a new concept used in the program ff_cmdln The input data is not read by the program via input files containing commands and values for the user interface but via the program call itself as command line parameters This concept has several advantages e Due to the limited number of paths through the program i e the fixed semantics it becomes feasible to check for reasonable input values e Input errors can be fixed in the batch file without having to open and edit one more input file e Other programs may call ff cmd1n without having to write a file containing the necessary commands first It has to be stretched that the same calculation program might be used both with the GUI and with batch programs Furthermore ff_cmdln and ffc are built from
81. that loss merely occurs under the following conditions e The system is in an overload state e The buffer is full Loss is distributed in a fair way among the groups which is based on their momentary input rate The loss rate becomes r Ls ris F ds 2 17 Ss The application of this principle to one group shows that loss is distributed evenly between the information streams belonging to that group However information streams of different groups may experience different loss probabilities 2 7 5 The roles of sources and servers From definitions 2 15f it becomes clear that from the drift point of view it does not matter whether the total input rate rises or sinks by Ar of the total service rate sinks or rises by Ar The servers act as sources with negative data rates This has been one of the reasons for choosing our symmetrical notation However this symmetry does not hold for everything servers do not experience any loss 18 CHAPTER 2 THE FLUID FLOW MODEL 2 8 Model variants and load conditions 2 8 1 Load definition The offered load is defined as the ratio of the total mean input rate and the total mean service rate to which the different groups of sources contribute in an additive way amp wt 2 A ay A 2 18 j 1 m m i 1 i 2 8 2 Model with infinite buffer The buffer is not of limited size K Thus there is no loss at all but on the other hand queuing delays might get extre
82. threshold step size between successive thresholds default 1 this value has to be positive to avoid endless loops Both lower and upper thresholds are modified automatically if necessary followed by a warning Non numerical inputs lead to errors 4 5 or 6 while a non positive step size throws error 7 back file D man qosthres htm Sources Page 1 2 Sources 7 A group of sources contains sources with similar characteristics and is defined by choosing a type CBR or VBR 2 state from the corresponding type list Groups of sources have to be defined one after another without gaps between them A group i ID in the table whose type is marked with is treated as not being defined this is the default for each group Valid definitions are e Group alone e Group and 2 e Group 1 2 and 3 From these definitions the number nN of groups of sources is calculated Invalid definitions are Group 1 and 3 Group 2 alone Group 2 and 3 Group 3 alone Definitions that include gaps throw an error This error is unnumbered because this problem only appears in connection to the GUI 7 Ifa Quality of Service QoS has been chosen that might be related to a group of sources e g the loss probability then the group for which the QoS should be determined might be selected via the corresponding radio button For the probability of saturation and the overflow probability of a certain buffer threshold such a setting has no meaning T
83. tput file Output file The output of the calculation program is written to a file The format of this file is such that e it might be imported into MS Excel for further processing e g for producing graphical output e it might be used to produce PostScript files with gnuplot The columns of this file are described in the section Output files 20 The name of the output file has to be given To simplify the handling of output files on 21 Windows computers the length of the name has been limited to 8 characters A default name ffcout is provided However this file name should be used with caution if more than one user uses the program at the same time An extension XIS is attached automatically This has the advantage that on Windows computers MS Excel can be started within the browser window just by clicking on the file name after the file has been produced One of the following radio buttons is used to specify the kind of output that is desired a New file PostScript First a new output file is written including the header line that contains abbreviations for the different columns A file that has been existing under the same name before is overwritten without check and warning This makes it easy to replace erroneous calculations but might be quite dangerous if different users use the same file name The required steps to import the data into Excel are described under the corresponding keyword The file is also displayed s
84. ually represents a remote user accessing the web server should be allowed to carry out all the scripts and programs as well as to access and write files in the corresponding directory Besides the code attached to this project see section 3 3 the server requires access to or instal lation of the following software e a Perl interpreter e a C runtime library for the execution of the calculation program e the public domain plot program gnuplot if PostScript output is desired More on installation and application is to be found in the appendix On the other hand the concept of a web compute server implies that this server should be able to carry out more than one calculation process at the time For contemporary computers and operating systems this should not be any problem But the more processes are carried out at the same time the longer each calculation takes Therefore it is recommended to limit the user group that might connect to a certain web compute server 24 CHAPTER 3 THE FLUID FLOW CALCULATOR 3 2 2 The clients The role of each client 1 e browser consists in representing the GUI to the user while the server is almost relieved from that besides from producing the HTML code to be displayed by the browser The concept allows more than one client connecting itself to the server at the same time The clients themselves Microsoft Explorer or Netscape Communicator e g work almost independently of the underlying ope
85. urthermore the CGI script is compiled by Perl on the fly which means that the only program to be compiled manually in case of a change is the calculation program itself The parts of the software are described in the following section 3 3 Software components 3 3 1 HTML form page ffcalc htm The main tasks of the HTML form page consist in providing the GUI for collecting user input and in sending this input to the CGI script The latter is done via the POST facility 1 e the script is called with a couple of command line parameters that are determined by the variables 3 3 SOFTWARE COMPONENTS 25 used in the HTML form Observe that different browsers might send the information in different orders the script ffcout cgi will have to take care of this The following variable types have been used e select choose from list of items input ASCII text in general e radio choose from a couple of possibilities submit and reset button All the fields are initialized with default values The user may fill in the fields which mostly require numerical input or choose options being offered in whatever order s he wants The structure of the page is as follows 1 The Quality of Service the fluid flow model and the buffer related thresholds have to be chosen 2 The groups of sources and their parameters have to be defined 3 The servers have to be specified 4 The desired kind of output has to be chosen The button resets
86. very important that state O exhibits the strongest negative and state v 1 the strongest positive drift Therefore r0 lt r1 has to be guaranteed when creating the source objects In the program eigenvalues are marked as being oo by explicitly setting them to FF_D_B_OVER ff_const h Section 4 7 will reveal that for infinite buffer only the negative eigenvalues are needed in this case the program sets the positive eigenvalues also to oo and thus skips the calculation of the corresponding eigenvectors Making use of a generating functions approach for the eigenvectors see Ani 82 Kos 84 Ste 91 Fie 97 et al the other eigenvalues might be obtained from formula whose order is given by the two times the number of VBR 2 state groups of servers and sources Carrying out this analysis is only feasible for one such group as one group of VBR 2 state sources in combination with one group of VBR 2 state servers already leads to equations of order four to be solved Even though a closed solution exists its implementation is much too complicated 36 CHAPTER 4 FLUID FLOW ANALYSIS AND ITS IMPLEMENTATION The analysis of two or more groups of VBR 2 state sources in combination with one group of VBR 2 state servers needs to be carried out numerically anyway and way to do this will be described in the following subsections The determination of eigenvalues is performed by the functions int RPMUXC eigensys int chk_en i
87. x class IMATRIX integer index vector class IVECTOR matrix class MATRIX vector class VECTOR source server base class RPbaseC CBR source server class NRPC VBR on off source server class NIRPC VBR on off source server class NIRPC VBR high low source server class NMMRPC VBR high low source server class NMMRPC VBR Poisson test class ooIRPC VBR Poisson test class ooIRPC ae ad utility for compilation S lincludes methods for solving linear systems of equations 2for notions see Fie 98 3calls gnu compiler g 4calls Sun compiler CC links in sunmath library 55 Installation The web compute server requires the following files in the WWW_home_directory e g www or wwwroot that is to be found under http Server_address WWW_home e the HTML forms ffcalc htmand ffcalcl htm the CGI script cout cgi and ffcoutl cgi the executables f _cmdln exe and fflcmdin exe the Gnuplot executable UNIX LINUX gnuplot Windows 95 98 NT wgnup132 exe in the directory man the HTML manual and help files index htm root file usage htm units htm gosthres htm 1 2 3 4 5 sources htm 6 servers htm 7 output htm 8 excelgnu htm 9 errcodes htm 10 load htm 11 warnings htm 12 nostates htm 13 strange htm 14 software htm 15 param htm 16 websconf htm 17 securadm htm only if the long double version of the calculation program is available 56 APPENDIX Configuration
88. xpected error conditions the channel bit rate sinks temporarily to merely 50 of its original bit rate which is the same than that of the source when transmitting J 0 5 h 7 The source has on off characteristics with a low activity factor of a 0 01 and a certain mean cycle time t while the probability that the channel server has its full capacity may vary between 0 5 and 0 9 and the mean cycle time of the channel may deviate from that of the source by several orders of magnitude The Quality of Service QoS related parameter is the loss probability More information can be obtained from a conference paper Fie 00b that is one of the basic results from this project We shall now look at some results The figures have been produced using gnuplot s eepic in terface and modified afterwards Figure 5 1 demonstrates which influence the ratio of the mean cycle times of servers and sources has on loss probabilities Especially when the probability that the server is fully available is quite high the loss probability varies by about eight orders of magnitude between 107 and 107 A low loss probability is obtained if the server s cycle time is much shorter than that of the source However if the mean cycle time of the server becomes equal or larger than that of the source the loss probability reaches quite high values For QoS a slowly varying channel capacity with quite long channel low times represents a danger which should

fulltext - DiVA Portal

Contents

Download Pdf Manuals

Related Search

Related Contents