YEQT-II (Young European Queueing Theorists)

Stochastic analysis of modern communication networks

December 1-3, 2008

EURANDOM, Eindhoven, The Netherlands

ABSTRACTS

Urtzi Ayesta (LAAS, CNRS, Toulouse, France)
Joint work with: I.M. Verloop and S.C. Borst

Monotonicity properties for multi-class queueing systems

We study multi-dimensional stochastic processes that arise in queueing models used in the performance evaluation of wired and wireless networks. The evolution of the stochastic process is determined by the scheduling policy used in the associated queueing network. For general arrival and service processes, we give sufficient conditions in order to compare sample-path wise the workload and the number of users under different policies. This allows us to evaluate the performance of the system under various policies in terms of stability, the mean overall delay and the weighted mean number of users.

We apply the general framework to linear bandwidth-sharing networks, where users of various classes require service from different subsets of shared resources simultaneously. For the important family of weighted $\alpha$-fair policies, stability results are derived and monotonicity is established of the weighted mean number of users with respect to the fairness parameter $\alpha$ and the relative weights. In order to broaden the comparison results, we investigate a heavy-traffic regime and perform numerical experiments. In addition, we study a single-server queue with two user classes, and show that under Discriminatory Processor Sharing (DPS) or Generalized Processor Sharing (GPS) the mean overall sojourn time is monotone with respect to the ratio of the weights. Finally we extend the framework to obtain comparison results that cover the single-server queue with an arbitrary number of classes as well.

Florence Bénézit (EPFL, Lausanne, Switzerland)

Distributed Voting Algorithms

Each node in a network makes a binary choice: it votes for A or B, Yes or No, 1 or 0... The goal of a distributed voting algorithm is to let every node in the network know the majority vote by means of local interactions only. In our talk we develop several voting algorithms which follow a classical setting. At any iteration, each node has a state, which was initialized with its vote. When communicating with its neighbors, a node updates its state according to its own state and its neighbors states. The updating rule (also called automaton) should be the same for all nodes and it should not change with time. At convergence, every node should be able to deduce the majority vote from its state. Previous work has systematically considered 1 bit states (0 or 1) although no solution was ever found in that case. Our voting algorithm uses 2 bits states and it converges correctly in finite time with probability 1 in any connected network. Several extensions of the 2 bits voting algorithm will be presented as well.

Augustin Chaintreau (Thomson, Paris, France)
Joint work with Pierre Fraigniaud and Emmanuelle Lebhar, from CNRS-LIAFA, and Université Paris 7

"Move and Forget": Random Walks seen from an Algorithmic Perspective

Abstract: This talk describes a model designed to shed light on the algorithmic properties of networks where nodes move according to random walks. We focus on navigation, a remarkable property of augmented networks, which states that short paths exist and may be found with local information by a simple decentralized algorithm. This property, introduced in 2000 in a famous paper by J. Kleinberg is frequently cited as the most complete explanation for the "small world" phenomenon exhibited in social networks. In spite of many extensions of this result, the conditions for navigation remain fragile, and no local dynamics have been shown formally to converge to a navigable network.

Here we introduce the first model proving the emergence of navigation from a local evolution. One could expect that nodes following random mobility makes navigable networks even more difficult to construct; this work proves the exact opposite as navigation is shown here to be a consequence of random mobility, combined with a simple temporal dynamics. The essential ingredient of the proof can be formulated as a game of "stopped random walk", where the objective is to target an appropriate density distribution while choosing the stopping age. For simple random walks, we prove that a natural solution exists for this game and is independent of the dimension of the space. We will conclude with partial results on generalized versions of this game.

James Cruise (Bristol University, England)

A Scaling Framework for the Many Flows Asymptotic, through Large Deviations.

We introduce a new framework of scalings for the many flows asymptotic. This asymptotic was first introduced by Weiss. This asymptotic is useful in estimating drop probabilities for modelling congestion control protocols as well as providing insight into observed phenomenon.

To introduce the framework we re-examine the previously studied results and see how the scalings naturally generalise. With in this we consider a simple Markovian example. We follow this by the sample path large deviations for fractional Brownian motion with in this framework and leading to a reconsideration of the traditional Huristness ideas.

Bernardo D'Auria (Carlos III university , Madrid, Spain)
Joint work with J. Ivanovs and O. Kella

