Samenvatting
The processorsharing discipline was originally introduced as a modeling abstraction for the design and performance analysis of the processing unit of a computer system. Under the processorsharing discipline, all active tasks are assumed to be processed
simultaneously, receiving an equal share of the server capacity. Various extensions of the basic egalitarian discipline have been developed in order to capture scenarios with heterogeneous service shares and network settings. Over the past several years, the processorsharing discipline has received renewed attention as a powerful tool in modeling and analyzing dynamic bandwidth sharing among elastic transfers in communication networks like the Internet. The sojourn time of a customer, i.e. the amount of time a customer spends in the system from his arrival until his service completion, is the most important performance measure for processorsharing systems. In this monograph we study various asymptotic properties of the sojourn time distribution. The advantage of considering the asymptotic behavior is that the analysis often provides insight into the
typical scenario for a long sojourn time to occur. Moreover, the resulting asymptotic
formulas can be used for approximate analysis, providing accurate estimates in situations where numerical procedures become unreliable. In order to analyze the sojourn time asymptotics, we apply several probabilistic and analytic techniques, such as Laplace transforms, branching arguments, largedeviations methods and fluid limits. The main focus in this thesis is on the PS queue where the service time has a lighttailed distribution. This case has received relatively little attention compared to the case of heavytailed distributions. Exact asymptotics (of highly uncommon and interesting form) were only available for the M/M/1 queue and were obtained by analytical methods that did not provide insight into the nature of the underlying rare event.
In Chapter 2 we analyze the asymptotic behavior of the sojourn time distribution in the classical singlenode PS queue. We derive exact tail asymptotics for the sojourn time distribution in the queue with Poisson arrivals and deterministic service times. The proof involves a geometric random sum representation of the sojourn time, and a connection with Yule processes. Numerical experiments demonstrate a remarkable accuracy of the asymptotic approximation. In Chapter 3 we consider the M/G/1 queue, and investigate the tail behavior of the sojourn time distribution for a request of a given length. An exponential
asymptote is proved for general service times in two special cases: when the traffic load is sufficiently high and when the request length is sufficiently small. Using the branching process technique, we derive exact asymptotics of exponential type for the sojourn time in the M/M/1 queue. We study the accuracy of the exponential asymptote using numerical methods.
In Chapter 4 we study the GI/GI/1 queue operating under a PS discipline with stochastically varying service rate. The focus is on logarithmic estimates of the tail of the sojourn time distribution, under the assumption that the service time distribution has a light tail. The analysis in this chapter relies predominantly on largedeviations techniques. Furthermore, we extend our results to a similar system operating under the discriminatory processorsharing discipline.
In Chapters 5 and 6 we analyze the behavior of alphafair bandwidthsharing networks which can be regarded as generalizations of a processorsharing discipline from a single node to a network with several shared links. In Chapter 5 we focus on an overload scenario where the traffic load on one or several of the links exceeds the capacity. In order to characterize the overload behavior, we examine the fluid limit, which emerges from a suitably scaled version of the number of flows of the various classes. We derive a functional equation characterizing the fluid limit. We show that any strictly positive solution must be unique, which in particular implies the convergence of the scaled number of flows to the fluid limit for nonzero initial states when the traffic load is sufficiently high. In addition, we establish the uniqueness of the fluid limit for networks with a tree topology. For the case of a zero initial state and zerodegree homogeneous rate allocation functions, we show that there exists a uniquely determined linear solution to the fluidlimit equation, and obtain a fixedpoint equation for the corresponding asymptotic growth rates. The results are illustrated for parking lot, linear and star networks as important special cases.
We briefly discuss extensions to models with user impatience.
In Chapter 6 we derive the asymptotics for the sojourn time distribution in a specific type of bandwidthsharing network: a parking lot network. Such networks can be practically useful in modeling access networks consisting of several multiplexing stages. Using largedeviations techniques and the fluidlimit results from
Chapter 5, we obtain the logarithmic asymptote under the assumption that flow sizes have a lighttailed distribution. In addition, we derive stochastic bounds for the number of flows and the workload in the system.
Originele taal2  Engels 

Kwalificatie  Doctor in de Filosofie 
Toekennende instantie 

Begeleider(s)/adviseur 

Datum van toekenning  5 feb 2009 
Plaats van publicatie  Eindhoven 
Uitgever  
Gedrukte ISBN's  9789038614953 
DOI's  
Status  Gepubliceerd  2009 
Vingerafdruk Duik in de onderzoeksthema's van 'Sojourn time tails in processorsharing systems'. Samen vormen ze een unieke vingerafdruk.
Citeer dit
Egorova, R. R. (2009). Sojourn time tails in processorsharing systems. Technische Universiteit Eindhoven. https://doi.org/10.6100/IR639849