November 11-12-13, 2015

Workshop on

 YEQT IX

 "Scaling limits in queueing networks"

SUMMARY

This will be the ninth edition of the Young European Queueing Theorists  (YEQT) workshop. The topic of this year’s workshop is about “Scaling limits of queueing networks”. We have selected four topics in queueing theory around which we intend to develop a clustered program:

1. Asymptotic analysis of many-server queues
2. Applications of fluid and diffusion limits in queueing networks
3. Scaling of Markov processes
4. Diffusion control problems
 

Former YEQT workshops

ORGANISERS *

* Scientific advisor: Onno Boxma (TU Eindhoven)

LIST OF SPEAKERS

KEYNOTE:

TUTORIAL SPEAKERS

INVITED SPEAKERS

PROGRAMME 

tentative

WEDNESDAY NOVEMBER 11

THURSDAY NOVEMBER 12

FRIDAY NOVEMBER 13

ABSTRACTS

Gianmarco Bet

Critical queues exhibiting the depletion-of-points effect

We consider a model for a queue in which only a finite (but large) number of customers can potentially join. We show that, when critical (for an appropriate definition of criticality) and suitably rescaled, the queue length converges to a Brownian motion with parabolic drift. This is closely related to the so-called depletion-of-points effect that is typical of the exploration process of random graphs. We make this connection explicit and present a more general result in which the Brownian motion is replaced by a stable motion.

PRESENTATION

Cédric Bourdais

Reservation in vehicle-sharing systems

We introduce a stochastic network as a simple homogeneous model for vehicle sharing systems with reservation. Large systems are studied via the mean field limit. This limit is a dynamical system solution of an ODE. We prove that its equilibrium point is unique , characterized as a tandem of two queues. This characterization allows to investigate the fleet size which maximizes the average number of satisfied users (those who can find both a car and a parking spot at the stations of their choice), when the system is large and in stationary regime. The arguments are the probabilistic interpretation of the limit, real analysis and combinatorics.
(joint work with Chritine Fricker)

PRESENTATION

Asaf Cohen

A Multiclass Queueing Model in the Moderate-Deviation Heavy-Traffic Regime

We consider a multiclass single-server queueing control problem in the moderate-deviation heavy-traffic regime with a discounted risk-sensitive cost. In the scaling limit, an optimal control problem associated with the model is shown to be governed by a differential (deterministic) game that can be explicitly solved and that admits an optimal stationary feedback policy. We also present a stationary asymptotic optimal policy that satisfies a state space collapse property.
(joint work with Rami Atar)

PRESENTATION (only available by email, please send request to koorn@eurandom.tue.nl)

Sarah Eugene

Stochastic Modelling of Polymerisation of Proteins

To investigate intrinsic or extrinsic variability among amyloid formation experiments, we propose and study a new stochastic model, which is able to capture the main mechanisms of brillization while
keeping a relative simplicity, which allows us for quantitative analysis. At rst order, a law of large numbers shows its convergence towards the deterministic law of mass action, whereas at second order we
prove a central limit theorem, which provides a stochastic di erential equation that we solve explicitely. We then compared our analytical results with experimental data obtained on 2-m formation, what leads
us to modify the original model by the addition of a conformation step. This new model is able to explain intrinsic variability in amyloid formation not only for in vivo but also for in vitro experiments, and paves
the way for a new and e cient methodology.

PRESENTATION

David Goldberg

Beating the curse of dimensionality in inventory problems with lead times
(or how a "random walk / queueing perspective" helped make progress on a fundamental problem in inventory control)

Inventory models, which are core to the study of Operations Research and Operations Management, share many features with queueing models and random walks.
In this talk, I will discuss how a ``random walk / queueing perspective" was very helpful in making fundamental progress on several long-standing algorithmic problems in this area.