Generalized Jordan Chains with Application to Markov Additive Processes with One-sided Jumps

We analyze the generator of a spectrally negative Markov Additive Process, F(), and prove that the only stochastic matrix + that solves the matrix equation F(&#1048576;) = 0 is given by the generator of the Markov Environment process computed at the ascending ladder times. We give a complete description of the matrix + in terms of generalized Jordan chains of the generator F(). Finally we apply the obtained formula to dierent cases and in particular we exhaustively solve the computation of the LST of the stationary distribution of a regulated Markov Modulated Brownian Motion.

Olivier Dousse (Nokia research center, Switzerland)

Short-term fairness in CSMA networks as a three player ruin problem.

We consider a circle-shaped network of $N$ equally spaced wireless devices implementing some CSMA protocol (such as IEEE 802.11 for example). Using a Markovian model (that will also be presented in Prof. Thiran's tutorial), we look at the fairness properties of the protocol in this configuration. Assessing the short-term fairness of this network amounts to solve a particular three-player ruin problem, where the game ends only when two players are simultaneously ruined. In this talk, we present an exact solution for this problem, and get some asymptotic results about the fairness of the network when $N$ tends to infinity.

Eleni Drinea (EPFL, Lausanne, Switzerland)
Joint work with Christina Fragouli and Lorenzo Keller.

Delay in broadcasting with network coding and feedback

We consider the problem of minimizing delay when broadcasting over erasure channels with feedback. More specifically, a sender wishes to communicate the same set of messages to several receivers. The sender can broadcast a single message or a combination (encoding) of messages to all receivers at each time step, through separate erasure channels. Receivers provide feedback as to whether the transmission was received. Our notion of delay is motivated by real-time applications that request progressively refined input, such as the successive refinement of an image encoded using multiple description coding. This setup is novel because it combines coding techniques and feedback information while previous approaches used uncoded scheduling or erasure correction coding (e.g., maximum distance separable codes). We show several complexity results and propose heuristic online algorithms.

Ken Duffy (Hamilton Institute, NUI Maynooth, Ireland)

Long-range-dependence properties of departures from a balanced queue.

If a queue is fed by a single fluid on/off source of traffic and processed at its mean arrival rate, then the resulting departures process has power tailed on times that have infinite mean. Motivated by processes of this sort, in this talk we discuss results regarding measures of the long range dependence of on/off processes with power tailed sojourn times that have infinite mean.

Several difficulties arise in analyzing these processes, including the lack of existence of stationary versions of the processes of interest and the need to determine appropriate power spectrum regularizations.

Contrary to intuition, if on times have infinite mean, we will show that as the power-tail gets heavier, the process becomes less long-range dependent. That is, the processes's autocorrelation function decays more rapidly and the power spectrum diverges more slowly.

It will be demonstrated that, despite the new regularization, the popular Wavelet estimator of power spectrum divergence and the Variance-Time Plot Method for autocorrelation decay, match with theory. The reasons behind this will be explained.

This talk is based on two papers written with Christopher King (Northeastern University) and David Malone (NUI Maynooth): "Ambiguities in estimates of critical exponents for long-range dependent processes", Physica A, 377 (1), 43-52, 2007 and "Some remarks on LD plots for heavy-tailed traffic", ACM SIGCOMM Computer Communications Review, 37 (1), 41-42, 2007.

Olivier Leveque (EPFL, Lausanne, Switzerland)

Information Theoretic Operating Regimes of Large Wireless Networks

In analyzing the point-to-point wireless channel, insights about two qualitatively different operating regimes - bandwidth and power limited - have proven indispensable in the design of good communication schemes. In this talk, we propose a new scaling law formulation for wireless networks that allows us to develop a theory that is analogous to the point to point case. We identify fundamental operating regimes of wireless networks and derive architectural guidelines for the design of optimal schemes.

Our analysis shows that in a given wireless network with arbitrary size, area, power, etc., there are three parameters of importance: the short-distance SNR, the long-distance SNR, and the power path loss exponent. Depending on these parameters we identify four qualitatively different regimes. One of these regimes is especially interesting since it is fundamentally a consequence of the heterogeneous nature of links in a network and does not occur in the point-to-point case; the network capacity is both power and bandwith limited. This regime has thus far remained hidden due to the limitations of the existing formulation.

Existing schemes, either multihop transmission or hierarchical cooperation, fail to achieve capacity in this regime; we propose a new hybrid scheme that achieves capacity.

Lasse Leskelä (Helsinki University of Technology, Finland)

Throughput capacity of a class of stochastic peer-to-peer network models

Abstract: A key feature in today's peer-to-peer file sharing networks is that that the number of peers acting as servers grows, as more peers join the system. Ignoring the physical network constraints, the throughput capacity of many peer-to-peer systems, measured as the maximal sustainable rate of completed file transfers, may hence be considered infinite. Modeling the network as a random dynamical system, the throughput capacity may alternatively be defined as the the maximal arrival rate of new peers, such that the number of peers in the system remains stable (stochastically bounded over time). In this talk I will present a sharp capacity characterization of a class of stochastic peer-to-peer models where the throughput capacity may be finite or infinite, depending on how long the peers are willing to act as servers. Instead of looking at the deterministic large population scaling limit, the analysis is conducted directly in the stochastic regime, using coupling techniques as a main tool.

Michel Mandjes (UvA, CWI, EURANDOM, Netherlands)
Joint work with K. Debicki, A. Es-Saghouani, L.N. Andersen, P. Glynn, and T. Ott

Transient results for levy-driven queues, and it contains

In this talk I will describe a family of results related to the transient analysis of queues with Levy input. It has been argued that queues with Levy input play an important role in the analysis of communication networks, under specific scalings. Therefore, for proper traffic management, insight into the transient behavior is of crucial importance.

In the first part, I will derive a couple of structural properties of the covariance function of the workload; in more detail, the object we study is r(t) := Cov(Q(0), Q(t)), where Q(t) is the workload at time t, assuming the queue starts in stationarity at time 0. In case of spectrally-positive input, the Laplace transform of r(t) can be explicitly given, relying on martingale arguments. Extensively using the concept of complete monotonicity (Bernstein, '29), we can prove that r(t) is positive, decreasing, and convex, thus complementing an earlier result by Ott ('77) for the compound Poisson case. We also derive the asymptotics of r(t) for both the case of light-tailed and heavy-tailed input.

In the second part of the lecture, the focus lies on the analysis of busy periods. The underlying goal lies in devising methods for fast simulation of r(t) by importance sampling. These require insight in the behavior of the Levy process conditional on the rare event of a long busy period. We determine the distribution of Q(0), given that the busy period lasts for another t time units, for t large.

Interestingly, for Brownian motion this turns out to be an Erlang(2) distribution, which may relate to findings by Iglehart et al. in the 1970s.

The third part of the presentation is about bivariate asymptotics, i.e., probabilities of the type P(Q(0) > pB, Q(T_B) > qB), with a focus on their limiting behavior when B grows large. We present explicit conditions under which these probabilities are essentially determined by the "most binding" of both events (so that they look like P(Q(0) > max{p,q}B) for B large), which is typically the case when T_B grows slower than B. We also identify a second regime in which the probability essentially decouples to

P(Q(0) > pB) P(Q(0) > qB),

i.e., the events are asymptotically independent; this is typically the case when T_B grows (substantially) faster than B. There are intermediate regimes, though, which are particularly interesting in the case of regularly varying input.

Time permitting, I can present a few intriguing results on one-sided and two-sided reflected Levy processes. Most notably, I will demonstrate how to prove that the expected value of the position at time t, starting in 0, is an increasing and concave function, and (just for the one-sided reflection) that the variance of the position at time t is increasing. This is done by proving these results for their discrete-time counterpart (i.e., reflected random walks), and then I use a limiting argument.

Laurent Massoulié (Thomson, Paris, France)

Peer-to-Peer live streaming: recent results and open problems

Abstract: In peer-to-peer live streaming, a continuous stream of data is generated, that receivers aim to obtain either from servers or other receivers. The design and analysis of such systems provides a rich playground for queueing theorists. Ideal design should balance the following objectives: rate, delay, and cost efficiency. We will present rate- and delay-optimal schemes, whose analysis involves fluid limits and epidemic diffusion analysis respectively. We will also discuss open problems around delay and cost efficiency, and preliminary results in this direction.

Pascal Moyal (Pascal University of Compiegne, France)

Weak Stability of queues with deadlines

We investigate the stability of queues with deadlines. In such systems, the customers are impatient, and are discarded whenever their deadline elapses before they could begin (or complete) their service.

Using Renovating Events Theory, we first propose a sufficient condition for the existence and uniqueness of a stationary profile, which is the planar sequence-valued descriptor keeping track of the remaining services and the remaining lead times of the customers.

In the FIFO case, this condition can be relaxed. We show the existence of a stationary workload in a weak sense, by using tightness techniques and an enrichment of the probability space related to that introduced by Neveu for loss systems.

Georgios Paschos (CERTH-ITI, Greece)
J
oint work with Petteri Mannersalo, Eitan Altman, Sara Alouf and Amar Azad

WiMAX sleep mode: Performance analysis and optimal policies

Since 2005, IEEE 802.16e propose a simple mechanism for WiMAX terminals to save power by turning off the radio transceiver. To start with, extensive analysis of the performance of the standards is required. Using this knowledge one can optimize the available (from the standards) settings to obtain as optimal behaviour as the standards allow. Then, it is interesting to look at the global optimality by finding the policy that yields the best selection of sleeping periods. How far are the stardards from this solution?

Balakrishna Prabhu (LAAS-CNRS, France)
Joint work with Eitan Altman (INRIA Sophia-Antipolis) and Urtzi Ayesta (LAAS-CNRS)

Load Balancing for Processor Sharing Systems

In this talk, we present optimal load balancing strategies for a multi-class multi-server processor-sharing system with a Poisson input stream, heterogeneous service rates, and a server-dependent holding cost per unit time for two different settings - $(i)$ the centralized setting in which a dispatcher routes jobs based on their service requirements with the objective of minimizing the weighted mean sojourn time in the system; and $(ii)$ the distributed non-cooperative setting in which each job, aware of its service requirement, selects a server with the objective of minimizing its weighted mean sojourn time in the system. For these two settings, we characterize the set of optimal routing policies and obtain a closed form expression for the load on each server under any such policy. Furthermore, we show the existence of an optimal policy that routes jobs independently of their service time requirement. Finally, we show that the Price of Anarchy (PoA) for such systems can be unbounded.

Alexander Proutiere (Microsoft Research, Cambridge, England)

Bits in the air: a queueing perspective of wireless communication

Florian Simatos (INRIA Paris-Rocquencourt, France)

Peer-to-peer systems and branching processes: two simple examples

Similarly as for infection processes, the core mechanism of peer-to-peer networks, where a client becomes a server once it has the file, gives rise to branching-like dynamics. This fact has already been observed for some time now, and the intent of this talk is to highlight two new problems related to branching processes and triggered by peer-to-peer networks. These problems turn out to be of independent mathematical interest, and further provide insight into the original network models. The first example is concerned with a flash crowd scenario: a popular file is released, which immediately yields a high demand. During a first period of time, the number of servers can be approximated by a binary Bellman-Harris process, and one wants to know the extent to which this approximation holds. We will show how the split times of this process define a bins and balls problem in random environment, whose solution provides insight into this question.

In the second example, a simple multichunk scenario is considered: a peer-to-peer architecture is used to make it possible for a user to watch a movie while still downloading it. For load balancing purposes, the network defined this way has a linear structure, and a peer downloads a given chunk only from peers who have one more chunk. The stability analysis of such a network involves Yule processes where particles are killed at random times.

Vijay Subramanian (Hamilton Institute, NUI Maynooth, Ireland)
Joint work with Somsak Kittipiyakul and Tara Javidi at UCSD

Many-Sources Large Deviations for Max-Weight Scheduling

We establish a many-sources large deviations principle (LDP) for the transient workload of a multi-queue single-server system where the service rates are chosen from a compact, convex and coordinate- convex rate region and where the service discipline is the max-weight policy. Under the assumption that the arrival processes satisfy a many- sources LDP, this is accomplished by employing Garcia's extended contraction principle that is applicable to quasi-continuous mappings.

For the simplex rate-region we also establish an LDP for the stationary workload under the additional restriction that the max- weight policy also be work-conserving. The LDP result can be used to calculate asymptotic buffer overflow probabilities accounting for the multiplexing gain, when the arrival process is an average of i.i.d.

processes. We express the rate function for the stationary workloads in term of the rate functions of the finite-horizon workloads when the arrival processes have i.i.d. increments.

Patrick Thiran (EPFL, Lausanne, Switzerland)
Joint work with Adel Aziz (EPFL), Olivier Dousse (Nokia), Mathilde Durvy (Cisco) and David Starobinski (Boston University).

Fairness, Spatial Reuse, Long term Fairness, Phase Transition and Stability in CSMA/CA Networks.

IEEE 802.11 is probably the most widely used Medium Access Control protocol in current wireless networks. In the single-hop setting (wireless LAN), its performance is quite well understood. In the multi-hop setting however, there is, to date, no widely accepted model that captures rigorously all the essential features of the protocol while staying simple enough to provide insight, even though some significant progress has been made in the recent years. Still, when confronted with experimental results, people often find it hard to interpret them. In this tutorial, we will present some recent models, as well as the methods that have been used to explore some fundamental properties of these networks, and which borrow tools from queuing theory, Markov random fields and more generally statistical physics.

We first consider a network where all nodes are saturated traffic sources. We use a continuous-time Markovian loss network, that enables us to study systematically the trade-off between spatial reuse and (long-term) fairness, which is inherent to these decentralized CSMA/CA MAC protocols. We show in particular that the widely observed unfairness of the protocol in small network topologies does not always persist in large topologies. In large 1-dim. networks, nodes sufficiently far away from the border of the network have equal access to the channel. In 2-dim. networks, we observe a phase transition, linked to the existence of multiple Gibbs measures in the Markov Random Field model. If the access intensity of the protocol is small, border effects remain local and the protocol is long term fair as in 1-dim. networks. However, for a large enough access intensity, the border effects persist independently of the size of the network and the protocol is strongly unfair.

Next, we consider the more complex scenario of a network where one node (the source) is saturated, but where all the other nodes only relay the traffic from this source to a sink. Relay nodes can either be bufferless, in which case the quantity of interest is the fraction of lost packets in the network, or on the contrary have an infinite buffer, in which case the property of interest is the stability of the network. Two main factors impact stability: the network size and the so-called "stealing effect", a consequence of the hidden node problem and non-zero propagation delays.

Neil Walton (Cambridge University, England)

Proportional Fairness and its Relationship with Multi-class Queueing Networks

A network of single server queues with routing is considered. These networks have a product form stationary distribution. A new limit result proves a sequence of such networks converges weakly to a stochastic flow level model. This stochastic model is insensitive. A large deviation principle for the stationary distribution of these queueing networks is found. Its rate function has a dual formulation that coincides with proportional fairness. It is proven that the stationary throughput of the queueing model converges to a proportionally fair allocation.

The queueing models considered have no prescribed optimization structure. Regardless of this, we find a proportionally fair allocation forms an entropy minimizing state of these networks. Proportional fairness occurs as a consequence of a collapse in the state space of the queueing model.

This work combines classical queueing networks with more recent work on stochastic flow level models and proportional fairness. One could view these seemingly different models as the same system described at different levels of granularity: a microscopic, queueing level description; a macroscopic, flow level description and a teleological, optimization description.

Cornelia Wichelhaus (Heidelberg university, Germany)

Nonparametric inference for networks of queues

Stochastic networks are systems of interacting components with the typical application fields telecommunication systems, the internet as well as systems of neurons and population models. For applications statistical inference of the service time distributions based on incomplete observations of the systems is of great importance in order to classify the performance behavior. For example, a unimodal service time density shows a homogeneous service behavior whereas a bimodal density may indicate that there are two distinct customer populations or breakdowns of the server. In the statistical literature there are only results for single node systems and moreover, for the most part the analysis is done in case of exponential distributed arrival times only. With this talk we try to close this gap and present a statistical analysis study of an open network of G/G/∞ queues. At each node we observe the external input process and the external departure process which are general second-order stationary point processes. Our aim is to estimate the service time densities at the nodes as well as the routing probabilities. Our approach relies on spectral analysis methods for multivariate point processes. We show consistency and asymptotic normality for our estimators.

Bert Zwart (CWI & EURANDOM, The Netherlands)
Joint work with Sem Borst and Regina Egorova