logo

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

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


 

April 27-29, 2011

STOCHASTIC ACTIVITY MONTH

Workshop in honour of

FRANK KELLY

    

  REGISTRATION SPEAKERS

PROGRAMME

ABSTRACTS



Organisers

Remco van der Hofstad Eindhoven University of Technology / EURANDOM 
Sem Borst Eindhoven University of Technology
Onno Boxma Eindhoven University of Technology / EURANDOM
   

 

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

Roberto Fernandez University of Utrecht, NL
Richard Gibbens University of Cambridge, UK
Frank Kelly University of Cambridge, UK
Johan van Leeuwaarden TU/e / EURANDOM, NL
Michel Mandjes University of Amsterdam / CWI, NL
Werner Scheinhardt University Twente, NL
Devavrat Shah Massachusetts Institute of Technology, USA
Florian Simatos CWI / EURANDOM, NL
Neil Walton University of Cambridge / University of Amsterdam, NL
Gideon Weiss University of Haifa, IS
Damon Wischik University College London, UK

 


 


Programme

 

Thursday April 28

09.20-09.30

 WELCOME by Remco van der Hofstad

09.30-10:10

 Florian Simatos Heavy Traffic of the Processor Sharing Queue via Excursion Theory

10.10-10.50

 Roberto Fernandez

Perfect simulation of loss networks and statistical mechanical models with exclusions

10.50-11.20

 BREAK

 

11.20-12.00

 Werner Scheinhardt

Fair sharing of capacity in Jackson networks

12.00-12.40

 Michel Mandjes

Birthday surprises

 

Friday April 29

09.30-10.10

 Devavrat Shah  Product-form distributions for network algorithms

10.10-10:50

 Gideon Weiss Stability and Performance of queueing networks with infinite supply of work

10.50-11.20

 BREAK

 

11.20-12.00

 Neil Walton 

From multi-class queueing networks to utility optimization

12.00-12.40

 Damon Wischik

The development of Multipath TCP

12.40-14.00

 LUNCH

 

14:00-14.40

 Johan van Leeuwaarden

Backlog-Based Random Access in Wireless Networks

14.40-15:20

 Richard Gibbens

An investigation of proportionally fair ramp metering

15:20-15:50

 BREAK  

15.50-16.30

 Frank Kelly Notes on electricity networks
16.30-18.00 DRINKS  

 


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
S
tochastics-Theoretical and Applied Research

        

Last updated 18-07-11,
by PK