28973 articles – 22398 references  [version française]

hal-00165807, version 1

## Asymptotic Results on Infinite Tandem Queueing Networks

François Baccelli () 1, Alexander Borovkov () 2, Jean Mairesse () 3

Probability Theory and Related Fields 118, 3 (2000) 365-405

Abstract: We consider an infinite tandem queueing network consisting of ./GI/1 stations with i.i.d. service times. We investigate the asymptotic behavior of t(n,k), the inter-arrival times between customers n and (n+1) at station k, and that of w(n,k), the waiting time of customer n at station k. We establish a duality property by which w(n,k) and the idle times'' y(n,k) play symmetrical roles. This duality structure, interesting by itself, is also instrumental in proving some of the ergodic results. We consider two versions of the model: the quadrant and the half-plane. In the quadrant version, the sequences of boundary conditions {w(0,k), k in N} and {t(n,0), n in N}, are given. In the half-plane version, the sequence {t(n,0), n in Z} is given. Under appropriate assumptions on the boundary conditions and on the services, we obtain ergodic results for both versions of the model. For the quadrant version, we prove the existence of temporally ergodic evolutions and of spatially ergodic ones. Furthermore, the process {t(n,k), n in N} converges weakly with k to a limiting distribution, which is invariant for the queueing operator. In the more difficult half plane problem, the aim is to obtain evolutions which are both temporally and spatially ergodic. We prove that [1/n \sum_{k=1}^n w(0,k) ] converges almost surely and in L1 to a finite constant. This constitutes a first step in trying to prove that {t(n,k), n in Z} converges weakly with k to an invariant limiting distribution.

• 1:  TREC (INRIA Rocquencourt)
• INRIA – Ecole normale supérieure de Paris - ENS Paris
• 2:  Sobolev Institute of Mathematics
• Novosibirsk State University
• 3:  Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA)
• CNRS : UMR7089 – Université Paris VII - Paris Diderot
• Domain : Computer Science/Discrete Mathematics
Mathematics/Probability
• Keywords : Tandem queueing networks – last passage percolation.

• hal-00165807, version 1
• oai:hal.archives-ouvertes.fr:hal-00165807
• From:
• Submitted on: Friday, 27 July 2007 15:42:40
• Updated on: Friday, 27 July 2007 15:42:40