documentsn.com

In 1960, Gilbert [3] proposed a model to characterise a burst-noise channel.It adds memory to the Binary Symmetric Channel coded into two states of theMarkov chain. Gilbert considered the special case of an error-free good state(k 1) and suggested to estimate the model parameters from three measurableinstances of a binary error process {Et }t N , where Et 1 indicates an error:a P (1),b P (1 1),c P (111).P (101) P (111)(3)By knowing a, b and c, the three model parameters can be computed in thefollowing manner1 r ac b2;2ac b(a c)h 1 b;1 rp ar.1 h a(4)Gilbert argues that the c measurement may be avoided by choosing h 0.5 andusing 1 r 2b. Furthermore, he showed that the method introduced above canlead to ridiculous parameters (p, r, h 0, or p, r, h 1), if the observation (thetrace) is too small. Morgera et al. [17] also conclude that the method proposedby Gilbert is more appropriate for longer traces. In case of shorter observations,better results can be obtained when considering the Gilbert model as HiddenMarkov Model trained by the Baum-Welch algorithm [18–20].Parameters of an even simplified Gilbert model with h 0 can also beestimated with the method presented by Yajnik et al. [8]p P (1 0);r P (0 1).(5)A more intuitive parameter estimation technique can be found by consideringthe Average Burst Error Length (ABEL) to determine r 1/ABEL and theaverage number of packet drops to determine pE . Equation (2) leads to p pE · r/(h pE ). Gilbert’s model was extended by Elliott [4] in 1963 includingerrors in both states as in Figure 2.ModelParameter Training Complexity SimplificationSimple Gilbertp, rsimplek 1, h {0, 0.5}Gilbertp, r, hmediumk 1Gilbert-Elliott p, r, h, khigh/Table 2. Comparison of simplified two-state Markov channel models4Variance of the Error Process over Multiple TimeScalesThe second order statistics of the 2-state Markov process can be derived viagenerating functions. While it is straightforward to compute the distribution

function of errors in time frames of length N 1 iteratively from the resultfor length N , a non-iterative direct solution is less obvious already for the 2state Markov model [21]. To the authors knowledge, explicit expressions for thevariance of the number of errors during a time frame of fixed length, are notgiven in the literature, although there is a large volume of work involving theGilbert-Elliott model, as partly discussed in Section 6 on related work. However,most of this work is devoted to error detecting and correcting codes and theresidual error probabilities of coding schemes, rather than on traffic or packetloss characterisation. Second order statistics in multiple time scales is a standardapproach in teletraffic modelling [5, 6].Although Markov models do not exhibit self-similar properties, they havebeen successfully adapted to self-similar traffic [22] and are still popular sincethey often lead to simple analytical results. Following this trend, we next derivethe variance of the number of packet drops as errors in the 2-state Gilbert-Elliottmodel over a range of relevant time frames.4.1Generating Functionsdef PiLet GN (z) (BN (z)) denote the generating function X(z) i P {X i}zfor the number of packet drops in a sequence of N packet arrivals, leaving theMarkov chain in the last step at state G (B). Iterative relationships can be setup to compute GN 1 (z) from GN (z) taking into account the state transitionsand factors (k (1 k)z) and (h (1 h)z) for possible drop of the (N 1)-thpacket with state dependent probabilities 1 k and 1 h, respectively:GN 1 (z) (1 p)(k (1 k)z)GN (z) r(h (1 h)z)BN (z)(6)BN 1 (z) p(k (1 k)z)GN (z) (1 r)(h (1 h)z)BN (z)(7)Starting in steady state conditions we initialiseG0 (z) r;p rB0 (z) p.p r(8)The corresponding distributions GN (z), BN (z) remain defective GN (1) r/(p r) and BN (1) p/(p r) N N. We finally evaluate complete distributionsgiven by GN (z) BN (z) where GN (1) BN (1) 1 independent of the finalstate.The k-th moment can be derived from the generating function by consideringthe k-th derivative [23, 24]: E[X k ] z k X(z) z 1 . The mean µX E(X) andthe second moment E(X 2 ) are sufficient to derive the second order statisticsinvolving the first and second derivative of the generating functions.G0N 1 (z) (1 p) · ((1 k) · GN (z) (k (1 k)z) · G0N (z))0 r · ((1 h) · BN (z) (h (1 h)z) · BN(z))G00N 1 (z) (1 p) · (2(1 k) · G0N (z) (k (1 k)z) · G00N (z))000 r · (2(1 h) · BN(z) (h (1 h)z) · BN(z))(9)(10)

