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.

Rising energy costs and the push for green computing have inspired a lot of research effort towards energy efficient computing. Incorporating low energy sleep states in server farms is one of the proposed solutions. This paper studies the trade-off between energy and performance that is inherent in such solutions using the popular cost metric Energy-Response-time-Weighted-Sum (ERWS). We apply the Markov Decision Process (MDP) theory to the task assignment problem, and derive a near-optimal dynamic task assignment policy for minimizing the ERWS cost metric. Furthermore, we consider a performance constrained energy minimization problem, and provide an algorithm that builds a dynamic task assignment policy by choosing the right energy weight value for the ERWS cost metric. We also show that the resulting task assignment policy behaves like a modified version of the Join the Shortest Queue (JSQ), having a near-optimal performance by minimizing energy consumption while still obeying response time constraint.

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 explore the performance of different resource allocation schemes for transferring elastic traffic in a cellular network that is either overlaid or underlaid with D2D traffic. To this end, we model a single cell during uplink transmissions and jointly consider the presence of a randomly varying number of D2D and cellular users in the system. We use different processor sharing queueing models to characterize the performance of the overlaying and underlaying schemes and measure the performance as the mean flow level delay. In the overlaying approach, depending on the load a certain fraction of the radio resources is reserved for the D2D traffic and the cellular traffic, and hence there is no interference between the D2D and cellular users. In the underlaying approach, the D2D users are allowed to opportunistically transmit unless being interfered by a cellular user nearby. Our numerical studies reveal that the underlaying D2D traffic scheme provides a good performance compared to other methods, especially if the interference range of a cellular user is small compared with the cell dimensions. Moreover, the so-called dynamic overlay method we propose appears to perform better than the static overlay scheme.

We study the Round-Robin (RR) routing to a system of parallel queues, which serve jobs according to FCFS or preemptive LCFS scheduling disciplines. The cost structure comprises two components: a service fee and a queueing delay related component. With Poisson arrivals, the inter-arrival time to each queue obeys the Erlang distribution. This allows us to study the mean and transient behavior of the queues separately. The service fee is independent of the scheduling and queueing, and we obtain the corresponding mean cost rate and value function in closed forms. With respect to queueing delay, we first derive integral expressions enabling efficient computation of the corresponding size-aware value functions. By decomposition, these yield also the value function for the whole system of m parallel queues fed by RR. Given the value function, one can carry out the first policy iteration step with arbitrary holding cost rates (e.g., delay, slowdown, etc.) yielding efficient size-, cost- and state-aware policies. Moreover, the mean waiting and sojourn times in the corresponding systems get resolved at the same time. The results are demonstrated in the numerical examples, where we compute near optimal job routing policies for sample systems.

We study the cell selection techniques for M2M traffic between an LTE macrocell and WLAN femtocells in a heterogeneous network deployment scenario. With the dense deployment of femtocells (operating in WLAN), M2M traffic can primarily be served by them while the macrocell (operating in LTE) can be used by the machines in case of congestion in their own femtocell. We study various load balancing strategies that aid the machines to select a proper cell in such a multi-RAT heterogeneous network deployment scenario so that the access delay for the M2M traffic is minimized. In particular, we derive the optimal static policy of choosing between the WLAN femtocell and the LTE macrocell. In addition, we develop dynamic policies based on the information about the arrivals and the number of backlogged users, and compare their performance against each other and with the optimal static policy. Our results indicate that the potential gains from the dynamic policies can be significant. Moreover, simple backlog-based heuristics perform close to or better than the optimal static policy.

We consider the optimal opportunistic scheduling problem for downlink data traffic in a wireless cell with time-varying channels. The scheduler itself operates in a very fast timescale of milliseconds, but the objective function is related to minimizing the holding costs in a much longer timescale, at the so-called flow level. The Whittle index approach is a powerful tool in this context, since it renders the flow level optimization problem with heterogeneous users tractable. Until now, this approach has been applied to the opportunistic scheduling problem to generate non-anticipating index policies that may depend on the amount of attained service but do not utilize the exact size information. In this paper, we produce a size-aware (i.e., anticipating) index policy by applying the Whittle index approach in a novel way. By a numerical study based on simulations, we demonstrate that the resulting size-aware index policy systematically improves performance. As a side result, we show that the opportunistic scheduling problem is indexable when the file sizes follow the Pascal distribution, and we derive the corresponding Whittle index, which generalizes earlier results.