In particular, many classical inventory models become notoriously challenging to optimize in the presence of positive lead times (i.e. delay between ordering more units to sell and receiving those units), since the state-space blows up and dynamic programming techniques become intractable. This includes, for example, lost sales models with positive lead times, and dual-sourcing models with positive lead time gap between the two suppliers. In this talk, we will present a new algorithmic approach to such problems, which shows that as the lead time grows large, simple policies become asymptotically optimal. These results are quite surprising, as this setting had remained an open algorithmic challenge for over forty years. In particular, we will show that a simple constant-order policy is asymptotically optimal for lost sales models with large lead times, and provide explicit bounds on the optimality gap which demonstrate good performance even for small-to-moderate lead times. We will also show that the so-called Tailored-Base Surge heuristic for dual-sourcing problems is asymptotically optimal as the lead time gap between the two sources grows large. In both cases, our results provide a new algorithmic approach to these problems, as well as a solid theoretical foundation for the good performance of these algorithms observed numerically by previous researchers. Our approach combines ideas from the theory of random walks and queues, convex analysis, and inventory control.

Varun Gupta

Designing load balancing and admission control policies: lessons from NDS regime

We will consider two problems in control of queueing systems: (1) load balancing policies for a multi-server system with Processor Sharing servers, and (2) admission control into a server with state-dependent service rates. For the first, our goal is to study the performance of simple heuristics such as Shortest Queue, and the effect of service distribution on the performance. For the second system, our goal is to design admission control policies tailored specifically to the service distribution. We find that the NDS (non-degenerate slowdown) scaling regime is surprisingly accurate at predicting the performance for both, and provides insights which are robust to the scale and traffic intensity of the system.

PRESENTATION

Harsha Honnappa

Approximation Techniques for Transitory Stochastic Processes

We start by considering a queueing system where a finite number of customers apply for service, and service times are generally distributed and service is first-come-first-served. We model the arrival epochs as independent random variables drawn from a common ‘scattering’ distribution. In prior work, showed that the diffusion approximation to the work load process is a diffusion process reflected through what has come to be known as the ‘directional derivative reflection map’. In general, it seems impossible to compute the transient expectations associated with this diffusion. Here, we first show that it is possible to obtain a much simpler approximation under a first-order differentiability condition on the distribution function. Second, once a diffusion approximation has been found, we show how to compute approximations to the transient distribution of the diffusion under two conditions: a) when the infinitesimal parameters are slowly time-varying (or equivalently when steady state is a ‘reasonable’ approximation) we obtain an asymptotic expansion in terms of the point-wise stationary approximation, and b) when the time interval of study [0,t] is so small that steady state cannot be reached, we obtain Taylor series expansions in terms of the initial transient of a regulated Brownian motion with parameters ‘frozen’ to those at time zero. We conclude by discussing the implications of these approximations on on optimal control of these processes.
(joint work with Peter W. Glynn)

Tom Kurtz

Approaches to large system limits

A variety of methods for proving large system limits will be illustrated with models drawn form queueing and related contexts.
Methods considered will exploit time-change equations, exchangeable particle systems, and martingale problems.
 

Britt Mathijsen

Workload shifting in critical many-server systems

To release pressure from systems during periods of overload, we introduce the concept of Delayed Workload Shifting (DWS). Our basic model is an M/M/s/n queue with the additional feature that customers meeting a full system upon arrival are not admitted directly, but reattempt getting access after a random amount of time. By scaling the number of servers s and the threshold level n according to a two-fold QED regime, we show that the system with DWS can be approximated in terms of the QED limits of the system without DWS, but with corrected parameters that are obtained as solutions to fixed point equations. DWS leads to substantial performance gains in the QED regime. The DWS approximations serve as input for algorithms that achieve predefined performance targets in both stationary and time-varying environments. Similar algorithms can be designed for more advanced queueing system, including systems with returning customers or tandem networks.
(joint work with Johan van Leeuwaarden and Fiona Sloothaak)

PRESENTATION

Alexandre Proutière

Load Balancing in Heterogeneous Systems

