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.

It is well-known that mobility increases the throughput of wireless networks, and the main objective of this paper is to show that, depending on the system's parameters, delay can actually be negatively impacted. To do so, we study a Markovian model where users arrive to the network according to a Poisson process with rate λ and then move at speed α ε[0, ∞) between nodes while in service. Given the complexity of the model, we resort to approximation techniques in order to get insight into the influence of the speed α on the mean delay. Our main findings are the following: in the case where the network consists of two nodes, delay is monotone in α for small values of λ. We furthermore explicit a constant C such that delay is increasing if and only if ; in the general case, we provide numerical results showing that delay is not necessarily monotone in α. However, we compare the two extreme cases with 0 and infinite speed, and find that for small values of λ, delay is worse with infinite speed than with 0 speed if and only if . Finally, an intuitive interpretation of this constant C is provided.

We consider the problem of allocating a wireless channel to mobile users moving on a straight road. The objective is to maximize a given function of the total data transmitted. We develop a model within the multi-armed bandit framework and formulate an optimization problem under the constraint that at most one user can be served at a time. We solve the relaxed optimization problem, in which one user is served on the average, and show it to be indexable. A simple and easy-to-compute expression is given for the Whittle index. We then propose a heuristic policy for the original optimization problem using Whittle's index policy. The proposed heuristic is shown to perform well compared to some other heuristics in various settings including dynamic scenarios with arrivals of new users and the presence of heterogeneous users.

We consider a parallel-server system with homogeneous servers where incoming tasks, arriving at rate λ, are dispatched by n dispatchers, each of them balancing a fraction 1/n of the load to K/n servers. Servers are first-come-first-served (FCFS) queues and dispatchers implement size interval task assignment policy with equal load (SITA-E), a size-based policy such that the servers are equally loaded. We compare the performance of a system with n > 1 dispatchers and a single dispatcher. We show that the performance of a system with n dispatchers, K servers, and arrival rate λ coincides with that of a system with one dispatcher, K/n servers, and arrival rate λ/n. We define the degradation factor as the ratio between the performance of a system with K servers and arrival rate λ and the performance of a system with K/n servers and arrival rate λ/n. We establish a partial monotonicity on n for the degradation factor and, therefore, the degradation factor is lower bounded by one. We then investigate the upper bound of the degradation factor for particular distributions. We consider two continuous service time distributions: uniform and bounded Pareto and a discrete distribution with two values, which is the distribution that maximizes the variance for a given mean. We show that the performance degradation is small for uniformly distributed job sizes but that for Bounded Pareto and two points distributions it can be unbounded. We have investigated the degradation using the distribution obtained from real traces.

We consider a parallel-server system with K homogeneous servers where incoming tasks, arriving at rate λ, are dispatched by n dispatchers. Servers are FCFS queues and dispatchers implement a size-based policy such that the servers are equally loaded. We compare the performance of a system with n> 1 dispatchers and of a system with a single dispatcher. Every dispatcher handles a fraction 1/n of the incoming traffic and balances the load to K/n servers. We show that the performance of a system with n dispatchers, K servers and arrival rate λ coincides with that of a system with one dispatcher, K/n servers and arrival rate λ/n. Therefore, the performance comparison can be interpreted as the economies of scale in a system with one dispatcher when we scale up the number of servers and the arrival rate proportionately. We consider two continuous service time distributions: uniform and Bounded Pareto that have increasing and decreasing failure rates, respectively; and a discrete distribution with two values, which is the distribution that maximizes the variance for a given mean. We show that the performance degradation is small for uniformly distributed job sizes, but that for Bounded Pareto and two points distributions it can be unbounded.

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 investigate how to build a non-intrusive scheduled TCP. For the flows of a given origin-destination pair, the objective is to schedule their TCP segments (according to some desired criteria) without modifying the network bandwidth-share used by these flows, which in turn ensures friendliness with respect to the rest of the network. We show that in order for a scheduling algorithm to be strictly non-intrusive, a sufficient and necessary condition is that the sender's and receiver's buffers are infinite. We then show that, under the additional condition that segments are neither lost or reordered, the number of active TCP flows can be minimized by size-based schedulers, and we propose a new scheduler FAIR, which guarantees that the transfer time of every TCP flow for the origin-destination pair is reduced. We develop SCHED_TCP, a user space implementation of our scheme in order to evaluate its performance on the Internet. Our experiments illustrate the non-intrusive property of SCHED_TCP, and also illustrate that the performance gain with SCHED_TCP can be considerable. Our scheme is scalable, and it could be incrementally deployed on the Internet improving the user experience on every origin-destination pair. The main application domain of our approach correspond to situations in which there are many concurrent TCP connections within the same origin-destination pair, this might happen as a consequence of HTTP 1.1, Web 2.0 applications using AJAX (Google Maps etc.), Split TCP, Parallel Sockets, and also with the use of ChromeBook's where the user accesses to all services through the same back-end server infrastructure.

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.

Price of anarchy is an oft-used worst-case measure of the inefficiency of noncooperative decentralized architectures. For a noncooperative load-balancing game with two classes of servers and for a finite or infinite number of dispatchers, we show that the price of anarchy is an overly pessimistic measure that does not reflect the performance obtained in most instances of the problem. We explicitly characterize the worst-case traffic conditions for the efficiency of noncooperative load-balancing schemes and show that, contrary to a common belief, the worst inefficiency is in general not achieved in heavy traffic.

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.

