Search

Redundancy scheduling has emerged as a powerful strategy for improving response times in parallel-server systems. The key feature in redundancy scheduling is replication of a job upon arrival by dispatching replicas to different servers. Redundant copies are abandoned as soon as the first of these replicas finishes service. By creating multiple service opportunities, redundancy scheduling increases the chance of a fast response from a server that is quick to provide service and mitigates the risk of a long delay incurred when a single selected server turns out to be slow. The diversity enabled by redundant requests has been found to strongly improve the response time performance, especially in the case of highly variable service requirements. Analytical results for redundancy scheduling are unfortunately scarce however, and even the stability condition has largely remained elusive so far, except for exponentially distributed service requirements. In order to gain further insight in the role of the service requirement distribution, we explore the behavior of redundancy scheduling for scaled Bernoulli service requirements. We establish a sufficient stability condition for generally distributed service requirements, and we show that, for scaled Bernoulli service requirements, this condition is also asymptotically nearly necessary. This stability condition differs drastically from the exponential case, indicating that the stability condition depends on the service requirements in a sensitive and intricate manner.

We consider scheduling in networks with interference constraints and reconfiguration delays, which may be incurred when one service schedule is dropped and a distinct service schedule is adopted. Reconfiguration delays occur in a variety of communication settings, such as satellite, optical, or delay-tolerant networks. In the absence of reconfiguration delays it is well known that the celebrated Max-Weight scheduling algorithm guarantees throughput optimality without requiring any knowledge of arrival rates. As we will show, however, the Max-Weight algorithm may fail to achieve throughput optimality in case of nonzero reconfiguration delays. Motivated by the latter issue, we propose a class of adaptive scheduling algorithms which persist with the current schedule until a certain stopping criterion is reached, before switching to the next schedule. While earlier proposed Variable Frame-Based Max-Weight (VFMW) policies belong to this class, we also present Switching-Curve-Based (SCB) policies that are more adaptive to bursts in arrivals. We develop novel Lyapunov drift techniques to prove that this class of algorithms under certain conditions achieves throughput optimality by dynamically adapting the durations of the interswitching intervals. Numerical results demonstrate that these algorithms significantly outperform the ordinary Max-Weight algorithm, and that SCB policies yield a better delay performance than VFMW policies.

We consider a system of parallel servers handling users of various classes, whose service rates depend not only on user classes, but also on the set of active servers. We investigate the stability under two types of allocation strategies: (i) server assignment where the users are assigned to servers based on rates, load, and other considerations, and (ii) coordinated scheduling where the activity states of servers are coordinated. We show how the model may be applied to evaluate the downlink capacity of wireless data networks. Specifically, we examine the potential gains in wireless capacity from the two types of resource allocation strategies.

Over the past few decades, the Processor-Sharing (PS) discipline has attracted a great deal of attention in the queueing literature. While the PS paradigm emerged in the sixties as an idealization of round-robin scheduling in time-shared computer systems, it has recently captured renewed interest as a useful concept for modeling the flow-level performance of bandwidth-sharing protocols in communication networks. In contrast to the simple geometric queue length distribution, the sojourn time lacks such a nice closed-form characterization, even for exponential service requirements. In case of heavy-tailed service requirements however, there exists a simple asymptotic equivalence between the sojourn time and the service requirement distribution, which is commonly referred to as a reduced service rate approximation. In the present survey paper, we give an overview of several methods that have been developed to obtain such an asymptotic equivalence under various distributional assumptions. We outline the differences and similarities between the various approaches, discuss some connections, and present necessary and sufficient conditions for an asymptotic equivalence to hold. We also consider the generalization of the reduced service rate approximation to several extensions of the M/G/1 PS queue. In addition, we identify a relationship between the reduced service rate approximation and a queue length distribution with a geometrically decaying tail, and extend it to so-called bandwidth-sharing networks. The state-of-the-art with regard to sojourn time asymptotics in PS queues with light-tailed service requirements is also briefly described. Last, we reflect on some possible avenues for further research.

We consider a system with two heterogeneous traffic classes. The users from both classes randomly generate service requests, one class having light-tailed properties, the other one exhibiting heavy-tailed characteristics. The heterogeneity in service requirements reflects the extreme variability in flow sizes observed in the Internet, with a vast majority of small transfers (“mice”) and a limited number of exceptionally large flows (“elephants”). The active traffic flows share the available bandwidth in a Processor-Sharing (ps) fashion. Theps discipline has emerged as a natural paradigm for modeling the flow-level performance of band-width-sharing protocols liketcp. The number of simultaneously active traffic flows is limited by a threshold on the maximum system occupancy. We obtain the exact asymptotics of the transfer delays incurred by the users from the light-tailed class. The results show that the threshold mechanism significantly reduces the detrimental performance impact of the heavy-tailed class.