We consider the problem of load balancing in heterogeneous parallel processor sharing server systems, where the service rate achieved by a user at a server depends on both the user and the server. Such heterogeneity typically arises in wireless networks (e.g., servers may represent frequency bands, and the service rate of a user varies across bands). We investigate the performance of these systems under centralized and distributed control. In centralized systems, we focus on scenarios where the service rates of users at the various servers are unknown, and must be learnt in an online manner. The design of optimal load balancing strategies may then be casted as an instance of combinatorial bandits problems. We present fundamental performance limits for such problems, and propose algorithms approaching these limits. In distributed systems, users initially attach to an arbitrary server, and at random instants of time, may probe the load at a new server and migrate there to improve their service rate. We propose a natural distributed migration strategy, and analyze its convergence rate towards the Proportionally Fair allocation. We further establish its throughput optimality when users randomly arrive in the system and leave upon service completion.

PRESENTATION

Kavita Ramanan

Keynote: Stability of Stochastic Networks via Asymptotic Coupling

An important question in stochastic networks is that of stability.  A common approach that is used to prove uniqueness of stationary distributions is to establish positive Harris recurrence of the state process.  We will describe situations when this approach does not work, or seems particular challenging and instead, illustrate via two examples how asymptotic (equivalent) couplings may provide a more convenient alternative.

Scaling Limits of Randomized Load Balancing Networks

We introduce a general framework of interacting measure-valued representations for the study randomized load balancing networks. For a particular example, we show how their scaling limits can be used to provide insight into both the transient and steady state performance measures of the network.
(joint work with  Mohammadreza Aghajani)

Marty Reiman

Asymptotically Optimal Control of (Some) Stochastic Service Systems

Many control problems that arise in stochastic service systems (including both queueing and inventory systems) are extremely difficult to solve exactly. This has given rise to a great deal of research effort involving asymptotics, such as heavy traffic in the context of queueing systems, with the goal of providing good controls. A standard criterion for goodness in much of this work is asymptotic optimality.
Asymptotically optimal controls for stochastic service systems have also been investigated in other large parameter regimes, such as the arrival rate of demand into the system growing large. In this tutorial we provide a broad but idiosyncratic outline of this work and introduce some of the key ideas that arise in solving such problems, focusing on a small number of examples from both queueing and inventory.

Philippe Robert

On the dynamics of random neuronal networks

We study the mean-field limit and stationary distributions of a pulse-coupled network modeling the dynamics of a large neuronal assemblies. Our model takes into account explicitly the intrinsic randomness of firing times, contrasting with the classical integrate-and-fire model. The ergodicity properties of the Markov process associated to finite networks are investigated. We derive the limit in distribution of the sample path of the state of a neuron of the network  when its size gets large. The invariant distributions of this limiting  stochastic process are analyzed as well as their stability properties. We show that the system undergoes transitions as a function of the averaged connectivity parameter, and can support trivial states (where the network activity dies out, which is also the unique stationary state of finite networks in some cases) and self-sustained activity when connectivity level is sufficiently large, both being possibly stable.
(joint work with Jonathan Touboul)

PRESENTATION

Mark Shifrin

Asymptotically optimal policies for the multi-class finite queue

We consider a multiclass G/G/1 queue where tasks of various classes are served by single server with service sharing (scheduling) ability. Two possible buffer configurations are addressed - the case where tasks of different classes occupy dedicated buffers and the case where all tasks are processed from a single shared buffer. There is task admission and server scheduling control which aim to minimize the cost which consists of holding and rejection components. We construct policies that are asymptotically optimal in the heavy traffic limit. For both cases, the policies stem from solution to Harrison-Taksar (HT) free boundary problem and are expressed by a single free boundary point. The cµ priority rule is used by the policy in the case of dedicated buffers, but in a way that is novel, and, in particular, different than that used in
problems with infinite buffers. As for the case of a shared buffer, the HT problem solution follows a specific triangular form. In both cases the queuelength control policies are different from the known cµ priority rule and have a novel structure. We exemplify that the probabilistic methods we exploit can be successfully applied to solving scheduling and admission problems in cloud  computing.

