Mạng lưới giao thông và đánh giá hiệu suất P4

Self-Similar Network Traf®c and Performance Evaluation, Edited by Kihong Park and Walter Willinger Copyright # 2000 by John Wiley & Sons, Inc. Print ISBN 0-471-31974-0 Electronic ISBN 0-471-20644-X 4 QUEUEING BEHAVIOR UNDER FRACTIONAL BROWNIAN TRAFFIC ILKKA NORROS VTT Information Technology, Espoo, Finland 4.1 INTRODUCTION This chapter gives an overview of some properties of the storage occupancy process in a buffer fed with ``fractional Brownian traf®c,`` a Gaussian self-similar process. This model, called here ``fractional Brownian storage,`` is the logically simplest long-range-dependent (LRD) storage system having strictly self-similar input varia-tion. The impact of the self-similarity parameter H can be very clearly illustrated with this model. Even in this case, all the known explicitly calculable formulas for quantities like the storage occupancy distribution are only limit results, for example, large deviation asymptotics. Scaling formulas, on the other hand, hold exactly for this model. The simplicity is won at the price that the input model is not meaningful at smallest time scales, where half of the ``traf®c`` is negative. The model can be justi®ed by rigorous limit theorems, but it should be emphasized that this involves not only a central limit theorem (CLT) argument for Gaussianity but also a heavy traf®c limitÐsee Chapter 5. From a less rigorous, practical viewpoint one can say that fractional Brownian storage gives usable results when, at time scales relevant for queueing phenomena, the traf®c consists of independent streams such that a large number of them are simultaneously active, and second-order self-similarity (see Chapter 1) holds. Chapter 7 describes many features of storage processes with ®nitely aggregated on=off input traf®c, which differ qualitatively from those of fractional Brownian Self-Similar Network Traf®c and Performance Evaluation, Edited by Kihong Park and Walter Willinger ISBN 0-471-31974-0 Copyright # 2000 by John Wiley & Sons, Inc. 101 102 QUEUEING BEHAVIOR UNDER FRACTIONAL BROWNIAN TRAFFIC storage. For example, the correlation function of the input process remains unchanged if one changes the distributions of on and off periods to each other, whereas the queueing process usually becomes entirely different. Thus second-order self-similarity alone tells nothing about queueing behavior, if the traf®c variation cannot be considered Gaussian. Another important difference can be seen in how a queue builds up. Assume that the individual sources are relatively powerful so that a queue starts to build up when a small number, say, k of them are simultaneously active. Then a small increase in link speed can result in a considerable performance improvement, if it happens to increase the small integer k by one. A related observation about a possibly big effect of a small increase in buffer size is discussed in Chapter 10 in GI=GI=1 context. In fractional Brownian traf®c, in contrast, individual source streams are thought of as being in®nitely thin compared with the link speed, and phenomena caused by the granularityof traf®c are not re¯ected in the model. On the other hand, if the Gaussian property is suf®ciently well satis®ed, but second-order self-similarity holds only asymptotically, then some of the techniques presented in this chapter are still usable in a modi®ed form. See Addie et al. [1]. As a special case with H ˆ 1, the model includes the ``Brownian storage,`` which is often used in the heavy traf®c limit as a diffusion approximation for short-range-dependent (SRD) queueing systems. Many problems have explicit solutions in the Brownian case, and one method to study the fractional case is to analyze their derivations and identify the steps that are not justi®ed when H does not equal to 1. Regrettably, almost all methodological cornerstones of Brownian motion are based on independence and thus unavailable when H ˆ 1: independent increments, Markov property, margingale property, renewal times. Besides self-similarity, the general methods available for fractional Brownian storage come from the literature on Gaussian processes. In particular, the beautiful theory of their large deviations in path space turns out to be well suited for the needs of performance analysis. This chapter is structured as follows. The de®nitions are given in Section 4.2. Some basic scaling formulas are derived in Section 4.3. Results based on large deviations in path space are presented in Section 4.4. Finally, some other approaches are outlined in Section 4.5. 4.2 INPUT, OUTPUT, AND STORAGE PROCESSES We consider in continuous time an unlimited ¯uid storage that is fed by fractional Brownian traf®c, de®ned below, and emptied at constant service rate c. 4.2.1 The InputProcess, ``Fracitonal Brownian Traf®c`` The ¯uid input in time interval …s;tŠ is denoted by A…s;t† and it has the form A…s;t† ˆ m…t ÿ s† ‡ s…Zt ÿZs†; s;t 2 …ÿ1;1†;s t; 4.2 INPUT, OUTPUT, AND STORAGE PROCESSES 103 where m and s are nonnegative parameters, m < c, and the process …Zt†t2R is a normalized fractional Brownian motion (FBM), de®ned as a centered Gaussian process with stationary increments, continuous paths, and variance EZ2 ˆ jtj2H (see Chapter 1). Z is a self-similar process: …Z…at†;t 2 R†ˆ…aHZ…t†;t 2 R† …4:1† for every a > 0, where ˆ denotes that the processes have the same ®nite-dimen-sional distributions (considered as random elements of some appropriate space of continuous functions, the whole processes then have the same distribution). H is called the self-similarity parameter, and it is a number from the interval (0, 1). Thus the traf®c model has three parametersÐm;s2, and HÐand the storage model has in addition a fourth parameterÐc. The parameter m is the mean input rate, and s2 is the variance of traf®c in a time unit. It is often useful to write s2 ˆ ma; where a, the index of dispersion at unit time, has sometimes been called ``peaked-ness.`` The point in using ma instead of s2 is that varying m can now be interpreted as varying the number of traf®c sources alone, without changing their characteristics. The parameter H characterizes dependence in the input process. For H 2 …1 ;1†, all the random variables A…s;t† with s < t are strictly positively correlated. For H ˆ 1, the input process is a Brownian motion, and the storage model is a classical diffusion approximation for a queueing process. For H 2 …0;1†, inputs on disjoint intervals are negatively correlated. It is possible that this case has no natural applications in teletraf®c contexts, but including it comes usually for free, so we do not exclude it. We also write At ˆ A…0;t† for t 0; At ˆ ÿA…t;0† for t 0: …4:2† Then A…s;t† ˆ At ÿ As. This model was identi®ed by Leland et al. [8] and by Norros [12, 13] as a simple way to include the observed self-similarity features of data traf®c in mathematical performance analysis. 4.2.2 The Storage Process The storage occupancy process with fractional Brownian traf®c as input is de®ned by Reich`s formula: V ˆ sup…A…s;t†ÿ c…t ÿ s††; t 2 …ÿ1;1†: …4:3† st 104 QUEUEING BEHAVIOR UNDER FRACTIONAL BROWNIAN TRAFFIC In words: if A…s;t† > c…t ÿs†, the buffer must contain at time t at least the difference; a short reasoning yields that, on the other hand, it does not contain more than the maximum over s of such differences. Since Z has stationary increments, V is a stationary process. Z is invertible in time, so V0 is distributed like supt0…A…0;t† ÿ ct†. An application of Kolmogor-ov`s continuity criterion to the process zt=…1‡ jzj† yields limt!1 A…0;t†=t ˆ m with probability 1. Sincewe have assumed m < c, it follows that V0 is a.s. ®nite. Note that V is nonnegative, although the input process has (regrettably!) negative increments also. The ruggedness (nondifferentiability) of the fractional Brownian path implies a paradoxical property of V: the storage is almost always nonempty. Indeed, it can be shown that the supremum in Eq. (4.3) is positive with probability one, and by stationarity, the positivity must also hold for almost every time point in almost every realization of the process. The set of times t with Vt ˆ 0 is uncountable a.s., with almost every point being an accumulation point, so that between any two distinct busy periods there are a.s. in®nitely many tiny busy periods. This is, of course, an anomaly of the continuous-time model only, it has no counterpart in the teletraf®c reality being modeled. Note, on the other hand, that it is a natural feature of a heavy traf®c limit process (cf. Chapter 5), and that the case H ˆ 2 is no exception here. 4.2.3 The Output Process It is natural to de®ne the output within an interval …s;tŠ as U…s;t† ˆ A…s;t† ÿ Vt ‡ Vs; Ut ˆ U…0;t† for t 0: …4:4† We then have from Eqs. (4.3) and (4.2) that Ut ˆ V0 ‡ ct ÿ sup…cs ÿ As†; so that U is the difference of two increasing processes and thus has paths that are differentiable almost everywhere. Thus the microscale behavior of the output process is entirely different from that of the input processÐone more nonpleasant anomaly of our model! Since the storage is almost never empty, the output proceeds almost always with full rate c. However, the output within the set of time points where the storage is empty is negative, and the mean rate is still m as can be seen from (1.4) dividing by t and letting t ! 1. 4.3 SCALING RULES The self-similarity property (4.1) allows for deriving some useful relations. First, we observe that from a mathematical point of view, H is the only ``real parameter`` of the storage system, since the effect of the others reduces to scaling. 4.3 SCALING RULES 105 Proposition 4.3.1. Let the self-similarity parameter H be ®xed, and denote by V…m;s2;c† the storage occupany process of a fractional Brownian storage with parameters m, s2, and c. Then …m;s2;c† dcÿ m …0;1;1† t t2R a* at t2R where a* ˆ c ÿm1=…1ÿH†: Proof. For any a > 0, we have by Eq. (4.1) that V ˆ sup…A…s;t†ÿ c…t ÿ s†† st ˆ sup…s…Z ÿZ †ÿ…cÿ m†…t ÿ s†† st d sup…saÿH…Zat ÿ Zas†ÿ …cÿ m†…t ÿ s†† ˆ sup…saÿH…Zat ÿ Zas†ÿ …cÿ m†aÿ1…at ÿ as††; where the similarity in distribution holds for the whole processes, not just for a single t. Now, choose a ˆ a* by requiring that saÿH ˆ …cÿ m†aÿ1: j In particular, Proposition 4.3.1 has the following consequences. Corollary 4.3.2. The storage occupancy distribution obeys the scaling law P…V…m;s2;c† > x† ˆ P V…0;1;1† > cÿ mx H=…1ÿH† …0;1;1† s1=…1ÿH† Corollary 4.3.3. Denote by B…m;s2;c† the length of the busy period containing time zero in fractional Brownian storage with parameters m;s2;c. Its distribution obeys the scaling law P…B…m;s2;c† > x† ˆ P…B…0;1;1† > a*x†: Another type of scaling law is obtained from Corollary 4.3.2 by ®xing a ``quality of service criterion,`` requiring that the probability of exceeding a certain storage level x equals a given small number E. ... - tailieumienphi.vn