European Institute for Statistics, Probability, Stochastic Operations Research and their Applications

About | Research | Events | People | Reports | Alumni | ContactHome

24-25-26 OCTOBER, 2011

Young European Queueing Theorists (YEQT V)

Workshop on

“Stochastic Networks and Optimization”

 SUMMARY REGISTRATION SPEAKERS PROGRAMME ABSTRACTS

This will be the fifth edition of the Young European Queueing Theorists workshop. YEQT is organised for and by young researchers in the area of queueing theory. The event will take place on October 24-26, 2011, at Eurandom, Eindhoven, Netherlands. As the title suggests, the program consists mainly of talks by young researchers: final year PhD students, postdocs, or recently appointed assistant professors. The event provides an excellent opportunity for developing researchers to interact and present their research findings. For many participants, this is the first opportunity to present their work, and YEQT provides a friendly, yet research focused, venue for this purpose.

In addition to these talks, two keynote lectures are given by prominent senior researchers, and typically two or three tutorials are also given by senior researchers. The theme of this year's edition is "Stochastic Networks and Optimization". "Stochastic networks" because in queueing applications more often than not a queue is one component of a much larger network. "Optimization" because there is a growing number of researchers who apply optimization techniques to the design and control of such queueing systems. Thus, we feel this would be an appropriate tool kit for the next generation of queueing theorists to learn and develop.

Keynote speakers will be Mark Squillante (IBM) and Leandros Tassiulas (University of Thessaly). The tutorials will be given by Devavrat Shah (MIT) and David Gamarnik (MIT), who all have research interests fitting this topic perfectly.

 Neil Walton University of Amsterdam Florian Simatos CWI/Eurandom Marko Boon Eurandom and Eindhoven University of Technology

Former YEQT workshops

This is the fifth workshop in the series of YEQT (Young European Queueing Theorists) workshops.
The previous YEQT workshops are

YEQT-I    "Queueing theory without limits: transient and asymptotic analysis", October 17-19, 2007

Fee

Fee is 75 euros. The fee includes lunches, coffee/refreshments and the conference dinner.

Exceptions:
- Speakers and Organizers
- Participants from TU/e only pay 35 euro, if they want to join the dinner

Bank details are given on the registration form.

Registration

Registration is obligatory for all participants (organizers and speakers too!).

Please indicate on the registration form your attendance, participation in the lunches, dinner.

For keynote/tutorial speakers hotel accommodation will be reserved. You are requested to indicate which nights you need accommodation on the registration form.

For accepted contributed speakers, double rooms will be reserved. These rooms will be shared. For 45 euro per night (your own expense) you may prefer a single room. In that case please mark the box on the registration form.

Participants have to make their own hotelbooking. However, they can get a reduced rate if they book our preferred hotel Crown Inn.
Please send an email to Patty Koorn for instructions on how to obtain this special price.

Other hotels around: Eindhoven University of Technology (please note: prices listed are "best available").

Or you can consult the web pages of the Tourist Information Eindhoven, Postbus 7, 5600 AA Eindhoven.

Programme

Monday October 24

 09.20 - 09.30 Welcome Connie Cantrijn (Managing Director Eurandom) 09.30 - 10.10 Seva Shneer Stability of Markov-modulated Markov chains 10.10 - 10.50 Peter van de Ven Spatial instability of MaxWeight scheduling algorithms 10.50 - 11.20 Break 11.20 - 12.20 David Gamarnik (Tutorial)  Algorithmic challenges in the theory of queueing networks 12.20 - 14.00 Lunch 14.00 - 15.00 Mark Squillante (Keynote) Linear Stochastic Loss Networks: Analysis and Optimization 15.00 - 15.40 Istvan Kolossvary Explicit identification of the class of order 3 matrix exponential distributions 15.40 - 16.10 Break 16.10 - 16.50 Lasse Leskela Stochastic ordering of network throughputs using flow couplings 16.50 - 17.30 Mathieu Feuillet The time scales of a stochastic network with failures 18.30 - Conference Dinner

