April 27-29, 2011

STOCHASTIC ACTIVITY MONTH

Workshop in honour of

FRANK KELLY

Organisers

Registration

Registration is compulsory for all participants!

Registration fee is 75 euros, to be paid by all participants (excluding speakers and TU/e personnel)

Please click here to register.

(For the registration form you will be redirected to the website of the Eindhoven University of Technology)

Invited speakers

Programme

Thursday April 28

Friday April 29

Abstracts

Roberto Fernandez

Perfect simulation of loss networks and statistical mechanical models with exclusions

We study invariant measures of fixed routing loss networks via a ``backward-forward'' algorithm effectively leading to a perfect simulation scheme. The algorithm leads to a rather complete theory that can also be applied to point processes in statistics. Furthermore, many important models in (equilibrium) statistical mechanics can be realized as invariant measures of loss-network-like processes. Examples include the contour ensembles of low-temperature Ising models and, more generally, random cluster and other random geometrical models. For these models, our loss-network approach can successfully replace traditional approaches based on cluster or low temperature expansions.

PRESENTATION

Richard Gibbens

An investigation of proportionally fair ramp metering

This talk concerns ramp metering which is one important approach to dealing with congestion on motorways. Congestion occurs when demand exceeds available resources and can significantly reduce the capacity of the motorway network at peak times. Reduced capacity results in additional delays, increased environmental pollution and hinders passenger safety. Congestion is observed to cause low but highly volatile speeds resulting in more uncertain journey times (referred to as flow breakdown or stop-and-go behaviour).
Ramp metering is intended to control the entry of new flow in such a way as to maintain steady flow on the motorway and to avoid the flow breakdown associated with congestion. The rate of entry of flow is set according to the particular ramp metering strategy. Such strategies have been the subject of much attention in the transport literature. One of the key issues is the trade-off between efficiency and fair use of resources. This is a trade-off that has been considered extensively in the modelling and control of communication networks.
This talk adds to recent work on a ramp
metering strategy, proportionally fair metering, inspired by rate control mechanisms developed for the Internet. Specifically, we use simulation results to compare proportionally fair metering with a greedy strategy for a linear network with a series of entry points leading towards a single common destination for all the traffic, such as a radial route towards a city centre. Under our modelling assumptions, the greedy strategy is provably optimal for exogenously determined arrival streams of traffic, but it is unfair, in a certain precise sense, between different entry points and may well have perverse and suboptimal consequences if it influences traffic demand.
We further consider a network with parallel roads where flows of traffic may have route choice according to the levels of queueing at the individual entry points.
(Joint work with Frank Kelly)

PRESENTATION

Frank Kelly

Notes on electricity networks

PRESENTATION

Johan van Leeuwaarden

Backlog-Based Random Access in Wireless Networks

We explore the spatio-temporal congestion dynamics of wireless networks with backlog-based random-access mechanisms. Relatively simple distributed backlog-based access schemes provide the striking capability to match the optimal throughput performance of centralized scheduling algorithms in a wide range of scenarios. 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 access schemes can improve the delay performance, while retaining the maximum stability.
Joint work with Niek Bouman, Sem Borst and Alexandre Proutiere.

PRESENTATION

Michel Mandjes

Birthday surprises

The classical birthday problem is a standard exercise for our students: what is the probability that, among k people, everyone has a different birthday? Things complicate enormously, however, in the situation that the birthdays are not equally spread over the year, and also other ramifications can be thought of. In this presentation I will look at various generalized birthday problems, in various asymptotic regimes.
This talk contains joint work with Sandeep Juneja (TIFR).

PRESENTATION

Werner Scheinhardt

Fair sharing of capacity in Jackson networks

We consider networks of queues in which the independent operators of individual queues may cooperate to reduce the amount of waiting. More speci cally, we focus on Jackson networks in which the total capacity of the servers can be redistributed over all queues in any desired way. If we associate a cost to waiting that is linear in the queue lengths, it is known how the operators should share the available service capacity to minimize the long run total cost.The main question we try to answer is whether or not (the operators of) the individual queues will indeed cooperate in this way, and if so, how they will share the cost in the new situation. The main result is an explicit cost allocation that is beneficial for all operators.

PRESENTATION

Devavrat Shah

Product-form distributions for network algorithms

The "product-form" characterization of the stationary distribution make a queueing network analytically a lot more tractable. This has been the primary source of inspiration in the search for "product-form" characterization. In this talk, I will discuss implications of "product-form" distributions for algorithm design by means of two examples: (i) intra-queue scheduling and
(ii) inter-queue scheduling in a constrained queueing network.

PRESENTATION

Florian Simatos

Heavy Traffic of the Processor Sharing Queue via Excursion Theory

Thanks to a recent result of A. Lambert (AOP 2010), it is possible to realize one busy cycle of the queue length of the Processor-Sharing (PS) queue as the image by some functional of a Levy process. The functional involves the local time process and a random time-change. I will show how to exploit this mapping to derive the heavy traffic limit of the PS queue thanks to excursion theory.

Neil Walton

From multi-class queueing networks to utility optimization

In this talk, we discuss work on multi-class queues and utility optimization. We discuss, implement and combine a number of concepts developed by Frank over the last 35 years: we start with a quasi-reversible queueing network; we apply limit and primal-dual techniques similar to those applied to loss networks and the result is a network state that optimizes network utility. We discuss these approaches which owe greatly to Frank's contributions over the years.

Gideon Weiss

Stability and Performance of queueing networks with infinite supply of work

We generalize the standard multi-class queueing network model by allowing both standard queues and infinite virtual queues which have infinite supply of work. We pose the general problem of finding networks and policies which allow some of the nodes of the network to work with full utilization, and keep all the standard queues stable. Towards this end we show that re-entrant lines, systems of two servers with two re-entrant lines and rings of servers can be stabilized with priority policies under certain parameter restrictions. We further establish simple diffusion limits for the departure and work allocation processes. A third contribution of the paper is with respect to properties of the Markov processes associated with the models. Towards this end, we prove some technical results regarding pettiteness and smallness of compact sets in specific cases. The analysis throughout the paper, depends on model and policy and illustrates the difficulty in solving the general problem.

PRESENTATION

Damon Wischik

The development of Multipath TCP

In 2005, Kelly and Voice proposed and analysed a model for multipath congestion control in the Internet. Since 2007, several of us at UCL have been working to translate this idea into implementation, and an IETF working group will soon sign it off as an Experimental Standard. I will describe the repositionings and compromises we made en route to deployment, and discuss why the networking systems community has been slow to adopt theoretical work on congestion control.

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 'Laplacegebouw' building' (LG on the map). The university is located at 10 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
For more information please contact Mrs. Patty Koorn,
Workshop officer of  EURANDOM

Sponsored by:

STAR
Stochastics-Theoretical and Applied Research

Last updated 18-07-11,
by PK