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

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 6 THE SINGLE SERVER QUEUE: HEAVY TAILS AND HEAVY TRAFFIC O. J. BOXMA Department of Mathematics and Computing Science, Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands; and CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands J. W. COHEN CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands 6.1 INTRODUCTION Recently, there has been much interest in the behavior of queues with heavy-tailed service time distributions. This interest has been triggered by a large number of traf®c measurements on modern communication network traf®c (e.g., see Willinger et al. [38] for Ethernet LAN traf®c, Paxson and Floyd [30] for WAN traf®c, and Beran et al. [3] for VBR video traf®c; see also various chapters in this volume). These measurements and their statistical analysis (e.g., see Leland et al. [26]) suggest that modern communication traf®c often possesses the properties of self-similarity and long-range dependence. A natural possibility to introduce long-range dependence in an input traf®c process is to take a ¯uid queue and to assume that at least one of the input quantities I (on or off periods in the ¯uid queue fed by on=off sources) has the following ``heavy-tail`` behavior: P‰I > tŠt hntÿn; …6:1† 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. 143 144 THE SINGLE SERVER QUEUE: HEAVY TAILS AND HEAVY TRAFFIC with h a positive constant and 1 < n < 2 (here and later, f…t†t g…t† stands for f…t†=g…t† ! 1 with t ! 1; and many-valued functions like tÿn are de®ned by their principal value, so tÿn is real for t positive). In this context, regularly varying and subexponential distributions [5] have received special attention. We refer to Boxma and Dumas [12] for a survey on ¯uid queues with heavy-tailed on-period distribu-tions. In this chapter, we concentrate on the ordinary single server queue with regularly varying service and=or interarrival time distribution. The ¯uid queue is closely related to this ordinary queue (cf. Remarks 6.2.6 and 6.6.3), so that several of the results of the present chapter will also be relevant for ¯uid queues. When G…x† is the probability distribution of a nonnegative random variable G, then 1ÿG…x† ˆ P‰G > xŠ is said to be regularly varying at in®nity of index ÿn when 1ÿG…x† ˆ xÿnL…x†; x 0; …6:2† with L…x† a slowly varying function at in®nity, that is, L…tx† x!1 L…x† 8t > 0: L…† could, for instance, be a constant or a logarithmic function. If Eq. (6.2) holds, then we write P‰G > Š 2 R…ÿn†. Regular variation is an important asymptotic concept in probabilistic analysis. The main reference text is the book by Bingham et al. [5]. An early result concerning regular variation in queueing theory is due to Cohen [13]. He proved the following result for the GI=G=1 queue under the ®rst-come-®rst-served (FCFS) discipline: the tail of the waiting time distribution is regularly varying of index 1ÿ n if and only if the tail of the service time distribution is regularly varying of index ÿn;n > 1. This result has turned out to be very useful in relating the regularly varying tail behavior of on periods of on=off sources in ¯uid queues to the buffer content [7, 8]; see also Jelenkovic and Lazar [23] and Rolski et al. [32]. Cohen`s result implies that, in the case of regular variation, the tail of the waiting time distribution is one degree heavier than that of the service time distribution. For 1 < n < 2, the mean of the service time distribution is ®nite, but the mean of the waiting time distribution is in®nite. The ®rst issue that we consider in this chapter is whether other service disciplines besides FCFS may lead to a less detrimental waiting time behavior. We consider the M=G=1 queue with the processor sharing (PS) discipline and the M=G=1 queue with the last-come-®rst-served preemptive resume (LCFS-PR) discipline. Note that PS and LCFS-PR are well-known and important disciplines, that both play a key role in product-form networks. For both disciplines, the waiting time tail behavior turns out to be regularly varying of index ÿn iff the service time tail behavior is regularly varying of index ÿn. We refer to Anantharam [2] for a related investigation of the in¯uence of the service discipline on the tail behavior of a single server queue. 6.1 INTRODUCTION 145 The second issue under consideration in this chapter is the heavy traf®c behavior of a queue with heavy-tailed service time distribution. A queueing system is said to be in heavy traf®c when its traf®c load r ! 1. This issue is of theoretical interest, since in the traditional heavy traf®c limit theorems it is assumed that the second moments of service and interarrival times are ®nite, whereas Eq. (6.1) with 1 < n < 2 leads to an in®nite second moment. The issue is also of practical interest, since heavy traf®c limit theorems may give rise to useful approximations in situations with a reasonably light traf®c load. We ®rst focus on the M=G=1 queue, again with the three service disciplines FCFS, PS, and LCFS-PR. Subse-quently, we also allow interarrival times to be generally distributed and even heavy tailed. New heavy traf®c limit results are presented for the waiting time in the GI=G=1 queue with heavy-tailed interarrival and=or service time distribution. The case in which both tails are ``just as heavy`` is particularly interesting from a mathematical point of view. We identify coef®cients of contraction D…r† such that D…r† times the waiting time has a proper limiting distribution for r " 1. The third issue under consideration is the convergence of the workload process fvt;t 0g in the GI=G=1 queue with heavy-tailed interarrival and=or service time distribution. It is shown that D…r†vt=……1ÿr†D…r†† converges in distribution for r " 1, for all t 0. The thus scaled and contracted workload process converges weakly to the workload process of a queueing model of which the input process is described by n-stable Levy motion. This chapter is organized in the following way. In Section 6.2 we discuss the relation between the tail behavior of service times and waiting times, for the M=G=1 queue with service disciplines FCFS, PS, and LCFS-PR. In Section 6.3, for the same three M=G=1 variants, we present heavy traf®c limit theorems for waiting times, in the case of a regularly varying service time distribution with an in®nite variance. In the LCFS-PR case, the sojourn time distribution coincides with the M=G=1 busy period distribution. The heavy traf®c behavior of the latter distribution is investigated in detail; the tail behavior of the limiting distribution is studied in Section 6.4. Heavy traf®c limit theorems for the waiting time in the GI=G=1 q ueue with the FCFS service discipline are presented in Section 6.5. A distinction is made between the cases in which the interarrival time distribution has a heavier tail, the service time distribution has a heavier tail, and both tails are ``just as heavy.`` In Section 6.6 the input process and the workload process are studied for the GI=G=1 queue with heavy-tailed interarrival and=or service time distribution. The heavy traf®c behavior of those processes is characterized. Section 6.7 contains conclu-sions and some topics for further research. (Note: Several of the results in this chapter have appeared in recent reports of the authors and their colleagues; in those cases, proofs are generally omitted. Also, several chapters in this volume are related to the present work. We mention in particular the contributions of Jelenkovic (Chapter 10), of Likhanov (Chapter 8), of Makowski and Parulekar (Chapter 9), of Norros (Chapter 4), of Brichet et al. (Chapter 5), and of Resnick and Samorodnitsky (Chapter 7).) 146 THE SINGLE SERVER QUEUE: HEAVY TAILS AND HEAVY TRAFFIC 6.2 WAITING TIME TAIL BEHAVIOR 6.2.1 Introduction In Section 6.1 we have already mentioned a result of Cohen [13] that relates the (regularly varying) tail behavior of service and waiting times in the GI=G=1 queue with the FCFS discipline; it shows that the waiting time is ``one degree heavier``than the service time tail, in the case of regular variation. In Section 6.2.2 this result, and an extension, will be discussed in some more detail for the M=G=1 FCFS queue. A similar result for the M=G=1 queue with the PS discipline (due to Zwart and Boxma [42]) will be discussed in Section 6.2.3. That result shows that, under processor sharing, the waiting time tail is just as heavy as the service time tail. In Section 6.2.4 we prove that the latter phenomenon also occurs in the M=G=1 queue with the LCFS-PR discipline. In the present section we ®rst introduce some notation, and we present a very useful lemma that relates the tail behavior of a regularly varying probability distribution and the behavior of its Laplace±Stieltjes transform (LST) near the origin. Consider the M=G=1 queue. Customers arrive according to a Poisson process with rate l; their service times B1;B2;... are i.i.d. (independent, identically distributed) random variables with ®nite mean b and LST bfsg. A generic service time is denoted by B. By B* we denote a random variable of which the distribution is that of a residual service time: …1 P‰B* > xŠ ˆ b x P‰B > uŠ du; x 0: Its LST is given by b*fsg :ˆ …1ÿ bfsg†=bs. The traf®c load r :ˆ lb of the M=G=1 queue is assumed to be less than one, so that the steady-state waiting time distribution exists. Avery useful property of probability distributions with regularly varying tails is a characterization of the behavior of its LST near the origin. Let F…† be the distribution of a nonnegative random variable, with LST ffsg and ®nite ®rst n moments m1;...;mn (and m0 ˆ 1). De®ne " # f fsg :ˆ …ÿ1†n‡1 ffsgÿ n mj …ÿs† : jˆ0 Lemma 6.2.1. Let n < n < n‡1, C 0. The following statements are equiva-lent: fnfsg ˆ …C ‡ o…1††snL…1=s†; s # 0; s real; …6:3† n 1ÿF…t† ˆ …C ‡ o…1†† G…1ÿ n†tÿnL…t†; t ! 1: …6:4† 6.2 WAITING TIME TAIL BEHAVIOR 147 The case C > 0 is due to Bingham and Doney [4]. The case C ˆ 0 is treated in Boxma and Dumas [12, Lemma 2.2]. The case of an integer n is more complicated; see Bingham et al. [5, Theorem 8.1.6 and Chap. 3]. 6.2.2 The M=G=1 FCFS Queue We ®rst formulate the main result of Cohen [13] for the GI=G=1 queue with FCFS discipline in full generality. There is no need to specify the interarrival time distribution; the mean interarrival time and traf®c load are denoted by 1=l and r ˆ lb (as before). In what follows, W denotes the steady-state waiting time. Theorem 6.2.2. For r < 1 and n > 1, P‰B > xŠx …nÿ 1†bÿnL…x† () P‰W > xŠx 1ÿ rb1ÿnL…x†: …6:5† Pakes [29] has extended this result to the larger class S of subexponential distributions (i.i.d. stochastic variables X1 and X2 have a subexponential tail if P…X1 ‡ X2 > t†=P…X1 > t† 2†. His result states that P‰W > Š 2 S if and only if P‰B* > Š 2 S, and if either is the case then P‰W > xŠx 1ÿ rP‰B* > xŠ: …6:6† REMARK 6.2.3. Note that the interarrival time distribution has no in¯uence on the above-mentioned waiting time tail behavior. REMARK 6.2.4. In the case of Poisson arrivals, the Pollaczek±Khintchine formula reads: ÿsW 1ÿ r 1ÿ rb*fsg Re s 0; …6:7† and 1 P‰W > xŠ ˆ …1ÿr†r P‰B*‡ ‡ B* > xŠ; x 0: …6:8† nˆ1 Theorem 6.2.2 and Eq. (6.6) can be veri®ed very easily in the M=G=1 case. For example, the above-mentioned de®nition of subexponentiality implies that P‰B*‡ ‡ B* > xŠ nP‰B* > xŠ; and combination of Lemma 6.2.1 and Eq. (6.7) (that relates the LSTs of W and B*) readily yields the relation between the tail behavior of the distributions of W and B. ... - tailieumienphi.vn