00BN 1 (z) p · ((1 k) · GN (z) (k (1 k)z) · GN (z))(11)0 (1 r) · ((1 h) · BN (z) (h (1 h)z) · BN(z))00000BN 1 (z) p · (2(1 k) · GN (z) (k (1 k)z) · GN (z))000 (1 r) · (2(1 h) · BN(z) (h (1 h)z) · BN(z))4.2(12)Mean Values0B0The mean values are given by µGN GN (1) and µN BN (1), which leads to thefollowing expressions (1 k)r(1 h)pGBµG (1 p)· µ r· µ(13)N 1NN ,p rp rµBN 1 p·(1 k)r µGNp r (1 r) ·(1 h)p µBNp r .(14)BConsidering the sum of µGN 1 and µN 1 leads to the expected result of N 1times the failure rate in the steady state: (1 k)r (1 h)pGB (N 1)pE . (15)µN 1 µN 1 µN 1 (N 1) p rp rTo eliminate the reference to the opposite term, µBN 1 can be rewritten asµBN 1 pr(1 k)p(1 h)BBB p · µG µ µ (1 r)· µNN N {z N}p rp r(15) (N 1) ·pr(1 k) p2 (1 h) p rp r [1 (p r)] · p(1 h)B µN .p r(16)Next, we structure the above equation according to their dependence on Nand µBN with abbreviations for the main terms α, βB and γB :BµBN 1 (N 1) · βB α · (µN γB );βB : pr(1 k) p2 (1 h) ;p rp rα : 1 (p r);γB : (1 h)p.p r(17)(18)Computing a series of the first mean valuesµB1 βB αγB ,2µB2 2βB α(βB γB ) α γB ,(19)

suggests the general result, which is proven by induction over N :µBN γB NXαj (γB βB γB (N j))j 0 NαβB βB γB 1 αN ,1 α1 α 1 αfor α 6 1(20)The case α 1, which means p r 0 implies a reducible and thus non-ergodicMarkov chain, which is not relevant for modelling purposes.Due to the symmetry of both states G and B, GN (z) can be obtained fromBN (z) by swapping the parameters p r and h k and vice versa. Thus,NGN (p, r, h, k, z) BN (r, p, k, h, z) and µGN (p, r, h, k) µB (r, p, k, h). ConsiderBGing the sum µN µN again leads to Equation (15).4.3Explicit Solution for the VarianceUsing the mean values, the variance of the number of packet losses in a timeframe of size N can be derived as follows00GB0000G00N 1 (1) BN 1 (1) 2(1 k)µN 2(1 h)µN GN (1) BN (1) 2(1 k)NXi 1µGi 2(1 h)NXµBi .(21)i 1The sum of the mean values yields NNXX iβsαsµi βs γs 1 αi , s {G, B}1 α1 α 1 αi 1i 1 N (N 1)βsαα(1 αN ) βs γs N .2(1 α)1 α 1 α1 α200 µN , the previous(1) µ2N σNBased on the relationship G00N (1) BNGB0000of σNsolution for GN 1 (1) BN 1 (1) yields the standard deviation σN σNthe number of lost packets as well as the coefficient of variation cv (N ) σN /µN .We finally arrive at the following result for cv (N ) expressing the second orderstatistics of the number of errors or packet losses in a sequence of length Ngenerated by the Gilbert-Elliott model:p00 (1) µ2 µG00N (1) BNNNcv (N ) ;ω : (1 h)p (1 k)rµNs 1hp kr 2pr(1 p r)(h k)21 (1 p r)N 1 .ωω 2 (p r)N (p r)N(22)The solution is comprehensible enough to interpret the influence of the modelparameters. Note that the evaluation of the term 1 (1 p r)N may causenumerical instability for small p, r, which can be improved by implementing theequivalent form 1 (1 p r)N 1 eln(1 p r)·N .