Tuesday October 25

 09.30 - 10.30 Leandros Tassiulas (Keynote) Stochastic models and algorithms for cooperative information delivery 10.30 - 11.10 Jasper Goseling Energy-delay Tradeoff in Wireless Network Coding 11.10 - 11.30 Break 11.30 - 12.30 Devavrat Shah (Tutorial) Network Scheduling: Applications, Algorithms and Analysis 12.30 - 14.00 Lunch 14.00 - 15.00 Devavrat Shah (Tutorial) Network Scheduling: Applications, Algorithms and Analysis 15.00 - 15.40 Peter Jacko Value of Information in Optimal Flow-Level Scheduling of Users with Markovian Time-Varying Channels 15.40 - 16.10 Break 16.10 - 16.50 Niek Bouman Backlog-Based Random Access in Wireless Networks 16.50 - 17.30 Ana Busic Perfect sampling of queueing networks

Wednesday October 26

 09.30 - 10.30 Elena Yudovina A (very simple) limit order book model 10.30 - 11.10 Clement Dombry The intermediate scaling for the On/OFF network traffic model 11.10 - 11.30 Break 11.30 - 12.30 David Garmarnik (Tutorial) Algorithmic challenges in the theory of queueing networks 12.30 - 14.00 Lunch 14.00 - 14.40 Martin Erausquin Scheduling in a random environment: stability and asymptotic optimality 14.40 - 15.10 Break 15.10 - 15.50 Jiheng Zhang Modeling Webchat Service Center with Many LPS Servers 15.50 - 16.30 Masha Frolkova Fluid limits for bandwidth-sharing networks with rate constraints

Abstracts

Niek Bouman (TU/e)

Backlog-Based Random Access in Wireless Networks

We explore the spatio-temporal congestion dynamics of wireless networks with backlog-based random-access mechanisms. While relatively simple and inherently distributed in nature, suitably designed backlog-based access schemes provide the striking capability to match the optimal throughput performance of centralized scheduling algorithms in a wide range of scenarios. In this talk, we show that the specific activity functions for which maximum stability has been established, may however yield excessive queue lengths and delays. The results reveal that more aggressive/persistent access schemes can improve the delay performance, while retaining the maximum stability guarantees in a rich set of scenarios. In order to gain qualitative insights and examine stability properties we will investigate fluid limits where the system dynamics are scaled in space and time. As it turns out, several distinct types of fluid limits can arise, exhibiting various degrees of randomness, depending on the structure of the network, in conjunction with the form of the activity functions. Simulation experiments are conducted to illustrate and validate the analytical findings.

PRESENTATION

Ana Busic (INRIA)

Perfect sampling of queueing networks

Perfect sampling uses coupling arguments to provide a sample from the stationary distribution of a Markov chain. This technique is efficient if the transition function of the Markov chain is monotone. In the non-monotone case, one can construct bounding chains that can detect whether the initial chain has coupled. For instance, if the state space is a lattice, then one such bounding chain can be defined by taking the smallest interval (envelope) that contains the image of the one step transition function. We show that this is particularly effective when the events are piecewise homogeneous. We further investigate the classes of markovian queueing networks having this property and propose efficient algorithms in some cases.

Clément Dombry (Université de Poitiers)
(joint work with Ingemar Kaj)

The intermediate scaling for the On/OFF network traffic model

We discuss in this talk the scaling behavior in heavy-tailed stochastic models for transmission of packet trafﬁc on high-speed communication links. Popular models include inﬁnite source Poisson models, models based on aggregated renewal sequences, and models built from aggregated on-off sources. These three models share the following pattern: the asymptotic behavior of the cumulated workload when both the connection rate and the time scale go to inﬁnity depends crucially of the relative growth of both parameters and several regimes appear. If the sources connect at a fast rate over time the ﬂuctuations scale like fractional Brownian motion; if the connection rate is slow the trafﬁc ﬂuctuations are described by a stable Lévy motion. We emphasize in this talk the intermediate scaling and prove that the ON-OFF model has the same behavior as the other two models, namely a fractional Poisson process arises in the limit. The proof is based on a coupling between the
ON-OFF model and the renewal type model. The end of the talk is devoted to the presentation of new results on moment measures of heavy-tailed renewal point processes and their asymptotics. They clarify the existing result for the aggregation of renewal processes under intermediate scaling.

PRESENTATION

Martin Erausquin (UPV/EHU, University of the Basque Country)

1Scheduling in a random environment: stability and asymptotic optimality

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. 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 the cmu-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.

PRESENTATION

Mathieu Feuillet (INRIA)

The time scales of a stochastic network with failures

