ICMS

Workshop on Stochastic Processes in Communication Networks for Young Researchers

Jun 07, 2010 - Jun 11, 2010

15 South College Street, Edinburgh EH8 9AA

Organisers

Name	Institution
Denisov, Denis	Cardiff University
Lelarge, Marc	INRIA/ENS
Zwart, Bert	CWI

Programme Committee
Jose Blanchet (Columbia University)
Sergey Foss (Heriot-Watt and Institute of Mathematics, Novosibirsk)
Ramesh Johari (Stanford University)
Olivier Lévêque (EPFL)
Nelly Litvak (University of Twente)
Alexandre Proutiere (Microsoft Research)
Devavrat Shah (MIT)
Adam Wierman (Caltech)
Damon Wischik (UCL)
 

This satellite workshop is part of a larger program on Stochastic Processes in Communications Sciences at the Isaac Newton Institute at Cambridge University that will be running from January through the beginning of July of 2010, and will be concurrent with an additional thematic program on Stochastic Partial Differential Equations.

Tutorial Speakers
Bartek Blaszczyszyn (INRIA-ENS)
Philippe Robert (INRIA)
Remco van der Hofstad (Eindhoven University of Technology)
Martin Wainwright (UC Berkeley)
Damon Wischik (University College London)

Keynote Speakers
Sem Borst (Bell Laboratories, Alcatel-Lucent and CWI)
Peter Glynn (Stanford University)
Thomas Kurtz (University of Wisconsin - Madison)
Andrea Montanari (Stanford University)
Alexandre Proutiere (Microsoft Research)
Amin Saberi (Stanford University)
Leandros Tassiulas (University of Thessaly)

Invited Speakers
Jose Blanchet (Columbia University)
Ana Busic (INRIA-ENS)
Yogeshwaran Dhandapani (INRIA-ENS)
Ton Dieker (Georgia Institute of Technology)
David Goldberg (MIT)
Jevgenijs Ivanovs (EURANDOM)
Nelly Litvak (University of Twente)
Petar Momcilovic (University of Michigan)
Seva Shneer (EURANDOM)
Florian Simatos (CWI)
Vijay Subramanian (Hamilton Institute)
Neil Walton (University of Cambridge)
Jiheng Zhang (Hong Kong University of Science and Technology)

Arrangements

Attendance
If you would like to register an interest in attending this workshop please complete the application form.
Invited speakers were sent a separate invitation to complete a different form via e-mail in April 2010.

Registration fee
There will be a modest registration fee of 50.00 GBP to attend the workshop and limited space for poster presentation. To pay this registration fee in advance of the workshop please download the payment form and complete it. Please fax the completed form back to ICMS on 00 44 131 651 4381 if abroad or 0131 651 4381 if within the UK.

There is no registration fee for members of EURO-NF consortium. Details of the EURO-NF community can be found here.