We analyze a comprehensive model for multi-class job scheduling accounting for user abandonment, with the objective of minimizing the total discounted or time-average sum of linear holding costs and abandonment penalties. We assume geometric service times and Bernoulli abandonment probabilities. We solve analytically the case in which there are 1 or 2 users in the system to obtain an optimal index rule. For the case with more users we use recent advances from the restless bandits literature to obtain a new simple index rule, denoted by AJN, which we propose to use also in the system with arrivals. In the problem without abandonment, the proposed rule recovers the cμ-rule which is well-known to be optimal both without and with arrivals. Under certain conditions, our rule is equivalent to the cμ/θ-rule, which was recently proposed and shown to be asymptotically optimal in a multi-server system with overload conditions. We present results of an extensive computational study that suggest that our rule is almost always superior or equivalent to other rules proposed in the literature, and is often optimal.

We investigate the price of anarchy of a load balancing game with K dispatchers. The service rates and holding costs are assumed to depend on the server, and the service discipline is assumed to be processor-sharing at each server. The performance criterion is taken to be the weighted mean number of jobs in the system, or equivalently, the weighted mean sojourn time in the system. For this game, we first show that, for a fixed amount of total incoming traffic, the worst-case Nash equilibrium occurs when each player routes exactly the same amount of traffic, i.e., when the game is symmetric. For this symmetric game, we provide the expression for the loads on the servers at the Nash equilibrium. Using this result we then show that, for a system with two or more servers, the price of anarchy, which is the worst-case ratio of the global cost of the Nash equilibrium to the global cost of the centralized setting, is lower bounded by K/(2¿K-1) and upper bounded by ¿K, independently of the number of servers.

scheduling disciplines permit to model a wide variety of non-anticipating scheduling disciplines. Such disciplines have recently attracted attention in the context of the Internet as an appropriate flow-level model for the bandwidth sharing obtained when priority is given to short TCP connections. In this paper, we compare the mean delay in an M/G/1 queue among MLPS disciplines under the assumption that the service time distribution belongs to class Decreasing Hazard Rate (DHR). We are able to prove that, given an MLPS discipline, the mean delay is reduced whenever a level is added by splitting an existing one in several cases. The exceptions concern splitting the upper levels with PS internal discipline. Our numerical examples, however, indicate that the level splitting be advantageous even in these cases. Furthermore, we characterize the effect on the mean delay of changing internal disciplines within levels. By numerical means we demonstrate that the mean delay of an MLPS discipline can get close to the minimum optimal delay with just a few levels. As the number of levels increases in an MLPS discipline, the MLPS queue mimics closer and closer the behavior of a Foreground-Background queue, which is known to minimize the mean delay among all disciplines. Thus, our result provides a constructive way to demonstrate the optimality of FB. I.

As a natural multi-class generalization of the well-known (egalitarian) processor sharing (PS) service discipline, discriminatory processor sharing (DPS) is of great interest in many application areas, including telecommunications. Under DPS, the mean response time conditional on the service requirement is only known in closed form when all classes have exponential service requirement distributions. For generally distributed service requirements, Fayolle et al. (1980) showed that the expected conditional response times satisfy a system of integro-differential equations. In this paper, we exploit that result to prove that, provided the system is stable, for each class the expected unconditional response time is finite and that the expected conditional response time has an asymptote. The asymptotic bias of each class is found in closed form, involving the mean service requirements of all classes and the second moments of all classes but the one under consideration. In the course of the development we prove two other results that are of independent interest: we establish a conservation law for the time average unfinished work of all classes and, using a stochastic coupling argument, we show that the response times of different classes are stochastically ordered according to the DPS weights. Finally, we study DPS as a tool to achieve size based scheduling and we provide guidelines as to how the weights of DPS must be chosen such that DPS outperforms PS.

Internet measurements show that a small number of large TCP flows are responsible for the largest amount of data transferred, whereas most of the TCP sessions are made up of few packets. Several authors have invoked this property to suggest the use of scheduling algorithms, which favor short jobs, such as LAS (least attained service), to differentiate between short and long TCP flows. We propose a packet level stateless, threshold based scheduling mechanism for TCP flows, RuN2C. We describe an implementation of this mechanism, which has the advantage of being TCP compatible and progressively deployable. We compare the behavior of RuN2C with LAS based mechanisms through analytical models and simulations. As an analytical model, we use a two level priority processor sharing PS + PS. In the PS + PS system, a connection is classified as high or low priority depending on the amount of service it has obtained. We show that PS + PS reduces the mean response time in comparison with standard processor sharing when the hazard rate of the file size distribution is decreasing. By simulations we study the impact of RuN2C on extreme values of response times and the mean number of connections in the system. Both simulations and analytical results show that RuN2C has a very beneficial effect on the delay of short flows, while treating large flows as the current TCP implementation does. In contrast, we find that LAS based mechanisms can lead to pathological behavior in extreme cases.

Inspired by several recent papers that focus on scheduling disciplines for network flows, we present a mean delay analysis of Multilevel Processor Sharing (MLPS) scheduling disciplines in the context of M/G/1 queues. Such disciplines have been proposed to model the effect of the differentiation between short and long TCP flows in the Internet. Under MLPS, jobs are classified into classes depending on their attained service. We consider scheduling disciplines where jobs within the same class are served either with Processor Sharing (PS) or Foreground Background (FB) policy, and the class that contains jobs with the smallest attained service is served first. It is known that the FB policy minimizes (maximizes) the mean delay when the hazard rate of the job size distribution is decreasing (increasing). Our analysis, based on pathwise and meanwise arguments of the unfinished truncated work, shows that Two-Level Processor Sharing (TLPS) disciplines, e.g., FB+PS and PS+PS, are better than PS scheduling when the hazard rate of the job size distribution is decreasing. If the hazard rate is increasing and bounded, we show that PS outperforms PS+PS and FB+PS. We further extend our analysis to study local optimality within a level of an MLPS scheduling discipline.