Home

TR-Definition of a general and intuitive loss model for

Contents

1. Ihe eno cose euo o eae eor eoa e o soU eaae eco EOE 63 Page 1 of 70 General and Intuitive Loss Model and Netem Introduction netem is a module of Linux kernel that provides Network Emulation functionality for testing protocols by emulating the properties of wide area networks The current version emulates variable delay loss duplication and re ordering It has already been pointed out see for example 9 that the generation of loss with correlation is not working properly in the current version of Netem Starting from this consideration in this work we have e provided evidence of the weakness of correlated loss implementation e introduced a new loss model which integrates and complements several loss models available in the literaure e implemented the loss generation according to the proposed model within the module sch_netem e added new option in tc netem We first realized a patch that introduced new correlated loss models to netem The patch applied to Linux kernel 2 6 32 and iproute2 2 6 32 package On 18 Dec 2009 we have submitted a patch to the netdev veger kernel org mailing list in order to have NetemCLG included in the netem kernel module and in the iproute2 utilities The patch has been reworked and applied to kernel 2 6 39 while the needed changes to iproute2 have been added to iproute2 3 2 0 The version that has been included in kernel 2 6 39 and iproute2 3 2
2. 25 7 NETEMCLG IMPLEMENTATION eee eren ee eo tone etta pose etta sese Posee eto Pese toos eee etta 26 T L NETEMGEG AND TC NETEM PATCHES 2 recor eei eie re P des eerte Pe e Hae re odere 26 7 2 TC NETEM USER MANUAL FOR NEW 26 13 NETEMCLG CODE ENHANCEMBNTS 35 ted RE ERRARE ECHO Re ROI rre OU Ideo 30 8 TESTING THE PROPOSED LOSS 39 8 1 SQNGEN LOSS SEQUENCE 39 8 2 BUILDING SQNGEN E 39 8 3 STATISTICAL ANALYSIS OF GENERATED LOSS 50 8 4 GENERATED LOSS PROBABILITY 075 54 9 TESTING IN THE KERNEL SPACE 2 2 01 too Posee Pon e toos teta Posee Pose 58 9 1 TRACE2SEQ GENERATING LOSS SEQUENCES FROM TRACES isses nennen nennen nennen 58 9 2 COMPILE TRACE2SEQ AND SQNANALYZER 58 93 HOW TO USE TCPDUMP eter eee meet tee e e me aea en 58 9 4 SONANALYZER SEQUENCE nennen 59 9 5 COMPARISON OF STATISTICAL ANALYSIS BETWEEN USER AND KERNEL SPACE 60 9 6 GENERATED LOSS PROBABILITY PLOTS 62
3. e density 100 num of isolated drops bis length e pisol 100 length of all good bursts bis num of good bursts bis e mean length of good burst where ploss is the ratio between the number of losses and the length of the sequence piso is the ratio between the isolated losses and the length of the sequence mean length of burst is the ratio between the number of losses within the bursts and the sum of the length of all bursts in which the system have been during the sequence generation process The mean length of good burst formula is analogue to the previous one Once have calculated the parameters they will printer to screen stored in the apposite arrays in sample position and save to text files as we will seen ahead 7 2 3 2 External blind check function void external blind check int length int gmin max int sequence int sample float ploss ter float mean length of burst ter float density ter float pisolated loss ter float mean length of good burst ter In this second check the GI parameters are calculated performing an analysis of the sequence looking through the array where it was stored We call this external because the check is done outside of the generation algorithm and also blind because it leaves aside from any information different from the sequence itself The function gets in input the length of the sequence ength the maximum value of g
4. the variables relatives to the transition probabilities and the GI parameters are initially set to the default values Then the mandatory p parameters and if specified the optional parameters are read from keyboard and stored to the appropriate variables If the query mode is the 4 state transition probabilities are calculated and printed to the screen together with the correspondent GI parameters If the query mode is disabled the transition probabilities are passed to the kernel 055 structure J else if stremp argv gimodel NEXT double p13 0 double p31 1 double p32 0 double p23 1 double p14 0 double p 0 double 0 double density 1 double 0 double good burst length 1 if parse percent amp p argv explain loss gimodel p return 1 j int input params 1 counts the number of input parameters Page 36 of 70 General and Intuitive Loss Model and Netem if NEXT IS NUMBER NEXT input params burst strtod argv char NULL if NEXT IS NUMBER NEXT ARG input params if parse percent amp density argv explain loss gimodel density return 1 if p gt density printf nError p gt density n break if burst density lt 1 print nError burst density lt break ifiNEXT IS NUMBER NEXT input params if parse percent amp p
5. dile er all 14 cx tici 1 r htr h _ r 1 h rh r l A rh D RS x 5n nn As for the loss density within the burst we have to take into account that the density increases as all the loss events are concentrated in the burst that have at least one loss and that the length of these corrected bursts E B is shorter than the default burst length in the Gilbert Elliot model E B As we have done for the burst length we call p the default burst density that corresponds to the loss probability in the Bad state Let us define N the number of Gilbert Elliot burst in an arbitrary interval and N the number of corrected burst in the same interval The following equation holds pE B N pE B N pE B N therefore we can evaluate E SY We can now evaluate the ratio considering the probability that a Gilbert Elliot burst is also a corrected burst gt 0 1 0 1 4 1 A 1 h rh N 1 1 _1 h rh N Page 20 of 70 General and Intuitive Loss Model and Netem Therefore the density is 1 pE B N m 1 h rh 1 hrh 1 h r l1 h rh We can also find the relations between the transition probabilities and the Gilbert Elliot 4s parameters Pass r 1 k P P14P23P31 ptr P2
6. Finally the following figure show the last example with a sequence generated from 4 state model with parameter p13 5 and p31 20 sudo tc qdisc add dev wlan0 root netem loss state 5 20 daniele daniele Satellite L300 trace2seq 2000 La sequenza stata generata daniele daniele Satellite L300 sqnanalyzer sequence txt The sequence is 000111111000000000000000000000000000000000000000001 11111111110000000001 1 10000000000000000000000 00000000000000000000000000000000000000000001000000000000000000000000001 100000000000000000000000 00000000000000001011111111111110000000011111110000000000111111111110000000000000000000000000000 00000000011111111000011110000000000000000000000000000000000000111111000000111111111000000000011 10000000000000000000000000000000000001000000011111111000000000000000000000000000000000000000000 000000000000001111000000000000000000001000000000000010000000000000000001 10000000000000000000000 0000000000000000000000000000000000000000000001 1 100000000000000000000000001 1 11000000000000000000 00000000000000000000000000000001 1 1 110000000000001 100001000000001 1111101000000000000000000000000 0000000000001 1110000011001 1 1 110000000000000000000001 1 1 100000000000000001 111 1111000000000001 1000 001111111111110100000111111000000000110000000000000000000001 1000000000000000 1000000000000000000 00000000000000000000000000000000000000000 100000000000000000010000000000001 10000000000000000001 1 100001000000000000000000000000
7. P5 Te h l4r r l h hr pi 70 4 1 3 Revisiting the Simple Gilbert model The Gilbert model can be simplified setting h 0 In this way the Gilbert model becomes the same of the 2 state Markov model and is able to represent only consecutive burst losses This is also called Simple Gilbert model 11 Note that in this case there are no ambiguities with the burst definition because when the system is in the burst condition we will have only losses and no transmissions So in this case it is not needed to define special cases to make the model equivalent to the GI The Simple Gilbert Elliot seen introduced in Section 4 1 3 is equivalent to the 2 state Markov So we have the following relation E Pis r P Page 22 of 70 General and Intuitive Loss Model and Netem 4 2 Relations between models As we have widely explained the proposed GI General and Intuitive model and the underlying 4 state Markov model include all the others described model as particular cases The following table shows the features of all the models in terms of what type of losses they can describe MODEL GI STATES NUMBER OF BURST BURST ISOLATED BURST LOSSES LENGTH DENSITY LOSSES CORRELATION PARAMETERS PARAMETERS GI model 4 5 Yes Yes Yes Yes 4 state Markov Piso E GB Simple Gilbert Pross E B 2 2 Yes No No No Bernoulli Pross 2 1 No No No No Table 1 Features of GI loss
8. 0 d p13 pisol p burst pisol 1 density p pl3 p burst 1 density p p31 1 burst density good burst length 1 23 else input_params 2 p14 0 p32 0 p23 1 pisol 0 density 1 p13 p burst 1 1 p p31 l burst input_params 1 014 0 p32 0 23 1 pisol 0 density 1 13 31 1 burst 1 31 if query Df printf nTransition probabilities are n printf 3 is 3f 100 p13 Page 38 of 70 General and Intuitive Loss Model and Netem jelse printf p31 is 3f 100 p3 1 printf p32 is 3f 100 p32 printf p23 is 3f 100 p23 printf p14 is 3f n 100 p14 printf GI General and Intuitive parameters will be is 3f 100 p printf nburst is 3f burst printf density is 3f 100 density printf isolated ploss is 3f 100 pisol printf good burst length is 26 3f n good burst length loss type NETEM LOSS GI set percent amp gimodel p13 p13 set percent amp gimodel p31 p31 set percent amp gimodel p32 p32 set percent amp gimodel p23 p23 set percent amp gimodel p14 p14 loss gemodel the Gilbert Elliot model or one of its special cases Gilbert Simple Gilbert Bernoulli will be used In this case there is no need to co
9. 4 3 0 1 E GB 4 P23 In order to evaluate E B we introduce two auxiliary variables and E that will be useful to calculate the average burst length System stays in State 2 for an average time E that is equal to the average duration of a good sub burst within a burst and in State 3 for an average time E that is the average duration of a loss burst gud jc The average length of the burst is 5 z n E P31 P32 _ 331 P32 _ T Pos 0 P31 t P32 P31 P32 P31 P23P31 Solving the system we obtain the transition probabilities Py as P 2 P13P23 Pi4P23P31 Das 1 P23P31 Pi4P23P31 P13P32 E B p T P 4P23P31 2 Poss Psor ISOL FS n TM TA Py4P23P31 7 P23P31 1 Psor Xo T 1 curo P13P23 gt P23 7 FT P13P32 E GB P c l p E B 222223 P23P31 p E GB 1 P E GB i 1 Psor Page 8 of 70 General and Intuitive Loss Model and Netem where we substitute 75 m4 with the expressions in function of the transition probabilities found above The validity of this model is subject to the following constraints E B gt 1 Piso lt Pross Pross lt Pzoss Piso E B 1 p Pzoss E GB 21 E GB gt 1 p p Pisor 1 2 3 2 2 Independent loss events withi
10. It is able to model a system with consecutive loss events which can be characterized by a loss probability and a burst duration d Page 13 of 70 General and Intuitive Loss Model and Netem The other two parameters are h 0 1 k 0 3 3 3 Gilbert model The Gilbert model has two states Good and Bad and three independent parameters Within the Good state packet are never lost while within the Bad state there is a probability h that the packet is transmitted This is able to model the system in which the loss events appear in burst but within the bursts there are some transmitted packets and some loss packets ER A good way to characterize this system is to consider a loss probability a burst duration and a loss density within the burst loss density 1 h If the loss density is 100 h 0 the model becomes equivalent to Simple Gilbert The only other parameter is 1 0 3 3 4 Gilbert Elliot model The Gilbert Elliot model has two states Good and Bad and four independent parameters In this case it is possible to have loss events also in the Good state with probability 1 k Therefore k is the probability that the packet is transmitted while the system is in Good state If k 1 the model becomes equivalent to the Gilbert model Page 14 of 70 General and Intuitive Loss Model and Netem 1 ieee uan r The Gilbert Elliot model can be
11. length of burst corresponds to the mean time the system is in State 3 so E B hen the 31 transition probabilities are 1 Pu 4 E B gt E B EE P Loss P31 E B 1 P Page 11 of 70 General and Intuitive Loss Model and Netem 3 2 5 Bernoulli model model with 1 parameter p13 1 p13 p13 1 p13 Figure 6 The Bernoulli model as a Markov chain If we consider the special case of a 2 state Markov where the r parameter depends on p by the relation r 1 p we obtain the Bernoulli model At this point the Bad state collapses on the Good one so we can see this model as a 1 state Markov chain with an only independent parameter The Bernoulli model is the simplest case of loss model we consider It has only one parameter and can be see as a special case of the Simple Gilbert model where r 1 p So the only significant GI parameter is the loss probability Pross p So we have Pios 1 P Loss 3 3 Gilbert Elliot Model 3 3 1 Bernoulli model The Bernoulli loss model has two states and only one parameter the loss probabilities p This model is only able to model uncorrelated loss events Page 12 of 70 General and Intuitive Loss Model and Netem E m Since p is the only parameter the system is described as follows h 0 1 k 0 3 3 2 Simple Gilbert model The Simple Gilbert model has two states and two independent parameters p and r
12. 0 5 20 50 0 0 504 0 0040 0 126 20 148 50 093 0 2 095 2 10 100 0 01 1 999 0 01597 0 063 10 019 100 0 0092 0 2 10 80 0 01 1 987 0 01118 0 053 9 864 80 0142 0 0096 1 284 2 10 50 0 01 2 011 0 0059 0 038 10 018 49 997 0 00907 2 252 Table 11 Statistics for the GI model using 3 and 4 states 7 4 Generated loss probability plots We will now show a series of plots to evaluate the loss generator accuracy using the same simulation data of Section 7 3 Each plot for a fixed input loss probability and density shows a line joining the mean loss probability values that correspond to different input values of burst length The error bars represent the standard deviation Page 57 of 70 General and Intuitive Loss Model and Netem 2 2 2 15 2 1 2 05 Mean_Ploss Ploss 2 Density 100 5 10 20 length of burst input Ploss input 055 generated Figure 9 Generated loss probability 2 6 versus burst length Density 100 The first plot was made using a 2 state model specifying the two GI parameters Pross and E B The experimental values as seen in the previous sections are consistent with the theoretical ones The size of the confidence interval depends on the chosen burst length In fact the standard deviation becomes higher if we consider longer bursts resulting in a stronger variation of Pross Page 58 of 70 General and Intuitive Loss Model and Netem 2 2 2 15 2 1 2 05 Mean Ploss Plos
13. 0 in the sequence when arriving to the end of the sequence itself e If this_is_burst false so we are outside the burst o Ifk th value is the last of the sequence is 1 we have an isolated loss so the variables num of drops and num of isolated drops are increased o Ifk th value is land the following is still 1 according to the definition we entering in a new burst and we have its first loss event The values of the variable I this is burst is set to true and the variable num of drops num of burst drops length of all bursts num of bursts are increased o Ifthe k th value is 1 and the following is 0 we have a isolated loss event so the variables of drops and of isolated drops are increased At this stage the GI parameters are calculated through the formulas seen for the internal check s case Then they are printed to screen stored in the arrays and saved to text files Inside the arrays every value is put at distance sample j i 1 from the other where i log 2 1 in max and j log 1 In this way we use unique one dimensional array instead of a two dimensional array in which the index i j would represent the values of sample and gmin 7 2 3 3 Statistics function void statistics int num of samples float ploss float mean length of burst float density float pisolated loss float mean length of good burst int gmin int gmin max The statistics function charact
14. 1 break case 2 if rnd lt clg gt a5 clg gt state 3 return true jelse clg gt state 2 break case 3 if rnd lt clg gt a3 clg gt state 2 else if clg gt a3 lt rnd amp amp rnd lt clg gt a2 clg gt a3 clg gt state 1 J else if clg gt a2 clg gt a3 lt rnd clg gt state 3 return true break case 4 clg gt state 1 break return false Page 32 of 70 General and Intuitive Loss Model and Netem the oss gilb ell generator function it generates losses according to the Gilbert Elliot loss model or its special cases Gilbert or Simple Gilbert The function makes a comparison between the return value of the net random function and the transition probabilities outgoing from the current state then decides the next state A second random number is extracted and the comparison with the loss probability of the current state decides if the next packet will be transmitted or lost static bool loss gilb ell struct netem sched data q struct clgstate clg amp q gt clg switch clg gt state case I if net_random lt clg gt al clg gt state 2 if net_random lt clg gt a4 return true break case 2 if net_random lt clg gt a2 clg gt state 1 if clg gt a3 gt net_random return true break return false e the following code to the netem_enqueue function It calls depending on what model is selected one of the functions d
15. 2 300 Mean_length_of_good_burst 0 000 INTERNAL CHECK STATISTICS d hese the mean values oss 1 850 mean length of burst 0 000 density nan pisol 1 850 mean length of good burst 0 000 hese are the variance values oss 0 405 mean length of burst 0 000 density nan pisol 0 405 mean length of good burst 0 000 hese are the standard deviation values 055 0 636 mean length of burst 0 000 density nan pisol 0 636 mean length of good burst 0 000 These are the variation coefficients ploss 0 344 mean length of burst nan density nan pisol 0 344 mean length of good burst nan EXTERNAL CHECK STATISTICS For gmin 2 These are the mean values ploss 1 850 mean length of burst 0 000 density nan pisol 1 850 mean length of good burst 0 000 These are the variance values ploss 0 405 mean length of burst 0 000 density nan pisol 0 405 mean length of good burst 0 000 These are the standard deviation values ploss 0 63696 mean length of burst 0 000 density nan pisol 0 636 mean length of good burst 0 000 These are the variation coefficients ploss 0 344 mean length of burst nan density nan pisol 0 344 mean length of good burst nan For gmin 4 These are the mean values ploss 1 85096 mean length of burst 0 000 density nan pisol 1 850 mean length of good burst 0 000 Ba nese are nese are nese are he variance values loss 0 405 mean_length_of_burst 0 000 density nan pisol 0 405 mean_lengt
16. defines the beginning and the end of the bursts external_blind_check estimates the five GI General and Intuitive analyzing the generated sequence without using any extra information The check is repeated using different values of gmin which is the maximum number of zeros between two ones that identifies a burst Statistics calculates mean variance and coefficient of variation for the five GI General and Intuitive parameters arg error manages the errors concerning argument number or wrong format main is the main function that is executed when the program is launched It manages the input parameters parsing and calls the other functions The functions will be now described one by one Page 43 of 70 General and Intuitive Loss Model and Netem 7 2 2 2 Sqn_gen function GI sequence generator void sqn gen gsl rng q char sequence int length unsigned int p13 unsigned int p31 unsigned int p32 unsigned int p23 unsigned int p14 This function is a sequence generator based on the GI General and Intuitive loss model It is implemented through a for loop repeated for a number of times equal to the length of the sequence The first step is the extraction of a pseudorandom number with uniform distribution This is made through the net random gsl rng q function that generates the number through the gs rng get function of the GNU Scientific Library 1 5 that implements a Tausworthe generator The algorithm e
17. for small values of gmin The question is mirror to the burst length case if we choose to generate a small value of burst length we get a sequence with short bursts so the estimation will be good only for comparable values of gmin Page 68 of 70 General and Intuitive Loss Model and Netem References 1 2 3 4 5 6 7 8 9 10 11 12 13 Gilbert E N Capacity of a Burst Noise Channel BSTJ September 1960 Elliot E O Estimates of Error Rates for Codecs on Burst Noise Channels Bell System Techical Journal 42 1963 1977 1997 Clark A Modeling the Effects of Burst Packet Loss and Recency on Subjective Voice Quality IPtel 2001 Workshop Yajnik M Sue Moon Kurose J Towsley D Measurement and modelling of the temporal dependence in packet loss INFOCOM 99 Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies Proceedings IEEE ITU T SG12 D 139 Study of the relationship between instantaneous and overall subjective speech quality for time varying quality speech sequences France Telecom VoIP Troubleshooter http www voiptroubleshooter com indepth burstloss html T Friedman R Caceres A Clark Eds RTP Control Protocol Extended Reports RTCP XR IETF RFC 3611 Hemminger S Network Emulation with NetEm Open Source Development Lab April 2005 http devresources linux foundation org shemminger netem LCA2005 paper p
18. generated sequence has the following characteristics from sequence analysis P loss 20 050 Mean length of burst 9 120 Density 85 088 P_isol 0 650 Mean length of good burst 3 579 For GMIN 16 the generated sequence has the following characteristics from sequence analysis P loss 20 050 Mean length of burst 19 471 Density 59 063 P_isol 0 500 Mean length of good burst 6 949 For GMIN 32 the generated sequence has the following characteristics from sequence analysis loss 20 050 Mean length of burst 52 750 Density 37 441 1501 0 300 Mean length of good burst 11 579 For GMIN 64 the generated sequence has the following characteristics from sequence analysis loss 20 050 Mean length of burst 612 667 Density 21 763 1501 0 050 Mean length of good burst 18 203 For GMIN 128 the generated sequence has the following characteristics from sequence analysis P loss 20 050 Mean length of burst 1997 000 Density 20 080 P_isol 0 000 Mean length of good burst 19 463 8 5 Comparison of statistical analysis between User and Kernel space 8 5 1 Statistics for the GI model using 2 3 and 4 parameters In this section we reconsider the full GI model using 2 3 and 4 parameters Pross E B Density We will calculate the user space value through the sqngen program and the value of kernel space using sqnanalyzer Both methods calculate the results for different value of the gmin The number of experiments i
19. is not used in internal check that is unique However to maintain the same format for all the lines we will show N A in Emin fields relative to internal check The example in Section 7 2 3 5 leads up to the following lines of data dat and statistics dat 1 2 1000 4 loss_phys 2 10 80 2 N A 2 000000 0 000000 nan 2 000000 0 000000 2 2 000000 0 000 000 nan 2 000000 0 000000 4 2 000000 0 000000 nan 2 000000 0 000000 2 2 1000 4 loss_phys 2 10 80 2 N A 2 400000 0 000000 nan 2 400000 0 000000 2 2 400000 0 000 000 nan 2 400000 0 000000 4 2 400000 0 000000 nan 2 400000 0 000000 intenal N A 2 1000 loss phys 2 000000 10 000000 80 000000 2 000000 N A 2 200000 0 000000 nan 2 200000 0 000000 0 080000 0 000000 nan 0 080000 0 000000 0 282843 0 000000 nan 0 282843 0 000000 0 128565 nan nan 0 128565 nan external 2 2 1000 loss phys 2 000000 10 000000 80 000000 2 000000 N A 2 200000 0 000000 nan 2 200000 0 000000 0 080000 0 000000 nan 0 080000 0 000000 0 282843 0 000000 nan 0 282843 0 000000 0 128565 nan nan 0 128565 nan external 4 2 1000 loss phys 2 000000 10 000000 80 000000 2 000000 N A 2 200000 0 000000 nan 2 200000 0 000000 0 080000 0 000000 nan 0 080000 0 000000 0 282843 0 000000 nan 0 282843 0 000000 0 128565 nan nan 0 128565 nan Note that means not applicable 7 3 Statistical analysis of generated loss sequences In this section we evaluate the performance of our loss generator considering the size of the confidence i
20. models and its special cases 5 Definition and identification of a burst Intuitively a Bad burst is a period during which a high proportion of packets lost When a Bad burst can included transmitted packets there is the problem of delimiting the burst In fact it is possible that a single burst contains a sequence of transmitted packets in the middle so that it can be interpreted as two different bursts On the other hand it is possible that two different bursts are separated by only one or two transmitted packets so they can be merged in a single Bad burst In 7 a formal definition of a burst is given A burst is defined in terms of a value gmin as the longest sequence that starts with a lost or discarded packet does not contain any occurrences of gmin or more consecutively received and not discarded packets and ends with a lost or discarded packet Therefore the delimitation of bursts on an observed sequence of received lost packets depends on the choice of the gmin value This means that when we generate a received loss sequence using the GI model the average length of the burst E B evaluated with a given gmin value will not exactly match the input E B parameter In particular if gmin is small and the loss density in the burst is not high there will be a higher probability of splitting a burst into smaller bursts gt E B tends to be smaller than the input If gai is large there is an higher probability o
21. models with the evaluated GI parameters We found that the parameters evaluated by generated loss patterns are in accordance with our analytical models 4 1 1 Revisiting the Gilbert Elliot model In order to relate the classical Gilbert Elliot model and the 4 state model we put ourselves under the condition of independent loss events during the burst Roughly speaking states 1 and 4 correspond to the Good state in Gilbert Elliot States 3 and 2 correspond to the Bad state Note that the Good state is more properly a low loss state 6 The main difference is that transition from Bad to Good can happen in the Gilbert Elliot after either a loss o a transmission event while in 4 state model the transition can only happen after a loss event and this is needed in order to properly evaluate a burst length i e starting from a loss event and ending with a loss event The second difference is that in the Gilbert Elliot model it is possible to have two consecutive isolated loss events while in the 4 state model an isolated loss is always followed by a transmission Our goal in this section is to define a special case of the GI model whose behavior is very similar to the Gilbert Elliot one and to evaluate its parameters as a function of the Gilbert Elliot parameters We refer to it as the Gilbert Elliot 4s model Let us consider the loss patterns produced by the Gilbert Elliot model If we consider a burst length ignoring that the
22. of loss gimodel the 4 state generation algorithm will be used In the case of loss 4state the transition probabilities specified as input are directly passed to the algorithm while for the other options the input parameters are mapped to the 4 state transition probabilities and passed to netem thought the netlink socket The conversion formulas are shown in the following table Transition Loss gimodel probability Ds Psor E B 1 EH Psor T nd P31 1 E B p E B i E B 1 P32 p 1 E B p 1 p 1 E B Psor Psor Table 3 Relations between options and models in tc netem2 Page 25 of 70 General and Intuitive Loss Model and Netem Only one of the three different labels add change and del has to be chosen add is used to initialize a new option change to set new parameter s value s and del to remove already set parameters with a previous command Moreover the label eth0 identifies the chosen network interface so it is needed to replace it with the correct value according to the interface chosen for the simulation The parameters values are always expressed as percentage except for burst length that is integer Using the query mode the transition probabilities and the GI General and Intuitive parameters that corresponds to the specified input parameters are calculated and printed to screen but no operation is done on the qdisc so the user c
23. problems were evidenced in this discussion https lists linux foundation org pipermail netem 2007 September 001156 html where the author explains them with theoretical considerations about the algorithm used by Netem to decide if a packet has to be lost that is based on a correlated random number generator These results drove us to develop a new loss model to regard burst losses in a better way Considering the theoretical problems of the correlated generator we decided to use another approach choosing a Markov chain model in the proposed loss model 2 Existing loss models in the literature BERNOULLI SIMPLE GILBERT p Independent Consecutive loss events p loss events Ce 1 r 1 GILBERT GILBERT ELLIOT Correlated Correlated and isolated loss events loss events p 1 COE r Page 4 of 70 General and Intuitive Loss Model and Netem Figure 1 4 loss models existing in the literature The Bernoulli loss model has one state and one parameter the loss probability p It is only able to model uncorrelated loss events The Simple Gilbert model has two states and two independent parameters It is able to model a system with consecutive loss events which can be characterized by a loss probability and a burst duration The two input parameters p and r can be tuned in order to characterize the system The Gilbert model has two states Good and Bad and three independent para
24. the Simple Gilbert model The density parameter extends the model to the 3 state or the Gilbert one and pisol to the 4 state model or to the Gilbert Elliot If good burst length is not specified the hypothesis of statistical independence between burst losses will be used Otherwise the transition probability between good sub bursts and loss bursts will be fixed by the user sqngen num of samples length gmin max loss 4state p13 p31 p32 p23 p14 this one selects GI General and Intuitive model using the transition probabilities expressed as percentages as input parameters The two transition probabilities p13 and p31 are mandatory and if specified alone corresponds to a 2 state Markov chain The other parameters are optional and allow the user to consider the 3 state p32 and p23 or the complete 4 state models p14 sqngen num of samples length gmin max 1055 gilb ell p r 1 h 1 k This syntax selects the Gilbert Elliot model If we specify only the loss probability p the Bernoulli model is selected Otherwise if we specify the parameters p and r the Simple Gilbert model is selected and if we specify the parameters r and h we select the Gilbert model Finally if we define the parameters h and 1 k the Gilbert Elliot model will be used The parameters p and represent the transition probabilities between the Good and the Bad states The third parameter i
25. used to represent system in which there is a Good state with a relatively low loss probability and in which the loss events appear as isolated and independent each other and a Bad state in which you have a relatively high loss rate so that it is possible to detect a burst of loss event corresponding to the permanence of the system in the Bad state 4 Relations between the models in the literature and the 4 state Markov model In this section we want to relate the 4 loss models existing in the literature and described in section 2 with the 4 State Markov model and its GI characterization that we have proposed Our goal is to show that the 4 state model is able to produce loss patterns practically equivalent to those generated by the existing models to evaluate the input parameters to be provided to the 4 state model to simulate the behaviour of a given set of parameters for one of the existing models We used an analytical approach which allowed us to evaluate the GI parameters like burst length burst density ecc for the existing models starting from the native parameters of the model Then we can use these evaluated GI parameters as input to our 4 state model Page 15 of 70 General and Intuitive Loss Model and Netem A simulation campaign has been used to validate this approach as described in section 7 We compared the loss patterns produced by the simulators of the existing models and of the 4 state
26. 0 includes the GE Gilbert Elliot model and the 4 states model using transition probability as input according to the follow syntax loss state P13 P31 P32 P23 P14 loss gemodel PERCENT R 1 H 1 K We found two problems in the kernel module that implements the 4 states and GE loss generators Therefore we propose a patch to sch_netem c to fix these problems We have spotted the problems using the test tools developed to measure loss and loss correlation generated by netem kernel modules trace2seq c sqnanalyzer c Moreover we propose a further patch to tc netem that allows input of parameters using the GI General and Intuitive model according to the following syntax loss gimodel BURST DENSITY PISOL GOOD BURST LENGTH Page 2 of 70 General and Intuitive Loss Model and Netem 1 original problem weakness of Netem correlated loss generator In this Section we present a few examples of how the loss generator implemented in Netem works to prove the noticeable diseases that have driven us to rewrite it In the first test we introduce a 2 loss in packets coming out from eth0 interface through the command root darkstar tc qdisc add dev eth0 root netem loss 2 Trying a ping on the local network and transmitting 10000 packets we see the following output The packet loss as we expected is about 2 root darkstar ping i 0 0001 c 10000 q 192 168 1 1 PIN
27. 0000000111111111111 111111000000000000000000000000001 1 1 100000000000000000000000000000000000000000000000000000000000 00000000001 11111111111111000000001 1 11000000000000000001001 1 1 10000000000000000000000000000000000 1000001 11111111000000000000001 11101111111100000000000000000000000000010000000000000100000000000 00000000000000011111111000000000000000000000000000000111100000000000000000011111110000000000000 00000000000000000000000000000000000000000000000111100000000000000000000000000000000000000111111 11111100000000000000000000000001 1000000000001 1110000000000000000000000000000000001 1110000000000 0010000000000000001110000000000000011111110000000000000000000000000000000000000000000000 1000000 00000000000000000000000000000000000000001 111000000000010000000111100000000000000000000000000000 000000000000000000000000000000000000 1000000000000000000000001 1111110000000000000000000000000000 00000000111000001111100000100000000000011111111111110110000001111100000001110100000011111111111 11111111111111000000000000001111100000000001111000000000000000000001111111111110000000000011111 11111110011000000000000001111000111000000000111111100000000000000000000000000000000000000000000 00000000000000000000000000000110000000000000000000000000001111111110000000000000000001111000000 000000000000000000000001 11000000000000000000000000000000000000000000000000000000000000000000000 00000001100000001111111111100000000000000000000000000001 100000000000000000000000000000000111111 1110
28. 000001 1 1 1 1 1 1 110000000000000000000000000000000000010001 11100000000 01000000000000000000000000000001111100000000000000000000000010000000000000000000000000000000000 00011111111111111110000000000000000000000111111000000000000000000000000000000000000000001111111 11111111100000000000000000000000000000000000000000000011111111111111110000000000000000011110000 00000011100000000000000000001111110000001111100000000000110000000000111111100000000000000000000 0000011111111111110000000111100111011111100000000000000000000000000000000000001 1110000000001 100 00111111111111100000000001 1 1000000000000000000000000000000000000000000000000001 1 100000000000000 0000000000000 10000000000000000000000000001 10000000000000000000000000000000000000000000000001111 11101011111111000000111111111100000000001 1 1 1000000000000000000000000000000000000000000000000000 0001111111111110000000000000000001 11111100000000000001 1110001 1111111000000001 100000000000000010 00000 Length is 2000 For GMIN 2 the generated sequence has the following characteristics from sequence analysis P loss 20 050 Mean length of burst 6 306 Density 98 721 P_isol 0 750 Mean length of good burst 1 000 For GMIN 4 the generated sequence has the following characteristics from sequence analysis P loss 20 050 Mean length of burst 6 746 Density 96 985 1501 0 750 Mean length of good burst 1 500 Page 64 of 70 General and Intuitive Loss Model and Netem For GMIN 8 the
29. 000001000000000000000000000000000000000000000000000000010000000000000000000000 00000000000000000000000000000000000000000001000000000001000000000000000000000000000000000000000000000000000100000000000000100000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 The sequence has been generated using the loss option with the following input parameters P loss 2 000 Mean length of burst 10 Density 80 000 P isol 2 000 Mean length of good burst 0 The generated sequence has the following characteristics from the generator P loss 1 400 Mean length of burst 0 000 Density nan P isol 1 400 Mean length of good burst 0 000 For gminz2 the generated sequence has the following characteristics from sequence analysis P loss 1 400 Mean length of burst 0 000 Density nan P isol 1 400 Mean length of good burst 0 000 For gmin 4 the generated sequence has the following characteristics from sequence analysis P loss 1 400 Mean length of burst 0 000 Density nan P isol 1 400 Mean length of good burst 0 000 The sequence is 11111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111101111111111 11111111111111111101111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111101111111111111 11110111111111111111111111111111111111111
30. 0001000000000000000000000000000000000000001000000000000000000000000000000000000000000000000 00000000000000000010000010000000000000000000000000000000000000000000000000000000000010000000000 00000000000100000000000000110000000000000000000000000000000000000000000000000000000000000000000 00011 Length is 2000 For GMIN 2 the generated sequence has the following characteristics from sequence analysis P loss 16 950 Mean length of burst 6 113 Density 99 074 P_isol 0 900 Mean length of good burst 1 000 For GMIN 4 the generated sequence has the following characteristics from sequence analysis loss 16 950 Mean length of burst 6 837 Density 95 821 P_isol 0 900 Mean length of good burst 2 000 For GMIN 8 the generated sequence has the following characteristics from sequence analysis P loss 16 950 Mean length of burst 9 023 Density 83 505 1501 0 750 Mean length of good burst 4 000 For GMIN 16 the generated sequence has the following characteristics from sequence analysis P loss 16 950 Mean length of burst 19 690 Density 57 093 P_isol 0 650 Mean length of good burst 7 656 Page 62 of 70 General and Intuitive Loss Model and Netem For GMIN 32 the generated sequence has the following characteristics from sequence analysis P loss 16 950 Mean length of burst 59 625 Density 34 696 P_isol 0 400 Mean length of good burst 12 460 For GMIN 64 the generated sequence has the following char
31. 11000001110000000000000000000000000000000 00010100000111000111100000000011111001000011111110000000000000000001000101111001011111111110000 00110001000100001000010011000111110110000100111011011111110111111111000000000101111100000001000 00001110000111100000110011010000000000000111110000101111011110000001101001100011100000011000011 11111100000001100001110111111000000000000000000111111111101000011000000010000000010000000001111 10000010000001000000000010000010000111100011000101111111100001011000110011000011001111100000100 00111110000111111110111111111100001100010011001100110111001110000001111111111100000000111111011 11111111001100000110100000000001001101111111110110111000111100000110000000000000000010000000000 11111000011111000100111110000000000111100011110000000111100000000011111111111111000000000000000 01110010011111111110000100000000000000110011100011000000000000000010011000000000001111000101100 00000000110001111000101111111110000111111100001111100000011110000000000000000011111100111111000 11110000000000000000001100010000110000000000011100011000101110000000011011000000100011110000000 00000000000000001100011001000000001000100011110000000001100100111111101110000000111100000000010 00011000110111111110000000000111100011110010000001111111000000011000000000000000011001111111000 01111101000001110111101111000100111000001110000000000011000000000001000000000000000010100000011 10111 Length is 2000 For GMIN 2 the generated sequence has the following characteristics fr
32. 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 11111111101111111111111111111111111111111111111111111111111101111111111111111101111111111111111111111111111111111111111011111111111111111111111 11111111111111111111111111111111111110111111111111111111111111111111111111011111111111111111111111111111011111011111111111111111111111111111111 11111111111111111111101111111111111110110111111111111111111111101111111111111111111111111111111111111111111111111111111101111111111111111111111 1111111101111111111111111111111111111111111111111111111111111111111110111111111111101111111111111111111111111111111111111111111111111101111111 The sequence has been generated using the loss option with the following input parameters P loss 2 000 Mean length of burst 10 Density 80 000 P isol 2 000 Mean length of good burst 0 The generated sequence has the following characteristics from the generator P loss 2 300 Mean length of burst 0 000 Density nan P isol 2 300 Mean length of good burst 0 000 Page 50 of 70 General and Intuitive Loss Model and Netem For gmin 2 the generated sequence has the following characteristics from sequence analysis P_loss 2 300 Mean_length_of_burst 0 000 Density nan P_isol 2 300 Mean_length_of_good_burst 0 000 For gmin 4 the generated sequence has the following characteristics from sequence analysis P_loss 2 300 Mean_length_of_burst 0 000 Density nan P_isol
33. 2seq 1s developed to evaluate the correct behavior of the various loss models in the new Netem version inside the Linux kernel The program is written in C language and works from command line and receives as input parameter the number of packets transmitted We define a oss sequence as a sequence of 0 and 1 where 1 represents a loss event and 0 represents a successful transmission event 7race2seq generates a sequence taking from the file prova txt the ICMP packets stored in the file using TCPDUMP Then delete packets of type request and finally checks the sequence number of ICMP packets by setting the value 0 for sequence number in the file and the value 1 to the sequence number that have been lost The sequence generated is saved in the file sequence txt To check the GI parameters analyze the sequence generated by the program sqnanalyzer c that runs a blind external check as in the case of sqngen 8 2 Compile trace2seq and sqnanalyzer To compile trace2seq and sqnanalyzer through gcc use the command g trace2seq c o trace2seq g sqnanalyzer c o sqnanalyzer 8 3 Howto use TCPDUMP Once you have chosen the loss model to apply to the Kernel we can save data traffic in the file prova txt We open two terminals In the first we type the command tcpdump i wlan0 n icmp w prova 2 txt In this way tcpdump is listening that is expected packets are transm
34. 3P31 Pi4P23P31 P13P32 Po 1 k P 4P23P31 P23P31 p cht rh I A rh P 3P23 Pi3P32 E B _ P23 r l h rh P23 e 1 E 1 rh h2 14r 14 2p r Alk 2 Kr J 2 0425 r 1 hh 1 r a hey i h hr A hr r l A hr _ l h hrf r VY Ah hr P5 0 1 Pia aol 4 1 2 Revisiting the Gilbert model We have already shown in section 4 1 1 a special case of the GI model which has a behavior very similar to the Gilbert Elliot model and called it Gilbert Elliot 4s The Gilbert model is a special case of the Gilbert Elliot where we set 1 A 0 removing the Bad into Good state So the Gilbert model can be seen as a simplified 4 state model with only 3 states that we will call Gilbert 4s If we consider the Gilbert 4s model we have the following relation between the Gilbert parameters and the transition probabilities simplifying the Gilbert Elliot 4s case with k 1 Page 21 of 70 General and Intuitive Loss Model and Netem m _ Pis P23 Pross 2 P23P31 Pi3P32 Psor 9 pa eal sek _ P13P23 I A r h P13P32 lc hn ps r l h rh P23P31 pucr l ps E Up PS C1 ay 1e ry 0 0 i h hr nr r ha hr _ ur he r 1 ha hr
35. Definition of a general and intuitive loss model for packet networks and its implementation in the Netem module in the Linux kernel Version 3 1 August 2012 S Salsano Ludovici A Ordine D Giannuzzi University of Rome Tor Vergata Available at http netgroup uniroma2 it NetemCLG Contact stefano salsano uniromaz2 it COPYRIGHT Copyright and all rights therein are retained by authors This work may not be modified or reposted without the explicit permission of the copyright holder General and Intuitive Loss Model and Netem TABLE OF CONTENTS LINTRODUGCTION eire ero tone 3 2 THE PROBLEM WEAKNESS OF CURRENT NETEM LOSS 4 2 2 3 3 EXISTING LOSS MODELS IN THE 0 5 4 THE PROPOSED LOSS 7 4 THE 4 STATE MARKOV MODEL tir uhr tre em E P ir m PR eren 7 4 2 THE GI GENERAL AND INTUITIVE MODEL 2 2 2 0 8 4 3 GIEBERT ELEIOTDMODEL eret Der RR OD PEE Oe DR en pre 14 5 RELATIONS BETWEEN THE MODELS IN THE LITERATURE AND THE 4 STATE MARKOV MODEL T M P 17 5 2 RELATIONS BETWEEN MODELS eee trt tr pe P C E rede re Ier epe 25 6 DEFINITION AND IDENTIFICATION OF BURST e eeeee 00410 ento sesto esee
36. G 192 168 1 1 192 168 1 1 56 84 bytes of data 192 168 1 1 ping statistics 10000 packets transmitted 9798 received 2 packet loss time 20754ms rtt min avg max mdev 1 353 1 802 5 967 0 471 ms ipg ewma 2 075 1 665 ms Now we introduce a 10 correlation with still the same loss probability In this case we have a very bad performance the loss probability of the generated sequence is quite null root darkstar tc qdisc change dev wlan0 root netem loss 2 10 root darkstar ping 0 0001 10000 q 192 168 1 1 PING 192 168 1 1 192 168 1 1 56 84 bytes of data 192 168 1 1 ping statistics 10000 packets transmitted 9984 received 0 6 packet loss time 18916ms rtt min avg max mdev 1 366 1 850 46 033 0 878 ms pipe 4 ipg ewma 1 891 If we use a higher value of correlation the result are still worse with only 6 packet lost in a sequence of 10000 root darkstar tc qdisc change dev wlan0 root netem loss 2 30 root darkstar ping 0 0001 10000 q 192 168 1 1 PING 192 168 1 1 192 168 1 1 56 84 bytes of data 192 168 1 1 ping statistics 10000 packets transmitted 9994 received 0 packet loss time 18430ms rtt min avg max mdev 1 363 1 804 6 726 0 481 ms ipg ewma 1 843 1 769 ms The decay of packet losses with correlation seems to be lower if we consider higher value of loss in input for example 1096 Without correlation the performances ar
37. SS amp gemodel sizeof gemodel 0 return 1 J else fprintf stderr loss in the weeds n return 1 addattr_nest_end n start static int netem print opt struct qdisc util qu FILE f struct rtattr opt print op q q p const struct tc_netem_gemodel gemodel NULL const struct tc_netem_gimodel gimodel NULL Struct rtattr Ib NETEM LOSS MAX if tb TCA 10551 struct rtattr LOSS MAX 1 parse rtattr 1 NETEM LOSS MAX tb TCA LOSS if IB NETEM LOSS Page 40 of 70 General and Intuitive Loss Model and Netem gimodel DATA IbB NETEM LOSS if IB NETEM LOSS gemodel RTA DATA IbB NETEM LOSS if gimodel fprintf loss state p13 968 sprint_percent gimodel gt p13 1 fprintf f p31 965 sprint_percent gimodel gt p31 b1 fprintf f p32 965 sprint_percent gimodel gt p32 b1 fprintf f p23 965 sprint_percent gimodel gt p23 b1 Sprint p14 965 sprint_percent gimodel gt p14 b1 j if gemodel fprintf f loss gemodel s sprint_percent gemodel gt p 1 Jprintf f r 96s sprint percent gemodel 7r b1 fprintf f h 905 sprint percent gemodel h b1 fprintf f l k 965 sprint_percent gemodel gt k1 b1 7 Testing the proposed loss model 7 14 Sqngen loss sequence generator 7 1 1 Overview Sqngen is a l
38. _model CLG GILB q gt clg state 1 q gt clg al gt q gt clg a2 ge gt r q gt clg a3 ge gt h q gt clg a4 ge gt k1 break P return 0 j Add the function dump loss model static int dump loss model struct netem sched data q struct sk buff skb switch q 7loss model t case CLG RANDOM case 4 STATES struct tc netem gimodel pl3 q gt clg al p31 q gt clg a2 p32 q gt clg a3 14 q gt clg a4 p23 q gt clg a5 NLA PUT skb 1055 sizeof gi amp gi break Page 34 of 70 General and Intuitive Loss Model and Netem case CLG_GILB_ELL struct tc_netem_gemodel p gt clg al r 7clg a2 h 7clg a3 k1 7clg a4 NLA PUT skb NETEM LOSS GE sizeof ge amp ge break 6 5 2 tc netem This Section describes the pieces of code added to iproute2 package The modified files are pkt_sched h in lt iproute2_source_path gt include linux and q netem c in lt iproute2_source_path gt Ac A new file tc netem 8 which contains the Netem manpage was added lt iproute2_source_path gt man man8 Note that lt iproute2_source_path gt stands for the path where the iproute2 sources have been unpacked The pieces of codes added to implement the new features to tc are now shown explaining them step by step In file pktsched h were made the same changes seen for the kernel fil
39. acteristics from sequence analysis loss 16 950 Mean length of burst 202 857 Density 23 521 1501 0 250 Mean length of good burst 17 516 For GMIN 128 the generated sequence has the following characteristics from sequence analysis P loss 16 950 Mean length of burst 1966 000 Density 17 243 P_isol 0 000 Mean length of good burst 22 288 Now we show another example another example of the analysis through the sqnanalyzer and trace2seq program The following figure shows an example with a sequence generated from Gilbert Elliot model with parameter p 20 and r 30 sudo tc qdisc add dev wlan0 root netem loss gemodel 20 30 daniele daniele Satellite L300 trace2seq 2000 La sequenza stata generata daniele daniele Satellite L300 sqnanalyzer sequence txt The sequence is 0001111000000000001 11100100010000000000000000000000000001 11 1100001000000001 11100000001 101100000 100001 10100000000000001 111100001 100000000000000000011110000010000111111111111111110000000000000 01100000000001111111111100000000010111000000000000001111110000111111100000011111000000000010111 11110001110000000000111111000000000001110000000000001111111100001111111111100000001111111110000 10011000000011100100011111111111101111000111111100000000111011110000001110000000000000011101100 11110000000100000011011111111100000010000001100100110000011100001100111110000000000000000000000 110000000000111000110000111000011111111111000011111101
40. an understand what he would obtain with certain input parameters without necessarily make changes to the system configuration 6 2 1 Query mode examples Now we present a few examples of how the query mode works In particular we will analyze one of the most interesting things that is the possibility of finding the length of the good burst changing the burst density or setting it manually and seeing how the transition probabilities change The first of them shows the transition probabilities and all the GI General and Intuitive parameters that correspond to a sequence with a 2 loss probability and a mean burst length of 10 While p and p31 depend on the two input parameters the others are set to the default values tc qdisc add dev eth0 root netem query loss gimodel 2 10 Transition probabilities are p13 is 0 204 p31 is 10 000 p32 is 0 000 using statistical independence hypothesis p23 is 100 000 using statistical independence hypothesis p14 is 0 000 GI General and Intuitive parameters would be ploss is 2 000 burst duration is 10 000 burst density is 100 000 isolated ploss is 0 000 good burst duration is 1 000 using statistical independence hypothesis Now we reduce the burst density to 8096 leaving the other parameters to old values This choice affects p32 and p23 so the good burst became longer since we have less packet loss during the burst which length is the same of the previous case
41. d by a transmission event The average number of these loss events will in any case be the same the patterns can be slightly different The difference will be higher for increasing value of PISOL as the probability of having consecutive isolated loss events increases with PIsoL In order to evaluate the burst length we have to consider that there is an extended burst length that includes the initial and final transmission events with the burst This is easily evaluated as E B We want to evaluate the corrected burst length E B therefore we will consider all the possible extended burst lengths and for each of them we will evaluate the probability of the corrected burst length The probability that the extended burst length equals i can be evaluated as follows ij r1 7 Let as denote a burst as a sequence of L for loss and for transmissions for example TLLL denotes a bursts of one transmission and three losses the extended length is 4 and the corrected length is 3 as there is an initial transmission Page 17 of 70 General and Intuitive Loss Model and Netem If the extended burst length is 1 i 1 the corrected burst length can be 1 sequence L with probability 1 h 0 sequence with probability h If 2 the corrected burst length can be 2 LL with probability 1 h 1 TL or LT with overall probability 2h 1 h 0 TT with probabili
42. df Netem Packet loss correlation from Netem Mailing list https lists linux foundation org pipermail netem 2007 September 001 156 html Generic Netlink HOWTO The Linux Foundation http www linuxfoundation org en Net Generic_Netlink HOWTO G Hassingler O Hohlfeld The Gilbert Elliott Model for Packet Loss in Real Time Services on the Internet in 14 GIITG Konferenz MMB 2008 Dortmund Germany Hohlfeld Stochastic Packet Loss Model to Evaluate QoE Impairments PIK Praxis der Informationsverarbeitung und Kommunikation journal G Galati G Pavan Teoria dei fenomeni aleatori Texmat pp 358 359 Page 69 of 70
43. e still good root darkstar tc qdisc add dev wlan0 root netem loss 10 root darkstar ping 0 0001 10000 q 192 168 1 1 PING 192 168 1 1 192 168 1 1 56 84 bytes of data 192 168 1 1 ping statistics 10000 packets transmitted 8980 received 10 packet loss time 30197ms Page 3 of 70 General and Intuitive Loss Model and Netem rtt min avg max mdev 1 356 1 828 8 308 0 509 ms ipg ewma 3 020 1 813 ms With a 10 correlation the losses in the generated sequence are about half of what we have asked root darkstar tc qdisc change dev wlan0 root netem loss 10 10 root darkstar ping 0 0001 10000 q 192 168 1 1 PING 192 168 1 1 192 168 1 1 56 84 bytes of data 192 168 1 1 ping statistics 10000 packets transmitted 9451 received 5 packet loss time 25209ms rtt min avg max mdev 1 347 1 840 21 326 0 524 ms pipe 2 ipg ewma 2 521 Increasing the correlation value the dynamics is similar of what we have just seen with a loss of only 1 in the generated sequence root darkstar tc qdisc change dev wlan0 root netem loss 10 30 root darkstar ping 0 0001 10000 q 192 168 1 1 PING 192 168 1 1 192 168 1 1 56 84 bytes of data 192 168 1 1 ping statistics 10000 packets transmitted 9868 received 1 packet loss time 20697ms rtt min avg max mdev 1 364 1 885 18 923 0 691 ms pipe 2 ipg ewma 2 069 Similar
44. e theoretical values for mean variance and CV using the formulas shown in the previous section The following table shows a comparison between theoretical and experimental parameters for different values of n Pross and E B The coefficients of variation of the generated sequences are always similar to the theoretical ones but the accuracy is worst if we consider smaller values of loss probability Changing E B value does not affect the results heavily The simulation is made of 50 sequences whose length is 200000 PLOSS E B LOSS LOSS LOSS LOSS LOSS CV MEAN VARIANCE CV MEAN VARIANCE generated Page 54 of 70 General and Intuitive Loss Model and Netem theory theory theory generated generated 2 00 5 4000 34495 251 0 04643 2 0007 0 00862 0 04641 2 00 10 4000 72908 619 0 06750 1 98268 0 01766 0 06702 2 00 20 4000 149729 709 0 09673 1 96733 0 03362 0 0932 1 00 5 2000 17621 613 0 06637 1 00476 0 00532 0 07258 1 00 10 2000 37222 255 0 09646 0 99797 0 01091 0 10467 1 00 20 2000 76420 630 0 13822 1 01728 0 02061 0 14113 0 50 5 1000 8905 053 0 09436 0 51034 0 00217 0 09135 0 50 10 1000 18804 614 0 13712 0 50688 0 00411 0 12646 0 50 20 1000 38602 258 0 19647 0 48995 0 00796 0 18208 Table 7 Statistics for the GI model using 2 states Increasing the length of the sequence the variation is smaller both in theoret
45. e with the same name In the file g_netem c the following code was added to the function netem parse opt e query mode J if matches argv query 0 query l e loss state if the selection options is oss state there is no need for the conversion and the input parameters transition probabilities p13 p31 p32 p23 p14 are directly passed to the qdisc J else if stremp argv state double p13 NEXT ARG if parse percent amp pl13 argv explain loss p13 return 1 j set defaults set percent amp gimodel p13 p13 set percent amp gimodel p3l p13 set_percent amp gimodel p32 0 set_percent amp gimodel p23 1 set_percent amp gimodel p14 0 loss type NETEM LOSS GI if NEXT IS NUMBER continue NEXT ARG Page 35 of 70 General and Intuitive Loss Model and Netem if get_percent amp gimodel p31 argv explain loss p31 return 1 if NEXT IS NUMBER continue NEXT ARG if get percent amp gimodel p32 argv explain loss p32 return 1 j if NEXT IS NUMBER continue NEXT ARG if get percent amp gimodel p23 argv explain loss p23 return 1 if NEXT IS NUMBER continue NEXT ARG if get percent amp gimodel p14 argv explain loss p14 return 1 j e loss gimodel if the chosen option is loss gimodel General and Intuitive
46. ed depending on the values of this is burst variable In both cases the sequence analysis is done comparing two successive values k th and k 1 th at each time The following figure shows how the algorithm works 10 11or 01 settee 11 t BURST zeros gmin Figure 8 Blind external check algorithm e If this_is_burst true so we are into the burst we can have three different situations o Ifk th value is 0 we stays into the burst without a loss event so only the variable length of all bursts is increased o Ifk th value is 1 and the following is still 1 we have a loss event within the burst so the variables num of drops num of burst drops and length of all bursts are increased o Ifk th value is 1 and the following is 0 and the sequence contains at least other gmin values there is another loss within the burst so the variables num of drops num of burst drops length of all bursts are increased At this point according to Page 48 of 70 General and Intuitive Loss Model and Netem the definition the 1 could be the end of the burst To check if this is true a further for loop analyzes the following gmin values and if they all assume the value 0 the 1 is really the end of the burst In this case the variable this is burstis set to false Note that this check is performed only if the sequence contains at least gmin values following the 1 because it would be senseless to check the presence of a certain number of
47. erizes the generated sequences in statistic terms calculating the following estimators n Sample mean x x x nj i Sample variance s 1246 x n l j n Standard deviation from samples s 12 06 x 4 ia NE 5 Variation coefficient c i Page 49 of 70 General and Intuitive Loss Model and Netem The function gets in input num of samples the arrays with the GI parameters calculated by one of the two checking methods the 2min that it the maximum value of Zmin considered in external check and the value for which the statistics have to been calculated If we want to calculate the statistics for internal check the function has to been called fixing at 2 both the field relative to 8min and 2min max Finally the statistics are printed to screen and saved in statistics dat 7 2 3 4 Main function The main function as first stage saves the input parameters in the appropriate variables If the Gilbert or the Gilbert Elliot models are selected the ell gen function will be used Otherwise loss GI loss 4state options sqn gen will be used In this case if the input values are the transition probabilities this is made in directly while if the user specifies the GI parameters that they are mapped to the transition probabilities At this stage after having defined the needed variables and arrays the pseudo random number generator is initialized by the function gsl rn
48. escribed above and if the returned value is 1 drops the packet If logging is enabled prints a line in the kernel logs j static bool loss event struct netem sched data q switch q 7loss model t case CLG RANDOM return q gt loss amp amp q gt loss gt get crandom amp q loss cor case CLG 4 STATES return loss 4state q case CLG GILB ELL return loss gilb ell q j return false The function get 055 to read the parameters from the userspace static void get_loss_clg struct Qdisc sch const struct nlattr attr struct netem_sched_data q qdisc_priv sch const struct nlattr la int rem for each nested la attr rem 16 type nla_type la Page 33 of 70 General and Intuitive Loss Model and Netem switch type t case LOSS const struct tc netem gimodel data la E 8 EN if nla len la sizeof struct tc netem gimodel t info netem incorrect gi model sizeln return EINVAL q gt loss_model CLG 4 STATES q gt clg state 1 q gt clg al gi gt p13 q gt clg a2 gi gt p31 q gt clg a3 gi gt p32 q gt clg a4 gt 14 q gt clg a5 gi gt p23 break case NETEM LOSS const struct tc_netem_gemodel ge nla data la if nla len la sizeof struct tc netem gemodel t info netem incorrect ge model size return EINVAL q gt loss
49. f joining two bursts into a longer burst and this will me more likely if the average inter arrival of bursts is relatively small gt E B tends to be larger than the input Page 23 of 70 General and Intuitive Loss Model and Netem 6 NetemCLG Implementation 6 1 NetemCLG and tc netem patches to Linux Kernel 3 0 16 and iproute2 3 2 0 These patches allow to upgrade the Linux Kernel 3 0 16 and iproute2 3 2 0 with the latest change The kernel patch allows to correct the errors found in the file sch netem c and in particular in the function of the generators of losses of various model while the other patch is applied to the iproute2 and it is necessary to add the GI model to the application 6 1 1 How to apply patches This section describes how to install the patches that adds the new change of the correlated loss models to the sch netem module of the Linux kernel and to the utility These instructions included in file INSTALL TXT into the patch package To install the NetemCLG kernel patch do cd your linux source tree patch 1 Kernel 3 0 16 patch substitute Kernel 3 0 16 patch with the path where you have unpacked the archive Then enable as module Network Emulator NETEM in the kernel configuration under Networking Networking Options QoS and or fair queuing The command to load netem is modprobe sch netem while the command to unload is modprobe r sch netem To install
50. f user and kernel space are very similar 8 6 Generated loss probability plots 8 6 1 Mean burst length plots The plots concerning length of burst show the variation of E B parameter with the value of gmin chosen for the external check algorithm Page 66 of 70 General and Intuitive Loss Model and Netem 22 20 18 16 gth 14 12 10 Mean Burst len Ploss 20 Burst length 5 Density 100 SL EET m ILLI 2 4 8 16 Gmin Burst length input 4Mean burst length Figure 12 Burst length 5 versus gmin Ploss 20 Density 100 In this case the burst length is fixed to 5 the ploss to 20 and density to 100 The most interesting fact is the dependence from gmin of the value estimated though external check The value is close for small values of gmin and is farther if we consider higher values of gmin This is connected to the chosen input value for burst length 8 6 2 Mean density plots The plots concerning density as for burst length show the variation of the parameter with the value Of gmin chosen for the external check algorithm Page 67 of 70 General and Intuitive Loss Model and Netem 105 Ploss 20 Burst_length 5 100 RR N Density 100 95 90 85 ity 80 75 Mean Dens TO 65 60 55 2 4 8 16 Density input 4Mean Density Figure 13 Density 100 versus gmin Ploss 20 Burst length 5 In this case the estimated value is good only
51. ficient of variation for Gilbert Elliot model Page 53 of 70 General and Intuitive Loss Model and Netem Since mean is uy N Poss 1 r 1 h we can find the expression for the ptr ptr variance o c ty N r P hp kr d 2pr 1 p r h 1 1 p r N 1 k 1 h 2 p r ptr 1 1 1 h p 1 k rl ptr r For the Simple Gilbert model with the choices p p 3 r p31 k 1 and h 0 we get the simplified expressions for the mean CV and variance E Hy N Pross NC ptr 1 2 1 LS pao c N P31 JN Pig Pis P31 NP psi Apr l p r 1 1 ptr r Note that as explained in Section 4 4 of 11 with 0 and k 0 the Markov chain collapses to a single state That is equivalent to a Bernoulli model 7 3 3 Statistics for the model using 2 parameters Now we show data from a simulation performed using the 2 state model using the oss GI option of sqngen and setting the two parameters Pross and E B This is equivalent to consider a Simple Gilbert or a 2 state Markov model We can t describe any longer this situation through a binomial random variable in fact we don t have independent losses but we are expressly stating that the losses are consecutive within a burst period which length is 10 So we will calculate th
52. g set r time NULL Then we enter a for loop that is repeated for a number of times equal to the number of sequences to generate Inside the loop the input parameters are saved to the file data dat and then the functions sqn gen internal check and external check are called At this point through the statistics function mean variance and variation coefficient are calculated The function is called many times in another for loop using different values of 8min until min max 7 2 3 5 Output The program prints on the screen all the generated sequences together with the parameters calculated with the two checks as in the following example bash 3 1 sqngen 2 1000 4 loss GI 2 10 802 Transition probabilities are p13 0 000000 p31 12 500000 32 19 444445 23 77 777778 14 2 040816 sequence is 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001000000000010000000 00000000000000000000000000000000000000000000000000000000000000000000000000000001010000010000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000010000000
53. h_of_good_burst 0 000 he standard deviation values loss 0 636 mean_length_of_burst 0 000 density nan pisol 0 636 mean_length_of_good_burst 0 000 he variation coefficients loss 0 344 mean_length_of_burst nan density nan pisol 0 344 mean_length_of_good_burst na Data are also saved in two text files data dat statistics dat Every line of data dat has the following format If the input parameters are the transition probabilities sample num of samples length igmin max loss markov p31 p31 p32 p23 pl4 ploss bis duration bis density bis gmin l pisol bis ploss ter duration ter density ter pisol ter gmin 2 pisol bis ploss ter duration ter density ter pisol ter If the input parameters are the GI parameters sample num of samples length igmin max loss phys ploss duration density pisol good duration ploss bis duration bis density bis pisol bis good duration bis gmin l ploss ter duration ter density ter pisol ter good duration ter gmin 2 ploss ter duration ter density ter pisol ter good duration ter If the input parameters are the parameters of Bernoulli Gilbert or Gilbert Elliot model we will have compared to the previous case oss bern loss gilb or loss gilb ell instead ofloss phys and the opportune parameters p p and r p r 1 h I k instead of ploss duration density pisol good duration The variables have the same meaning we have just explained the bis suffix are relative to the parameters calculated by the in
54. hese parameters are hardly related to quantities that have an understandable meaning for an end user of the model So we aim to define a set of parameters that are more intuitive User in fact would like to handle parameters clearly connected to the loss probability the length of a burst or similar concepts We will refer to this characterization of the loss process and to the underlying 4 state markovian model as GI loss model where GI stands for General and Intuitive We will show that the GI set of parameters is equivalent to the set of state transition probabilities by providing the corresponding expressions Therefore the GI approach can be used to fully characterize the 4 state model The 5 quantities chosen as GI parameters are the following e Loss probability Mean burst length E B e Loss density within the burst Isolated loss probability Mean good burst length E GB In the next sub section we will evaluate the state transition probabilities for the case in which all the 5 parameters are used to characterize the loss model Then we will show how it is possible to characterize a loss model with reduced sets of parameters respectively 4 3 2 and 1 parameter Page 7 of 70 General and Intuitive Loss Model and Netem 3 2 1 model with 5 parameters The expressions for p Piso and E GB can be simply evaluated as follows Pos T 1 2 p mom 2
55. hm while for the other options the input parameters are mapped to the 4 state transition probabilities and passed to netem2 thought the netlink socket The conversion formulas are shown in the following table Page 29 of 70 General and Intuitive Loss Model and Netem Loss 4state Loss GI Loss bern Dow P P31 1 1 Press E B Dos E B p 1 E B 1 Dao 2 1 1 10 0 Du Eso 0 D Psor Table 5 Relations between options and models in tc netem2 For the Gilbert 4s and Gilbert Elliot 4s cases the conversion is made in two steps firstly the GI parameters that correspond to the input parameters are calculated Then the GI parameters are used to calculate the 4 state transition probabilities The relations used are the following Pross 1 k 1 h P13P23 Pi4P23P31 p r p r Pi Belus Pi4P23P31 Pi4Pa3P31 Pi3P32 1 P13P 23 r l h rh l1 h r h Pat r 1 h rh P23P31 E GB 1 P23 E B Note that one of the three different labels add change and del has to be chosen add is used to initialize a new option change to set new parameter s value s and del to remove already set parameters with a previous command Moreover the label eth0 identifies the chosen network interface so it is needed to replace it
56. ical and experimental values SAMPLES LENGTH PLOSS E B PLOSS PLOSS PLOSS u X cV 40 10000 2 10 1 946 0 24543 0 25458 40 20000 2 10 1 996 0 18467 0 2152 40 100000 2 10 2 009 0 04589 0 10663 40 200000 2 10 1 986 0 0162 0 06424 40 1000000 2 10 2 014 0 00376 0 03044 40 2000000 2 10 2 008 0 00181 0 02120 Table 8 Dependence of mean variance and coefficient of variation on the sequence length for the GI model using 2 states The number of samples considered does not seem to help in reducing variation as we see in the following table We can assume that 40 samples are enough to estimate variance SAMPLES PLOSS E B PLOSS PLOSS PLOSS Page 55 of 70 General and Intuitive Loss Model and Netem u o CV 25 2 10 2 013 0 02552 0 07936 40 2 10 1 997 0 01208 0 05503 50 2 10 1 988 0 01598 0 06356 100 2 10 2 005 0 02036 0 07115 200 2 10 2 008 0 02023 0 07083 250 2 10 2 001 0 02092 0 07228 500 2 10 2 002 0 0172 0 06549 1000 2 10 2 000 0 01744 0 06602 2000 2 10 2 003 0 01858 0 06805 Table 9 Dependence of mean variance and coefficient of variation on the number of samples for the GI model using 2 states 7 3 4 Statistics for Gilbert Elliot models In this section we report the statistics of a simulation relative to the Gilbert model performed specifying the three paramete
57. ics of a simulation relative to the Gilbert Elliot model performed specifying all parameters p r 1 h and 1 k Also in this case we will calculate the user space and kernel space values as in the section The number of experiments is 1 and the length of the sequence is 20000 PARAMETERS USER SPACE KERNEL SPACE id n E B d icu E B ao i58 20 30 100 0 39 645 5 262 95 521 3 180 39 650 5 430 95 273 2 970 z 20 30 40 0 16410 2 962 92 640 8 040 16 195 3 140 91 189 7 605 5 30 40 10 21810 3 242 89032 10 770 22 285 3 149 89 917 10 960 20 30 100 0 39 645 8 911 80 760 2 225 39650 9 464 80 537 2 035 z 20 30 40 0 16 410 4 873 71 429 6 960 16195 4 676 74 297 6 815 5 0 30 40 10 21810 5 641 67 917 9 225 22 285 5 767 67 236 9 285 20 30 100 0 39645 29 614 57 625 0 980 39 650 26 696 60 044 1 180 z 20 30 40 0 16 410 11 345 45 440 5 275 16 195 10 787 47 583 5 365 5 30 40 10 21 810 19 007 40 206 6 220 22 285 20 142 39 754 5 630 e 20 30 100 0 39 645 247 311 43 112 0 195 39 650 216 869 43 366 0 150 Y 30 40 0 16 410 47 295 26 218 2 770 16195 47 718 26 072 2 945 5 20 30 40 10 21 810 163 626 25045 1 525 22285 151 796 25 595 1 305 Table 11 Statistics for the Gilbert Elliot model using 2 3 and 4 parameters As above the test result shows that the value o
58. inition e State 1 packet received successfully e State 2 packet received within a burst e State 3 packet lost within a burst e State 4 isolated packet lost within a gap From the definition of State 4 we have p4 71 At this point there are five independent transition probabilities We will consider p31 P23 p32 pia while Pii 1 Pa 7 1 P33 1 2 Pu O The Markov chain can be described by the following set of balance equations Solving the system we find the expression of state probabilities mi i 1 4 as a function of the five independent transition probabilities pi Page 6 of 70 General and Intuitive Loss Model and Netem A pis Pig Hy Day 13P32 17 P 3 Ti Pig 1 State 4 is associated to isolated packet losses after that the system must come back to State 1 so we can assume p4 1 Solving the system we get the states probabilities Ae P23P31 P13P23 P23P31 PigP23P31 P13P 32 Pig Hy Pi3P32 T3 P32 2 Pr3 ze PisP25 P23P31 P14P23P31 P13P32 Tipi 7 P13P23 m m tm tn l PisP25 P23P31 Pi4P23P31 P13P32 Pi4P23P31 P 3P23 P23P31 Pi4Pa3P31 P13P32 3 2 The Gl General and Intuitive model The above described 4 state model uses transition probabilities between states as parameters to characterize the packet loss process T
59. interval between the two percentiles X w2 n 1 and 1 1 where 1 the degrees of freedom Since mean value is unknown we are estimating it from samples 7 3 2 Mean variance and coefficient of variation for the Gilbert Elliot model We calculate the coefficient of variation CV using the equations presented in 12 In this job the authors adopt a Gilbert Elliot loss model which formally is a 2 state model respectively named Bad B and Good We can have loss events in both the states with probability k and 1 respectively If we set 0 and k 1 we obtain a simple 2 state Markov chain where G state represents only correctly received packets and B state represents only loss packets The formula is obtained starting from the moment generating function Gy z and By z where N is the length of the sequence While in steady state we have Go z p and Gi z ps where and p are the state probabilities Gwa4 z be derived with a iterative procedure taking into account the state transition G ya 2 1 226 Z 2 and similarly for By z The k moments are derived by the relation E x T l 2 L4 So it is 2 possible to obtain an explicit solution for mean variance and coefficient of variation of loss events In particular the expression for the coefficient of variation is very simple c hp kr 2pr p r h kf EET JN Va hp Er 0 h p 0 rf p r r Equation 1 Coef
60. isol argv explain loss gimodel pisol return 1 j if pisol gt print nError pisol gt pn break if p pisol gt burst 1 pisol density p print nError p pisol gt burst 1 pisol density break if pisol gt 0 5 print nError pisol gt 0 51n break if NEXT IS NUMBER NEXT ARG input params good burst length strtod argv char NULL if good burst length lt 1 printf nError good burst lenght lt 1 In break if good burst length lt 1 density density print nError good_burst_lenght lt 1 density density n break Page 37 of 70 General and Intuitive Loss Model and Netem jelse if input_params gt 2 if input_params gt 3 if input_params gt 4 if input params 5 input params 5 p23 l good burst length p32 1 density density geood burst length p14 pisol 1 pisol p13 pisol p burst pisol 1 density p p31 1 burst density jelse input_params 4 p23 burst density I burst 1 p32 density 1 burst density 1 density 1 p14 pisol 1 pisol p13 pisol p burst pisol 1 density p p31 I1 burst density good burst length 1 23 jelse input_params 3 p23 burst density 1 burst 1 p32 density 1 burst density 1 density 1 burst pl4 0 pisol
61. itted So to transmit the packets in the second terminal type the command sudo ping 1 0 1 200 192 168 2 1 When the packet transmission is completed we block tcpdump by typing Ctrl C and then to convert the file prova 2 txt into a file readable in a text editor using the command tcpdump r prova 2 txt gt prova txt Page 61 of 70 General and Intuitive Loss Model and Netem 8 4 Sqnanalyzer Sequence analyzer Sqnanalyzer is a program written reusing part of the code of sqngen to analyze a known loss sequence made of 0 and 1 stored in a text file The syntax is the following sqnanalyzer sequence txt where sequence txt stands for the name of the file that contains the sequence Once the sequence has been read it is analyzed by the algorithm used by sqngen s external check that calculates the GI parameters repeating the analysis starting from g 2 until g 7128 doubling its value at each step The following figure shows an example with a sequence generated from GI model with parameter Ploss 20 and Burst 5 daniele daniele Satellite L300 sqnanalyzer sequence txt The sequence is 00000000000000000000000000000000001 100000000000000000000000000100000000000000000000000000000000 000000000000000000001 1 100001 100000000001 11111111000111110001100000000001 1 1 1 10000000000000000000 00100000001 100000000000000000000000000000000000000000001 1 1000000100000000000
62. loss ploss burst length density pisol good burst length tc qdisc add dev ethO root netem2 query loss 4state p13 p31 p32 p23 p14 tc qdisc add dev ethO root netem2 query loss bern p tc qdisc add dev ethO root netem2 query loss gilb 4s p 1 h tc qdisc add dev ethO root netem2 query loss gilb ell 4s p 1 h 1 k Adding a deterministic loss pattern tc qdisc add dev ethO root netem2 query loss pattern filename repetitions Enabling the logging mode tc qdisc add dev ethO root netem2 logging 1 Where the correspondence between options and model are OPTION MODEL Loss GI GI General and Intuitive Loss 4state 4 state Markov with transition probabilities as input parameters Allows special cases 3 state 2 state Bernoulli Loss bern Bernoulli Loss gilb Gilbert and Simple Gilbert as special case Loss gilb ell Gilbert Elliot and special cases Gilbert Simple Gilbert Loss gilb 4s Gilbert 4s Loss gilb ell 4s Gilbert Elliot 4s allows Gilbert 4s as special case Table 4 Options and models in tc netem2 If the selected option is oss gilb or loss gilb ell the Gilbert Elliot generation algorithm will be used If the selected option is one of oss loss 4 state loss bern loss gilb 4s or loss gilb ell 4s the 4 state generation algorithm will be used In the case of oss 4state the transition probabilities specified as input are directly passed to the algorit
63. meters Within the Good state packets are never lost Within the Bad state there is a probability h that a packet is transmitted This is able to model a system in which the loss events appear in burst but within the bursts there are some transmitted packets and some lost packets A good way to characterize this system is to consider a loss probability a burst duration and a loss density within the burst loss density 1 h If the loss density is 100 i e h 0 the model becomes equivalent to the Simple Gilbert The Gilbert Elliot model has two states Good and Bad and four independent parameters In this case is it possible to have loss events also in the Good state with probability 1 k Therefore k is the probability that the packet is transmitted while the system is in Good state If k 1 the model becomes equivalent to the Gilbert model The Gilbert Elliot model can be used to represent a system in which there is a Good state with a relatively low loss probability e g up to a few percent and in which the loss events appear as isolated and independent each other and a Bad state in which you have a relatively high loss rate e g from 30 40 up to 100 so that it is possible to detect a burst of loss event corresponding to the permanence of the system in the Bad state We note that a drawback of Gilbert and Gilbert Elliot model is that the length of a Bad period when h gt 0 does not exactly correspond to the le
64. n The result of function net random is compared with p23 If var_random lt p2 the system goes to State 3 If the system is in State 3 a 0 is appended to the sequence and printed to the screen The result of function net random is compared with p23 If var_random lt p32 the system goes to State 2 If var random p the system comes back to State 1 and a tag is appended to the sequence to mark the end of the burst The i counter is also incremented to avoid to overwrite it at the next step If no one of the two condition is satisfied so var_random gt p31 p32 the system stays in State 3 and we have a further loss event If the system is in State 4 a 0 is appended to the sequence and printed to the screen Since this is an isolated loss event the system goes to State 1 Page 44 of 70 General and Intuitive Loss Model and Netem The following figure shows summarizes how the algorithm works Input parameters PRNG var_random Tausworthe For each extraction packet burst drop random lt isolated drop random lt random lt random lt random burst drop p41 1 transmission Figure 7 GI loss generator algorithm At this point two different checks are performed on the parameters of the generated sequence 7 2 3 Gilb ell gen function Gilbert Elliot sequence generator void gilb ell gen gsl rng q char sequence int length unsigned int p unsigned int r un
65. n the GSL libraries The code is the same used in net random or random32 function of Linux kernel that is also used by Netem Once installed GSL it is possible to compile sqngen through gcc with the command Page 41 of 70 General and Intuitive Loss Model and Netem g Wall sqngen c lgsl lgslcblas o sqngen The building was tested with GCC 4 2 4 on Slackware Linux 12 2 7 2 1 User manual The syntax for sqngen is sqngen num of samples length gmin max model type model params where model type can be e 1055 4state e 1055 GI e loss gilb ell while model params is a set of model parameters dependent on the model type as in the following examples num of samples represents the number of sequences to generate length represents the length of each sequence while g max is the maximum value of gmin used in the external check To skip the external check value has to been set to 0 sqngen num of samples length gmin max loss GI ploss burst length density pisol good burst length this syntax selects GI General and Intuitive as model and uses its own parameter as input The burst length and good burst length parameters are expressed as integer values while ploss density and pisol as percentages The only mandatory parameter is ploss that corresponds alone to the Bernoulli model If burst length is also specified it corresponds to the 2 state Markov or to
66. n the bursts model with 4 parameters If there is no correlation between losses within the burst we can state the following equation between transition probabilities P32 p 1 This equation states that the probability of losing a packet after a successful transmission within the burst first member equals the probability of losing a packet after another packet has just been lost Note that 1 731 is the probability of remaining in the burst or Bad state after you have had a loss event in the burst We call this condition independent loss events during the burst Under this condition we need only 4 parameters to characterize the system and we cannot assign an arbitrary value to E GB Removing E GB and replacing its definition with the equation p 1 TR we obtain the following expressions for the transition probabilities Pross T3 T P E B p T Pennes of Pao 4 pu LOSS ISOL T tT n 1 Psor Xo P 2o _ p 1 p 32 T FT p E B M _ E B p 1 E B 232223 Pa P23P31 E B 1 P32 _ Prox Pel Did See 1 1 The following constraints apply here E B 2 1 0 lt Pzoss Pross lt Pross 1 lt E B 1 Pisox p Pzoss 1 p p E B 1 p E B 1 gt E B gt 2 p 1 Pisor lt 1 2 Page 9 of 70 General and Intuitive Loss Model and Netem 3 2 3 Remo
67. nfiguration under Networking Networking Options QoS and or fair queuing The command to load netem is modprobe sch netem while the command to unload is modprobe r sch netem To install the tc patch do cd your iproute2 source tree patch 1 lt iproute2 2 6 39 patch substitute iproute2 2 6 39 patch with the path where you have unpacked the iproute2 sources Then build iproute2 6 4 tc netem user manual for the originally proposed patch historical The first modified version of allowed the user to add loss features to the outgoing packets according to the following syntax This is reported mainly for historical reasons as the use of the old version is deprecated Page 28 of 70 General and Intuitive Loss Model and Netem Adding a loss pattern according to a model tc qdisc add change del dev ethO root netem loss ploss burst length density pisol good burst length tc qdisc add change del dev ethO root netem loss 4state p13 p31 p32 p23 p14 tc qdisc add change del dev ethO root netem2 loss bern p qdisc add change del dev ethO root netem2 loss gilb 1 h tc qdisc add change del dev ethO root netem loss gilb ell p r 1 h 1 k tc qdisc add change del dev ethO root netem2 loss 4s p 1 h tc qdisc add change del dev ethO root netem loss gilb ell 4s p 1 h 1 k Querying information from a loss model tc qdisc add dev ethO root netem2 query
68. ngth of a burst of loss events measured from the first loss event to the last loss event In fact when the system enters in the Bad state it does not have to generate a loss event immediately but there is a loss event with probability 1 h Likewise just before going back to the Good state the system can generate a set of transmission events still being in the Bad state Therefore the length of the Bad period according to the model is greater than the length of the burst measured from the first to last loss event For example assuming a loss density of 50 therefore h 0 5 you may have something similar to the pattern shown in Figure 2 Good Bad Good DUM 0000000001011010011101101000000000000 Burst of loss events Figure 2 Example of a loss pattern generate by a Gilbert or Gilbert Elliot model Page 5 of 70 General and Intuitive Loss Model and Netem 3 The proposed loss model 3 1 The 4 state Markov model p14 p13 p32 1 p31 p23 GOOD BAD Figure 3 4 state Markov model This 4 state Markov is the combination of two 2 state Markov sub models that represents two situations burst periods during which packets are received and lost according to a first 2 state model and gap periods during which packets are received and lost according to a second 2 state model The same 4 state model has already been proposed in 6 and was used in 3 The states have the following def
69. nt loss probability 1 h it remains in the same state Otherwise if a packet is correctly transmitted without coming out from the burst condition it goes to state 2 call it Good into Bad The difference respect to the Gilbert Elliot model is that the transitions from Page 16 of 70 General and Intuitive Loss Model and Netem state 1 Good to state 3 Bad only happen after a transmission event and will be followed by a loss event Likewise the transitions from state 3 Bad to state 1 Good only happen after that a loss event is verified and will be followed with a transmission event We believe this is a much cleaner modeling as a transition from Good to Bad in the model corresponds to a transmission event followed by a loss event and viceversa a transition from Bad to Good in the model correspond to a loss event followed by a transmission event In order to map the Gilbert Elliot model into our 4 state model we will evaluate the following GI parameters Loss probability P Isolated loss probability Mean burst length E B e Loss density within the burst Then we will derive the transition probabilities that correspond to the evaluated GI parameters Pross Ht Piso 1 As already noted under the Gilbert Elliot model the loss events in the Good state i e corresponding to the can also be consecutive while in the 4 state model they will always be followe
70. nters in a switch construct controlled by the variable state that assumes values between 1 and 4 depending on the state where the system is The switch construct uses the following series of variables e state identifies the current state Its default value is 1 At each step it is updated according to the result of the comparision between the last random number extracted and the transition probabilities to the other states 2 3 or 4 e tags counts the number of S and tags that defines the beginning and the end of each burst The number of iterations of the loop is length tags e i counts the iterations e length length of the sequence It doesn t include the tags In particular If the system is in State 1 a 0 is appended to the sequence and printed to the screen The result of function net random is compared with If var_random lt p there is a transition to State 3 In this way we have a loss event and we are entering in a new burst so S tag is inserted before the first 1 and the variable tags is incremented The 7 counter is also incremented to avoid to overwrite it at the next step If but var gt 1 4 the system goes to State 4 and we have an isolated loss event If none of the two conditions is verified system stays in State 1 If the system is in State 2 1 is appended to the sequence and printed to the scree
71. nterval where the generated Pzoss values fall We will compare the statistical values mean variance and coefficient of variation obtained from theoretical consideration with Page 52 of 70 General and Intuitive Loss Model and Netem experimental values calculated using sqngen s internal check after having generated a series of sequences with certain input parameters The aim of this part of the job is to estimate if and how the generator can be considered well enough for our purposes The computation of the standard deviation and so of the variation coefficient depends on the considered the loss model For the Bernoulli model we will use the mean and variance tests to validate our algorithm 7 3 1 Mean and variance tests The mean test with unknown variance as explained in 13 is based on the parameter X M sida hypothesis Ho which states sample mean is is not rejected if falls into the interval between the two percentiles t 5 n 1 and t 5 n 1 where n 1 are the degrees of freedom Since variance value is unknown we are estimating it from samples The variance test with unknown mean is J which is distributed as a Student variable So chosen a level of significance a the n X EOM based on the parameter y i l o which is distributed as Chi Square So chosen a level of significance the hypothesis which states sample variance is o is not rejected if Q falls into the
72. nversions and no information will be J else if stremp argv gemodel double p double h NEXT ARG if parse percent amp p argv explain loss gemodel p return 1 j set defaults set percent amp gemodel p p set percent amp gemodel r 1 p set percent amp gemodel h 0 set percent amp gemodel kl 0 loss type NETEM LOSS GE if NEXT IS NUMBER continue NEXT ARG if get percent amp gemodel r argv explain loss gemodel return 1 j if NEXT 15 NUMBER continue NEXT ARG if parse percent amp h argv explain loss gemodel h return 1 Page 39 of 70 General and Intuitive Loss Model and Netem set parameter h set_percent amp gemodel h 1 h if INEXT IS NUMBER continue NEXT ARG if get percent amp gemodel kl argv explain loss gemodel return 1 jelse fprintf stderr Unknown loss parameter s n a rgv return 1 Another pieces of code were added to netem print opt function netem_dump functions if loss type NETEM LOSS UNSPEC struct rtattr start start addattr_nest n 1024 TCA NETEM LOSS NLA F NESTED if loss type LOSS if addattr l n 1024 LOSS amp gimodel sizeof gimodel lt 0 return 1 J else if loss type LOSS GE if addattr_I n 1024 NETEM LO
73. odel and Netem h 5 r 1 r 1 h 2h 1 h 3h a 4h 1 5h 1 h h hy hy 6 1 2h 1 h 3h 1 4h 1 1 6h 1 h h hy hy hy The probability of having a burst with corrected length 0 i e with all transmission events is P B 0 2 3 1 r r0 r 2X a X _ rh 1 h crh The probability or having a burst with corrected length 1 is P B 1 P B 206 1 1 23b 1 5 r 1 1 r2h 1 1 r 35 1 5 I A i1 rY i 0 i 0 r l ni nit AA E Vener ay For j 2 2 the probability of having a burst with corrected length j is j j igh 1 n j 2 3h7 1 Ay 1 7 1 A r 1 r 2b 1 h 1 7 3 2 1 h r l hy l r ry hi r 1 h 1 7 1 i 0 i 0 E mr ee 1 A rh 1 A rh m Page 19 of 70 General and Intuitive Loss Model and Netem The average corrected length for bursts with corrected length gt 0 is 2 1 8 rh 1 Where gt 0 1 0 1 therefore 1 h rh 1 h rh r 1 n Y E l h l htrh 1 ar A ia je v
74. om sequence analysis loss 39 200 Mean length of burst 5 257 Density 96 037 1501 2 850 Mean length of good burst 1 000 For GMIN 4 the generated sequence has the following characteristics from sequence analysis loss 39 200 Mean length of burst 9 069 Density 80 757 1501 1 850 Mean length of good burst 1 935 For GMIN 8 the generated sequence has the following characteristics from sequence analysis loss 39 200 Mean length of burst 26 833 Density 59 394 1501 0 950 Mean length of good burst 3 189 Page 63 of 70 General and Intuitive Loss Model and Netem For GMIN 16 the generated sequence has the following characteristics from sequence analysis loss 39 200 Mean length of burst 112 267 Density 46 081 1501 0 400 Mean length of good burst 4 365 For GMIN 32 the generated sequence has the following characteristics from sequence analysis P loss 39 200 Mean length of burst 977 500 Density 40 000 P_isol 0 100 Mean length of good burst 5 167 For GMIN 64 the generated sequence has the following characteristics from sequence analysis loss 39 200 Mean length of burst 1997 000 Density 39 259 1501 0 000 Mean length of good burst 5 274 For GMIN 128 the generated sequence has the following characteristics from sequence analysis loss 39 200 Mean length of burst 1997 000 Density 39 259 1sol 0 000 Mean length of good burst 5 274
75. oss sequence generator developed to evaluate the behavior of the various loss models before implementing them in the new Netem version inside the Linux kernel The program is written in C language and works from command line We define a oss sequence as a sequence of 0 and 1 where 1 represents loss event and 0 represents a successful transmission event the length of the sequence specifies the number of events Sqngen on the basis of the input parameters generates a certain number of sequences of samples prints them on the screen and makes two checks on each sequence re calculating the GI parameters in two ways from the generated sequences an internal check that identifies the beginning and the end of the bursts using the tags introduced in the sequences during the generation and a blind external check that analyses the sequence without any additional information After all a simple statistical analysis is made on the generated sequences calculating mean variance and variation coefficient for the GI parameters Then all the relevant data input parameters GI parameters calculated by internal and external check statistical data are saved to text files 7 2 Building sqngen To build sqngen it is required to have GNU Scientific Library 1 12 http freshmeat net redir gnuscientificlibrary 3556 url tgz gsl 1 12 tar gz installed This is needed because sqngen uses Tausworthe random generator contained i
76. re at the beginning of a burst according to Gilbert Elliot so we set gilb ell burst true and the value of num of bursts is incremented If we find we are at the end of the burst so we set to false all the boolean variables relative to being into a burst gilb ell burst real burst and good burst Moreover we remove from the length of the bursts the number of initial and final zeros and for the length of the good burst only the number of the final zeros If we are in a Gilbert Elliot burst without having had loss event and we find a 1 then we enter in a real burst and set real burst true If we in a real burst and find a 1 or 0 length of all bursts is incremented If we found a 0 and we still haven t had losses this is an initial zeros Otherwise it Page 46 of 70 General and Intuitive Loss Model and Netem could be a final zero or an element of a good sub burst so both final zeros and length of all good bursts are incremented If we found a 1 we are sure that we are in a real burst so we set real burst true and good burst false because we are also sure of being out of any good bursts In this case the previous zeros were not final zeros but elements of a good bursts so we set final zeros 0 At this point we use the following formulas num of drops bis length e ploss 100 length of all bursts bis num of bursts bis e mean length of burst num of burst drops hs length of all bursts bis
77. re can be leading and trailing transmission events in a burst the burst loss burst length and the length in the bad period can be evaluated in the following way Pross _ 1 k P 1 4 ptr ptr r p l h Psor de However as shown in section 2 the loss sequences generated using the Gilbert Elliot model could have an extended burst length and so a reduced density due to the possible transmission events at the start and at the end of the burst Therefore we have denoted this extended burst length and this reduced density as E B and p Since the GI model states explicitly that a burst starts and ends with a loss event according to the definition given in the RFC3611 7 we need to fix the relations with some correction factors to take into account this fact Then we will find the value of GI parameters that makes the GI model s behavior the more possible similar to the Gilbert Elliot s one obtaining the special case of the GI model that we denote as Gilbert Elliot 4s If the system is in the state 1 call it Good and there is a loss event according to an independent loss probability 1 4 without entering in the burst condition the system goes into state 4 call it Bad into good At the next step it deterministically comes back to state 1 This is what we call an isolated loss Instead if the system is in the state 3 call it Bad and there is a loss event according to an independe
78. rkov chain 4 states and Gilbert Elliot models u32 al p13 for 4 states or p for Gilbert Elliot u32 a2 p31 for 4 states or r for Gilbert Elliot u32 a3 p32 for 4 states or h for Gilbert Elliot Page 31 of 70 General and Intuitive Loss Model and Netem u32 a4 p14 for 4 states or l k for Gilbert Elliot u32 a5 p23 used only in 4 states jclg the oss 4state generator function it generates losses according to the 4 state Markov chain adopted in the GI General and Intuitive loss model The function makes a comparison between the return value of the net random function and the transition probabilities outgoing from the current state then decides the next state and if the next packet has to be transmitted or lost The four states correspond to successfully transmitted packets within a gap period State 1 isolated losses within a gap period State 4 lost packets within a burst period State 3 successfully transmitted packets within a burst period State 2 static bool loss 4state struct netem sched data q struct clgstate clg amp q gt clg u32 rnd net random extracts a random number switch clg gt state case 1 if rnd lt clg gt a4 gt state 4 return true J else if clg gt a4 lt rnd amp amp rnd lt clg gt al clg gt a4 clg gt state 3 return true else if clg gt al clg gt a4 lt rnd clg gt state
79. rs p r and 1 h We will calculate the theoretical values for mean variance and CV using the formulas seen for the Gilbert Elliot model choosing 1 k 0 The number of samples is 50 each sequence has length 200000 We repeated the simulations using oss gilb ell model model input theoretical experimental p r 1 h 1 k ploss ploss ploss E B density pisol ploss ploss Ploss E B density pisol mean variance cV mean mean mean mean variance cV mean mean gilb_ell 0 204 1 100 0 16 94 1 075 0 069 100 100 0 16 84 1 081 0 061 99 65 100 0 gilb_ell 0 204 1 1 0 0 169 0 00015 0 072 50 74 3 921 0 0 169 0 00018 0 078 50 83 3 963 0 gilb_ell 0 204 1 2 0 0 338 0 0005 0 082 67 44 4 418 0 0 333 0 0006 0 077 66 88 4 448 0 gilb_ell 0 204 1 2 0 1 0 421 0 0069 0 065 67 44 4 418 0 1 0 420 0 0074 0 064 67 41 4 418 0 0842 Table 10 Statistics for Gilbert Elliot model 7 3 5 Statistics for the model using 3 and 4 parameters In this section we reconsider the full GI model using 3 and 4 parameters through the oss option and the parameters Pross E B p Piso all the cases of the previous section adding a isolated loss Page 56 of 70 General and Intuitive Loss Model and Netem probability of 0 1 So we are now using the full Gilbert Elliot model The number of experiments is 50 and the leng
80. rs to the arrays where the respective parameters will be stored The sequence is analyzed looking through each element one by one The following variables are used gilb ell burst boolean variabile If set to true we are in a burst condition according to Gilbert Elliot This corresponds to the Bad state of Gilbert Elliot If the burst doesn t contain any loss event it is not a burst according to RFC3611 e real burst boolean variable if set to true we are in a burst condition after we have had a loss event after entering in a Gilbert Elliot burst e good burst Boolean variable if set to true we are in a good sub burst so we have had some transmission in a real burst e num of bursts bis number of bursts e num of good bursts bis number of good bursts length of all bursts bis sum of the length of all the bursts we have had e length of all good bursts bis sum of the length of all the good bursts we have had e num drops bis total number of loss events e num of burst drops bis number of burst loss events e num of isolated drops bis number of isolated loss events e initial zeros counts the zeros at the beginning of the current Gilbert Elliot burst e final zeros counts the zeros at the end of current Gilbert Elliot burst e ones counts the ones loss events in the current burst e tags counts the S and E tags that marks the beginning and the end of the bursts if we find an S tag we a
81. s 1 and the length of the sequence is 20000 PARAMETERS USER SPACE KERNEL SPACE PLOSS E B DENSITY PISOL E E B nod bon Es E B id is 20 5 100 0 19 335 6 212 99 095 0 715 20 340 6 341 99 090 0 705 z 20 5 80 0 20 350 5 323 88 226 3 040 19 530 5 119 88 736 3 065 5 5 80 5 20 125 5 353 88 672 6 075 20 010 5 489 87 780 6 110 20 5 100 0 19335 7 058 95 542 0 690 20310 7 119 95 536 0 620 2 20 5 80 0 20 350 7 883 77 23 2415 19 530 7 437 78 047 2 465 5 5 80 5 20 125 8 043 76 030 5 265 20 010 7 905 76 506 5 405 20 5 100 0 19 335 9 720 83 009 0 575 20 310 10 146 82 434 0 530 z 20 5 80 0 20 350 12 051 64 583 1 905 19 530 11 010 65 379 1 930 5 5 80 5 20 125 13 223 60 250 4 430 20 010 13 751 58 460 4 375 20 5 100 0 19 335 20 557 57 932 0 400 20 310 19 697 60 048 0 380 z 20 5 80 0 20 350 27 595 45 595 1 225 19 530 27 270 43 368 1 140 5 20 5 80 5 20 125 45 830 35 292 2 495 20 010 43 401 35 597 2 475 Table 10 Statistics for the GI model using 2 3 and 4 parameters As we can see from the above table the resulting values of user space and kernel space are very similar Page 65 of 70 General and Intuitive Loss Model and Netem 8 5 2 Statistics for the Gilbert Elliot model using 2 3 and 4 parameters In this section we report the statist
82. s 2 Density 50 5 10 20 length of burst input Ploss input Ploss generated Figure 10 Generated loss probability 2 versus burst length Density 50 In this second plot we change the burst density value to the half setting the third GI parameter p to 50 This corresponds to a 3 state Markov model The generated values are still close to the input ones However there is a fluctuation of Pross with the burst length value Moreover the standard deviation still increments with higher values of E B but with a smaller confidence interval Page 59 of 70 General and Intuitive Loss Model and Netem 0 65 Ploss 0 5 Density 100 0 6 0 55 0 5 Mean Ploss 0 45 0 4 0 35 5 10 20 length of burst input Ploss input 4KPloss generated Figure 11 Generated loss probability 0 5 versus burst length Density 100 Coming back to the 2 state model or equivalently to p 100 and considering smaller values of Pross for example 0 5 while the mean values still close to the input ones the coefficients of variation are higher So the generator s behavior is less predictable using small loss probabilities Page 60 of 70 General and Intuitive Loss Model and Netem 8 Testing the Kernel Space implementation 8 1 Trace2seq generating loss sequences from traces Trace2seq generates a loss sequence file suitable to be processed by sqnanalyzer starting from traces captured with tcpdump 7race
83. s the loss probability in the Bad state while the fourth parameter 1 k is the loss probability Page 42 of 70 General and Intuitive Loss Model and Netem when the system is in the Good state The parameters must be expressed as percentage and it is needed to specify the mandatory parameters p If k is not specified the Gilbert model will be used If also h is not specified the Simple Gilbert model will be used The relations between options and model are shown in the following table OPTION MODEL MANDATORY OPTIONAL PARAMETERS PARAMETERS loss GI GI General and Intuitive Pross E B P E GB loss 4state GI General and Intuitive using 4 state transition probabilities PI Pa loss gilb ell Gilbert Elliot with special cases Gilbert l h l k Simple Gilbert Bernoulli Table 6 Relations between options and models in sqngen 7 2 2 How it works code description 7 2 2 1 sqngen c structure The program is composed of six functions sqn_gen is the GI sequence generator It returns a sequence of 0 and 1 according to the transition probabilities gilb ell gen is the Gilbert Elliot sequence generator On the basis of the 1 h and 1 k parameters returns a sequence of 0 and 1 internal_check estimates the five GI General and Intuitive analyzing the generated sequence and using the S and E tags that
84. signed int k unsigned int h This function is a sequence generator based on the Gilbert Elliot loss model including as special cases the Gilbert and the Simple Gilbert models As seen for the sqn gen function it is implemented through a for loop repeated for a number of times equal to the length of the sequence A pseudorandom number is extracted of the net random function The switch construct is still Page 45 of 70 General and Intuitive Loss Model and Netem controlled by the variable state which values can be or 2 At each extraction the value of return of the net random function is compared with the loss probability in the current state that is k for state 1 and h for state 2 Then there is a second comparison with the probability of going out from the current state that is p for state 1 and r for state 2 7 2 3 1 Internal check function void internal check int length char sequence int sample double ploss bis double mean length of burst bis double density bis double pisolated loss bis double mean length of good burst bis This function performs a first check on the generated sequence calculating the GI parameters using the variables increased during the generating process described in the previous section The function gets in input the length of the generated sequence ength the sequence identification number sample within the series num of samples and the pointe
85. tc qdisc add dev eth0 root netem query loss gimodel 2 10 80 The transition probabilities are p13 is 0 256 p31 is 12 500 p32 is 19 444 using statistical independence hypothesis p23 is 77 778 using statistical independence hypothesis Page 26 of 70 General and Intuitive Loss Model and Netem p14 is 0 000 The GI General and Intuitive parameters would be ploss is 2 000 burst duration is 10 000 burst density is 80 000 isolated ploss is 0 000 good burst duration is 1 286 using statistical independence hypothesis Note that in the examples shown until now we are calculating the good burst length still using the statistical independence hypothesis Now we try to set manually a higher value of good burst duration Comparing this to the previous case p32 increases This is reasonable because the burst length and the burst density are unchanged so we have a higher number of good bursts and we pass from state 3 to state 2 more frequently Moreover the good burst length is higher so it is less probable that we return to State 3 so p23 decreases tc qdisc add dev eth0 root netem query loss gimodel 2 10 80 0 2 The Transition probabilities are p13 is 0 256 p31 is 12 500 p32 is 12 500 p23 is 50 000 p14 is 0 000 The GI General and Intuitive parameters would be ploss is 2 000 burst duration is 10 000 burst density is 80 000 isolated ploss is 0 000 good burst d
86. ternal check while the ter suffix are relative to the parameters calculated by the external check Each one of the various 2inin Zminz is relative to a different value of Emi used in external check This is needed because the external check is repeated for different values of gmin Sample is the sequence which the values are relative for example sample 1 and num of samples 10 means that we are considering the first of ten generated sequence Page 51 of 70 General and Intuitive Loss Model and Netem The lines of statistics dat have the following format e internal N A ploss_mean mean_length_of_burst_mean density_mean pisol_mean mean length of good burst mean ploss variance mean length of burst mean density mean pisol variance mean length of good burst variance ploss stddev mean length of burst stddev density stddev pisol stddev mean length of good burst mean stddev ploss cx mean length of burst cx density cx pisol cx mean length of good burst cx e externab gmin ploss mean mean length of burst mean density mean pisol mean mean length of good burst mean ploss variance mean length of burst mean density mean pisol variance mean length of good burst variance ploss stddev mean length of burst stddev density stddev pisol stddev ploss cx mean length of burst cx density cx pisol cx mean length of good burst cx where internal and external identifies the check method Note that gmin
87. th of each sequence is 200000 PLOSS E B PISOL PLOSS PLOSS PLOSS E B PISOL E GB H 02 cv u H u H 2 5 100 0 1 995 0 01195 0 05479 4 97762 100 0 0 2 5 80 0 2 000 0 0072 0 042 5 023 79 889 0 1 336 2 5 50 0 2 009 0 0023 0 024 5 001 50 106 0 2 656 2 10 100 0 1 984 0 0103 0 051 9 926 100 0 0 2 10 80 0 1 989 0 0111 0 053 9 972 80 068 0 1 284 2 10 50 0 2 008 0 0100 0 049 9 977 50 007 0 2 254 2 20 100 0 1 982 0 037 0 097 20 104 100 0 0 2 20 80 0 2 026 0 0224 0 073 20 213 79 955 0 1 266 2 20 50 0 1 998 0 018 0 067 20 034 50 073 0 2 108 1 5 100 0 0 978 0 0034 0 059 4 939 100 0 0 1 5 80 0 0 984 0 0036 0 061 4 970 80 045 0 1 334 1 5 50 0 0 993 0 0023 0 048 4 956 50 163 0 2 666 1 10 100 0 1 006 0 0085 0 091 10 007 100 0 0 1 10 50 0 0 993 0 0050 0 071 10 09 49 951 0 2 247 1 20 100 0 0 962 0 0196 0 145 19 50 100 0 0 1 20 80 0 1 019 0 0140 0 116 20 37 80 049 0 1 264 1 20 50 0 0 993 0 0066 0 082 19 91 50 047 0 2 104 0 5 5 100 0 0 497 0 0019 0 088 5 026 100 0 0 0 5 5 80 0 0 505 0 0018 0 084 5 029 80 066 0 1 329 0 5 5 50 0 0 502 0 0007 0 054 5 035 49 890 0 2 679 0 5 10 100 0 0 490 0 0032 0 118 9 938 100 0 0 0 5 10 80 0 0 502 0 0030 0 109 10 069 79 853 0 1 289 0 5 10 50 0 0 489 0 0031 0 114 9 7887 50 211 0 2 252 0 5 20 100 0 0 515 0 0136 0 226 20 256 100 0 0 0 5 20 80 0 0 515 0 0097 0 191 19 985 79 815 0 1 264
88. the tc patch do cd your iproute2 source tree patch 1 lt iproute2 3 2 0 patch substitute iproute2 3 2 0 patch with the path where you have unpacked the archive Then build iproute2 6 2 tc netem user manual for the latest version The modified version of tc allows the user to add loss features to the outgoing packets according to several models according to the following syntax Page 24 of 70 General and Intuitive Loss Model and Netem Adding a loss pattern according to a model Querying information from a loss model qdisc add change del dev ethO root netem loss gimodel P BURST DENSITY PISOL GOOD BURST LENGTH I I tc qdisc add change del dev ethO root netem loss gemodel PERCENT R 1 H 1 K tc qdisc add change del dev ethO root netem loss state P13 P31 P32 P23 14 tc qdisc add dev ethO root netem query loss gimodel P BURST DENSITY PISOL GOOD BURST LENGTH III Where the correspondence between options and model are OPTION MODEL Loss gimodel GI General and Intuitive Allows special case 4 3 2 and 1 parameters Loss gemodel Bernoulli Simple Gilbert Gilbert Gilbert Elliot Loss state Loss 4 state with the transition probabilities p13 p31 p31 p23 p14 Table 2 Options and models in tc netem If the selected option is loss gemodel the Gilbert Elliot generation algorithm will be used If the selected option is one
89. to use in the check gmin max the array containing the sequence sequence the pointers to the arrays where similarly to the case of internal check the estimated values will be stored The ploss estimation is made counting the number of 1 in the sequence This is trivial while for the other parameter the question is very tricky because they involve the concept of burst Since we Page 47 of 70 General and Intuitive Loss Model and Netem do not have any extra information except the sequence itself it is needed to use a strict and not ambiguous definition of what is a burst We will use the definition presented in RFC3611 that is A burst is defined in terms of a value min as the longest sequence that starts with a lost or discarded packet does not contain any occurrences of min or more consecutively received and not discarded packets and ends with a lost or discarded packet Then estimated values are different choosing different values of We will now describe the various step of the algorithm A new boolean variable named this is burst is introduced Its values are true when we are into burst and false when we are outside The check is repeated through a for loop using different values of obtained using a base value 2 and doubling it at each instance of the loop until the maximum value gj 15 reached There is a second for loop where the analysis is performed Two situations are distinguish
90. ty h If1 3 the corrected burst length can be 3 LxL with probability 1 h 2 TLL LLT with probability 2h 1 h 1 TTL LTT with probability 3h 1 h 0 TTT with probability h If i 4 the corrected burst length can be 4 LxxL with probability 1 h 3 TLxL or LxLT with probability 2h 1 h 2 LLTT with probability 3h 1 hy 1 TTTL TILT TLTT LTTT with probability 4h 1 h 0 TTTT with probability h Ifi 5 the corrected burst length can be 5 LxxxL with probability 1 h 4 TLxxL LxxLT with probability 2h 1 h 3 TTLxL LxLTT LTxTL with probability 3h 1 hy 2 TTTLL TTLLT TLLTT LLTTT with probability 4h 1 h 1 TTTTL TTTLT TTLTT TLTTT LTTTT with probability 5h4 1 h 0 TTTTT with probability h Ifi 6 the corrected burst length can be 6 LxxxxL with probability 1 h 5 TLxxxL LxxxLT with probability 2h 1 h 4 TTLxxL LxxLTT LTxxTL with probability 3h 1 hy 3 TTTLxL TTLxLT TLxLTT LxLTTT with probability 4h 1 h 2 TTTTLL TTTLLT TTLLTT TLLTTT LLTTTT with probability 5h 1 h 1 TTTTTL TTTTLT TTTLTT TTLTTT TLTTTT LTTTTT with probability 6h 1 h 0 TTTTTT with probability h I P B i 6 5 4 3 2 1 0 1 h h 1 h 2h 1 h h r 1 r 1 h 2h 1 hy 3hY 1 h h r 1 r 1 h 2h 1 hy 3h 1 4h 1 h h Page 18 of 70 General and Intuitive Loss M
91. uration is 2 000 The last example shows that burst density value has a heavy influence on the good burst duration reducing density to 50 increases it more than twofold tc qdisc add dev eth0 root netem query loss gimodel 2 10 50 The transition probabilities are p13 is 0 417 p31 is 20 000 p32 is 44 444 using statistical independence hypothesis p23 is 44 444 using statistical independence hypothesis p14 is 0 000 Page 27 of 70 General and Intuitive Loss Model and Netem The GI General and Intuitive parameters would be ploss is 2 000 burst duration is 10 000 burst density is 50 000 isolated ploss is 0 000 good burst duration is 2 250 using statistical independence hypothesis 6 3 Original NetemCLG and tc netem patches to Linux Kernel 2 6 39 1 and iproute2 2 6 39 6 3 1 How to apply patch to kernel before it was accepted the scheduler in the kernel This section describes how to install the patches that adds the new change of the correlated loss models to the sch netem module of the Linux kernel and to the tc utility These instructions are included in file INSTALL TXT into the patch package To install the NetemCLG kernel patch do cd your linux source tree patch Kernel 2 6 39 1 patch substitute Kernel_2 6 39 1 patch with the path where you have unpacked the archive Then enable as module Network Emulator NETEM in the kernel co
92. ving isolated loss events model with 3 parameters Now we consider 3 state model obtained from the above shown 4 state setting 4 0 This means we will not have isolated loss events and will never enter in State 4 Since 0 the system can be described through three effective GI parameters Loss probability e Loss density within the burst e Mean burst length E B p13 p32 1 p23 1 p13 31 23 Figure 4 3 state model The transition probabilities become gt mim Loss T E B 3 E B E B P32 P23 1 B po _ 1 p E B p M n 5 HEB 1 _ E B p 1 9 E B 1 The model is valid under the following constraints E B 2 1 p PLoss lt Pzoss 1 1 lt E B 1 Piso p Pross 1 p E B 1 p E B 1 gt E B gt 2 p 1 p Page 10 of 70 General and Intuitive Loss Model and Netem 3 2 4 Consecutive losses model with 2 parameters Now we remove the State 2 relative to packets received during burst periods Therefore we can model loss bursts made of consecutive loss events We set p32 0 and p 1 for consistency reasons obtaining a 2 state Markov chain Pau i 5 Pis Ds z 72 1 _ Py P31 p13 1 p13 1 p31 p31 Figure 5 The 2 state Markov chain Since we have Piso 0 and p 1 the GI parameters involved are only two Pros and E B Mean
93. with the correct value according to the interface chosen for the simulation The parameters values are always expressed as percentage except for burst length that is integer Page 30 of 70 General and Intuitive Loss Model and Netem 6 5 NetemCLG code enhancements 6 5 1 NetemCLG This section describes the differences between Netem and NetemCLG or rather the pieces of code added to Netem to implement the new features described in Section 6 2 The modified files are sched h in kernel source path linclude linux and sch netem c in kernel source path net sched Note that kernel source gt stands for the path where the kernel sources have been unpacked Both in pkt sched h were added e the structure netem gimodel containing the parameters relative to the correlated loss models model to select a model a a2 a3 a4 a5 that contains the paramters relative to GI 4 state models struct tc netem gimodel State transition probabilities for 4 state model __u32 p13 __u32 p31 __u32 p32 __ 32 14 __u32 p23 struct tc_netem_gemodel Gilbert Elliot model __ 32 __ 32 u32 h __ 32 Only in sch_netem c were added e the following variables into the struct netem sched data CLG_RANDOM CLG_4_STATES CLG_GILB_ELL loss_model Correlated Loss Generation models struct clgstatef u state State of the Ma

Download Pdf Manuals

Related Search

Related Contents

GN70-B7086_UG_v1.0  Active Braille  Samsung 400MX-3 Uporabniški priročnik  UTILITY FLIGHT MANUAL  Mode d`emploi court pour les enseignants  2013 Jeep Grand Cherokee SRT8 User`s Guide    SISTEMA DE SONIDO PARA iPod MICD-009-HIFI  

Copyright © All rights reserved. Failed to retrieve file