Mardi 24 juin 1997, 10:00, Salle du Conseil
Ger Koole (Université d'Amsterdam, Pays Bas)
Partial information and routing to parallel servers.
Smoothing, Statistical Multiplexing and Call Admission Control for
Stored Video
Zhili ZHANG
(University of Massachusetts)
VBR compressed video is known to exhibit significant, multiple-time-scale
rate variability. A number of researchers have considered transmitting stored
video from a server to a client using smoothing algorithms to reduce this
rate variability. These algorithms exploit client buffering
capabilities and determine a "smooth" rate transmission schedule, while
ensuring that a client buffer neither overflows nor underflows.
In this paper, we investigate how video smoothing impacts the statistical
multiplexing gains available with such traffic and
show that a significant amount of statistical multiplexing gain can
be still be achieved.
We then examine the implication of these results
on network resource management and call admission control when
transmitting smooth stored video using variable-bit-rate (VBR) service
and {\em statistical Quality-of-Service (QoS) guarantees}.
Specifically, we present a
call admission control scheme based on a Chernoff bound method that uses a
simple, novel traffic model requiring only a few parameters. This scheme
provides an easy and flexible mechanism for supporting multiple VBR
service classes with different QoS requirements. We evaluate the efficacy of
the call admission control scheme over a set of MPEG video traces.
Rate based flow control with bandwidth information
Eitan Altman (INRIA Sophia Antipolis)
The ATM Forum has chosen the rate-based approach for flow control of
ABR traffic in ATM, and has specified the behavior of the source and
destination, as well as the manner in which feedback information
should be conveyed back to the source. The decision on the precise
control mechanism, however, has been left to the designer of the
switches. We propose in this paper a reactive control scheme that is
based only on information on the available bandwidth. We analyze its
stability, and test its performance by simulations in the
presence of other higher priority video traffic.
Décodage de Viterbi concurrent pour les réseaux de Petri stochastiques,
avec application au diagnostic dans les réseaux de télécommunications
Albert Benveniste (INRIA-IRISA)
Travaux joints par Renée Boubour et Claude Jard (Projet Pampa),
et Armen Aghasaryan, Eric Fabre et Albert Benveniste (Projet Sigma2).
L'objectif général est de concevoir un système de diagnostic de pannes
dans les réseaux de télécommunications, qui soit autant que possible
distribué. Ce qui signifie en pratique que l'on cherche à ce que les
capteurs répartis dans le réseau à surveiller, au lieu de simplement
remonter les alarmes brutes au superviseur (créant ainsi un sur-traffic
et rendant critique le superviseur centralisé), élaborent de manière
concurrente un résumé d'information ("statistique suffisante") plus
compact, qui peut être condensé à son tour, hiérarchiquement, jusqu'à
remontée finale au superviseur. On illustrera le propos par la
surveillance d'un petit bout de réseau SDH (dans le cadre d'une
CTI-CNET).
Pour cela, l'idée est d'étendre l'approche HMM (couramment utilisée en
reconnaissance de la parole, mais aussi, moins couramment, en
surveillance de systèmes industriels) aux systèmes distribués. D'où le
remplacement du modèle semi-Markovien par un Réseau de Petri
stochastique.
Afin de tirer au mieux avantage des Réseaux de Petri comme modèles de
systèmes concurrents, on adopte le point de vue moderne des sémantiques
en ordres partiels, ainsi que des techniques de dépliage de réseaux de
Petri. Renée Boubour et Claude Jard ont ainsi mis au point un algorithme
concurrent de reconnaissance de toutes les séquences d'états compatibles
avec les observations faites sur le réseau. D'autre part, Armen
Aghasaryan, Eric Fabre et Albert Benveniste ont étendu cet algorithme à
la prise en compte des vraisemblances des diverses histoires
compatibles, afin de les discriminer. Ceci a nécessité: 1/ la définition
d'un nouveau type de Réseau de Petri stochastique, compatible avec une
sémantique en ordres partiels, et 2/ la mise au point de l'algorithme de
Viterbi associé.
Thomas Bonald (INRIA Sophia Antipolis)
On s'intéresse ici à un système de polling mixte, c'est à dire comportant
deux types de clients : les clients exogènes, qui arrivent dans le
système, et une fois servis, le quittent définitivement, et les clients
permanents, en nombre fixe, qui circulent en permanence dans le réseau
en suivant une route aléatoire. Les différents régimes de service
considérés sont les régimes `exhaustif', `gated' et `globally-gated'.
On montre par une approche fluide qu'une condition nécessaire et suffisante
de Harris récurrence positive du processus de Markov décrivant le système est,
au cas critique près, $\rho<1$, où $\rho$ est le facteur de charge total
des flux exogènes. En particulier, cette condition ne dépend pas des clients
permanents.
Matthias Grossglauser (INRIA Sophia Antipolis)
Measurement-based Admission Control (MBAC) is an attractive mechanism
to concurrently offer Quality of Service (QoS) to users,
without requiring a-priori traffic specification and on-line policing.
However, several aspects of such a system need to be clearly understood
in order to devise robust MBAC schemes.
Through a sequence of increasingly sophisticated stochastic models,
we study the impact of parameter estimation errors, of flow arrival
and departure dynamics, and of estimation memory on the performance
of an MBAC system.
We show that a {\em certainty equivalence} assumption, i.e., assuming
that the measured parameters are the real ones, can grossly compromise
the target performance of the system. We quantify the improvement in
performance as a function of the memory size of the estimator and a
more conservative choice of the certainty-equivalent parameters. Our
results yield valuable new insight into the performance of MBAC
schemes, and represent quantitative guidelines for the design of
robust schemes.
Existence, unicite et attractivite du point fixe d'une file
./GI/1/\infty
Jean Mairesse (CNRS, Universite Paris 7)
On etudie une infinite de files ./GI/1/\infty en serie, alimentees par
un processus d'arrivee stationnaire et ergodique. A la station k, le
temps de service du client n et l'inter-arrivee entre les clients n et
n+1 sont notes respectivement s(n,k) et t(n,k). On suppose les s(n,k)
i.i.d. et verifiant la condition
\exists a >0, E[ s(0,0)^2[\log^{2+a} s(0,0)]^{+} ] < \infty
On considere le systeme sous la condition usuelle de stabilite:
1=E[s(0,0)] < E[t(0,0)]=\alpha
Sous ces hypotheses, on prouve l'existence d'un processus
d'inter-arrivees stationnaire unique T={t_n,n\in \Z}
verifiant E[t_0]=\alpha et tel que {t(n,k),n\in \Z} converge
faiblement vers T.
D'autre part, on prouve que T est un `point fixe' pour la file
d'attente, c'est a dire que si {t(n,0), n\in \Z}
est distribue suivant T, alors {t(n,1), n\in \Z} verifie la meme
propriete.
Ce resultat generalise les resultats obtenus par Anantharam et
Mountford et Prabhakar pour le cas de services exponentiels.
Asymptotic Behavior of a Multiplexer Fed by a Long-Range Dependent Process.
Philippe Nain (INRIA Sophia Antipolis)
We study the asymptotics of the queue length in a buffer
fed by an $M/G/\infty$ process where $G$ is a subexponential distribution.
More precisely, we derive asymptotic upper and lower bounds on the
queue length distribution.
We find the bounds to be tight in some instances, e.g.,
$G$ corresponding to either the Pareto or lognormal distribution and
$c-\rho< 1$ where $c$ is the rate at which the buffer receives service
and $\rho$ is the arrival rate to the buffer.
Stochastic Bounds for Queueing Systems with Multiple On-Off Sources.
Zhen Liu (INRIA Sophia Antipolis)
Consider a queueing system where the input traffic consists of
background traffic, modeled by a Markov Arrival Process (MAP),
and foreground traffic modeled by $N \geq 1$ homogeneous on-off sources.
The queueing system has an increasing and concave service rate,
which includes as a particular case multi-server queueing systems.
Both the infinite-capacity and the finite-capacity buffer cases
are analyzed. We show that the queue length in the infinite-capacity buffer
system (respectively the number of losses in finite-capacity buffer system)
is larger in the increasing convex order sense
(respectively the strong stochastic order sense)
than the queue length (respectively the number of losses)
of the queueing system with the same background traffic and
$MN$ homogeneous on-off sources of the same total intensity
as the foreground traffic, where $M$ is an arbitrary integer.
As a consequence, the queue length and the loss with a foreground traffic
of multiple homogeneous on-off sources
is upper bounded by that with a single on-off source
and lower bounded by a Poisson source,
where the bounds are obtained in the increasing convex order
(respectively the strong stochastic order).
We also compare $N\geq 1$ homogeneous arbitrary two-state
Markov Modulated Poisson Process (MMPP) sources.
We prove the monotonicity of the queue length
in the transition rates and its convexity in the arrival rates.
In order to establish these results, we propose a new approach
for the stochastic comparison of queues using dynamic programming.
Such an approach seems to be promising for the comparison of other Markovian
traffic models.
Ensembles d'arrêt: résultats de type Gamma et propriétés de recouvrement
Sergei Zouev (INRIA Sophia Antipolis)
Récemment les résultats de type Gamma suivants ont
été démontrés. étant
donné le nombre $N$ des points d'un processus de Poisson
homogène qui définissent une figure aléatoire, le volume de
cette dernière est distribué selon une loi $\Gamma(N,\lambda)$,
o\`u $\lambda$ est l'intensité du processus. Le but de cet
article est de donner une autre description de la classe des
ensembles aléatoires pour lesquels des résultats de ce type sont
valides. Nous montrons que cette classe est peut être définie
comme celle des \emph{ensembles d'arrêt} par rapport à la
filtration naturelle du processus ponctuel avec des certains
propriétés de similarité. Le preuve est très courte et
utilise une technique de martingale pour les processus
directionnels, en particulier, l'analogue du théorème d'arrêt
de Doob. Cette approche donne un
nouveau point de vue sur la nature des objets géométriques construits
à partir des points d'un processus. Nous montrons par exemple que
dans le cas Poissonnien, la probabilité qu'un point soit contenu
dans un ensemble d'arrêt ne dépend pas du fait que ce point est
un point du processus ou non.
Performance Bounds for Guaranteed and Adaptive Services
Rajeev Agrawal (University of Wisconsin-Madison)
We investigate issues related to the efficient support of
guaranteed and adaptive service categories in integrated services
networks. The guaranteed service category is targeted at real-time
applications that require hard end-to-end delay bounds for
burstiness constrained traffic, while the adaptive service
category is intended for sessions that have a minimum bandwidth
requirement, and use a window based flow control mechanism to avail
themselves of unused bandwidth in the network. The analytic
framework presented here uses two basic network elements - regulators
and schedulers. Regulators enforce burstiness constraints on the
traffice flow while schedulers ensure that a certain level of
service (quantified by a service curve) is provided to the session
by each network element it traverses. We model guaranteed service
sessions as feed-forward networks of regulators and schedulers,
and adaptive service sessions as similar networks with feedback.
Our formulation is more general than prior work on schedulers
and regulators, and allows for easy aggregation rules for networks
of these elements. We present these rules and discuss several
corollaries of this network calculus. In particular, we obtain bounds
on delay, queue length and burstiness for unicast guaranteed sessions,
and also discuss the relationship between throughput and buffering
requirements for unicast and multicast adaptive sessions with
end-to-end and hop-by-hop window flow control.
Multimodularity (Part II):
applications in (max,+) linear systems and routing in N queues.
Bruno Gaujal (INRIA Sophia Antipolis)
This talk is the sequence of Eitan Altman's one.
We show that the travelling time of a customer in any (max,+)
system is multimodular w.r.t. the arrival sequence.
This is used to exhibit the admission sequence
that minimises the travelling time under rate constraints.
In the second part of the talk, we recall general
results on multicriteria optimization and
their relation with balanced sequences.
This general framework is applied for routing in several queues.
As an example, the optimality of round robbin routing
into homogeneuous queues comes out as a simple corollary
of the methodology.
Network Calculus Made Easy
Jean-Yves Le Boudec (EPFL, Suisse)
We define general concepts that extend, and simplify, the network
calculus developed by Cruz for
guaranteed quality of service networks. We introduce two operators, on
arrival and service curves, and show how
their systematic use simplifies the derivation of many fundamental
results. We define a general form of deterministic effective
bandwidth that is particularly simple and efficient to use. We apply
the concepts to derive new results concerning shaping and multiplexing
of several flows onto one single flow. We show that, for a very broad
family of shapers, namely those which shape according to a concave
curve, the output of a shaper is still constrained by the same arrival
curve as the input, in addition to being constrained by the shaper
curve.
Modèles markoviens de ressources partagées
Florence Forbes (University of Washington)
Selon les domaines d'applications, différentes façons de modéliser le
partage de ressources ont été envisagées. Un des premiers modèles
apparus est le ``Dining Philosophers' Problem'' de Dijkstra, généralisé
par la suite par Chandy et Misra avec le ``Drinking Philosophers' Problem''.
Nous nous intéressons à des versions markoviennes de ces situations, dans
lesquelles les durées pour la prise et l'utilisation des ressources sont
aléatoires. Nous utilisons le formalisme des systèmes de particules.
Nous présentons une nouvelle classe de
modèles markoviens de ressources partagées pour lesquels nous
généralisons des outils classiques pour les systèmes de spins.
Nous étudions l'équilibre de ces systèmes à l'aide de
résultats de réversibilité et envisageons
des techniques de comparaison stochastique pour évaluer les
performances des systèmes et obtenir des résultats d'ergodicité.
Pour des systèmes finis, nous
donnons quelques calculs explicites de mesures d'équilibre. Des systèmes
qui augmentent en taille et en complexité peuvent être approchés par des
systèmes infinis. Pour de tels systèmes nous mettons en évidence des
phénomènes de transition de phase.
Dernière modification: 28 janvier 1997
Contact: Zhen Liu