4.4Simple CasesIn case of h k, both states are indistinguishable and the Markov chain collapsesto a single state leading to the simplified resultsh.(23)cv (N ) (1 h)NNThis corresponds to a binomial distribution GN (z) BN (z) [h (1 h)z]of independent random packet losses generated by a memoryless process.If p r 1, the Markov chain again generates a memoryless process, sincethe transition probabilities, e.g. to state B, are the same starting from B or G:P (qt B qt 1 G) p;P (qt B qt 1 B) 1 r p.Again, the coefficient of variation is simplified:s1hp krcv (N ) .N (1 h)p (1 k)r(24)(25)The precondition p r 1/N also leads to a simpler representation of theform, since the last fraction in Equation (22) approaches 0 in that case:rhp kr (N 1)pr(h k)2 ;ω : (1 h)p (1 k)r.cv (N ) NωN ω24.5Parameter Impact on the Second Order Statistics of theGilbert-Elliott Model10.10.01p r 1.01*10-1p r 1.01*10-2p r 1.01*10-3p r 1.01*10-4p r 1.01*10-5p r 1.01*10-6p r 1.01*10-70.001100 101 102 103 104 105 106 107 108 109N - Time Scale [Packets](a) h 0, k 1Coefficient of Variation cv(N)Coefficient of Variation cv(N)101010.10.01p r 1.1*10-1p r 1.1*10-2p r 1.1*10-3p r 1.1*10-4p r 1.1*10-5p r 1.1*10-6p r 1.1*10-70.001100 101 102 103 104 105 106 107 108 109N - Time Scale [Packets](b) h 0.99, k 0.9999Fig. 3. Parameter impact on the second order statistics of the Gilbert-Elliott modelBased on the analytical result in Equation (22) for cv (N ), the main propertiesof the second order statistics of the Gilbert-Elliott model become visible.

p1. pThe starting point of the curves for cv (N ) is given by cv (1) (hp kr)/ω 1/pE 1 and thus only depends on the packet loss rate.2. Figure 3(a) shows curves of cv (N ) for h 0 and k 1 such that thebad state generates bursts of subsequent packet losses and pE πB r/(p r). In all examples of Figure 3(a) we keep the ratio r/p 1/100constant such that pE 1/101 cv (1) 10. The curves are characterisedby a horizontal part, which holds the variance on the initial cv (1) valuefollowed by a declining part. The length of the part at constant level dependson p r, i.e. on the intensity of transitions between the states, which isdifferent but fixed for each curve in Figure 3(a). The sojourn times of thegood and bad state are geometrically distributed with mean (1 p)/p and(1 r)/r, respectively. For limp r 0 the mean holding times of the statesare extended on longer times scales.3. Then the correlation in the modelling process persists over about the sametime scale and the transition point from the constant to the declining partof the cv (N ) curve is shifted in the range between 1/p and 1/r.The decreasing part soon approaches the same slope as is valid for a memoryless process with independent random losses at a given rate, such thatcv (kN )/cv (N ) k.Figure 3(b) shows results, where p r is again stepwise reduced by a factor10 as in 3(a), but this time with h 0.99, which means a low loss probability of1% in the bad state and by settingr/p 1/10 the total loss probability is kept at pE 1/1100 cv (1) 1099. Again the coefficient of variation stays ata constant level over multiple time scales for small p r, but essentially belowthe initial cv (1) value.5EvaluationThe evaluation of the trained 2-state Markov models using the coefficient ofvariation cv (N ) σN /µN is shown for two backbone traces with different packetloss rates in Figure 4 and 5. The Poisson process provides a linear lower boundfor cv (N ) without any autocorrelation. The parameters of the simple Gilbert(h 0, k 1) and the Gilbert model have been estimated from the given tracesusing the traditional methods proposed by Yajnik et al. [8] and Gilbert [3] asintroduced in Section 3.Moreover, the simplified Gilbert, the Gilbert and the Gilbert-Elliott modelhave been trained based on the second order statistics over multiple timescalesN [1, 105 ], as shown in Figure 4 and 5. The model parameters were estimated by fitting the coefficient of variation curve to the one obtained from thecorresponding trace using the Levenberg-Marquardt algorithm for numeric optimisation of non-linear functions. Initial trial values for the parameters wereestimated from the study of the impact of different model parameters discussedin Section 4.5.