We consider a set of nodes which store files in a network. Each node breaks down regularly, in which case it loses all the files it contains. In order to avoid definitive losses of files, a back-up mechanism is used and files are duplicated in different nodes. A small part of the bandwidth of each node is dedicated to this back-up mechanism. We propose a simple Markovian model in order to evaluate the long-term evolution of such a system. With this model, we are able to define the capacity of the system, that is the maximum number of files that can be stored in each node. If we consider this system at the "macroscopic level" (i.e. using a scaling when the number of nodes and files grows to infinity), important losses are observed above capacity and no loss is observed below capacity. Below capacity, the system then lives in a kind of steady-state. Thanks to several scaling methods with different time scales, we are able to describe precisely the behavior of the network and finally we obtain the decay rate of the network which can be seen as the speed at which files are lost.

PRESENTATION

Masha Frolkova (CWI)

Fluid limits for bandwidth-sharing networks with rate constraints

Bandwidth-sharing networks as considered by Massoulié \& Roberts (1998,1999) are important flow level models of communication networks. We focus on the fact that it takes a significant number of users to saturate a link, necessitating the inclusion of individual rate constraints. In particular we extend work of Reed \& Zwart (2010) on fluid limits of bandwidth sharing with rate constraints under Markovian assumptions: we consider a bandwidth-sharing network with rate constraints where job sizes and patience times have a general distribution. We obtain a fluid limit and investigate its properties. In particular we show that the invariant distributions of the pre-limit networks converge to that of the fluid limit.

PRESENTATION

David Gamarnik (MIT)

Algorithmic challenges in the theory of queueing networks

The theory of queueing systems is traditionally considered as a branch of applied probability. Hence the toolkit used in the analysis of queueing system draws heavily on the theory of stochastic processes. Many problems in the area of queueing networks, however, are of algorithmic nature, and thus require algorithmic/complexity theoretic approaches. In this tutorial we will discuss several such questions, ranging from some older results on designing optimal control of queueing networks, to more recent results on determining stability properties of queueing networks leading to the fascinating theory of algorithmic undecidability (non-computability).
We will illustrate these approaches on a broad scope of models, including multiclass queueing networks, constrained random walks and Skorokhod mapping problem, the latter arising in studying queueing networks in the heavy traffic regime.
No background in the theory of algorithms and complexity theory is expected and the tutorial will be completely self-contained.

PRESENTATION

Jasper Goseling (University of Twente)

Energy-delay Tradeoff in Wireless Network Coding

A queueing model for wireless communication network in which network coding is employed is introduced. It is shown that networks with coding are closely related to queueing networks with positive and negative customers. Analytical upper and lower bounds on the energy consumption and the delay are obtained using a Markov reward approach. The tradeoff between minimizing energy consumption and minimizing delay is investigated. Exact expressions are given for the minimum energy consumption and the minimum delay attainable in a network.

PRESENTATION

Peter Jacko (BCAM - Basque Center for Applied Mathematics)

Value of Information in Optimal Flow-Level Scheduling of Users with Markovian Time-Varying Channels

We design, characterize in closed-form, and evaluate a new index rule for Markovian time-varying channels, which gives rise to a simple opportunistic scheduling rule for flow-level scheduling in wireless downlink systems. For user channels we employ the Gilbert-Elliot model with a flow-level interpretation: the channel condition follows a general two-state Markov chain with distinct probabilities of finishing the flow transmission. The index value of the bad channel condition takes into account both the one-period and the steady-state potential improvement of the service completion probability, while the good channel condition gets an absolute priority with the $c \mu$ -index (well-known to be throughput-optimal) as the tie-breaking rule. Our computational study confirms near-optimality of the proposed rule in most of the instances, and suggests that information about the channels steady state is often enough to achieve near-optimality.

PRESENTATION

István Kolossváry (Budapest University of Technology and Economics)

Explicit identification of the class of order 3 matrix exponential distributions

