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(􀀀) = 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.

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