Coefficient of Variation cv(N)101TracePoisson ProcessSimple Gilbert using eq. (5)Gilbert using eq. (3-4)Simple Gilbert ndusing 2nd order statisticsGilbert using 2 order statisticsGilbert-Elliott using 2nd order statistics0.1100101102103N - Time Scale [Packets]104105Fig. 4. Evaluation of the trained 2-state Markov models using the coefficient of variation cv σ/µ for a backbone trace with a mean packet loss rate of 0.7%.Trace Trained Model0.7 % Simple GilbertGilbertElliott0.1 % Simple 322532.9365·10 51.3343·10 51.33308·10 .00601795hkpE010.95%0.56351310.77%0.559691 0.999372 0.71%010.13%0.55504410.098%0.554949 0.999999 0.098%Table 3. Estimated model parameters for both traces using second order statistics.The mean packet loss rate of the first trace is 0.7% and 0.1% in case of the second.The distance between different model curves as shown in Figure 4 and 5 andthe trace curve is measured by the the Mean Square Error (MSE)5 5MSE(model) 1010X(cmodel(N ) cmodel(N ))2 ,vv(26)N 1where a smaller MSE indicates a better fit. Table 4 compares the consideredmodels.The model parameters resulting from the adaption to the coefficient of variation found in the trace are given in Table 3. This trend confirms the assignmentof h 0.5 by Gilbert [3]. The packet loss rate pE of the simple Gilbert modelwith h 0 essentially deviates from the trace.

Coefficient of Variation cv(N)1010.1100TracePoisson ProcessSimple Gilbert using eq. (5)Gilbert using eq. (3-4)Simple Gilbert using 2nd order statisticsGilbert-Elliott using 2nd order statistics101102103N - Time Scale [Packets]104105Fig. 5. Evaluation of the trained 2-state Markov models using the coefficient of variation cv σ/µ for a backbone trace with a mean packet loss rate of 0.1%.Trace / Model Simple Gilbert (eq. 5) Gilbert (eq. 3-4) Simple Gilbert Gilbert 91.09Table 4. Mean Square Error (MSE) distance between different trained models and thetwo traces. The Markov models were trained using classical techniques (eq. 5 and 3-4)and the second order statistics as described in Section 4.However, when we look at the distribution of the length of packet losses in aseries, then the classical fitting procedures seem to be in favour, as experiencedfrom first evaluations. This is not unexpected, since they are closer related toerror burst lengths whereas the second order statistics can include long rangecorrelation. The extraction of the most relevant information in measurementtraces to be used for the fitting of model parameters with regard to the Qualityof Experience aspects (QoE) is still for further study. The relevance of burstssurely increases with the observed mean failure burst length in a consideredtraffic flow.6Related WorkCuperman [21] derives the generating function Hm (z) for m errors in a binaryseries of arbitrary length, where P (m, n) denotes the probability of m errors in

