A classical result in queuing theory states that in a parallel-queue single-server model, the maximum stability region is unaffected by scheduling decision epochs, and in particular is the same for preemptive and non-preemptive systems. We examine a scenario where queues are randomly connected to the server and show that, unlike the classical case, the maximum stability region strongly depends on the scheduling decision epochs. We compare three settings: decisions can be made anytime (unconstrained), decisions are made only at departures (non-preemptive), and decisions occur when a$\gamma $-rate exponential clock rings. We observe a significant reduction in the stability region in the non-preemptive setting compared to the unconstrained one, showing that a non-preemptive scheduler cannot take opportunistically advantage of the random varying connectivity. Also, in the$\gamma $-rate clock setting, one can be arbitrarily close to the maximum stability region in the unconstrained setting if we choose$\gamma $large enough. In all the settings, we show that the Longest Connected Queue (LCQ) policy achieves maximum stability. From a methodological viewpoint, we introduce a new theoretical tool called “test for fluid limits” (TFL), which offers a method to determine stability on the basis of a simple formal test.

We develop a unifying framework to obtain efficient index policies for restless multi-armed bandit problems with birth-and-death state evolution. This is a broad class of stochastic resource allocation problems whose objective is to determine efficient policies to share resources among competing projects. In a seminal work, Whittle developed a methodology to derive well-performing Whittle’s index policies that are obtained by solving a relaxed version of the original problem. Our first main contribution is the derivation of a closed-form expression for Whittle’s index as a function of the steady-state probabilities. In some particular cases, qualitative insights can be obtained from its expression; nevertheless, it requires several technical conditions to be verified. We, therefore, formulate a fluid version of the relaxed optimization problem, and in our second main contribution, we develop a fluid index policy. The latter does provide qualitative insights and it is equivalent to Whittle’s index policy in the light-traffic regime. The applicability of our approach is illustrated by two important problems: optimal class selection and optimal load balancing. Allowing state-dependent capacities, we can model important phenomena, e.g., power-aware server-farms and opportunistic scheduling in wireless systems. Whittle’s index and our fluid index policy show remarkably good performance in numerical simulations.

We develop a unifying framework to obtain efficient index policies for restless multi-armed bandit problems with birth-and-death state evolution. This is a broad class of stochastic resource allocation problems whose objective is to determine efficient policies to share resources among competing projects. In a seminal work, Whittle developed a methodology to derive well-performing (Whittle's) index policies that are obtained by solving a relaxed version of the original problem. Our first main contribution is the derivation of a closed-form expression for Whittle's index as a function of the steady-state probabilities. It can be efficiently calculated, however, it requires several technical conditions to be verified, and in addition, it does not provide qualitative insights into Whittle's index. We therefore formulate a fluid version of the relaxed optimization problem and in our second main contribution we develop a fluid index policy. The latter does provide qualitative insights and is close to Whittle's index. The applicability of our approach is illustrated by two important problems: optimal class selection and optimal load balancing. Allowing state-dependent capacities we can model important phenomena: e.g. power-aware server-farms and opportunistic scheduling in wireless systems. Numerical simulations show that Whittle's index and our fluid index policy are both nearly optimal.

We study a multi-class time-sharing discipline with relative priorities known as Discriminatory Processor Sharing (DPS), which provides a natural framework to model service differentiation in systems. The analysis of DPS is extremely challenging and analytical results are scarce. We develop closed-form approximations for the mean conditional and unconditional sojourn times. The main benefits of the approximations lie in its simplicity, the fact that it applies for general service requirements with finite second moments, and that it provides insights into the dependency of the performance on the system parameters. We show that the approximation for the mean (un)conditional sojourn time of a customer is decreasing as its relative priority increases. We also show that the approximation is exact in various scenarios, and that it is uniformly bounded in the second moments of the service requirements. Finally we numerically illustrate that the approximation is accurate across a broad range of parameters.

We investigate a resource allocation problem in a multi-class server with convex holding costs and user impatience under the average cost criterion. In general, the optimal policy has a complex dependency on all the input parameters and state information. Our main contribution is to derive index policies that can serve as heuristics and are shown to give good performance. Our index policy attributes to each class an index, which depends on the number of customers currently present in that class. The index values are obtained by solving a relaxed version of the optimal stochastic control problem and combining results from restless multi-armed bandits and queueing theory. They can be expressed as a function of the steady-state distribution probabilities of a one-dimensional birth-and-death process. For linear holding cost, the index can be calculated in closed-form and turns out to be independent of the arrival rates and the number of customers present. In the case of no abandonments and linear holding cost, our index coincides with the cμ-rule, which is known to be optimal in this simple setting. For general convex holding cost we derive properties of the index value in limiting regimes: we consider the behavior of the index (i) as the number of customers in a class grows large, which allows us to derive the asymptotic structure of the index policies, and (ii) as the abandonment rate vanishes, which allows us to retrieve an index policy proposed for the multi-class M/M/1 queue with convex holding cost and no abandonments. In fact, in a multi-server environment it follows from recent advances that the index policy is asymptotically optimal for linear holding cost. To obtain further insights into the index policy, we consider the fluid version of the relaxed problem and derive a closed-form expression for the fluid index. The latter coincides with the stochastic model in case of linear holding costs. For arbitrary convex holding cost the fluid index can be seen as the Gcμθ-rule, that is, including abandonments into the generalized cμ-rule (Gcμ-rule). Numerical experiments show that our index policies become optimal as the load in the system increases.

We investigate the scheduling of a common resource between several concurrent users when the feasible transmission rate of each user varies randomly over time. Time is slotted, and users arrive and depart upon service completion. This may model, for example, the flow-level behavior of end-users in a narrowband HDR wireless channel (CDMA 1xEV-DO). As performance criteria, we consider the stability of the system and the mean delay experienced by the users. Given the complexity of the problem, we investigate the fluid-scaled system, which allows to obtain important results and insights for the original system: 1) We characterize for a large class of scheduling policies the stability conditions and identify a set of maximum stable policies, giving in each time-slot preference to users being in their best possible channel condition. We find in particular that many opportunistic scheduling policies like Score-Based, Proportionally Best, or Potential Improvement are stable under the maximum stability conditions, whereas the opportunistic scheduler Relative-Best or thecμ-rule are not. 2) We show that choosing the right tie-breaking rule is crucial for the performance (e.g., average delay) as perceived by a user. We prove that a policy is asymptotically optimal if it is maximum stable and the tie-breaking rule gives priority to the user with the highest departure probability. We will refer to such tie-breaking rule as myopic. 3) We derive the growth rates of the number of users in the system in overload settings under various policies, which give additional insights on the performance. 4) We conclude that simple priority-index policies with the myopic tie-breaking rule are stable and asymptotically optimal. All our findings are validated with extensive numerical experiments.

