YEQT-III (Young European Queueing Theorists)
"Scheduling and Resource Sharing in Queueing Networks"
November 19-21, 2009

Programme

Thursday November 19
 

Friday November 20
 

Saturday November 20

Abstracts

Sandjai Bhulai

Optimal Scheduling Policies for the Limited Processor Sharing Queue

We study a limited processor sharing queue (LPS with Poisson arrivals and phase type service times. The processor can admit a limited number of requests for service. We present a new decomposition-based approach to analyze monotonicity properties that lead to a complete characterization for the optimal scheduling policy providing new fundamental insights into the optimal control of LPS queues. The results show that a considerable gain can be obtained by using the dynamic policy.

Matthieu Feuillet

Modeling Networks under the Law of the Jungle

In this talk we seek to characterize the behavior of the Internet in the absence of congestion control. More specifically, we assume all sources transmit at their maximum rate and recover from packet loss by the use of some ideal erasure coding scheme. We estimate the efficiency of resource utilization in terms of the maximum load the network can sustain, accounting for the random nature of traffic. We introduce stochastic processes describing the Law of the Jungle and we present results concerning resource utilization, fairness and the impact of access rates. Contrary to common belief, there is generally no congestion collapse. Efficiency remains high in most cases as long as maximum source rates are smaller than link capacities by one or two orders of magnitude.

Presentation
 

Itai Gurvich

On Optimality Gaps of Asymptotically Optimal Policies in the Many-server Heavy-traffic Regime

Optimality gaps in many-server asymptotic optimality results are typically shown to be of a smaller order of magnitude than the square-root of the demand rate but a more refined characterization of these gaps is usually not provided. Our work is concerned with characterizing and improving these gaps. First, we show that, in some cases, the optimality gaps that are provided in the literature can be tightened significantly without changing the prescribed control. For other cases, we discuss how to modify the limiting diffusion control problem (and the resulting control) so as to improve on the optimality gap. The analysis relates the optimality gaps to the connection between preemptive and non-preemptive controls and between diffusion control problems and dynamic programming.  

This is joint work with Baris Ata.

Presentation

Bruce Hajek

Collecting Coupons with Continuous Arrivals of Collectors

Distributed protocols for peer-to-peer file sharing over the Internet, such as BitTorrent, have been highly successful in recent years. The idea is that files to be shared are broken into chunks. As new peers enter the system they strive to obtain a complete collection from other peers. The problem of chunk collection is much like the classical coupon collector problem, but different collectors can make copies of coupons for each other. An interesting aspect is the effect of continuous arrivals of collectors who depart upon completing their collections. The theory for understanding the success of peer-to-peer systems has lagged far behind practice, and there is also much room to understand the relative strengths of different protocols in a variety of applications.

In this talk I shall discuss some stochastic models and present some recent results on the theory of peer-to-peer file sharing. Based in part on joint work with Ji Zhu.

Presentation I

Presentation II

Moshe Haviv

Strategic Customers behavior in Memoryless and non Memorylesss queues

Part 1: The whereabouts of customers in a queuing system interact. If more customers join the queue, one's waiting time may increase, up to a level that one may prefer not to join at all. This logic applies of course to the other customers, but if all stay out one may better join. So who are those to join and who are those not to join? Also, if too many packets are routed along one path, then an individual packet might be better assigned to some other path. But who will select this path, the individual himself or a central planner? Their objectives may not coincide: a self optimizer customer ignores the externalities that may results from any of his decisions and which effect others. For another decision problem, suppose acquiring the information which line or path is shorter, comes with some cost. Clearly, one has an incentive to pay for this information. Yet, one's incentive goes down with the fraction of those who acquire
the information as the more informed customers are, the More they will tend to make the two lines even anyhow. The tutorial will deal with these and similar decision models.

Many decision problems in queues can be modeled as non-cooperative games. In such games players, (or in our case, customers, service providers or routers) have to take actions. While selecting their actions they are not fully informed on the actions taken by others. In fact, in many situations, decision making is down simultaneously. Of course, each player wants to optimize his gains (utility) but one's optimal action is a function of what others are doing. Here comes the solution concept of Nash equilibrium. It replaces the concept of optimal solution which is used when a single decision maker is involved. Specifically, Nash equilibrium is a set of strategies, one for each player (usually refer to as a  strategy profile), so that, given that all obey this profile, each one of them does his best by following it too.

Most of the tutorial will be devoted to customers as decision makers who take actions as time progresses. Examples for that are to join or not to join the queue, which line to join, to pay or not to pay a premium in order to get higher priority level, or to renege or not from a queue when waiting costs start to be high. We will also consider service providers as decision makers. Here the assumption is that they select some parameters while trying to maximize their or the society's revenues. Examples for that are selecting entry fees, designing set of priority premiums, or selecting service rates (ie, bandwidth allocation). The service providers analyze their revenues by considering the Nash equilibria in the games between customers resulting from any option of their decisions.

The way the tutorial will approach the variety of decision models is by considering the information sets that customers may possess when they select their actions. Specifically, we first look into models in which customers do not know the actual level of congestion when they make up their mind (the unobservable case), while in the second case we assume that they do know (the observable case). A classic example is when customers have to decide if to queue or not to queue in a first-come first-served model where they are not informed on the actual queue length upon their arrival (the unobservable case) and when they are informed on the queue length (the observable case). Another example is when joining customers have the options to pay a premium in order to belong to a higher priority class of customers. The unobservable version  here is when they do not know how many customers are in the system at decision instants while in the observable version they are informed upon arrival on the number of customers belonging to each class.

The same approach is applicable for the central planner who wishes to maximize his profits. In the unobservable case, one-for-all price has to be administrated while in the observable version, the price can vary with the queue length. A more primitive question here is if the service provider should reveal the queue length to the customers (assuming that this is in his discretion). It is not always clear what it is best for him.

A few other examples for decision making will be given in the tutorial. Among them: if and when  to renege from a queue after waiting for a while, or when to check again if a server previously found to be busy is now available.

The talk is based on a 2003 book co-authored with Refael Hassin bearing the same title To Queue or not to Queue: EquilibriumBehavior in Queueing Systems, and published by Kluwer's International Series. Also, to appear, under the talk's title in Wiley Encyclopedia for Operations Research.

Part 2 (To queue or not to queue: The cases of partially and  fully observable M/G/1 queues): The intuition while observing the economy of queueing systems, is  that one's motivation to join the system, decreases with its level of congestion. This is certainly true in the case where service times are memoryless or when the actual workloads are known.  However, as in the quite general queueing model we describe below,  sometimes the opposite is the case.

The point of departure is the standard first-come first-served single server  queue with Poisson arrivals. Customers commence service immediately  if upon their arrival the server is idle. Otherwise, they are  informed if the queue is empty or not. Then, they have to decide whether  to join or not. We assume that the customers are homogeneous and  when they consider their moves, they assess their queueing costs  against their reward due to service completion. As the whereabouts of  customers interact, we look for the (possibly mixed) join/do not join Nash  equilibrium strategy, a strategy that if adopted by all, then under the  resulting  steady-state conditions, no one has any incentive not to follow  it oneself. We show that when the queue is empty then, depending on the  service distribution, both `avoid the crowd' (ATC) and `follow the crowd'  (FTC) scenarios (as well as none-of-the-above) are possible. (Under ATC  (FTC, reps.) one's best action is do the opposite of (same as, reps.)  what all others do.)  When the queue  is not empty, the situation is always that of ATC. Also, we show that under  Nash equilibrium it is possible  (depending on the service distribution)  that the joining probability when  the queue is empty is smaller than it is  when the queue is not  empty.

 The key technical difficulty in the above partially observable model  is to assess the mean residual service times of the one who is currently in  service, given the information of an empty or not empty line. This task becomes even harder in the fully observable case when the actual  queue length is informed prior to action taking. This is due to the fact that the mean  residual service time is  Queue-length dependent.  Moreover, as customers decide whether to join or not, a symmetric joining  (mixed) policy  prescribes a joining probability to each queue length.  Thus, the  resulting arrival process is no longer Poisson but one with  queue-length dependent joining rates. We derive the Laplace-Stieltjes  transform for the residual service time given the  queue length and define  a recursive procedure for the corresponding  means for this state dependent  arrival rate model. Implicit formulas for the equilibrium joining
 probabilities  are then determined.

