An Algebra for Queueing Networks with Time Varying Service and its Application to the Analysis of Integrated Service Networks

Abstract : We introduce a queueing network model that allows us to capture the time-varying service delivered to a traffic stream due to the presence of random perturbations (e.g. cross-traffic in a communication network). We first present the model for a single queue and then describe how such queues may be interconnected using the operations of {\em fork (or in-synchronization)} and {\em join (or out-synchronization)}. Such networks may be seen as a generalization of stochastic event graphs, and of the class of fork-join networks. The departure processes in such a network satisfy a system of equations along with the exogenous arrival processes and the service processes of the various queues. This system can be seen as a general time-varying linear system in the $(\min,+)$ semi-field. We obtain an explicit representation of the departure process in terms of the exogenous arrival processes and the service processes. Sufficient conditions are derived for this system to have a unique solution. We also study liveness and absence of explosion in this class of networks. Under appropriate stationarity and ergodicity assumptions, we establish stability theorems for such networks. To this end we first obtain a rate result for the departure process in terms of the rates of the exogenous arrival process and the throughput of a saturated system. We then use this result to show that in a network with a single exogenous arrival, all queue lengths are finite with probability one if the arrival rate is less than the throughput of the saturated system, and to give a representation of the queue length process. This class of networks allows for a detailed description of controlled sessions in integrated service networks. We also show that it contains several earlier discrete event models of the literature pertaining to stochastic Petri nets, service curves and fork-join networks, and show how the present model unifies them in a single algebraic structure. This structure is that of a semi-ring of functions of two real variables, where the addition is the pointwise minimum and the multiplication a generalization of inf-convolution
Type de document :
Rapport
RR-3435, INRIA. 1998
Liste complète des métadonnées

https://hal.inria.fr/inria-00073255
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:21:28
Dernière modification le : samedi 27 janvier 2018 - 01:30:56
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:39:52

Fichiers

Identifiants

  • HAL Id : inria-00073255, version 1

Collections

Citation

Rajeev Agrawal, François Baccelli, Rajendran Rajan. An Algebra for Queueing Networks with Time Varying Service and its Application to the Analysis of Integrated Service Networks. RR-3435, INRIA. 1998. 〈inria-00073255〉

Partager

Métriques

Consultations de la notice

253

Téléchargements de fichiers

373