NSF Funding
Limited travel and subsistence funds are available from the NSF and U.S. AFOSR grants to support the participation of researchers (of any nationality) affiliated to a U.S. institution. If you wish to be considered for an NSF grant, please complete the attached form (http://www.newton.ac.uk/cgi/nsfsupport)

Applicants for support should include a brief letter indicating their mathematical interests and reasons for wishing to participate in the programme, their first and second choices for dates of stay, and their other funding sources (if any). They should also send a CV and, in the case of graduate students, a letter of recommendation from the dissertation advisor.

Travel
Information about international travel to the UK and Edinburgh is available here.  If you are travelling from overseas you may require an entry visa. A European visa does not guarantee entry to the UK. Please use this link to the UK Visas site to find out if you need a visa and if so how to apply for one.

Please note that it is your responsibility to have adequate travel insurance to cover medical and other emergencies that may occur on your trip.

You may find this city centre map useful. It shows the workshop venue and other city centre landmarks.

A taxi directly from the airport will cost approximately 15.00 to 20.00 GBP to the city centre for a one-way journey. There is also a bus service from the airport to the city centre.

Within the city, Lothian buses charge £1.20 for a single, £3.00 for a day ticket. Please note that the exact fare is required and no change is given.

If travelling by train, please note that Edinburgh has two railway stations - Waverley Railway Station being the main station and closest to the workshop venue at 15 South College Street. If you alight at Edinburgh Waverley, the workshop venue is an easy 10 minute walk over North and South Bridge map. The second railway station is called Haymarket and is at the West End of the city centre.

Accommodation
You are asked to book your own accommodation.

A list of various hotels and guest houses and prices is available here . Sections 4 is particularly relevant.  You may also find the following suggestions helpful:

Jurys Inn Edinburgh, 43 Jeffrey Street, Edinburgh EH1 1DH (close to workshop venue and city centre)
+44 (0)131 200 3300 - www.jurys-edinburgh-hotels.com 

The Kenneth Mackenzie Suite, 7 Richmond Place, Edinburgh, EH8 9ST (University accommodation)
+44 (0)131 651 2007 - http://www.edinburghfirst.com/accommodation/kennethmackenzie.asp

Edinburgh First (University Accommodation at Pollock Halls)
+44 (0)131 651 2007 - http://www.edinburghfirst.co.uk/for-accommodation/pollock-halls

Hotel Ibis, 6 Hunter Square, Off Royal Mile, Edinburgh EH1 1QW
+44 (0)131 240 7000 - www.hotels-europe.com/ibishotels/england/edinburgh.htm

Smiths Guest House, 77 Mayfield Road, Edinburgh EH9 3AA
+44 (0)131 667 2524 - www.smithsgh.com - mail@smithsgh.com

Scottish Youth Hostel Association
0870 155 3255 (UK only) - Scottish Youth Hostel Association

Edinburgh Tourist Board - www.edinburgh.org/accom

Catering
Morning and afternoon tea/coffee/biscuits will be provided on each day of the workshop. 

On Monday 7 June a buffet lunch will be served in the Chapterhouse, within the workshop venue at 15 South College Street.

There will be a workshop dinner on Tuesday 8 June at 19.30 in The Magnum Restaurant, 1 Albany Street, Edinburgh, EH1 3PY

Financial Arrangements
Financial arrangements for invited speakers will be laid out in their invitation email and again in the email to be sent shortly before the workshop.

For all other participants, if we agree to pay some of your travel or accomodation costs, then you will be informed by email in the middle of May.

Where it is due, reimbursement will take place after the workshop and will involve payment directly into your bank account. At Registration you will be given an expenses claim form from the Isaac Newton Institute and this should be returned to INI, with original receipts.

 

Programme

Monday 7 June

08.30-09.45	Registration, Ground Floor, 15 South College Street
09.45-10.30	Welcome & introduction Martin Wainwright (UC Berkeley) Graphical models and message-passing algorithms: Some introductory lectures pdf of presentation
10.30-11.15	Philippe Robert (INRIA) Probabilistics methods in the analysis of stochastic networks pdf of presentation
11.15-11.45	Coffee
11.45-12.30	Damon Wischik (University College London) Queueing theory for switched networks pdf of presentation
12.30-14.00	Lunch - Buffet lunch served in the Chapterhouse, 15 South College Street
14.00-14.30	David Goldberg (MIT) Performance Bounds for Large Scale Queueing Systems pdf of presentation
14.30-15.00	Petar Momcilovic (University of Michigan) Linear loss networks pdf of presentation
15.00-15.30	Florian Simatos (CWI) Interacting branching processes and linear file-sharing networks pdf of presentation
15.30-16.00	Coffee
16.00-16.45	Thomas Kurtz (University of Wisconsin - Madison) Counting processes, stochastic equations, and asymptotics for stochastic models pdf of presentation
16.45-17.30	Andrea Montanari (Stanford University) Message passing algorithms, random convex functions, and the risk of the LASSO pdf of presentation

 

Tuesday 8 June

09.30-10.15	Martin Wainwright (UC Berkeley) Graphical models and message-passing algorithms: Some introductory lectures
10.15-11.00	Bartek Blaszczyszyn (INRIA-ENS) Stochastic geometry and wireless networks pdf of presentation
11.00-11.30	Coffee
11.30-12.15	Philippe Robert (INRIA) Probabilistics methods in the analysis of stochastic networks pdf of presentation
12.15-14.00	Lunch
14.00-14.30	Yogeshwaran Dhandapani (INRIA-ENS) Percolation and directionally convex ordering of point processes pdf of presentation
14.30-15.00	Vijay Subramanian (Hamilton Institute) Large deviations of max-weight scheduling policies on convex rate regions pdf of presentation
15.00-15.30	Nelly Litvak (University of Twente) A Scaling Analysis of a Cat and Mouse Markov Chain pdf of presentation
15.30-16.00	Coffee
16.00-16.45	Leandros Tassiulas (University of Thessaly) Stochastic models and algorithms for cooperative information delivery
16.45-17.30	Amin Saberi (Stanford University) Game dynamics, equilibrium selection and network structure pdf of presentation
19.30	Workshop Dinner at The Magnum Restaurant, 1 Albany Street, Edinburgh

 

Wednesday 9 June

09.30-10.15	Damon Wischik (University College London) Queueing theory for switched networks pdf of presentation
10.15-11.00	Remco van der Hofstad (Eindhoven University of Technology) Processes on random graphs: routing and attack vulnerability
11.00-11.30	Coffee
11.30-12.15	Martin Wainwright, UC Berkeley Graphical models and message-passing algorithms: Some introductory lectures
12.15-14.00	Lunch and poster session
14.00	Free afternoon

 

Thursday 10 June

09.30-10.15	Remco van der Hofstad (Eindhoven University of Technology) Processes on random graphs: routing and attack vulnerability
10.15-11.00	Bartek Blaszczyszyn (INRIA-ENS) Stochastic geometry and wireless networks pdf of presentation
11.00-11.30	Coffee
11.30-12.15	Philippe Robert (INRIA) Probabilistics methods in the analysis of stochastic networks pdf of presentation
12.15-14.00	Lunch
14.00-14.30	Ton Dieker (Georgia Institute of Technology) Capacity allocation in feedforward queueing networks pdf of presentation
14.30-15.00	Jevgenijs Ivanovs (EURANDOM) Markov-modulated Brownian motion with two reflecting barriers pdf of presentation
15.00-15.30	Jiheng Zhang (Hong Kong University of Science and Technology) Fluid models of many-server queues with abandonment pdf of presentation
15.30-16.00	Coffee
16.00-16.45	Alexandre Proutiere (Microsoft Research) Load balancing via Random Local Search in closed and open systems pdf of presentation
16.45-17.30	Sem Borst (Bell Laboratories, Alcatel-Lucent & Eindhoven University of Technology) Wireless Random-Access Networks: Fairness, Performance and Stability pdf of presentation

 

Friday 11 June

09.30-10.15	Remco van der Hofstad (Eindhoven University of Technology) Processes on random graphs: routing and attack vulnerability
10.15-11.00	Bartek Blaszczyszyn (INRIA-ENS) Stochastic geometry and wireless networks pdf of presentation
11.00-11.30	Coffee
11.30-12.15	Philippe Robert (INRIA) Probabilistics methods in the analysis of stochastic networks pdf of presentation
12.15-14.00	Lunch
14.00-14.30	Seva Shneer (EPFL) Comparing throughputs and fairness in slotted and non-slotted CSMA pdf of presentation
14.30-15.00	Ana Busic (INRIA-ENS) Stability of the bipartite matching model pdf of presentation
15.00-15.30	Neil Walton (University of Cambridge) Utility optimization in congested queueing networks pdf of presentation
15.30-16.00	Coffee
16.00-16.45	Peter Glynn (Stanford University) Lyapunov functions and the analysis of queues pdf of presentation
16.45-17.30	Jose Blanchet (Columbia University) Importance sampling for heavy-tailed systems pdf of presentation

 

 

Presentations:

Presentation Details
Blanchet, Jose
Importance Sampling for Heavy-tailed Systems
View Abstract Hide Abstract
A standard technique for designing provably efficient (bounded coefficient of variation) state-dependent importance sampling estimators for large deviations problems with heavy tails proceeds as follows: a) propose a good parametric family of importance sampling distributions (good in the sense of at least qualitatively approximating the conditional distribution of the underlying process given the event of interest); b) construct a parametric family of proposed Lyapunov functions to control the second moment of the underlying estimator generated by the family chosen in a), typically this step involves fluid heuristics, which are common in the setting of heavy-tailed large deviations; c) rigorously verify the Lyapunov criterion by appropriately selecting the parameters in both the family introduced in a) and the candidate function proposed in b). Appropriate parametric families (those for which one can rigorously verify strong efficiency) have so far been derived for regularly varying distributions only. Also, because of the heavy-tailed assumptions the expected termination time of the algorithms sometimes is infinite. In this talk, we develop parametric families that ensure strong efficiency beyond regular variation. In addition, we show how our techniques can be used to control the termination time of the algorithms without sacrificing efficiency.
Blaszczyszyn, Bartek
Stochastic geometry and wireless networks
View Abstract Hide Abstract
The aim of this tutorial is to show how stochastic geometry can be used in a more or less systematic way to analyze some key phenomena that arise in the context of wireless ad-hoc networks, namely medium access and routing. We limit ourselves to simple (yet not simplistic) model of Poisson mobile ad-hoc network (MANET) with slotted Aloha and concentrate on the so-called outage scenario, where a successful transmission requires a signal-to-Interference-and-Noise (SINR) larger than some threshold. We also assume Rayleigh fading. Starting from a simple explicit expression for the successful transmission probability we will show first how various network performance metrics related to the throughput can be evaluated in the scenario where all the receivers are located within some fixed distance to the receiver. Then we make a first step towards a joint analysis of MAC and routing considering a few more complex scenarios for receiver location, all motivated by the fact that real routing mechanisms typically select receivers in the vicinity of the respective emitters. The analysis of these more adequate models reveals interesting phenomena related to the local delay in MANETs, namely the number of times slots required for nodes to transmit a packet to their prescribed next-hop receivers. We will show that in most cases, each node has a finite-mean geometric random delay and thus a positive next hop throughput, however, the spatial (or large population) averaging of these individual finite mean-delays leads to infinite values in several practical cases. In some cases it exhibits a phase transition, where the spatial average is finite when certain model parameters are below a threshold and infinite above. Finally, we consider a fully cross-layer MAC/routing model, where there is no predefined route and where the routing scheme tries to take advantage of the variability of MAC and fading to decide on the next relay for each packet at each time slot. An important negative consequence of the previous observation on local delays is that the mean end-to-end delay of a packet delivery in Poisson MANET scales super-linearly with the distance between source and destination, or, in other words, the asymptotic velocity of a typical packet is null, even if this packet is considered as a priority packet and experiences no queuing in the nodes. The main positive result, formulated and proved using the framework of the first passage percolation on a SINR space-time graph, states that when adding a periodic node infrastructure of arbitrarily small intensity to the Poisson MANET makes the end-to-end delay scale linearly with the delivery distance. The tutorial is based on the book "Stochastic Geometry and Wireless Networks, Volume II – Applications" by F. Baccelli and B. Blaszczyszyn, Foundations and Trends in Networking, NoW Publishers, 2009. It is also available at http://hal.inria.fr/inria-00403040
Borst, Sem
Wireless Random-Access Networks: Fairness, Performance and Stability
View Abstract Hide Abstract
Random-access algorithms such as the Carrier-Sense Multiple-Access (CSMA) protocol provide a popular mechanism for distributed medium access control in emerging large-scale wireless networks. In the CSMA protocol, each node attempts to access the medium after a certain back-off time, but nodes that sense activity of interfering nodes freeze their back-off timer until the medium is sensed idle. Under suitable assumptions, the joint activity state of the various nodes may be modelled as a reversible Markov process with a convenient product-form stationary distribution. These models yield relatively simple estimates for the long-term throughputs and turn out to be remarkably accurate. The above-mentioned models tend to assume exponential back-off periods and transmission durations, and consider a scenario where buffers are saturated, and nodes always have packets pending for transmission. In reality, back-off periods and transmission times are non-exponential, while the buffers may occasionally be empty as packets are randomly generated and transmitted over time, and nodes may refrain from competition for the medium during these periods. Motivated by these observations, we examine two extensions: (i) general distributions of transmission times and back-off periods; (ii) queueing dynamics in scenarios with packet arrivals. We show that the the stationary distribution of the joint activity state is not only insensitive with respect to the distribution of the transmission times, but also that of the back-off periods, regardless of whether back-offs are frozen or not during activity of neighbouring nodes. In addition, we explicitly identify the stability conditions in a few relevant scenarios, and illustrate the difficulty arising in other cases. Also, the stationary distribution may not reflect the performance over shorter time intervals, and in particular, long-term fairness may hide severe starvation effects over shorter time periods due to meta-stability. We will discuss how the short-term throughput performance is affected by the size and structure of the network topology. Note: based on joint work with Johan van Leeuwaarden (TU/e), Alexandre Proutiere, (Microsoft), Patrick Thiran (EPFL) and Peter van de Ven (TU/e)
Busic, Ana
Stability of the bipartite matching model
View Abstract Hide Abstract
We consider the bipartite matching model of customers and servers introduced by Caldentey, Kaplan, and Weiss (Adv. Appl. Probab., 2009). Customers and servers play symmetrical roles. There is a finite set C resp. S, of customer, resp. server, classes. Time is discrete and at each time step, one customer and one server arrive in the system according to a joint probability measure on CxS, independently of the past. Also, at each time step, pairs of matched customer and server, if they exist, depart from the system. Authorized matchings are given by a fixed bipartite graph. A matching policy is chosen, which decides how to match when there are several possibilities. Customers/servers that cannot be matched are stored in a buffer. The evolution of the model can be described by a discrete time Markov chain. We study its stability under various admissible matching policies including: ML (Match the Longest), MS (Match the Shortest), FIFO (match the oldest), priorities. There exist natural necessary conditions for stability (independent of the matching policy) defining the maximal possible stability region. For some bipartite graphs, we prove that the stability region is indeed maximal for any admissible matching policy. For the ML policy, we prove that the stability region is maximal for any bipartite graph. For the MS and priority policies, we exhibit a bipartite graph with a non-maximal stability region. This is a joint work with Varun Gupta and Jean Mairesse.
Dhandapani, Yogeshwaran
Percolation and directionally convex ordering of point processes.
View Abstract Hide Abstract
In this talk, we explain the relation between directionally convex ordering of point processes and percolation. Directionally convex ordering has been used to compare point processes with same mean intensities. We will start with a primer on directionally convex ordering of point processes and examples of point processes that are directionally convex ordered. We link directionally convex ordering to percolation as well as clustering by showing that they impact negatively the capacity functionals of their corresponding Boolean models. This is used to show ordering of some new critical radii which act as upper and lower bounds to the usual critical radius for percolation of a point process. The upper bound increases with dcx order while the lower bound decreases. In the second part, we exploit the fact that many probabilities of additive shot-noise fields of point processes can be bounded by their Laplace transforms. This for sparse point processes (i.e, lesser than Poisson point process in dcx order) can be bounded by the corresponding Laplace transform of Poisson-driven shot-noise fields. For a nice class of functionals, one can compute the latter explicitly to ascertain non-triviality of phase transition in various percolation models. We carry out such a program for providing uniform upper and lower bounds (uniform over all sparse point processes) for the critical radius for $k$-percolation and percolation in SINR (Signal-to-Interference-Noise-Ratio) graphs.
Dieker, Ton
Capacity allocation in feedforward queueing networks
View Abstract Hide Abstract
Allocation of service capacity ('staffing') at stations in queueing networks is both of fundamental and practical interest. Unfortunately, the problem is mathematically intractable in general and one therefore typically resorts to approximations or computer simulation. This talk describes a joint work with M. Squillante and S. Ghosh (IBM Research) on an algorithm that serves as an approximation for the 'best' capacity allocation rule for feedforward networks. The algorithm can be interpreted as a fixed-point iteration algorithm, and we are interested in uniqueness of a fixed point and in convergence properties.
Glynn, Peter
Lyapunov functions and the analysis of queues
View Abstract Hide Abstract
Lyapunov functions are a key tool in the analysis of systems described as Markov processes, and are now widely applied as a means of establishing stability of queueing systems. In this talk, we provide an overview of this methodology and discuss how Lyapunov ideas also arise naturally when bounding equilibrium moments, non-equilibrium expectations, studying smoothness of expectations as function of model parameters, and bounding the variance of importance sampling estimators.
Goldberg, David
Performance Bounds for Large Scale Queueing Systems
View Abstract Hide Abstract
In this talk, we resolve several open questions related to a certain heavy traffic scaling regime (Halfin-Whitt) for parallel server queues, which has recently been used in the modeling of call centers. In particular, we derive the asymptotics of the steady-state queue length for a very general class of service distributions. We also bound the large deviations behavior of the limiting steady-state queue length, and prove that the associated critical exponent takes a particularly simple form in certain cases. For certain initial conditions, we extend our results to the transient regime. Our main proof technique involves bounding the multiserver queue between two simpler systems. These systems exhibit an interesting duality, and yield bounds of a very general nature, which may be useful in answering a range of questions related to the modeling and optimization of queues.
Ivanovs, Jevgenijs
Markov-modulated Brownian motion with two reflecting barriers
View Abstract Hide Abstract
We consider a Markov-modulated Brownian motion reflected to stay in a strip [0,B]. The stationary distribution of this process is known to have a simple form under some assumptions. We provide a short probabilistic argument leading to this result and explaining its simplicity. This argument allows for generalizations including the distribution of the reflected process at an independent exponential time. This talk is based on the first part of arXiv:1003.4107
Kurtz, Tom
Counting processes, stochastic equations, and asymptotics for stochastic models
View Abstract Hide Abstract
Many stochastic models can be represented as solutions of stochastic equations for which Poisson processes or Poisson random measures are the primary inputs. A variety of examples will be given illustrating these equations and how they can be used to study limit theorems for stochastic models.
Litvak, Nelly
A Scaling Analysis of a Cat and Mouse Markov Chain
View Abstract Hide Abstract
Motivated by an original on-line page-ranking algorithm, starting from an arbitrary Markov chain on a discrete state space S, a two-dimensional Markov chain on the product space S X S, the cat and mouse Markov chain, is constructed. The first coordinate of this Markov chain behaves like the original Markov chain and the second component changes only when both coordinates are equal. The asymptotic properties of this Markov chain are investigated. A representation of its invariant measure is in particular obtained. When the state space is infinite it is shown that this Markov chain is in fact null recurrent if the initial Markov chain is positive recurrent and reversible. In this context, the scaling properties of the location of the second component, the mouse, are investigated in various situations: simple random walks in Z and Z^2, reflected simple random walk in N and also in a continuous time setting. For several of these processes, a time scaling with rapid growth gives an interesting asymptotic behavior related to limit results for occupation times and rare events of Markov processes.
Momcilovic, Petar
Linear loss networks
View Abstract Hide Abstract
We investigate properties of throughput and cost in linear loss networks. The maximum throughput of the network with exponential service times is derived and the arrival process that maximizes throughput, given a fixed arrival rate, is established. 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. We establish the asymptotic throughput and network cost under this critical loading. Moreover, we characterize the departure process from such a network. This process (appropriately scaled) is the (asymptotic) fixed point of the network, i.e., the arrival and departure processes have the same statistical description. Joint work with Mark Squillante and Yoojin Choi.
Montanari, Andrea
Message passing algorithms, random convex functions, and the risk of the LASSO
View Abstract Hide Abstract
We consider the problem of learning a vector x0 from noisy linear observation. In many contexts (ranging from model selection to image processing) it is desirable to construct a sparse estimator. In this case, a popular approach consists in solving an l_1-penalized least squares problem known as the LASSO or Bassis Pursuit DeNoising (BPDN). For sequences of matrices of increasing dimensions, with independent gaussian entries, we prove that the normalized risk of the LASSO converges to a limit, and we obtain an explicit expression for this limit. The proof is based on the analysis of an approximate message passing (AMP) algorithm,
Proutiere, Alexandre
Load balancing via Random Local Search in closed and open systems
View Abstract Hide Abstract
We analyze the performance of random load resampling and migration strategies in parallel server systems. Clients initially attach to an arbitrary server, but may switch servers independently at random instants of time in an attempt to improve their service rate. We first analyze the natural Random Local Search (RLS) strategy. Under this strategy, after sampling a new server randomly, clients only switch to it if their service rate is improved. In closed systems, where the client population is fixed, we derive tight estimates of the time it takes under RLS strategy to balance the load across servers. We then study open systems where clients arrive according to a random process and leave the system upon service completion. In this scenario, we analyze how client migrations within the system interact with the system dynamics induced by client arrivals and departures. We compare the load-aware RLS strategy to a load-oblivious strategy in which clients just randomly switch server without accounting for the server loads. Surprisingly, we show that both load-oblivious and load-aware strategies stabilize the system whenever this is at all possible. We further demonstrate, using large-system asymptotics, that the average client sojourn time under the load-oblivious strategy is not considerably reduced when clients apply smarter load-aware strategies.
Robert, Philippe
Probabilistics methods in the analysis of stochastic networks
View Abstract Hide Abstract
To follow
Saberi, Amin
Game Dynamics, Equilibrium Selection and Network Structure
View Abstract Hide Abstract
Coordination games describe social or economic interactions in which the adoption of a common strategy has higher payoff. They are classically used to model the spread of conventions, behaviors, and technologies in societies. Since the pioneering work of Ellison (1993), specific network structures have been shown to have dramatic influence on the convergence of such dynamics. In this talk, I will try to make these results more precise and use the intuition for designing effective algorithms.
Shneer, Seva
Comparing throughputs and fairness in slotted and non-slotted CSMA
View Abstract Hide Abstract
We consider a system consisting of n radios on a line. Each radio acts as a transmitter and a receiver but can not transmit and receive simultaneously. The well-known CSMA protocol is often used to govern the behaviour of the radios in such a system, and the performance of the system in this case is well understood. We consider a discrete-time analogue of the CSMA protocol and in the case of a completely saturated system find exact formulas for the total throughput of the system governed by this algorithm and for individual throughputs of all transmitters. We then compare these throughputs with the throughputs achieved by the classical CSMA protocol. The fairness of the two protocols is also compared. Finally, we discuss bounds for the throughput of a system where the first radio (source) is saturated and messages are relayed by the intermediate radios to the last one (destination). The results are also generalised to the case when the channel used by the radios is such that 2 of them cannot send messages simultaneously if the distance between them is not larger than k, where k is a positive integer. This is a joint work with Peter van de Ven (EURANDOM and Eindhoven University of Technology)
Simatos, Florian
Interacting branching processes and linear file-sharing networks
View Abstract Hide Abstract
File-sharing networks are distributed systems used to disseminate files among nodes of a communication network. The general simple principle of these systems is that once a node has retrieved a file, it may become a server for this file. In this paper, the capacity of these networks is analyzed with a stochastic model when there is a constant flow of incoming requests for a given file. It is shown that the problem can be solved by analyzing the asymptotic behaviour of a class of interacting branching processes. Several results of independent interest concerning these branching processes are derived and then used to study the file-sharing systems. (Joint work with L. Leskelä and P. Robert)
Subramanian, Vijay
Large deviations of max-weight scheduling policies on convex rate regions
View Abstract Hide Abstract
We consider a single server discrete-time system with K users where the server picks operating points from a compact, convex and co-ordinate convex set in $Re_+^K$. For this system we analyse the performance of a stablising policy that at any given time picks operating points from the allowed rate region that maximise a weighted sum of rate, where the weights depend upon the workloads of the users. Assuming a large deviations principle (LDP) for the arrival processes in the Skorohod space of functions that are right-continuous with left-hand limits we establish an LDP for the workload process using a generalised version of the contraction principle to derive the corresponding rate function. With the LDP result available we then analyse the tail probabilities of the workloads under different buffering scenarios.
Tassiulas, Leandros
Stochastic models and algorithms for cooperative information delivery
View Abstract Hide Abstract
Recent advances in information and communication theory suggest novel 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 in an intermediate relay node 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. 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.
van der Hofstad, Remco
Processes on random graphs: routing and attack vulnerability
View Abstract Hide Abstract
Empirical findings have shown that many real-world networks share fascinating features. Indeed, many real-world networks are small worlds, in the sense that typical distances are much smaller than the size of the network. Further, many real-world networks are scale-free in the sense that there is a high variability in the number of connections of the elements of the networks. Therefore, such networks are highly inhomogeneous. Spurred by these empirical findings, models have been proposed for such networks. In this talk, we shall discuss empirical findings of real-world networks, and describe some of the models proposed for them. In the real-world, we are not only interested in the topology of networks, but also in processes living on them. Think of routing on the Internet, the spread of information and disease on social networks, and searching on the World-Wide Web. In this talk, we discuss two of such processes in detail. The first example is first-passage percolation on random graphs, which is a simple model for shortest-weight routing on complex networks. We discuss how random edge weight change the structure of shortest-weight paths, and derive precise limiting results for the weight and number of edges in the shortest-weight path between two uniform vertices. The results show that adding i.i.d. exponential weights on the edges has a marked effect on the structure of shortest-weight paths. We close this part by discussing various open problems and conjectures. The second example is percolation on random graph, which is a simple model for the attack vulnerability of networks. We discuss the connectivity behavior at and close to the critical value. Our results show that, for inhomogeneous random graphs with highly variable vertex degrees, the critical behavior admits a transition when the third moment of the degrees turns from finite to infinite. When the third moment is finite, the largest clusters in a graph of n vertices have size n^{2/3} and the scaling limit equals that on the Erdoes-Renyi random graph. When the third moment is infinite, the largest clusters have size to n^{alpha} for some alphain (1/2,2/3), and the scaling limit is rather different. Similar phase transitions have been shown to occur for typical distances in such random graphs when the variance of the degrees turns from finite to infinite. We finally discuss some of the ingredients used in the proofs, namely the tree-like nature of the random graphs under consideration and the use of (continuous- and discrete-time) branching processes. This is joint work with: Gerard Hooghiemstra, Shankar Bhamidi, Johan van Leeuwaarden, Piet Van Mieghem, Henri van den Esker and Dmitri Znamenski.
Wainwright, Martin
Graphical models and message-passing algorithms: Some introductory lectures
View Abstract Hide Abstract
ABSTRACT: Graphical models arise from a marriage between graph theory and probability theory, and have put to fruitful use in a variety of disciplines, among them statistical physics, image processing, communication theory, bioinformatics and networking. Graphical models naturally give rise to local ``message-passing'' algorithms for performing various types of distributed computation, which have been highly influential in these disciplines. In this series of tutorial lectures, we provide an introduction to this area. We begin with basics of the field (including Markov properties, Hammersley-Clifford, message-passing on trees, junction tree framework) before moving onto a selection of more advanced topics (e.g., message-passing on graphs with cycles, convergence issues, variational methods, and linear-programming relaxations). A short book on graphical models: http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJor08_FTML.pdf
Walton, Neil
Utility Optimization in Congested Queueing Networks
View Abstract Hide Abstract
We consider a multi-class single server queueing network as a model of a packet switching network. The rates packets are sent into this network are controlled by queues which act as congestion windows. By considering a sequence of such congestion windows we allow the network to become congested. We show the stationary throughput of routes on this sequence of networks converges to an allocation that maximizes aggregate utility subject to the network's capacity constraints. To perform this analysis we require that our utility functions satisfy an exponential concavity condition. This family of utilities includes weighted $alpha$-fair utilities for $alpha >1$.
Wischik, Damon
Queueing theory for switched networks
View Abstract Hide Abstract
A switched network consists of a collection of queues, with constraints on which queues may be served simultaneously, plus a policy for choosing which set of queues to serve at a given instant. Switched networks can be used to model diverse communications systems such as Internet routers, bandwidth sharing by TCP, and wireless networks. I will describe these modelling applications. I will also describe several approaches to performance analysis: stability analysis via Lyapunov functions, heavy traffic analysis, overload analysis, and underload analysis using large deviations theory.
Zhang, Jiheng
Fluid Models of Many-server Queues with Abandonment
View Abstract Hide Abstract
We study many-server queues with abandonment in which customers have general service and patience time distributions. The dynamics of the system are modeled using measure-valued processes, to keep track of the residual service and patience times of each customer. Deterministic fluid models are established to provide first-order approximation for this model. The fluid model solution, which is proved to uniquely exists, serves as the fluid limit of the many-server queue, as the number of servers becomes large. Based on the fluid model solution, first-order approximations for various performance quantities are proposed.