Presentation

Nidhi Hegde

Scheduling Mobile Users in Wireless Networks

We consider the performance evaluation of scheduling schemes in wireless networks with mobile users.  We first establish properties of optimal scheduling schemes in a static environment, without user mobility.  We then extend the framework to networks with mobile users.  The impact of mobility on the network capacity and user throughput will be examined. Building on these results, we offer design principles for scheduling mobile users.

Presentation

David Hodge

Optimal index policies for multi-product make-to-stock queues: if resources are more costly would we use less?

We consider a key structural property of optimal inventory replenishment policies in a model with diminishing returns for resource effort. Our bottleneck lies in the limit on the replenishment rate. One could imagine that in communications networks the replenishment is analogous to packaging up processed jobs which are then placed in a queue to be distributed to customers according to a stochastic delivery process.

We target indexability, namely statewise monotonicity of the optimal policy in the resource cost, for both the standard lost sales model and a back-order model. We demonstrate conditions for indexability together with some surprising counterexamples. In the cases of non-indexability we are able to establish a notion of asymptotic indexability – with monotonic policies over a wide range of replenishment cost values. The work provides an easy algorithm for the more general multi-product replenishment problem via the derived indices. We then numerically evaluate the efficiency of this algorithm for tackling the general multi-product inventory replenishment problem with diminishing returns in a wide variety of examples.