In heterogeneous LTE networks, an incoming user can either join the femto or the macro base station at the random access stage. We consider a system that has a single macro base station and a number of femtocells in its coverage area. We study the problem of optimally choosing either the femto or the macro station based on the knowledge of the traffic arrival rate and the number of backlogged users in both cells. In this paper, we derive the optimal static policy of choosing the base stations that minimizes the average access delay. We also develop various dynamic policies based on the information about the arrivals and backlogged users, and compare their performance against each other and with the optimal static policy. We observe that some of these dynamic policies give very good performance, which provides a lower bound of performance. In addition, a dynamic policy that utilizes only the backlog levels, although not always as good as the optimal static policy, is robust and still stable for a wide range of arrival rates.

We consider a system of parallel queues where tasks are assigned (dispatched) to one of the available servers upon arrival. The dispatching decision is based on the full state information, i.e., on the sizes of the new and existing jobs. We are interested in minimizing the so-called mean slowdown criterion corresponding to the mean of the sojourn time divided by the processing time. Assuming no new jobs arrive, the shortest-processing-time-product (SPTP) schedule is known to minimize the slowdown of the existing jobs. The main contribution of this paper is three-fold: 1) To show the optimality of SPTP with respect to slowdown in a single server queue under Poisson arrivals; 2) to derive the so-called size-aware value functions for M/G/1-FIFO/LIFO/SPTP with general holding costs of which the slowdown criterion is a special case; and 3) to utilize the value functions to derive efficient dispatching policies so as to minimize the mean slowdown in a heterogeneous server system. The derived policies offer a significantly better performance than e.g., the size-aware-task-assignment with equal load (SITA-E) and least-work-left (LWL) policies.

We consider a dynamic dispatching problem where jobs are assigned upon arrival into parallel queues. Jobs have an arbitrary size distribution and each queue has its own service rate, queueing discipline, and operating power while serving jobs. Our goal is to minimize a weighted sum of delay and energy consumption under the assumption that the dispatcher is aware of the remaining service time of each job in the system, including that of the arriving job. We devise efficient dispatching heuristics based on the first policy iteration procedure of Markov Decision Processes. The resulting policies are illustrated by numerical examples. Direct control over the trade-off between performance and energy consumption will be increasingly important in future ICT equipment designs wherever dynamic queue assignment is needed.

We consider service systems where new jobs not only increase the load but also improve the service ability of such a system, cf. opportunistic scheduling gain in wireless systems. We study the optimal trade-off between the SRPT (Shortest Remaining Processing Time) discipline and opportunistic scheduling in the systems characterized by compact and symmetric capacity regions. The objective is to minimize the mean delay in a transient setting where all jobs are available at time 0 and no new jobs arrive thereafter. Our main result gives conditions under which the optimal rate vector does not depend on the sizes of the jobs as long as their order (in size) remains the same. In addition, it shows that in this case the optimal policy applies the SRPT principle serving the shortest job with the highest rate of the optimal rate vector, the second shortest with the second highest rate etc. We also give a recursive algorithm to determine both the optimal rate vector and the minimum mean delay. In some special cases, the rate vector, as well as the minimum mean delay, have even explicit expressions as demonstrated in the paper. For the general case, we derive both an upper bound and a lower bound of the minimum mean delay.

The fundamental P2P principle that downloading peers help other peers can be applied in the context of video-on-demand. This represents a demanding application combining aspects of other well-known P2P applications, i.e., live streaming and traditional file sharing. We seek to provide insight on fundamental questions about the performance and scalability of the system. A deterministic fluid model is derived that explicitly takes into account the video transfer and playback phases. The analytical results are complemented with extensive simulations from the corresponding stochastic model, as well as traces from a more realistic BitTorrent simulator.

HSDPA/HDR systems allow the use of sophisticated opportunistic schedulers that can utilize information on instantaneous channel conditions. On the other hand, for elastic data traffic the size of the files can be used in size-dependent scheduling methods, e.g., the well known SRPT scheduler, to minimize the flow delays. In this paper, we consider the optimal use of both size and channel information for minimizing the flow delay. We derive several heuristics which utilize both types of information. In a static setting with two flows and two rates, the optimal policy can be constructed via dynamic programming and can be compared against the policies using exact size knowledge. In the dynamic setting (stochastically arriving flows with random sizes), extensive simulations have been performed to evaluate the performance of the schedulers under heavy traffic. In the symmetric setting, the differences between the schedulers are clearly visible, while in the asymmetric setting the dynamics are more complex. The results still show that significant gains can be achieved with additionally using size information.

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.

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.