Abstract
In this thesis we study queueing models that arise in the context of resource sharing in communication networks. We determine scheduling policies that (asymptotically) optimize the performance of the system, and evaluate policies that share the resources among the users in a fair manner.
Chapter 1 gives an overview of several concepts related to resourcesharing systems and introduces the queueing models and main techniques used throughout the thesis. We describe the workconserving singleserver system, the linear bandwidthsharing network, and the parallel twoserver model. In the latter two models the speed at which the system works depends on the scheduling decision taken and on the types of users presently in the system. These models can therefore be seen as extensions of the singleserver model. The stochastic evolution of the numbers of users is determined by the scheduling policy, which specifies how the resources are shared among all users. We use samplepath techniques and stochastic dynamic programming tools in order to characterize policies that minimize the holding cost.
Since the original stochastic model is not always tractable, we also investigate two limiting regimes. One of them is the heavytraffic regime where we let the offered load approach the maximum capacity. In the other regime we consider the queuelength processes under the socalled fluid scaling.
In Chapter 2 we focus on the singleserver system in heavy traffic and analyze a generalization of the DPS policy. More specifically, we consider phasetype distributed service requirements and allow customers to have different weights in various phases of their service. In our main result we establish a statespace collapse for the scaled steadystate queue length vector in heavy traffic. The result shows that in the limit, the queue length vector is the product of an exponentially distributed random variable and a deterministic vector. The proof consists in showing that the joint probability generating function of the queue lengths satisfies a partial differential equation that allows a closedform solution after passing to the heavytraffic
limit. Our result has several interesting consequences for the standard DPS queue.
We derive that, conditioned on the number of customers, the remaining service requirements of the various customers are independent and distributed according to the forward recurrence times. In addition, we show that the scaled holding cost stochastically reduces as more preference is given according to the mean forward recurrence times of the service requirements.
In Chapters 3–7 we study the linear bandwidthsharing network. This network provides a natural modeling framework for the dynamic flowlevel interaction among data transfers in wired communication networks. It models the bandwidth sharing of data traffic that traverses multiple links and the cross traffic it meets on its route. Sizebased scheduling policies, such as SRPT and LAS, are popular mechanisms for reducing the number of users in singleserver systems by favoring smaller requests over larger ones.
In Chapter 3 we prove that straightforward extensions of such policies may cause instability effects in the linear network and will therefore certainly not yield optimal performance. For networks with sufficiently many nodes, instability phenomena may in fact arise at arbitrarily low traffic loads.
In Chapters 4–6 we turn to finding policies that minimize the holding cost in a linear network. In Chapter 4 we restrict the search to the class of nonanticipating policies and assume exponentially distributed service requirements. We show that simple priority rules are optimal for certain settings of the parameters of the service requirements. For the remaining cases we prove that, in the case of a twonode linear network, an averagecost optimal policy is characterized by "switching curves", i.e., the policy dynamically switches between several priority rules. Since an exact characterization of these curves is not possible in general, we study in Chapter 5 the related fluid control problem. We show that the optimal fluid control can be explicitly characterized by linear switching curves. In most cases these curves provide asymptotically fluidoptimal policies in the original stochastic model as well. For some scenarios however, fluidbased switching curves may result in a policy that is unstable. In that case, the diffusion scaling is appropriate and efficient switchingcurve policies have a squareroot shape. The class of weighted afair bandwidthsharing policies are commonly accepted to model the dynamic flowlevel bandwidthallocation as realized by packetbased protocols. Through numerical experiments we evaluate the performance of these policies by comparing them to asymptotically optimal policies. In Chapter 4 we find that the gap between afair policies and optimal policies is not that large provided the system load is moderate. In addition, the performance under afair policies is quite insensitive to a, as long as this value is not too small. In Chapter 5 we observe that weighted afair policies can approach the optimal performance when choosingthe weights appropriately.
In Chapter 6 we consider a linear network with generally distributed service requirements and allow anticipating policies. We focus on policies that allocate the capacity across the classes such that stability of the system is guaranteed. Motivated by the sizebased scheduling results for singleserver systems, we then prioritize within a class the large requests over the small ones. These sizebased scheduling policies are proven to be asymptotically optimal in a heavytraffic setting for service requirements with bounded support. In addition, we show that these policies may outperform afair policies, which are nonanticipating, by an arbitrarily large factor when the load is sufficiently high.
In Chapter 7 we first focus on a multiclass queueing system with general interarrival
times and service requirements, and give sufficient conditions in order to compare samplepath wise the workload and the number of users under different policies. This allows us to evaluate the performance of the system under various policies in terms of stability and the mean holding cost. We then apply this framework to the linear network under weighted afair policies. We obtain stability results and, in the case of exponentially distributed service requirements, establish monotonicity of the mean holding cost with respect to the fairness parameter a and the relative weights. In addition, we investigate the monotonicity properties in a heavytraffic regime and perform numerical experiments. Furthermore, for a singleserver system with two user classes we obtain that under DPS and GPS the mean holding cost is monotone with respect to their relative weights. This result is in line with the monotonicity result for DPS under a heavytraffic setting as obtained in Chapter 2.
In Chapter 8 we focus on a parallel twoservermodel with two classes of users with exponentially distributed service requirements. The study of this model is motivated by scheduling questions in wireless cellular communication networks. It may model for example the power control of two interfering base stations. For certain choices of the parameters of the service requirements we give an exact characterization of an optimal policy. For the remaining cases we study the related deterministic fluid control model for which we show that the optimal control is described by a switching curve. Using similar techniques as in Chapter 5, we prove that policies characterized
by either linear or exponential switching curves are asymptotically fluidoptimal in the original stochastic model. For a moderatelyloaded system, we numerically compare these fluidbased policies with MaxWeight and thresholdbased policies, which are known to be optimal in a heavytraffic setting. We observe that the fluidbased and the thresholdbased policies perform well, while significant performance gains can be achieved over MaxWeight policies.
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  26 Nov 2009 
Place of Publication  Eindhoven 
Publisher  
Print ISBNs  9789038620565 
DOIs  
Publication status  Published  2009 
Fingerprint Dive into the research topics of 'Scheduling in stochastic resourcesharing systems'. Together they form a unique fingerprint.
Cite this
Verloop, I. M. (2009). Scheduling in stochastic resourcesharing systems. Technische Universiteit Eindhoven. https://doi.org/10.6100/IR653227