Product form solution for g-networks with dependent service

Pavel Bocharov; Ciro D'Apice; Evgeny Gavrilov; Alexandre Pechinkin[1]

  • [1] Institute of Informatics Problems Russian Academy of Sciences Moscow, Russia

RAIRO - Operations Research - Recherche Opérationnelle (2004)

  • Volume: 38, Issue: 2, page 105-119
  • ISSN: 0399-0559

Abstract

top
We consider a G-network with Poisson flow of positive customers. Each positive customer entering the network is characterized by a set of stochastic parameters: customer route, the length of customer route, customer volume and his service length at each route stage as well. The following node types are considered: (0) an exponential node with servers, infinite buffer and FIFO discipline; (1) an infinite-server node; (2) a single-server node with infinite buffer and LIFO PR discipline; (3) a single-server node with infinite buffer and PS discipline. Negative customers arriving at each node also form a Poisson flow. A negative customer entering a node with customers in service, with probability chooses one of served positive customer as a “target”. Then, if the node is of a type 0 the negative customer immediately “kills” (displaces from the network) the target customer, and if the node is of types 1–3 the negative customer with given probability depending on parameters of the target customer route kills this customer and with complementary probability he quits the network with no service. A product form for the stationary probabilities of underlying Markov process is obtained.

How to cite

top

Bocharov, Pavel, et al. "Product form solution for g-networks with dependent service." RAIRO - Operations Research - Recherche Opérationnelle 38.2 (2004): 105-119. <http://eudml.org/doc/245053>.

