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

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 7 FLUID QUEUES, ON=OFF PROCESSES, AND TELETRAFFIC MODELING WITH HIGHLY VARIABLE AND CORRELATED INPUTS SIDNEY RESNICK AND GENNADY SAMORODNITSKY Cornell University, School of Operations Research and Industrial Engineering, Ithaca, NY 14853 7.1 INTRODUCTION Large teletraf®c data sets exhibiting nonstandard features incompatiblewith classical assumptions of short-range dependence and exponentially decreasing tails can now be explored, for instance, at the ITA Web site www.acm.org=sigcomm=ITA=. These data sets exhibit the phenomena of heavy-tailed marginal distributions and long-range dependence. Tails can be so heavy that only in®nite variance models are possible (e.g., see Willinger et al. [49]), and sometimes, as in ®le size data, even ®rst moments are in®nite [1]. See also Beran et al. [3], Crovella and Bestavros [12±14], Leland et al. [33], Resnick [38], Taqqu et al. [48], and Willinger et al. [49]. Other areas where heavy tails and long-range dependence are crucial properties are ®nance, insurance, and hydrology [4±7, 16, 17, 24±26, 35, 37]. New features in the teletraf®c data discussed in recent studies suggest several issues for study and discussion. Statistical. How can statistical models be ®t to such data? Finite variance black box time series modeling has traditionally been dominated by ARMA or Box± Jenkins models. These models can be adapted to heavy-tailed data and work very well on simulated data. However, for real nonsimulated data exhibiting 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. 171 172 FLUID QUEUES, ON=OFF PROCESSES, AND TELETRAFFIC MODELING dependencies, such ARMA models provide unacceptable ®ts and do not capture the correct dependence structure. For discussion see Davis and Resnick [15], Resnick [38, 39], Resnick et al. [42], and Resnick and van den Berg [43]. Probabilistic. What probability models explain observed features in the data such as long-range dependence and heavy tails. Consequences. Dothe new features revealed by current teletraf®c data studies mean we have to give up Poisson derived models and exponentially bounded tails and the highly linear models of time series? Various bits of evidence emphasize the de®ciencies of classical modeling. There are simulation studies [34] and the experimental queueing analysis of Erramilli, Narayan, and Willinger [18]. An analytic example [40] shows that for a simple G=M=1 queue, a stationary input with long-range dependence can induce heavy tails for the waiting time distribution and for the distribution of the number in the system. Connections between long-range dependence and heavy tails need to be more systematically explored but it is clear that in certain circumstances, long-range dependent (LRD) inputs can cause heavy-tailed outputs and (as we discuss here) heavy tails can cause long-range dependence. We discuss three models where heavy tails induce long-range dependence: 1. A single channel on=off source feeding a single server working at constant rate r > 0. Transmission or on periods have heavy-tailed distributions. 2. A multisourcesystemwhereasingleserverworkingatconstantrater > 0 isfed by J > 1 on=off sources. Transmission periods have heavy-tailed distributions. 3. An in®nite source model feeding a single server working at constant rate r > 0. At Poisson time points, nodes or sources commence transmitting. Transmission times have heavy-tailed distributions. In each of the three cases, our basic descriptor of system performance is the time for buffer content to reach a critical level. Such a measure of performance is path based and makes sense without regard to stability of the model, existence of moments of input variables, or properties of steady-state quantities. 7.2 A SINGLE CHANNEL ON/OFF COMMUNICATION MODEL 7.2.1 BasicSetup We consider ®rst communication between a single source and a single destination server. The source transmits for random on periods alternating with random off periods when the source is silent. During the on periods, transmission is at unit rate. Let fXon;Xn;n 1g be i.i.d. nonnegative random variables representing on periods. The common distribution is Fon. Similarly, fYoff;Yn;n 1g are i.i.d. 7.2 A SINGLE CHANNEL ON/OFF COMMUNICATION MODEL 173 nonnegative random variables independent of fXon;Xn;n 1g representing off periods and these have common distribution Foff. The means are …1 mon ˆ Fon…s† ds; 0 …1 moff ˆ Foff…s† ds; 0 which are assumed ®nite and the sum of the means is m :ˆ mon ‡ moff. Using these random variables we generate an alternating renewal sequence characterized as follows. 1. The interarrival distribution is Fon Foff and the mean interarrival time is m ˆ mon ‡ moff. 2. The renewal times are n 0; …Xi ‡ Yi†;n 1 : iˆ1 Because of the ®niteness of the means, the renewal process has a stationary version: n D;D‡ …Xi ‡ Yi†;n 1 : iˆ1 where D is a delay random variable satisfying P‰D > xŠ ˆ …1 P‰Xon ‡Yoff > sŠ ds x ˆ …1 1ÿFon Foff…s† ds: x However, making the process stationary in this manner has the disadvantage that the initial delay period D does not decompose into an on and an off period the way subsequent inter-renewal periods do and the following procedure is preferable for generating the stationary alternating renewal process. De®ne independent random variables B;X…0†;Y…0†, which are assumed independent of fXon;Xn;n 1g and fYoff;Yn;n 1g, by P‰B ˆ 1Š ˆ mon ˆ 1ÿ P‰B ˆ 0Š; P‰X…0† > xŠ ˆ …1 1ÿFon…s† ds :ˆ 1ÿ F…0†…x†; x on P‰Y…0† > xŠ ˆ …1 1ÿFoff…s† ds :ˆ 1ÿ F…0†…x†: x off 174 FLUID QUEUES, ON=OFF PROCESSES, AND TELETRAFFIC MODELING The delay random variable D…0† is de®ned by D…0† ˆ B…X…0† ‡ Yoff† ‡ …1ÿ B†Y…0†: This delayed renewal sequence fSn;n 0g :ˆ D…0†;D…0† ‡ …Xi ‡ Yi†;n 1 iˆ1 is a stationary renewal process. 7.2.2 High Variability Induces Long-Range Dependence Consider the indicator process fZ g, which is 1 iff t is in an on period. Thus, for t D…0†, 1; if Sn t < Sn ‡ Xn‡1; some n t 0; if Sn ‡ Xn‡1 t < Sn‡1; some n and if 0 t < D…0† we de®ne ( 1; t 0; if B ˆ 1 and 0 t < X…0†; otherwise: A standard renewal argument gives the following result [22]. Proposition 7.2.1. fZt;t 0g is strictly stationary and P‰Zt ˆ 1Š ˆ mon : Conditional on Zt ˆ 1, the subsequent sequence of on=off periods is the same as seen from time 0 in the stationary process with B ˆ 1. It is easiest to express long-range dependence in terms of slow decay of covariance functions so we consider the second-order properties of the stationary process fZtg (See Heath et al. [22].) The basis for the next result is a renewal theory argument. Theorem 7.2.2. The covariance function g…s† ˆ Cov…Zt;Zt‡s† 7.2 A SINGLE CHANNEL ON/OFF COMMUNICATION MODEL 175 of the stationary process fZ…t†;t 0g is g…s† ˆ mon moff ÿ…s off…s ÿ u†F…0† U…du† ˆ mon moff ÿF…0† U …1ÿ Foff†…s† ˆ monmoff ÿ 1…s z…s ÿo†U…dw†; 0 where U ˆ 1 …Fon Foff†n nˆ0 and z…t† ˆ …t off…x†Fon…t ÿ x† dx 0 ˆ monF…0† …1ÿ Foff…t† ˆ moffF…0† …1ÿ Fon†…t†: How dowe analyze the asymptotic behavior of g…† as a function of s? Note g…s† is of the form h i g…s† ˆ const lim z U…v† ÿ z U…s† so we need rates of convergence in the key renewal theorem. This can be based on a theorem of Frenk [19] and is given in Heath et al. [22]. Theorem 7.2.3. Assume that there is an n 1 such that …Fon Foff†n is non-singular. Suppose Fon…t† ˆ tÿaL…t†; t ! 1; where 1 < a < 2 and L is slowly varying at in®nity and assume off…t† ˆ o…Fon…t††; t ! 1: Then g…t† …aÿ 1†m3 tÿ…aÿ1†L…t†; t ! 1: ... - tailieumienphi.vn