The signalling subsystem is the most expensive and complex element in cellular networks. Today's networks use signalling mechanisms whose design builds on more than 20 years of the operational expertise. Despite this, the signalling subsystem of all mobile network standards remains vulnerable to failures of equipment and to sharp increases in offered load caused by unanticipated traffic patterns. In this work we analyse the technical vulnerability of paging - a key signalling mechanism that is responsible for notifying mobile terminals of downlink service requests. Our assessment considers the operation of Long-Term Evolution (LTE) networks and in particular the performance of the paging mechanism on the radio interface. We implemented the paging procedure in a simulator, and we propose and verify a mathematical model of the system behaviour. The proposed mathematical model effectively captures the non-zero threshold of paging failure probability; it is scrupulously precise for the paging loads below the nonzero threshold and delivers a close approximation with the increasing paging load. The mathematical model can be applied to optimise the performance of the paging mechanism and to devise techniques able to overcome its technical vulnerability.

Bandwidth-sharing networks as considered by Massoulie & Roberts provide a natural modeling framework for describing the dynamic flow-level interaction among elastic data transfers. Although valuable stability results have been obtained, crucial performance metrics such as flow-level delays and throughputs in these models have remained intractable in all but a few special cases. In particular, it is not well understood to what extent flow-level delays and throughputs achieved by standard bandwidth-sharing mechanisms such as alpha-fair strategies leave potential room for improvement. In order to gain a better understanding of the latter issue, we set out to determine the scheduling policies that minimize the mean delay in some simple linear bandwidth-sharing networks. While admittedly simple, linear networks provide a useful model for flows that traverse several links and experience bandwidth contention from independent cross-traffic. Even for linear topologies it is rarely possible however to explicitly identify optimal policies except in a few limited cases with exponentially distributed flow sizes. Rather than aiming for strictly optimal policies, we therefore focus on a class of relatively simple priority-type strategies that only separate large flows from small ones. To benchmark the performance of these strategies, we compare them with proportional fair as the prototypical alpha-fair policy, and establish that the mean delay may be reduced by an arbitrarily large factor when the load is sufficiently high. In addition, we show the above strategies to be asymptotically optimal for flow size distributions with bounded support. Numerical experiments reveal that even at fairly moderate load values the performance gains can be significant.