Les séminaires du projet MISTRAL
en année scolaire 9798
Seminars of Project MISTRAL
in the academic year 9798

Vendredi 12 septembre 1997, 11:00, Salle de Conférence CERMICS
Hayriye Ayhan
(Georgia Institute of Technology)
Bias Optimality in a TwoClass Queueing System

Vendredi 19 septembre 1997, 11:00, Salle du Conseil
Harold J. Kushner
(Brown University, USA)
Optimal Control of Assignment of Jobs to Processors Under Heavy Traffic

Vendredi 19 septembre 1997, 15:00, Salle du Conseil
Sergei Zouev
(INRIA Sophia Antipolis)
Arrangements of points: asymptotical optimality.

Vendredi 10 octobre 1997, 10:00, Salle du Conseil
Thomas Bonald
(INRIA Sophia Antipolis)
On the Stable Behaviors of Window Flow Control.

Jeudi 16 octobre 1997, 10:00, Salle du Conseil
M. Menshikov (Moscow State University)
Random walks in random environment: martingale approach

Vendredi 24 octobre 1997, 10:00, E003
Francois Baccelli
(INRIA Sophia Antipolis)
Evénements Rares de Processus Stationnaires

Vendredi 7 novembre 1997, 10:00, Salle du Conseil
Hayriye Ayhan
(Georgia Institute of Technology)
On the TimeDependent Occupancy and Backlog Distributions for the
GI/G/\infty Queue

Vendredi 14 novembre 1997, 10:00, Salle du Conseil
Armand M. Makowski
(University of Maryland et INRIA Sophia Antipolis)
From Optimal Search Theory to Sequential Paging in Cellular Networks

Vendredi 21 novembre 1997, 15:00, Salle du Conseil
Jorn Migge
(INRIA Sophia Antipolis)
Fixed Priority Preemptive Scheduling: Stochastic Response Times Bounds

Vendredi 23 janvier 1998, 10:00, Salle E002
Zhen LIU
(INRIA Sophia Antipolis)
Some Scheduling Problems in the Web Search Engines

Vendredi 23 janvier 1998, 14:00, Salle E002
Serguei Foss
(INRIA Sophia Antipolis et Univ. de Novossibirsk)
On the $\phi$renovation.

Mardi 3 février 1998, 14:00, Salle du Conseil
Jean Mairesse
(LIAFA)
Calcul exact de taux de croissance pour des modeles de tas de pieces

Vendredi 27 février 1998, 10:00, Salle E002
Serguei Foss
(INRIA Sophia Antipolis et Univ. de Novossibirsk)
The Fluid Approximation Approach: a Generalized Stability
Criterion and its Application to a Polling System

Vendredi 6 mars 1998, 10:00, Salle du Conseil
Peter Kemper
(Universität Dortmund)
How does functional and quantitative analysis of discrete event
dynamic systems profit from Kronecker algebra?

Vendredi 6 mars 1998, 11:00, Salle du Conseil
Serguei Foss
(INRIA Sophia Antipolis et Univ. de Novossibirsk)
On a Perfect Simulation of Stationary Distributions by
Backwards Coupling.

Vendredi 20 mars 1998, 10:00, Salle du Conseil
Keith Ross
(Eurecom)
A Pragmatic Approach for Guaranteeing QoS to Regulated Traffic in Networks

