Zero-automatic networks

ABSTRACT

We continue the study of zero-automatic queues first introduced in [3]. These queues are characterized by a special buffering mechanism evolving like a random walk on some infinite group or monoid. The simple M/M/1 queue and Gelenbe's G-queue with positive and negative customers are the two simplest 0-automatic queues. All 0-automatic queues are quasi-reversible [3]. In this paper, we introduce and study networks of 0-automatic queues. We consider two types of networks, with either a Jackson-like or a Kelly-like routing mechanism. In both cases, and under the stability condition, we prove that the stationary distribution of the buffer content has a "product-form" and can be explicitly determined.

REFERENCES

• 1: P. Brémaud. Markov chains: Gibbs fields, Monte Carlo simulation, and queues, volume 31 of Texts in Applied Mathematics. Springer-Verlag, New York, 1999.
• 2: J. W. Cohen. The single server queue. North-Holland, Amsterdam, 1982. 2nd edition.
• 3: T.-H. Dao-Thi and J. Mairesse. Zero-automatic queues. Formal Techniques for Computer Systems and Business Processes LNCS 3670, p. 64--78, Springer, 2005. A long version is available at http://www.liafa.jussieu.fr/~mairesse/Article/0queue.ps.gz
• 4: E. Dynkin and M. Malyutov. Random walk on groups with a finite number of generators. Sov. Math. Dokl., 2:399--402, 1961.
• 5: Jean-Michel Fourneau , Erol Gelenbe , Rina Suros, G-networks with multiple classes of negative and positive customers, Theoretical Computer Science, v.155 n.1, p.141-156, Feb. 26, 1996 [doi>10.1016/0304-3975(95)00018-6]
• 6: E. Gelenbe. Product-form queueing networks with negative and positive customers. J. Appl. Probab., 28(3), 1991.
• 7: E. Gelenbe , G. Pujolle , J. C. C. Nelson, Introduction to queueing networks, John Wiley & Sons, Inc., New York, NY, 1987
• 8: Y. Guivarc'h. Sur la loi des grands nombres et le rayon spectral d'une marche aléatoire. Astérisque, 74:47--98, 1980.
• 9: F. Kelly. Reversibility and Stochastic Networks. Wiley, New-York, 1979.
• 10: F. Ledrappier. Some asymptotic properties of random walks on free groups. In J. Taylor, editor, Topics in probability and Lie groups: boundary theory, number 28 in CRM Proc. Lect. Notes, pages 117--152. American Mathematical Society, 2001.
• 11: J. Mairesse. Random walks on groups and monoids with a Markovian harmonic measure. Electron. J. Probab., 10:1417--1441, 2005.
• 12: J. Mairesse and F. Mathéus. Random walks on free products of cyclic groups. To appear in J. London Math. Soc., 2006. Available at arXiv:math.PR/0509211, 2005.
• 13: M. Neuts. Matrix-geometric solutions in stochastic models: An algorithmic approach. Johns Hopkins University Press, Baltimore, Md., 1981.
• 14: S. Sawyer and T. Steger. The rate of escape for anisotropic random walks in a tree. Probab. Theory Related Fields, 76(2):207--230, 1987.
• 15: R. Serfozo. Introduction to Stochastic Networks. Springer, Berlin, 1999.
• 16: W. Woess. Random walks on infinite graphs and groups. Number 138 in Cambridge Tracts in Mathematics. Cambridge University Press, 2000.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Theory

Keywords:
Jackson network, Kelly network, product form, quasi-reversibility, queueing theory