@article{Bocharov2004,
abstract = {We consider a G-network with Poisson flow of positive customers. Each positive customer entering the network is characterized by a set of stochastic parameters: customer route, the length of customer route, customer volume and his service length at each route stage as well. The following node types are considered: (0) an exponential node with $c_n$ servers, infinite buffer and FIFO discipline; (1) an infinite-server node; (2) a single-server node with infinite buffer and LIFO PR discipline; (3) a single-server node with infinite buffer and PS discipline. Negative customers arriving at each node also form a Poisson flow. A negative customer entering a node with $k$ customers in service, with probability $1/k$ chooses one of served positive customer as a “target”. Then, if the node is of a type 0 the negative customer immediately “kills” (displaces from the network) the target customer, and if the node is of types 1–3 the negative customer with given probability depending on parameters of the target customer route kills this customer and with complementary probability he quits the network with no service. A product form for the stationary probabilities of underlying Markov process is obtained.},
affiliation = {Institute of Informatics Problems Russian Academy of Sciences Moscow, Russia},
author = {Bocharov, Pavel, D'Apice, Ciro, Gavrilov, Evgeny, Pechinkin, Alexandre},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
language = {eng},
number = {2},
pages = {105-119},
publisher = {EDP-Sciences},
title = {Product form solution for g-networks with dependent service},
url = {http://eudml.org/doc/245053},
volume = {38},
year = {2004},
}

TY - JOUR
AU - Bocharov, Pavel
AU - D'Apice, Ciro
AU - Gavrilov, Evgeny
AU - Pechinkin, Alexandre
TI - Product form solution for g-networks with dependent service
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2004
PB - EDP-Sciences
VL - 38
IS - 2
SP - 105
EP - 119
AB - We consider a G-network with Poisson flow of positive customers. Each positive customer entering the network is characterized by a set of stochastic parameters: customer route, the length of customer route, customer volume and his service length at each route stage as well. The following node types are considered: (0) an exponential node with $c_n$ servers, infinite buffer and FIFO discipline; (1) an infinite-server node; (2) a single-server node with infinite buffer and LIFO PR discipline; (3) a single-server node with infinite buffer and PS discipline. Negative customers arriving at each node also form a Poisson flow. A negative customer entering a node with $k$ customers in service, with probability $1/k$ chooses one of served positive customer as a “target”. Then, if the node is of a type 0 the negative customer immediately “kills” (displaces from the network) the target customer, and if the node is of types 1–3 the negative customer with given probability depending on parameters of the target customer route kills this customer and with complementary probability he quits the network with no service. A product form for the stationary probabilities of underlying Markov process is obtained.
LA - eng
UR - http://eudml.org/doc/245053
ER -

References

top
  1. [1] G.P. Basharin, P.P. Bocharov and Ya. A. Kogan, Analysis of Queues in Computer Networks. Theory and Design Methods, Moscow, Nauka (1989) (in Russian). Zbl0708.68005MR998560
  2. [2] G.P. Basharin and A.L. Tolmachev, The theory of queueing networks and its application to analysis of information-computer systems, in Itogi Nauki i Tekhniki. Teoria Veroyatnostei, Mat. Statistika, Teoret. Kibertetika 21 3-120. Moscow, VINITI (1983). Zbl0562.60098MR731075
  3. [3] F. Baskett, K.M. Chandy, R.R. Muntz and F.G. Palacios, Open, closed and mixed networks of queues with different classes of customers. J. ACM 22 (1975) 248-260. Zbl0313.68055MR365749
  4. [4] P.P. Bocharov and V.M. Vishnevskii, G-networks: development of the theory of multiplicative networks. Autom. Remote Control 64 (2003) 714-739. Zbl1066.90009MR2093399
  5. [5] J. Bourrely and E. Gelenbe, Mémoires associatives: évaluation et architectures. C.R. Acad. Sci. Paris II 309 (1989) 523-526. 
  6. [6] C. Cramer and E. Gelenbe, Video quality and traffic QoS in learning-based subsampled and receiver-interpolated video sequences. IEEE J. on Selected Areas in Communications 18 (2000) 150-167. 
  7. [7] Y. Feng and E. Gelenbe, Adaptive object tracking and video compression. Network and Information Systems J. 1 (1999) 371-400. 
  8. [8] E. Gelenbe, Queuing networks with negative and positive customers. J. Appl. Prob. 28 (1991) 656-663. Zbl0741.60091MR1123837
  9. [9] J.-M. Fourneau, E. Gelenbe and R. Suros, G-networks with multiple classes of positive and negative customers. Theoret. Comp. Sci. 155 (1996) 141-156. Zbl0873.68010MR1379069
  10. [10] E. Gelenbe, Réseaux stochastiques ouverts avec clients négatifs et positifs, et réseaux neuronaux. C.R. Acad. Sci. Paris II 309 (1989) 979-982. MR1029869
  11. [11] E. Gelenbe, Random neural networks with positive and negative signals and product form solution. Neural Comput. 1 (1989) 502-510. 
  12. [12] E. Gelenbe, Réseaux neuronaux aléatoires stables. C.R. Acad. Sci. II 310 (1990) 177-180. MR1053298
  13. [13] E. Gelenbe, Stable random neural networks. Neural Comput. 2 (1990) 239-247. MR1053298
  14. [14] E. Gelenbe, G-networks with instantaneous customer movement. J. Appl. Probab. 30 (1993) 742-748. Zbl0781.60088MR1232750
  15. [15] E. Gelenbe, G-Networks with signals and batch removal. Probab. Eng. Inform. Sci. 7 (1993) 335-342. 
  16. [16] E. Gelenbe, Learning in the recurrent random network. Neural Comput. 5 (1993) 154-164. 
  17. [17] E. Gelenbe, G-networks: An unifying model for queuing networks and neural networks. Ann. Oper. Res. 48 (1994) 433-461. Zbl0803.90058MR1264694
  18. [18] E. Gelenbe, The first decade of G-networks. Eur. J. Oper. Res. 126 (2000) 231-232. 
  19. [19] E. Gelenbe and J.M. Fourneau, Random neural networks with multiple classes of signals. Neural Comput. 11 (1999) 953-963. 
  20. [20] E. Gelenbe and J.-M. Fourneau, G-Networks with resets. Perform. Eval. 49 (2002) 179-192, also in Proc. IFIP WG 7.3/ACM-SIGMETRICS Performance ’02 Conf., Rome, Italy (2002). Zbl1043.68006
  21. [21] E. Gelenbe, P. Glynn and K. Sigman, Queues with negative arrivals. J. Appl. Probab. 28 (1991) 245-250. Zbl0744.60110MR1090463
  22. [22] E. Gelenbe and K. Hussain, Learning in the multiple class random neural network. IEEE Trans. on Neural Networks 13 (2002) 1257-1267. 
  23. [23] E. Gelenbe and A. Labed, G-networks with multiple classes of signals and positive customers. Eur. J. Oper. Res. 108 (1998) 293-305. Zbl0954.90009
  24. [24] E. Gelenbe and I. Mitrani, Analysis and Synthesis of Computer Systems. New York, London Academic Press (1980). Zbl0484.68026MR696380
  25. [25] E. Gelenbe and G. Pujolle, Introduction to Queueing Networks. New York, Wiley (1998). Zbl0654.60079MR874339
  26. [26] E. Gelenbe and M. Schassberger, Stability of product form G-Networks. Probab. Eng. Inform. Sci. 6 (1992) 271-276. Zbl1134.60396
  27. [27] E. Gelenbe, E. Seref and Z. Xu, Simulation with learning agents. Proc. of the IEEE 89 (2001) 148-157. 
  28. [28] E. Gelenbe and H. Shachnai, On G-networks and resource allocation in multimedia systems. Eur. J. Oper. Res. 126 (2000) 308-318. Zbl0960.90007MR1785797
  29. [29] J.R. Jackson, Networks of waiting lines. Oper. Res. 15 (1957) 234-265. MR93061
  30. [30] J.R. Jackson, Jobshop-like queueing systems. Manage. Sci. 10 (1963) 131-142. 
  31. [31] F.P. Kelly, Reversibility and Stochastic Networks. Chichester, Wiley (1979). Zbl0422.60001MR554920
  32. [32] D. Kouvatsos, Entropy maximisation and queueing network models. Ann. Oper. Res. 48 (1994) 63-126. Zbl0789.90032
  33. [33] A.V. Pechinkin and V.V. Rykov, Product form for open queueing networks with dependent service times, in Proc. Distributed Computer Communication Networks. Theory and Applications, Moscow: Institute for Information Transmission Problems RAS (1977) 171-178. 
  34. [34] M. Schwartz, Telecommunication Networks: Protocols, Modeling and Analysis. New York, Addison Wesley (1987). 
  35. [35] N.M. Van Dijk, Queueing Networks and Product Forms. New York, Wiley (1993). MR1266845
  36. [36] V.M. Vishnevskii, Theoretical Foundations of Computer Network Design. Moscow, Tekhnosfera 2003 (in Russian). 

NotesEmbed ?

top

You must be logged in to post comments.