About | Research | Events | People | Reports | Alumni | Contact | Home
24-25-26 OCTOBER, 2011 Young European Queueing Theorists (YEQT V) Workshop on “Stochastic Networks and Optimization”
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.
Former YEQT workshops This is the fifth workshop in the series of YEQT (Young European Queueing Theorists) workshops. The previous YEQT workshops are YEQT-IV "Optimal Control in Stochastic Systems", November 25-27, 2010YEQT-III "Scheduling and Resource Sharing in Queueing Networks", November 19-21, 2009YEQT-II "Stochastic analysis of modern communication networks", December 1-3, 2008YEQT-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. 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. Or you can consult the web pages of the Tourist Information Eindhoven, Postbus 7, 5600 AA Eindhoven. Monday October 24
Tuesday October 25
Wednesday October 26
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. Ana Busic (INRIA) Perfect sampling of queueing networks
Clément Dombry (Université de Poitiers) 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 traffic on high-speed communication
links. Popular models include infinite 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 infinity
depends crucially of the relative growth of both parameters and several regimes
appear. If the sources connect at a fast rate over time the fluctuations scale
like fractional Brownian motion; if the connection rate is slow the traffic fluctuations
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 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. 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. Masha Frolkova (CWI) 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.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). 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. 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. 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 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. 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 Mark Squillante (IBM T.J. Watson
Research Center) 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. 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.
Conference Location
For all information on how to come to Eindhoven, please check http://www.eurandom.tue.nl/contact.htm
Contact
Sponsored by:
Last updated
17-11-11,
|