Participants

Name	Institution
Arfeen, Muhammad Asad	University of Canterbury, Christchurch
Baccelli, François	INRIA/ENS
Blanchet, Jose	Columbia University
Blaszczyszyn, Bartek	INRIA/ENS
Borst, Sem	Eindhoven University of Technology
Bouman, Niek	Eindhoven University of Technology
Buke, Burak	University of Edinburgh
Busic, Ana	INRIA/ENS
Chen, Lisa	The University of Auckland
Cruise, James	University of Bristol
Denisov, Denis	Cardiff University
Dhandapani, Yogeshwaran	INRIA/ENS
Dieker, Ton	Georgia Institute of Technology
Dommers, Sander	Eindhoven University of Technology/EURANDOM
Eshete, Addisu	Norwegian University of Science and Technology
Foss, Sergey	Heriot-Watt University
Frolkova, Maria	CWI
Gibbens, Richard	University of Cambridge
Glynn, Peter	Stanford University
Goldberg, David	MIT
Haddad, Jean-Paul	University of Waterloo
Haji Mirsadeghi, Mir Omid	INRIA/ENS
Hunter, David	University of Essex
Ivanovs, Jevgenijs	EURANDOM
Khandwawala, Mustafa	Indian Institute of Science
Kurtz, Tom	University of Wisconsin - Madison
Lelarge, Marc	INRIA/ENS
Litvak, Nelly	University of Twente
Moench, Christian	University of Bath
Momcilovic, Petar	University of Michigan
Montanari, Andrea	Stanford University
Muratov, Anton	Chalmers University of Technology
Parker, Ben	Queen Mary, University of London
Proutiere, Alexandre	Microsoft Research
Robert, Philippe	INRIA
Saberi, Amin	Stanford University
Sejdinovic, Dino	University of Bristol
Shneer, Seva	EPFL
Simatos, Florian	CWI
Subramanian, Vijay	Hamilton Institute
Sundaresan, Rajesh	Indian Institute of Science
Tabis, Kamil	University of Wroclaw
Tassiulas, Leandros	University of Thessaly
van der Hofstad, Remco	Eindhoven University of Technology
Vlasiou, Maria	Eindhoven University of Technology
Vukobratovic, Dejan	University of Strathclyde
Wainwright, Martin	Univerisity of California - Berkeley
Walton, Neil	University of Cambridge
Wierman, Adam	California Institute of Technology
Wischik, Damon	UCL
Yudovina, Elena	University of Cambridge
Zachary, Stan	Heriot-Watt University
Zhang, Jiheng	The Hong Kong University of Science and Techonology
Ziedins, Ilze	The University of Auckland
Zuyev, Sergei	Chalmers University of Technology
Zwart, Bert	CWI