Presentation

Peter Jacko

An Optimal Index Policy for the Multi-Armed Bandit Problem with Re-Initializing Bandits

In the multi-armed bandit problem it is assumed that the bandits are freezing, i.e., they maintain their state when not played. This results to be a crucial condition for proving optimality of the index policy: "At every period play the bandit of highest Gittins index". Instead of the freezing assumption, we consider bandits that move to a re-initializing state when not played. Such dynamics is well known in reinforcement learning, where a system quits a trial and starts a new upon receiving negative feedback from the external critic, and also appears in the simplest variants of the Transmission Control Protocol implemented in the Internet. We prove that if for every re-initializing bandit there exist marginal productivity indices (which generalize those of Gittins) such that the re-initializing state has the highest index among all the bandit’s states, then the marginal-productivity-index policy is optimal. Using analogous ideas we also give a new proof of the classic problem with freezing bandits that yields complementary insights to the existing proofs.

Presentation

Matthieu Jonckheere

Optimizing Admission Control in Balanced Networks

Consider a multiclass stochastic network with state dependent service rates and arrival rates describing bandwidth-sharing mechanisms as well as admission control and/or load balancing schemes. Given Poisson arrival and exponential service requirements, the number of customers in the network evolves as a multi-dimensional birth-and-death process on a finite subset of N^k. We assume that the death (i.e. service) rates and the birth rates depending on the whole state of the system, satisfy a local balance condition. This makes the resulting network a so-called Whittle network and the stochastic process describing the state of the network is reversible with
an explicit stationary distribution that is in fact insensitive to the service time distribution. Given routing constraints, we are interested in the optimal performance of such networks. We first construct bounds for generic performance criteria, that can be evaluated using recursive procedures, these bounds being attained in the case of a unique arrival process. We then study the case of several arrival processes, focusing in particular on the instance with admission control only. Building on convexity properties, we characterize the optimal policy, and give criteria on the service rates for which our bounds are again attained.

Presentation

Yoav Kerner

A queueing approach to a multi class M/G/1 make-to-stock with backlog

A single machine produces an item according to a renewal process. Customers of each class arrive according to independent Poisson processes and differ from each other only in their waiting cost, which is assumed to be linear. We assume finite classes. We consider a linear (both in time and inventory level) holding cost. One would like to find a policy that minimizes the overall cost. An Inventory Rationing (IR) policy is defined by a base stock level and a finite sequence of thresholds, such that a class i customer receives an item if and only if the inventory level exceeds the threshold R_i. The IR policy can be presented as an M/G/1 priority system with state dependent arrival rates. In general, the IR policy is not optimal, even when the information given to the decision maker is only the queue lengths of various customers types. In this talk we will discuss cases in which the IR policy is optimal, and we will present an improvement when it is not. The analysis is based on busy period analysis of M/G/1 priority system and on obtaining the conditional residual service time in such a system.

Presentation

Iordanis Koutsopoulos

Client and Server Games in Peer-to-Peer Networks

We consider a content sharing network of non-cooperative peers. The strategy set of each peer comprises, (i) client strategies, namely feasible request load splits to servers, and (ii) server strategies, namely scheduling disciplines on requests. The performance metric is average retrieval delay. First, we consider the request load splitting game for given server strategies such as First-In-First-Out or given absolute priority policies. A peer splits its request load to servers to optimize its performance objective. We consider the class of best response load splitting policies residing between the following extremes: a truly selfish, or egotistic one, where a peer optimizes its own  delay, and a pseudo-selfish or altruistic one, where a peer also considers incurred delays to others. We derive conditions for Nash equilibrium points (NEPs) and discuss convergence to NEP and properties of the NEP. For both the egotistic cases, the NEP is unique. For the altruistic case, each of the multiple NEPs is an optimum, a global one for the FIFO case and a local one otherwise.