PRESENTATION

Wen Sun

The Time Scales For A Stochastic Network With Failures

A transient Markov process with d+ 1 nodes and an absorbing state is studied to investigate the qualitative behavior of a large scale storage network of non reliable file servers. Each file has at most d copies and each copy of a file is lost at some rate. The network can duplicate files with at least 1 copy and less than d copies. In this talk it is assumed that the duplication capacity of the system is allocated to the files with the least number of copies. A file with 0 copies is lost for good. When the size of system, i.e. the number of servers, goes to infinity, it is shown that there is a critical value for the mean number of files per server such that below this quantity, the system is stable, it stays away from absorbing state –all files lost. In this case, a quasi-stationary state is reached where most of files have the maximum number of copies. Above this value, the network looses quickly a significant fraction of files until some equilibrium is reached. By a convenient scaling of the time scale, the evolution of the network towards the absorbing state can be described via a stochastic averaging principle. It is shown that the fluctuations conveniently renormalized converge to an Ornstein-Uhlenbeck process.
(joint work with Mathieu Feuillet and Philippe Robert)

PRESENTATION

Mirco Tribastone

Fluid limits for formal models of software performance

Formal languages for the specification and analysis of software performance models are attractive because they can express several real-world communication and coordination paradigms such as fork/join synchronization, asynchronous interaction, and layered service behavior. Being often based on continuous-time Markov chains, unfortunately they are prone to the infamous problem of state-space explosion, which severely hinders their practical applicability to large-scale systems. This talk will discuss the key ideas on automatically deriving (and proving the convergence of) fluid limits for such languages, with applications to the approximation of layered queuing networks based on ordinary differential equations (ODEs). We will also present ongoing work on taming the complexity of certain models where even the ODE limits are not compact enough for tractable numerical analysis.

PRESENTATION

Hannah Van den Bossche

Public vs. personal transportation: a rational choice based on queueing theory

One’s choice between public and personal transport for the daily commute depends on various factors including convenience, comfort, monetary cost and travel times. Abstracting convenience, comfort and monetary cost in a single fixed cost, we focus on the tradeoff between travel times and this cost, assuming fixed travel times for public transport. Such a tradeoff obviously depends on the decisions of other commuters, as travel times for personal transport depend on traffic density. This dependency is very well captured by the so-called fundamental diagram of traffic flow. The diagram relates traffic flux (and therefore also the travel times) to traffic density, an increased density leading to increased travel times.
We propose a simple Markovian queueing model to study congestion at a macroscopic scale. Noting that travel times are hardly influenced by the presence of traffic when there is limited traffic, and that travel times are dominated by the limited capacity of the road when there is congestion, we adopt a Markovian level-dependent queueing system, service rates being sub-linear in terms of the queue content. For this queueing system we first study the stationary waiting times assuming fixed arrival rates. As the arrival rate is typically not stationary during rush hour, we then study the transient waiting times in the fluid limit. Our fluid approximation is motivated by the large amounts of road users during rush hour. Based on the fluid approximation, we determine the fraction of road users choosing for public transport at any time by game theoretic arguments. Finally, we discuss several extensions of the macroscopic model. First, the implicit assumption of exponential travel times is relaxed to phase-type distributed travel times. Secondly, we introduce a notion of local traffic density, say at the level of a neighbourhood. We then obtain a traffic model at a mesoscopic scale: the travel times no longer depend on the global density (or queue content) but on the local density.

PRESENTATION

Amadine Véber

Resource sharing with logarithmic weights

We shall consider a communication network in which J clients share a server. If client j has x jobs waiting, it receives a fraction of the capacity of the server which is proportional to ln(1+x). In contrast with the case of a linear allocation of resources (i.e., proportional to x), when the total number of jobs tends to infinity several timescales interact in a fine way to shape the asymptotic behaviour of the system.
In particular, the numbers of jobs corresponding to each client may then evolve on different temporal scales and have very different orders of magnitude.
(joint work with Philippe Robert)