The analysis of queuing systems with generally distributed inter-arrival and/or service time is difficult in many cases. For this reason phase type (PH) distributions are often used for approximation, because these distributions have a nice Markovian stochastic interpretation and the generator matrix of the overall Markov chain describing the behavior of the queuing system has a special structure. Due to this special structure efficient numerical methods, referred to as matrix geometric methods, are available to determine the stationary and transient behavior of the approximating system. The computational complexity of these methods depends on the size of the PH distributions. The
goal of the approximation is to reach greater accuracy without increasing the dimensions of the PH distributions too much. A possible way to achieve this goal is to use a wider class of distributions for the fitting that can still be analyzed with the same efficient numerical
methods.
A greater fitting accuracy can be achieved without increasing the size of the involved matrixes using matrix exponential (ME) distributions. The generator of an ME distribution doesn’t have to meet the restrictions of a PH distribution, which gives a greater flexibility in the fitting.
Furthermore, due to the same matrix exponential form of the density function, the same efficient numerical methods are available to analyze queuing systems with ME distributions. The drawback of the use of ME distributions is that it is difficult to decide whether the result of a fitting algorithm determines a valid ME distribution or not. The non-negativity of the density function must be checked for this. The density function has different forms according to the eigenvalue structure of the generator. The presentation will show that for order 3 ME distributions it is possible to check the non-negative property in an explicit way in all possible cases. To this end an order reduction
approach is introduced with which all the cases can be handled in a similar way. It is also demonstrated that the higher order cases requires the numerical solution of transcendent equations to check the non-negativity of matrix exponential functions.

Lasse Leskelä (University of Jyväskylä)

Stochastic ordering of network throughputs using flow couplings

A standard way to prove the stability of a queueing network is to show that the number of customers in the network is stochastically dominated by another network which is known to be stable. This approach is limited in practice because networks where the arrival and deparature rates depend on the queue lengths are usually not stochastically monotone. On the other hand, in most applications we care more about what goes through the network than what is inside it. In this talk I will describe a non-Markov coupling technique for Markov queueing networks that allows to stochastically order throughputs in networks where traditional couplings of customer populations would fail. This technique may be regarded as a probabilistic analogue of the Markov reward comparison approach developed by Nico van Dijk and others over the past two decades.

PRESENTATION

Devavrat Shah (MIT)

Network Scheduling: Applications, Algorithms and Analysis

Scheduling resources is one of the most ubiquitous problem arising in the context of variety of "networked" systems. This includes communication networks, data storage and computation networks, transportation networks and manufacturing networks. The stochastic processing networks model has been an excellent abstraction that faithfully captures the underlying reality for the purpose of addressing the challenge of resource allocation across this range of applications. In the past two decades, there has been a concerted effort to address the grand challenge of designing high-performance (read optimal) and implementable (read extremely simple) scheduling algorithms for generic stochastic network model. This has led to a great deal of progress at all fronts: new applications, interesting algorithms and novel analytic techniques. This tutorial will make an attempt to describe the state-of-art in this quest from personally biased perspective. Specifically, the tutorial will promote the view of the resource scheduling question from perspective of achievable trade-offs between three performance metrics: capacity, queue-sizes, and complexity. Tutorial will end with my favorite open research direction.

Seva Shneer (Heriot-Watt University)

Stability of Markov-modulated Markov chains

We consider a discrete-time Markov chain $(X_n, Y_n)$, where the $X$-component forms a Markov chain itself. Assuming that $(X_n)$ is
ergodic, we formulate the following “naive” conjecture.
Consider an auxiliary Markov chain whose transition probabilities are the averages of transition probabilities of the $Y$-component of the $(X, Y)$-chain, where the averaging is weighted by the stationary distribution of the $X$-component. The conjecture is: if the this chain is
positive recurrent, then so is the $(X, Y )$-chain. We first show that, under appropriate technical assumptions, such a general result indeed holds, and then apply it to two versions of a multi-access wireless model governed by two randomized protocols.

Mark Squillante (IBM T.J. Watson Research Center)
(joint work with Petar Momcilovic)

Linear Stochastic Loss Networks: Analysis and Optimization

We investigate fundamental properties of throughput and cost in linear stochastic loss networks where customers enter at a fixed source node, are relayed from one node to the next node in a fixed sequence of nodes, and exit the network at a fixed destination node. The maximum throughput of the stochastic network with exponential service times is derived and the arrival process that maximizes throughput, given a fixed arrival rate, is established. We first show that it is feasible to achieve an asymptotic throughput scalability of $c/\sqrt{k}$ in a linear $k$-node loss network as the size of the stochastic network grows, where the maximum achievable $c$ in a network with exponential service times is shown to be equal to the service rate multiplied by $1/\sqrt{\pi}$. Then, for general service times, an asymptotically critical loading regime is identified such that the probability of an arbitrary customer being lost is strictly within $(0, 1)$ as the network size increases. This regime delivers throughput comparable to the maximum at a relatively low network cost, and we further establish the asymptotic throughput and network cost under this critical loading. These results support a general framework for the optimization of tradeoffs between throughput and cost in the critical regime under a wide variety of utility functions. Some previous work that motivated and led to our investigation of this particular stochastic network will be discussed.