Next, we include scheduling in peer strategies. With its scheduling discipline, a peer cannot directly affect its delay, but it can affect the NEP after peers play the load splitting game. The idea is that peer i should offer high priority to (and thus attract traffic from) higher-priority peers that cause large delay to i at other servers. We devise two-stage game models, where, at a first stage, a peer selects a scheduling rule in terms of a convex combination of absolute priorities, and subsequently peers play the load splitting game. In the most sophisticated rule, a peer selects a scheduling discipline that minimizes its delay at equilibrium, after peers play the load splitting game. We also suggest various heuristics for picking the scheduling discipline. Our models and results capture the dual client-server peer role and aim at quantifying the impact of selfish peer interaction on equilibria.

Presentation

Pasi Lassila

Minimizing the Mean Flow-Level Delay in Wireless Systems

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 delay. We consider the use of both size and channel information for minimizing the flow delay in the dynamic setting with randomly arriving flows having random sizes and independent random channel rate variations. We start by considering the case where the scheduler is only aware of the mean rate of the user channels. In this case, the system can be modeled as an M/G/1 queue, for which the SRPT policy provides the optimal policy. In the case where both instantaneous rate and size information is available, the optimal policy is not known. In our work, we study simple index and priority policies, and use the well-known PF policy as the baseline. In this setting, the stability of the policies becomes an issue, especially when considering users with highly asymmetric channels.

Presentation

Erjen Lefeber

Controller Design for Networks of Switching Servers with Setup Times

In this talk we consider the controller design for networks of switching servers, e.g. manufacturing systems or urban road networks (traffic light control). Control of these networks is difficult, since using controllers that are stable for a server in isolation might render the network unstable. We present an approach to controller design which is inspired from control theory. To that end, instead of starting from a policy and then analyzing the proposed policy, we start from a priori
specified desired network behavior.  Using this desired behavior for the network under consideration as a starting point, we derive a policy which guarantees convergence of the system towards this desired behavior. Though the policy is tailor made for both the network under consideration and its desired behavior, we aim for a general methodology that is applicable to arbitrary networks and arbitrary feasible network behavior. Furthermore, even though the approach is based on deterministic fluid queues, the resulting controllers are feedbacks which can also be applied when inter-arrival times and service times are stochastic. First simulation experiments show promising results.

Marc Lelarge

Efficient Control of Epidemics over Random Networks.

Motivated by the modeling of the spread of viruses or epidemics with coordination among agents, we introduce a new model generalizing both the basic contact model and the bootstrap percolation. We analyze this percolated threshold model when the underlying network is a random graph with fixed degree distribution. Our main results unify many results in the random graphs literature. In particular, we provide a necessary and sufficient condition under which a single node can trigger a large cascade. Then we quantify the possible impact of an attacker against a degree based vaccination and an acquaintance vaccination. We define a security metric allowing to compare the different vaccinations. The acquaintance vaccination requires no knowledge of the node degrees or any other global information and is shown to be much more efficient than the uniform vaccination in all cases.

Presentation

Seva Shneer

Throughputs and fairness in slotted and non-slotted versions of CSMA

We consider a system consisting of $n$ transmitters/receivers placed on a line. The channel used by transmitters is such that $2$ transmitters cannot send messages at the same time if the distance between them is not larger than $k$, where $k$ is a positive integer. The well-known CSMA protocol is often used to govern the behaviour of the transmitters in this scenario, and the performance of the system in this case is well-understood. We propose a discrete-time analogue of the CSMA protocol and in the case of a completely saturated system find exact formulas for the total throughput of the system governed by this algorithm and for individual throughputs of all transmitters. We then compare these throughputs with the throughputs achieved by the classical CSMA protocol. The fairness of both protocols is also compared. Finally, we discuss bounds for the throughput of a system where the first transmitter (source) is saturated and messages are relayed by the intermediate transmitters to the last one (destination). This is a joint work with Peter van de Ven (TU/e and EURANDOM).

Slawomir Stanczak

Efficient versus Fair Resource Allocation in Autonomous Wireless Interference Networks

Wireless resources are scarce and the capacity of wireless links exhibits an ephemeral and dynamic nature, depending for instance on wireless channel characteristics and transmit powers of all interfering links. At the same time, wireless networks will have to support a wide range of applications having fundamentally different QoS requirements and traffic characteristics. All this requires a better understanding of the fundamental tradeoffs and interdependencies in wireless networks, with the goal of designing resource allocation strategies that exploit these interdependencies to achieve significant performance gains. In this talk, we will present a systematic summary of some recent results and algorithmic solutions for resource allocation and interference management in distributed wireless networks. The main focus is on a joint optimization of physical-layer signaling and the medium access control, including power control and link scheduling. A particular interest is attached to advanced multiple antenna and beam forming technologies. A distributed implementation of the algorithms is based on the concept of an adjoint network; this concept also has an interesting application in wireless sensor networks.