PRESENTATION

Dongyuan Zhan

Compensation and Staffing to Trade Off Speed and Quality in Large Service Systems

Most common queueing models used for service system design assume the servers work at fixed (possibly heterogeneous) rates. However, real-life service systems are staffed by people, and people may change their service speed in response to their compensation incentives. The delicacy is that the resulting employee service rate affects the staffing, but also the staffing affects the resulting employee service rate. Our objective in this paper is to find a joint compensation and staffing policy that induces optimal service system performance.
We do this under the assumption that there is a trade-off between service speed and quality, and employees are paid based on both. The employees each selfishly choose their own service speed in order to maximize their own expected utility, which can have both a monetary and a non-monetary component. We characterize the symmetric equilibrium service speed in large systems under a simple linear compensation and staffing policy. We show that there is a limiting first best policy within that class. The important insight is that in the large system limit the problem decouples into one where the system manager first jointly determines the staffing and service speed, and second uses the compensation to achieve that desired service speed. We further show the conditions under which a critically loaded, efficiency-driven, quality-driven, or mixed regime emerges under a first-best policy.
(joint work with Amy R. Ward)

PRESENTATION

 

---

---

 

 

PRACTICAL INFORMATION

●      Venue

Eurandom, Mathematics and Computer Science Dept, TU Eindhoven,

De Groene Loper 5, 5612 AZ  EINDHOVEN,  The Netherlands

Eurandom is located on the campus of Eindhoven University of Technology, in the Metaforum building (4th floor) (about the building). The university is located at 10 minutes walking distance from Eindhoven main railway station (take the exit north side and walk towards the tall building on the right with the sign TU/e).
Accessibility TU/e campus and map.

 

●      Registration

CLOSED !!

Unfortunately we can not except anymore registrations. We are at maximum capacity.

We will ask all speakers if we can put their presentations online after the event, so if you could not be there in person, you can at least read all the material.

 

 

 

●      Accommodation / Funding

Hotel will be booked for all invited speakers. Please give your arrival and departure date on the registration form.

Other participants have to make their own arrangements.

For hotels around the university, please see: Hotels (please note: prices listed are "best available"). 

More hotel options can be found on the webpages of the Tourist Information Eindhoven, Postbus 7, 5600 AA Eindhoven.

 

●      Travel

For those arriving by plane, there is a convenient direct train connection between Amsterdam Schiphol airport and Eindhoven. This trip will take about one and a half hour. For more detailed information, please consult the NS travel information pages or see Eurandom web page location.

Many low cost carriers also fly to Eindhoven Airport. There is a bus connection to the Eindhoven central railway station from the airport. (Bus route number 401) For details on departure times consult http://www.9292ov.nl

The University  can be reached easily by car from the highways leading to Eindhoven (for details, see our route descriptions or consult our map with highway connections.

 

●      Conference facilities : Conference room, Metaforum Building  MF11&12

The meeting-room is equipped with a data projector, an overhead projector, a projection screen and a blackboard. Please note that speakers and participants making an oral presentation are kindly requested to bring their own laptop or their presentation on a memory stick.

 

●      Conference Secretariat

Upon arrival, participants should register with the workshop officer, and collect their name badges. The workshop officer will be present for the duration of the conference, taking care of the administrative aspects and the day-to-day running of the conference: registration, issuing certificates and receipts, etc.

 

●      Cancellation

Should you need to cancel your participation, please contact Patty Koorn, the Workshop Officer.

 

●      Contact

Mrs. Patty Koorn, Workshop Officer, Eurandom/TU Eindhoven, koorn@eurandom.tue.nl

 

SPONSORS

The organisers acknowledge the financial support/sponsorship of:

 

 

 

 

 

 

---

 

 

        

Last updated 18-11-15,
by PK

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