Leandros Tassiulas (University of Thessaly)

Stochastic models and algorithms for cooperative information delivery

Recent advances in information and communication theory as well as networking suggest novel internet architectures where end-to-end information delivery is facilitated through cooperation at various stages during the information transport process. We consider a stochastic dynamic model of information transport in an architecture where various information streams are mixed at intermediate relay nodes before delivery. The objective is to increase the efficiency of the system through judicious exploitation of transmission overhearing, inherent in radio broadcast. Other user overheard information is used as a key to extract own information in future transmissions. The availability of that information through judicious caching schemes is crucial for the success of the method. Algorithms for selecting mixing combinations to increase transport efficiency are considered. They rely on complete information about the state of overheard information. When state information is not readily available but is gradually revealed through feedback, the mixing algorithm should account both for efficient state probing as well as for effective information recovery. System capacity characterization and efficient algorithms are obtained for the limited state information as well. Connections with information theory and the repercussions of this approach on characterizing and achieving the capacity of the broadcast erasure channel is considered as well.

Peter van de Ven (IBM)

Spatial instability of MaxWeight scheduling algorithms

MaxWeight scheduling has gained enormous popularity as a powerful paradigm for achieving queue stability and maximum throughput in a wide variety of scenarios. The maximum-stability guarantees however rely on the fundamental premise that the system consists of a fixed set of flows with stationary ergodic traffic processes. In the present paper we examine networks where the population of active flows varies over time, as flows eventually end while new flows occasionally start. We show that MaxWeight policies may fail to provide maximum stability due to persistent inefficient spatial reuse. The intuitive explanation is that these policies tend to serve flows with large backlogs, even when the resulting spatial reuse is not particularly efficient, and fail to exploit maximum spatial reuse patterns involving flows with smaller backlogs. These results indicate that instability of MaxWeight scheduling can occur due to spatial inefficiency in networks with fixed transmission rates, which is fundamentally different from the inability to fully exploit time-varying rates shown in prior work. We discuss how the potential instability effects can be countered by spatial traffic aggregation, and describe some of the associated challenges and performance trade-offs.

Elena Yudovina (University of Cambridge)

A (very simple) limit order book model

We consider a very simple model of the dynamics of a limit order book in which nobody knows anything. We show that some economically-sensible characteristics emerge; for example, eventually sufficiently low-priced bid offers (and sufficiently high-priced ask offers) stop being fulfilled. We also see that the system is monotonic with respect to a number of parameters. Finally, we examine the behaviour of the intermediate-priced offers, which would be most interesting in a real-world scenario, and compare to some results on real-world limit order books.

PRESENTATION

Jiheng Zhang (HKUST)

Modeling Webchat Service Center with Many LPS Servers

In addition to regular call centers, many companies start to provide customer support via online chat. The difference is that each agent is allowed to chat with multiple customers simultaneously. The model is essentially a many server queue, with each server being a limited processor sharing (LPS) server. We study the model in the (many-server) heavy traffic regime under fluid scaling. We first identify the fluid limit as the unique solution of an ODE that is determined by certain averaging principle. We also show that the fluid limit converges to an invariant state at time goes to infinity. The invariant state of the fluid limit provides good approximations for the steady state of the stochastic system, based on which we asymptotically solve the joint optimization of staffing (determine the number of servers) and controlling (determine the limit on sharing) for the stochastic system.

PRESENTATION

Practical information

Conference Location
The workshop location is Eurandom,  Den Dolech 2, 5612 AZ Eindhoven, Laplace Building, 1st floor, LG 1.105.

EURANDOM is located on the campus of Eindhoven University of Technology, in the 'Laplace Building' (LG on the map). The university is located at 15 minutes walking distance from Eindhoven railway station (take the exit north side and walk towards the tall building on the right with the sign TU/e).

For all information on how to come to Eindhoven, please check http://www.eurandom.tue.nl/contact.htm

Contact