Presentation (changed speaker)

Ioannidis Stratis

Scalable and Reliable Searching in Unstructured Peer-to-Peer Systems

Searching in unstructured peer-to-peer systems poses a challenge because of high churn: both the topology and the content stored by peers can change quickly as peers arrive and depart, while the network formed under this churn process can be arbitrary at any point in time. Ideally, a search mechanism in a peer-to-peer system should be scalable:  as, typically, peers have limited bandwidth, the traffic generated by queries should not grow significantly as the peer population increases.  Moreover, a search mechanism should also be reliable: if certain content is in the system,  searching should locate it with reasonable guarantees. These two goals can be conflicting, as generating more queries increases a mechanism's reliability but decreases its scalability. Hence, a fundamental question regarding searching in unstructured systems is whether a mechanism can exhibit both properties, despite the network's dynamic and arbitrary nature.  We show this is indeed the case, by proposing a novel mechanism that is both scalable and reliable.  To obtain this result, we model the evolution of the network as a Markov chain over the set of possible overlay graph configurations, whose transitions depend on the connection protocol followed by peer arrivals and departures. 

Presentation

Control of Systems with Flexible Multi-server Pools: A Shadow Routing Approach

A general model with multiple input flows (classes) and several flexible multi-server pools is considered. We propose a robust, generic scheme for routing new arrivals, which optimally balances server pools' loads, without the knowledge of the flow input rates and without solving any optimization problem. The scheme is based on Shadow routing in a virtual queuing system. We study the behavior of our scheme in the Halfin-Whitt (or, QED) asymptotic regime.

Jean Walrand

Scheduling for Communication and Processing Networks

The talk reviews the history and recent results on the scheduling of tasks that require access to a set of resources.

The first step was the discovery that maximum weighted matching achieves the maximum throughput for a class of such scheduling problems that includes wireless networks and packet switches [1]. However, this algorithm is too complex to be directly applicable.
The second step was understanding when a simpler algorithm, longest queue first, also achieves maximum throughput [2]. This algorithm suggests that, in general, the scheduling should favor tasks with a larger backlog. The third step was inventing a distributed algorithm where tasks select an independent random back off delay before asking for the resources; this delay has a mean value that decreases exponentially with the backlog [3]. Using stochastic approximation theory, one shows that this algorithm achieves the maximum throughput [4]. The fourth step is a modification of maximum weight matching to achieve the maximum utility in a processing network where tasks not only share resources but also require access to parts [5].
The talk explains the intuition behind the results and the main ideas of
the proofs.

Main references:

[1] L. Tassiulas, A. Ephremides, ``Stability properties of constrained
queueing systems and scheduling for maximum throughput in multihop radio
networks,'' IEEE Transactions on Automatic Control, Vol. 37, No. 12, pp.
1936-1949, December 1992.

[2] A. Dimakis and J. Walrand, “Sufficient Conditions for Stability of
Longest Queue First Scheduling: Second Order Properties Using Fluid
Limits,” Journal of Applied Probability, May 2005.

[3] L. Jiang and J. Walrand, “A Distributed CSMA Algorithm for
Throughput and Utility Maximization in Wireless Networks," Allerton 2008.

[4] Libin Jiang and Jean Walrand, "Convergence and Stability of a
Distributed CSMA Algorithm for Maximal Network Throughput," IEEE
Conference on Decision and Control, Dec 2009.

[5] Libin Jiang and Jean Walrand, "Utility-Maximizing Scheduling for
Stochastic Processing Networks," Forty-Seventh Annual Allerton
Conference, Illinois, USA September 2009.

Presentation

Bert Zwart

Scheduling Performance and Asymptotics

Abstract: We give an overview of recent research on the performance of scheduling disciplines such as Processor Sharing and Shortest Remaining Processing time, motivated by recent problems in computer systems and communication networks. Emphasis is on the impact of the choice of the scheduling discipline on the occurrence of rare events, and the behavior under critical load. The aim is to give the audience an overview of the results in this area, to provide intuition behind these results, and to review some of the basic techniques behind them. See http://www.cs.cmu.edu/afs/cs.cmu.edu/user/harchol/www/Papers/boxma.pdf for some background.

Presentation I

Presentation II

    P.O. Box 513, 5600 MB  Eindhoven, The Netherlands
tel. +31 40 2478100  fax +31 40 2478190  
  e-mail: office@eurandom.tue.nl