We consider two types of queues with workload-dependent arrival rate and service speed. Our study is motivated by queueing scenarios where the arrival rate and/or speed of the server depends on the amount of work present, like production systems and the Internet. First, in the M/G/1 case, we compare the steady-state distribution of the workload (both at arbitrary epochs and at arrival instants) in two models, in which the ratio of arrival rate and service speed is equal. Applying level crossing arguments, we show that the steady-state distributions are proportional. Second, we consider a G/G/1-type queue with workload-dependent interarrival times and service speed. Using a stochastic mean-value approach, several well-known relations for the workload at various epochs in the ordinary G/G/1 queue are generalized.

We consider a system of two coupled queues Q1 and Q2. When both queues are backlogged, they are each served at unit rate. However, when one queue empties, the service rate at the other queue increases. Thus, the two queues are coupled through the mechanism for dynamically sharing surplus service capacity. We derive the asymptotic workload behavior at Q1 for various scenarios where at least one of the two queues has a heavy-tailed service time distribution. First of all, we consider a situation where the traffic load at Q1 is below the nominal unit service rate. We show that if the service time distribution at Q1 is heavy-tailed, then the workload behaves exactly as if Q1 is served in isolation at a constant rate, which only depends on the service time distribution at Q2 through its mean. In addition, we establish that if the service time distribution at Q1 is exponential, then the workload distribution is either exponential or semi-exponential, depending on whether the traffic load at Q2 exceeds the nominal service rate or not. Next, we focus on a regime where the traffic load at Q1 exceeds the nominal service rate, so that Q1 relies on the surplus capacity from Q2 to maintain stability. In that case, the workload distribution at Q1 is determined by the heaviest of the two service time distributions, so that Q1 may inherit potentially heavier-tailed characteristics from Q2.

We consider a slotted queueing system with C servers (processors) that can handle tasks (jobs). Tasks arrive in batches of random size at the start of every slot. Any task can be executed by any server in one slot with success probability α. If a task execution fails, then the task must be handled in some later time slot until it has been completed successfully. Tasks may be processed by several servers simultaneously. In that case, the task is completed successfully if the task execution is successful on at least one of the servers.We examine the impact of various allocation strategies on the mean number of tasks in the system and the mean response time of tasks. It is proven that both these performance measures are minimized by the strategy which always distributes the tasks over the servers as evenly as possible. Subsequently, we determine the distribution of the number of tasks in the system for a broad class of task allocation strategies, which includes the above optimal strategy as a special case. Some numerical experiments are performed to illustrate the performance characteristics of the various strategies.

We are pleased to present this special issue “Recent Trends in the Mathematics of Wireless Communication Networks: Algorithms, Models, and Methods.” Wireless communication systems have experienced a spectacular expansion over the last few decades, now providing the predominant means of Internet access. The capacity of these systems is constrained by a set of scarce resources such as radio frequencies, transmit power, and time slots. Information theory offers a powerful mathematical framework to understand how these transmission resources should be allocated so as to maximize the capacity at the physical layer, yielding valuable insights for the design of efficient schemes for, e.g., modulation, coding, and power control. Typically, however, information-theoretic models pertain to idealized scenarios: They do not account for random user behavior and dynamics at higher network layers; the practical application-specific performance requirements are largely ignored, and algorithmic implementation constraints are usually not considered. Designing systems while systematically addressing all of these aspects has posed major challenges in the last few decades. The vital need for wireless networks with significantly better performance has rejuvenated research activities toward tackling these challenges.

We discuss a statistical model to generate correlated shadow-fading patterns for wireless systems in the absence of detailed propagation and landscape information. The currently available autocorrelation models result in anomalous effects that depend on traffic density and mobility, as they propose independent random processes for each mobile. Our approach involves generating a pre-computed fading map with the right marginal distributions and spatial correlations, which avoids inconsistencies such as providing widely differing values for mobiles close to each other. The correlations are introduced via a Gaussian random field, which has a covariance structure that depends on a set of parameters which can be computed from local measurements. The model is efficiently implemented using standard linear-algebra methods. We conclude by describing a simulation experiment to study the effect of correlations on call dropping. The experiment reveals a strong relationship between call dropping and the correlation length of the fading pattern, and indicates circumstances under which dropping may be relatively high.

We consider networks where traffic is served according to the Generalised Processor Sharing (GPS) principle. GPS-based scheduling algorithms are considered important for providing differentiated quality of service in integrated-services networks. We are interested in the workload of a particular flow i at the bottleneck node on its path. Flow i is assumed to have long-tailed traffic characteristics. We distinguish between two traffic scenarios, (i) flow i generates instantaneous traffic bursts and (ii) flow i generates traffic according to an on/off process. In addition, we consider two configurations of feed-forward networks. First we focus on the situation where other flows join the path of flow i. Then we extend the model by adding flows which can branch off at any node, with cross traffic as a special case. We prove that under certain conditions the tail behaviour of the workload distribution of flow i is equivalent to that in a two-node tandem network where flow i is served in isolation at constant rates. These rates only depend on the traffic characteristics of the other flows through their average rates. This means that the results do not rely on any specific assumptions regarding the traffic processes of the other flows. In particular, flow i is not affected by excessive activity of flows with ‘heavier-tailed’ traffic characteristics. This confirms that GPS has the potential to protect individual flows against extreme behaviour of other flows, while obtaining substantial multiplexing gains.