Vendredi 10 avril 1998, 10:00, Salle du Conseil
Laurent Massoulie
(CNET)
Equité et Qualité de service pour le transfert de flux de trafic
élastique.
Pointeurs vers les autres annonces:
Résumés (Abstracts)
We consider a finite capacity queueing system with a Poisson arrival
process and exponential service times. Arriving customers are of two
types and offer a reward depending on their type. The server must then
decide, based on the reward being offered and how much space is
remaining, whether the arriving customer should be accepted. A
traditional objective function is to maximize the gain; that is, the
long run average reward. However, it is quite possible to have multiple
gain optimal policies. Bias optimality is a more refined objective
function which can distinguish among multiple gain optimal policies.
This talk focuses on describing the structure of stationary,
deterministic optimal policies and extending this optimality to
distinguish between multiple gain optimal policies. We show that these
policies are of trunk reservation type and must occur at consecutive
trunk reservation levels. We then prove that we can distinguish among
these gain optimal policies using the bias (transient reward).
This is a joint work with Robert D. Foley and Mark E. Lewis.
We treat many forms of the classical assignment problem. Jobs and their work
rerquirements arrive at random. The jobs fall into two classes, dominant
streams and streams which occur with less frequency. Only the latter are
controlled, but the model is the basis for the general problem.
They can be either queued or assigned immediately to a processor queue.
There are several processors, differing in speeds, etc. The optimal control
problems under heavy traffic converge to a limit optimal control problem,
and good controls for the limit problem are also good for the physical
problem, even under moderate traffic.
There can be state dependence, batch arrivals, different information
structures, and rather arbitrary cost functions.
Let F be a functional of configurations of N independently distributed in a
phase space X. Let p_N(x) with the point density that minimizes the
expectation of F. We present a new method based on the stochastic gradient
tecnique for Poisson processes that allows in many cases to find the
asymptotically optimal density p(x)=lim_N p_N(x).
Flow control mechanisms are used in packetswitched networks to
prevent routers from congestion, by regulating sending rate of
the users. The most widely used mechanism is the windowbased
scheme, like that of TCP over the Internet. In such a scheme,
the destination sends an acknowledgment to the source upon
reception of a packet, and the window refers to the maximal
number of unacknowledged packets in the network.
The goal of this work is to evaluate the impact of the exogenous
traffic generated by the other connections on the performance of the
window flow control. Our approach consists in studying the stability
of a model where the input flows are represented by stationary
ergodic point processes. By establishing necessary and sufficient
conditions for stability, we obtain bounds on the maximal throughput
allowed by the flow control. These results are illustrated by several
examples.
Keywords: Window flow control, TCP, stability, stationary ergodic
point process, (max,+)linear system.
This is a joint work with Francois Baccelli.
We consider two examples of countable Markov chains in random environment
using the Lyapunov functions approach: a onedimensional random walk and a
random string. In each case for typical configurations of the environment we
obtain a full classification of the ergodic and transience behavior of the
corresponding model.
Kielson (1979) et Aldous (1989) ont donné des expressions
pour le comportement asymptotique du temps moyen jusqu'à
l'occurrence d'un événement rare. Dans cet article, nous
généralisons ces résultats
du cadre markovien au cadre stationnaire grâce à la
la théorie des processus ponctuels.
Deux notions d'indépendance et d'exponentialité
asymptotiques sont introduites qui permettent d'étudier
le comportement asymptotique de ce temps moyen
sous diverses lois de probabilité.
We consider an infinite server queueing system. An examination of sample
path dynamics allows a straightforward development of integral equations
having solutions that give timedependent occupancy (number of
customers) and backlog (unfinished work) distributions (conditioned on
the time of the first arrival) for the GI/G/\infty queue. These
integral equations are amenable to numerical evaluation and can be
generalized to characterize GI^X/G/\infy queue. Two examples are
given that illustrate the results.
This is a joint work with J.LimonRobles and M.A. Wortman.
A more efficient use of limited wireless
resources in emerging personal communication services (PCS)
requires much smaller cells (microcells and picocells) than those used in
conventional cellular networks. Tracking the mobile stations
will become a challenging task as the cell sizes shrink
and the number of cells increases.
In order to ensure reliable communication, a mobile station
has to send/receive signaling messages from/to the
base station. Depending on the system design, signaling messages serve
various purposes such as frame synchronization, base station identification,
mobility management, handoff decision making, etc. With the expansion
of both the number of services available to users,
and the number of mobile stations in service, the radio spectrum will
become a scarce commodity. This calls for a reduction in the signaling
load between the mobile station and the base station in order to make
more bandwidth available for voice and data traffic. One way
to reduce the signaling load associated with paging and location area
updating is to deploy cellular networks with more intelligent
mobile tracking and location management techniques.
In this talk, we propose a novel paging architecture
that reduces the signaling load while expediting the paging process.
The method is based on the theory of optimal search
with discrete efforts, and exploits the observation that
paging a mobile station resident in one of several cells
is analoguous to searching an object hidden in one of a finite
number of boxes. Building on this analogy, we integrate some
wellknown optimal search strategies into a novel paging
technique. The proposed scheme requires minimal computational
power in the base stations and switching centers,
is fully compatible with standard mobility management techniques and
does not require additional database resources to keep track of the
movements of the mobile station within a location area.
Moreover, through simulations, we show that the
performance characteristics of this paging scheme are
often superior to that of the conventional blanket paging algorithm.
The main concern about realtime systems is the observance of deadlines,
generally called feasibility. If this property is satisfied the integrity
of the system is meant to be ensured.
To determine if a system is indeed feasible, it is necessary to find
the worst case response times of tasks, for the given scheduling policy.
However, deadlines are not always critical and thus it is not just necessary
to know if a task completes in time or not. If longer response times are
permitted, provided that they occur not to often, a less tight deadline
could be chosen, increasing the chance of the hole task set to be feasible.
Thus, it would be useful to know more about the distribution of response
times.
For the fixed priority preemptive schedulingpolicy, we have derived a
bound on the tail of the response time distributions, in the case where
interactivation and execution times are assumed to be independent and
bounded. We have studied their efficiency using simulations.
Robots are deployed by a Web search engine in order to maintain
the currency of its data base of Web pages.
In this talk we address some scheduling problems arising in these systems.
The first problem is concerned with the
robot scheduling policies that minimize the
fractions $r_i$ of time pages spend outofdate,
assuming independent Poisson pagechange processes, and
a general distribution for the page access time $X$. We show
that, if $X$ is decreased in the increasingconvex
ordering sense, then $r_i$ is decreased for all $i$ under any
scheduling policy, and that, in order to minimize expected total
obsolescence time of any page, the accesses to that page should be
as evenly spaced in time as possible.
We then investigate the problem of scheduling to minimize the
cost function $\sum c_i r_i,$ where the $c_i$ are given weights
proportional to the pagechange rates $\mu_i$. We give a tight bound on the
performance of such a policy and prove that the optimal frequency
at which the robot should access page $i$ is proportional
to $\ln (h_i)^{1}$, where $h_i := {\rm E}e^{\mu_iX}.$
Note that this reduces to being proportional to $\mu_i$ when
$X$ is a constant, but not, as one might expect, when $X$ has
a general distribution.
Next, we evaluate randomized accessing policies whereby
the choices of page access are determined by independent
random samples from the distribution $\{f_i\}$.
We show that when the weights $c_i$ in the cost function
are proportional to $\mu_i$, the minimum cost is achieved
when $f_i$ is proportional to $(h_i)^{1}  1$.
We shall also present and analyze a heuristic policy that is especially
suited to the asymptotic regime of large data bases.
Last, we discuss about the problem of determining the number
of robots to be used in order to maximize the indexing throughput
while keeping the communication and/or CPU overhead small.
To solve this problem, we use a queueing system with a finitecapacity buffer
to model the indexing engine. The cost function is defined
as a combination of the probabilities of empty buffer and full buffer.
Both dynamic and static policies are considered.
The first part of results is obtained jointly by Z. Liu and Ed. Coffman,
and will be presented by Z. Liu. The last part of results is obtained
by J. Talim, Z. Liu and P. Nain.
Let $X(n+1) = f(X(n), \xi_n)$ be a stochastic recursive
sequence taking values in a state space ${\cal X}$, and
$\phi : {\cal X} \to {\cal Y}$ be a measurable function.
We discuss conditions for the sequence $Y(n)= \phi (X(n))$
to converge to a proper limit in the total variation norm.
Algorithms for perfect or exact simulation of random samples
from the invariant measure of a Markov chain have received
considerable recent attention following the introduction of
the ``couplingfromthepast'' technique of Propp and Wilson.
1. We place such algorithms in the context of backward coupling
of stochastic recursive sequences.
2. We discuss also the problem how to eliminate the user
impatience bias.
In fact, the running time of the ProppWilson algorithm
(as well as that of similar ones) is a random variable with
an unbounded support, whose order of magnitude is typically
unknown a priori and which depends, in general, on the
state sampled, so a user with limited patience has to
introduce a systematic bias by aborting a long run.
A variety of formalisms exists for the modeling and description of
discrete event dynamic systems (DEDS), which typically allow for a
distributed state description and local state transition rules.
Petri nets are a well known example of this class.
Deciding functional or quantitative properties of a model at the level
of the modeling formalims itself is only possible in severly restricted cases.
Hence most analysis methods map a model to an associated labeled transition
system (LTS), e.g. a reachability graph, and analyze the LTS instead.
Realworld applications of this technique yield extremely large LTS with
obvious implications for computation times and space requirements.
Kronecker representations of LTS result in a suitable data structure to reduce
space requirements for the representation of an LTS significantly.
This talk gives an overview of different matrix representations of LTS
using Kronecker algebra. It focuses on the key ideas and observations
to make analysis algorithms for functional and quantitative analysis
work efficiently with Kronecker representations of LTS.
On appelle modele de tas de pieces, un systeme constitue d'un ensemble
fini de pieces (ou blocs solides ayant la forme de polyominos) et
d'une operation de concatenation qui consiste a empiler les pieces
suivant le mecanisme du jeu de Tetris. Dans le cas d'un modele aleatoire,
on choisit de facon i.i.d. la suite de pieces a empiler.
On rappellera dans un premier temps comment la hauteur d'un empilement
s'obtient a l'aide d'un systeme lineaire dans le semianneau (max,+).
On demontre ensuite que la vitesse de croissance asymptotique des
empilements est calculable a l'aide d'un automate fini:
(i) pour le comportement optimal si les pieces sont a hauteurs
entieres; (ii) pour le comportement en moyenne (cas aleatoire) si
les pieces sont a hauteurs entieres et sont 2 a 2 noncommutantes.
Le premier resultat se demontre a l'aide d'une generalisation des
Formes Normales de CartierFoata, et le second par une operation dite
de ``completion'' qui peut s'interpreter de facon algebrique comme
une residuation matricielle dans le semi anneau (max,+).
C'est un travail commun avec Stephane Gaubert, Inria Rocquencourt.
Recently, the fluid approximation approach (introduced by P.R.Kumar,
H.Chen and A.Mandelbaum, A.Rybko and A.Stolyar, J.Dai) became a very
popular
and useful tool for a stability study of queueing models.
Verbally, one can explain the main idea of this approach as follows.
For a Markov process X(t), t \geq 0 that characterizes a dynamical
behavior of a system, (a) one introduces an appropriate linear
scaling (the same in time and in space) where a scaling parameter is
a norm X(0)= const at time 0, and (b) one considers a family of
weak
limits when X(0) \to \infty . Each such a limit \varphi (t); t
\geq 0
is called a {\it fluid limit}, and the family of all fluid limits
(or its weak closure) is called a {\it fluid model}. A fluid model is
{\it stable} if there exist a finite constant T and a constant
\varepsilon \in (0,1] such that \varphi (T) \leq 1  \varepsilon
a.s. for any fluid limit.
It is known (J.Dai(95)) that if a fluid model
is stable, then (under certain integrability assumptions) the
underlying Markov process is positive recurrent.
We introduce a more general notion of stability of fluid model:
the fluid model is stable if there exist a constant \varepsion \in
(0,1] and, for any fluid limit \varphi, a stopping time
T_{\varphi} such that
(a) {\bf E} \varphi (T_{\varphi}) \leq 1  \varepsion ;
(b) random variables \{ T_{\varphi} \} are uniformly integrable.
We show that the stability of fluid model in this more general sense
implies the positive recurrence of Markov process as well.
The example of twoserver twostation polling model will be
considered also. It will be shown that
(i) the corresponding fluid model may be unstable in the ``pathwise''
sense but stable in our generalized one;
(ii) under certain conditions, the total amount of fluid may tend
to 0 even in the unstable case;
(iii) some intriguing open problems will be discussed also.
Multimedia traffic can tolerate some loss but has rigid
delay constraints. A natural QoS requirement
for a multimedia connection is a prescribed bound on the
the fraction of traffic that exceeds an endtoend delay limit.
To account for a diversity of traffic types,
the endtoend delay limit and the prescribed bound should
be connection specific.
In this talk we consider traffic management schemes that
guarantee QoS to multimedia traffic while simultaneously permitting
the network to have a large connectioncarrying capacity.
In order for the network to guarantee QoS,
each connection's traffic is regulated. In order to
support many connections, the links statistically
multiplex the connections' traffic. We propose
a pragmatic scheme for multimedia traffic which consists of
(i) cascaded leakybuckets for traffic regulation,
(ii) smoothers at the network edges, and (iii) bufferless statistical
multiplexers within the network. For this scheme we show that loss
probabilities are minimized with simple onebuffer smoothers which
operate at specific minimum rates. We also show that the worstcase
input traffic is extremal onoff traffic for all connections.
These two results lead to a straightforward scheme for guaranteeing
QoS to regulated traffic. We argue that the connectioncarrying
capacity of our scheme is significantly larger than schemes which
use sharedbuffer multiplexers in conjunction with reshapers.
Using MPEG video traces, we present numerical results which demonstrate
the methodology.
This is a joint work with Martin Reisslein and Srini Rajagopal.
L'équité (au sens ``maxmin'') d'une allocation de débits à des
flux traversant un réseau est une notion classique dans les réseaux
de données; on cherche généralement à allouer les ressources de
capacité de façon équitable afin de satisfaire au mieux chaque
usager. F.P. Kelly a récemment introduit la notion alternative
d'équité ``proportionnelle'', et a montré que le protocole TCP
aurait plus tendance à réaliser un partage équitable en ce second
sens plutôt qu'au sens maxmin.
On montrera de quelle manière un algorithme de contrôle par
fenêtres fixes est naturellement associé à l'une ou l'autre de ces
notions d'équité, selon que la politique de service à chaque file
est FIFO ou Fair Queueing. On présentera un algorithme stochastique,
de type Métropolis, permettant la réalisation approchée de tel ou
tel partage équitable des capacités. On s'intéressera ensuite à
la performance en termes de temps moyen de transfert de messages
associée au critère maxmin ou au critère proportionnel, sous
l'hypothèse qu'un protocole idéal réalise instantanément une
allocation équitable de débits aux messages en cours.
Contact: Zhen Liu
Last modified: Wed Apr 1 09:55:30 MET DST