About | Research | Events | People | Reports | Alumni | Contact | Home
STOCHASTIC ACTIVITY MONTH
Sergey Foss (Heriot Watt) How Big Queues Occur in Multi-Server System with Heavy Tails We present upper and lower bounds for the tail distribution of
the stationary waiting time in the stable $GI/GI/s$ FCFS queue. These bounds
depend on the value of the traffic load $\rho$ which is the ratio of mean
service and mean interarrival times. For service times with regularly varying
tail distribution the bounds are exact up to a constant, and we are able to
establish a ``principle of $s-k$ big jumps'' in this case (here $k$ is the
integer part of $\rho$). As another corollary of the bounds obtained, we provide
a new proof of necessity and sufficiency of conditions for existence of moments
of the stationary waiting time. Marc Lelarge (INRIA) Bipartite graph structures for efficient balancing of heterogeneous loads Motivated by a problem of contents placement in the context of
video-on-demand applications, we compute the size of a maximum spanning subgraph
with degree constraints on a random sparse bipartite graph. Our proof makes a
rigorous use of the cavity method leading to recursive distributional equations
which we solve. We also analyse the structure of the optimal solution by
identifying a saturated core. As applications, we characterise the performances
of various placement strategies (in function of the memory size available and
statistics of the requests).
Last updated
18-04-11, |