a series of length n. XpHm (z) P (m, n)z zp rn mg(z) n XP (0k 1 1/1)z k ; 1 g(z)1 z 2[g(z)]m 1(27)1 m nk 1However, the result is not directly transferable to obtain the second order statistics, since it is summing up over an infinite range of the length n rather thanfocusing on a fixed length n.Girod et al. [7] found a simple Gilbert model (k 1, h 0) useful to describethe characteristics of packet losses in Internet connections and to derive an errormodel for Internet video transmissions on top, as lost packets will affect theperceived quality of the video transmission. Huitika et al. [25] extended thesimple Gilbert model by adapting it to the datagram loss process in the scopeof real-time video transmissions, by adding a third state to describe out-of-orderpackets. Zhang et al. [9] use a simple Gilbert model to describe a cell discardmodel for MPEG video transmissions in ATM networks, where the cell lossesare caused by excessive load at ATM multiplexers.McDougall et al. [26] proposed a 4-state Markov model with a hypergeometrical distribution of the sojourn time in the good and bad state as approximationof an IEEE 802.11 channel. Poikonen et al. [14] [15] compared finite state Markovmodels, such as the McDougall model, in order to simulate the packet error behaviour of a DVB-H system. The McDougall model and the Markov-based TraceAnalysis (MTA) [27] outperformed the Gilbert model, as the latter was unable toreproduce the variance in burst error lengths. Yajnik et al. [8] point out that thesimple Gilbert model is suitable if the error gap length of the traces is geometrically distributed, but can be outperformed by considering high-order Markovchains.Tang et al. [12] used a simple Gilbert model to create a multicast loss modelin IEEE 802.11 channels. Hartwell et al. [13] compared five finite-state Markovmodels to create a frame loss model for IEEE 802.11 indoor networks and foundout that high order models trained by the Baum-Welch algorithm outperformedthe Gilbert model. McDougall et al. [11] were able to reproduce the packeterror rate and the average burst error length of an IEEE 802.11 channel usingthe simple Gilbert model, but failed to replicate the variance in error burstlengths and therefore suggested to use Gamma based state durations, as in [28].McDougall et al. [11] also suggest that the restriction of geometrically distributedstate lengths due to the Gilbert-Elliott model can be overcome and, for example,the Gamma distribution can be used.7ConclusionThis work provides a method to adapt the parameter set of a 2-state Markovianerror pattern generator to match the second order statistics over multiple time

scales. The generating functions approach provides recursive relationships forthe distribution of the number of lost packets, which finally leads to an explicitand clearly structured solution for the second order statistics. Special cases ofthe model as well as the impact of its parameters are discussed. Naturally, fittingprocedures based on second order statistics yield a closer match in multiple timescales than classical adaptation schemes, which on the other hand are better inmodelling error bursts.Therefore it depends on the purpose of the model and it partly remainsfor further study, which statistical indicators should be involved in the fittingprocedure. However, the proposed approach gives more flexibility to includeinformation from different time scales enabling a simple and useful fit for longtraces of traffic and packet loss processes. Several Markov approaches have beenproposed providing more states and parameters, which improve the accuracyof the fit to the observed process characteristics on account of more complexadaptation schemes.AcknowledgementsWe would like to thank for the support by Deutsche Telekom Laboratories (TLabs), Berlin within the T-V-Model project and especially the fruitful discussionswith Rüdiger Geib at T-Systems.References1. Floyd, S., Jacobson, V.: Random early detection gateways for congestion avoidance. IEEE/ACM Trans. Netw. 1 (1993) 397–4132. Haßlinger, G., Mende, J., Geib, R., Beckhaus, T., Hartleb, F.: Measurement andcharacteristics of aggregated traffic in broadband access networks. In Mason, L.,Drwiega, T., J.Yan, eds.: 20th International Teletraffic Congress (ITC20), Ottawa,Canada, Springer LNCS 4516 (2007) 998–10103. Gilbert, E.N.: Capacity of a Burst-Noise Channel. Bell System Technical Journal39 (1960) 1253–12654. Elliott, E.O.: Estimates of Error Rates for Codes on Burst-Noise Channels. BellSystem Technical Journal 42 (1963) 1977–19975. Tsybakov, B., Georganas, N.D.: On self-similar traffic in atm queues: definitions,overflow probability bound, and cell delay distribution. IEEE/ACM Trans. Netw.5 (1997) 397–4096. Leland, W.E., Taqqu, M.S., Willinger, W., Wilson, D.V.: On the self-similar natureof ethernet traffic. ACM SIGCOMM Computer Communication Review 23 (1993)183–1937. Girod, B., Stuhlmüller, K., Link, M., Horn, U.: Packet Loss Resilient InternetVideo Streaming. In: Proceedings of SPIE Visual Communications and ImageProcessing. (1999) 833–8448. Yajnik, M., Moon, S.B., Kurose, J.F., Towsley, D.F.: Mea

1 T-Systems, Deutsche-Telekom-Allee 7, D-64295 Darmstadt, Germany 2 Darmstadt University of Technology, Merckstr. 25, D-64283 Darmstadt, Germany armstadt.de Abstract. The estimation of quality for real-time services over telecom-munication networks requires realistic models for impairments and fail-