Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-25T08:09:07.991Z Has data issue: false hasContentIssue false
  • English
  • Français

PRODUCT-FORM IN G-NETWORKS

Published online by Cambridge University Press:  18 May 2016

Andrea Marin
Andrea Marin*
Affiliation:
Department of Environmental Sciences, Informatics and Statistics Universià Ca’ Foscari Venezia, Italy E-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The introduction of the class of queueing networks called G-networks by Gelenbe has been a breakthrough in the field of stochastic modeling since it has largely expanded the class of models which are analytically or numerically tractable. From a theoretical point of view, the introduction of the G-networks has lead to very important considerations: first, a product-form queueing network may have non-linear traffic equations; secondly, we can have a product-form equilibrium distribution even if the customer routing is defined in such a way that more than two queues can change their states at the same time epoch. In this work, we review some of the classes of product-forms introduced for the analysis of the G-networks with special attention to these two aspects. We propose a methodology that, coherently with the product-form result, allows for a modular analysis of the G-queues to derive the equilibrium distribution of the network.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 30 , Issue 3: Erol Gelenbe's 70th Birthday , July 2016 , pp. 345 - 360
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
Copyright © Cambridge University Press 2016

References

1.Albarelli, A., Rodolà, E., Bergamasco, F., & Torsello, A. (2011). A non-cooperative game for 3D object recognition in cluttered scenes. In Proceedings of Int. Conf. on 3D Imaging, Modeling, Processing, Visualization and Transmission, 3DIMPVT, Hangzhou, China, pp. 252–259.CrossRefGoogle Scholar
2.Balsamo, S., Dei Rossi, G., & Marin, A. (2010). A numerical algorithm for the solution of product-form models with infinite state spaces. In Proceedings of EPEW (Aldini, A., Bernardo, M., Bononi, L., & Cortellessa, L.S., V. Eds.), Berlin Heidelberg: Springer, vol. 6342, pp. 191–206.CrossRefGoogle Scholar
3.Balsamo, S., Harrison, P.G., & Marin, A. (2010). A unifying approach to product-forms in networks with finite capacity constraints. In Proceedings of SIGMETRICS, New York, NY, USA, pp. 25–36.CrossRefGoogle Scholar
4.Balsamo, S., Harrison, P.G., & Marin, A. (2012). Methodological Construction of Product-form Stochastic Petri-Nets for Performance Evaluation. Journal of System and Software 85(7): 1520–1539.CrossRefGoogle Scholar
5.Balsamo, S. & Marin, A. (2007). Queueing networks in formal methods for performance evaluation. In Formal Methods for Performance Evaluation (Bernardo, M. & Hillston, S. J., Eds.), LNCS, vol. 4468, Berlin, Heidelberg: Springer, pp. 34–82.Google Scholar
6.Balsamo, S. & Marin, A. (2011). Performance engineering with product-form models: efficient solutions and applications. In Proceedings of ICPE’11—Second Joint WOSP/SIPEW International Conference on Performance Engineering, Karlsruhe, Germany, pp. 437–448.Google Scholar
7.Balsamo, S. & Marin, A. (2013). Separable solutions for Markov processes in random environments. European Journal of Operational Research 229(2): 391–403.CrossRefGoogle Scholar
8.Baskett, F., Chandy, K.M., Muntz, R.R., & Palacios, F.G. (1975). Open, closed, and mixed networks of queues with different classes of customers. Journal of ACM 22(2): 248–260.Google Scholar
9.Chao, X., Miyazawa, M., & Pinedo, M. (1999). Queueing networks. Customers, Signals and Product Form Solutions. West Sussex, England: Wiley.Google Scholar
10.Fourneau, J.M., Gelenbe, E., & Suros, R. (1996). G-Networks with multiple classes of positive and negative customers. Theoretical Computer Science 155: 141–156.CrossRefGoogle Scholar
11.Fourneau, J.M., Plateau, B., & Stewart, W.J. (2007). Product form for stochastic automata networks. In Proceedings of Valuetools. ICST, Brussels, Belgium: ICST, pp. 1–10.CrossRefGoogle Scholar
12.Fourneau, J.M., Plateau, B., & Stewart, W.J. (2008). An algebraic condition for product form in stochastic automata networks without synchronizations. Performance Evaluation 65(11–12): 854–868.CrossRefGoogle Scholar
13.Fourneau, J.M. & Quessette, F. (2006). Computing the steady-state distribution of G-networks with synchronized partial flushing. In Proceedings of ISCIS, 21th International Symposium, Istanbul, Turkey, pp. 887–896.Google Scholar
14.Fourneau, J.-M. (2007). Closed G-networks with resets: product form solution. In Proceedings of QEST, Edinburgh, Scotland, UK, pp. 287–296.Google Scholar
15.Fournau, J.-M., Kloul, L., & Quessette, F. (1995). G-networks with jumps back to zero. In Proceedings of ACM/IEEE MASCOTS, Duram, NC, USA, pp. 28–32.Google Scholar
16.Fourneau, J.-M., Kloul, L., & Quessette, F. (2000). Multiple class G-networks with iterated deletions. Performance Evaluation 42(1): 1–20.Google Scholar
17.Fourneau, J.-M., Kloul, L., & Verchère, D. (2000). Multiple class G-networks with list-oriented deletions. European Journal of Operational Research 126(2): 250–272.CrossRefGoogle Scholar
18.Fourneau, J.-M. & Wolter, K. (2015). Mixed networks with multiple classes of customers and restart. In Proceedings of ASMTA, Albena, Bulgaria, pp. 73–86.CrossRefGoogle Scholar
19.Gelenbe, E. (1989). Random neural networks with negative and positive signals and product form solution. Neural Computation 1(4): 502–510.Google Scholar
20.Gelenbe, E. (1993). G-networks with triggered customer movement. Journal of Applied Probability 30: 742–748.Google Scholar
21.Gelenbe, E. (1993). G-networks with signals and batch removal}. Probability in the Engineering and Informational Sciences 7: 335–342.Google Scholar
22.Gelenbe, E. (1993). G-networks: A unifying model for neural nets and queueing networks. In Proceedings of MASCOTS, San Diego, CA, USA, pp. 3–8.Google Scholar
23.Gelenbe, E. (1993). Learning in the recurrent random neural network. Neural Computation 5: 154–164.Google Scholar
24.Gelenbe, E. (1994). A unifying model for neural and queueing networks. Annals of Operations Research 48: 433–461.Google Scholar
25.Gelenbe, E. (2007). Steady-state solution of probabilistic gene regulatory networks. Physics Review E 76(3): 031903.Google Scholar
26.Gelenbe, E. (2009). Steps toward self-aware networks. Communications of the ACM 52(7): 66–75.CrossRefGoogle Scholar
27.Gelenbe, E. (2011). Energy packet networks: ICT based energy allocation and storage. In Proceedings of GreeNets, Colmar, France, pp. 186–195.Google Scholar
28.Gelenbe, E. (2012). Energy packet networks: smart electricity storage to meet surges in demand. In Proceedings of SIMUTOOLS, Sirmione-Desenzano, Italy, pp. 1–7.Google Scholar
29.Gelenbe, E. (2014). Adaptive management of energy packets. In Proceedings of IEEE COMPSAC, Vasteras, Sweden, pp. 1–6.CrossRefGoogle Scholar
30.Gelenbe, E., Feng, Y., & Krishnan, K. (1996). Neural network methods for volumetric magnetic resonance imaging of the human brain. Proceedings of IEEE 84(10): 1488–1496.Google Scholar
31.Gelenbe, E. & Fourneau, J.-M. (2002). G-networks with resets. Performance Evaluation 49: 179–191.Google Scholar
32.Gelenbe, E., Lent, R., & Xu, Z. (2001). Design and performance of cognitive packet networks. Performance Evaluation 46(2–3): 155–176.Google Scholar
33.Gelenbe, E., Lent, R., & Xu, Z. (2001). Measurement and performance of a cognitive packet network. Computer Networks 37(6): 691–701.Google Scholar
34.Gelenbe, E., Harman, K., & Krolik, J. (1998). Learning neural networks for detection and classification of synchronous recurrent transient signals. Signal Processing 64(3): 233–247.Google Scholar
35.Gelenbe, E. & Kazhmaganbetova, Z. (2014). Cognitive packet network for bilateral asymmetric connections. IEEE Transactions Industrial Informatics 10(3): 1717–1725.CrossRefGoogle Scholar
36.Gelenbe, E. & Labed, A. (1998). G-networks with multiple classes of signals and positive customers. European Journal of Operational Research 108(2): 293–305.CrossRefGoogle Scholar
37.Gelenbe, E. & Marin, A. (2015). Interconnected wireless sensors with energy harvesting. In Proceedings of ASMTA, Albena, Bulgaria, pp. 87–99.Google Scholar
38.Gelenbe, E. & Morfopoulou, C. (2011). A framework for energy-aware routing in packet networks. Computer Journal 54(6): 850–859.Google Scholar
39.Gelenbe, E. & Morfopoulou, C. (2012). Power savings in packet networks via optimised routing. MONET 17(1): 152–159.Google Scholar
40.Gelenbe, E. & Schassberger, M. (1992). Stability of product form G-networks. Probability in the Engineering and Informational Sciences 6: 271–276.CrossRefGoogle Scholar
41.Gelenbe, E., Sungur, M., Cramer, C., & Gelenbe, P. (1996). Traffic and video quality with adaptive neural compression. Multimedia Systems 4(6): 357–369.CrossRefGoogle Scholar
42.Gelenbe, E. & Timotheou, S. (2008). Random neural networks with synchronized interactions. Neural Computation 20(9): 2308–2324.Google Scholar
43.Gelenbe, E., Timotheou, S., & Nicholson, D. (2010). Fast distributed near-optimum assignment of assets to tasks. Computer Journal 53(9): 1360–1369.CrossRefGoogle Scholar
44.Gelenbe, E. & Tugce Ceran, E. (2015). Central or distributed energy storage for processors with energy harvesting. In Proceedings of Sustain IT, Madrid, Spain, pp. 1–3.Google Scholar
45.Gordon, W.J. & Newell, G.F. (1967). Cyclic queueing networks with exponential servers. Operations Research 15(2): 254–265.Google Scholar
46.Harrison, P.G. (2003). Turning back time in Markovian process algebra. Theoretical Computer Science 290(3): 1947–1986.Google Scholar
47.Harrison, P.G. (2004). Compositional reversed Markov processes, with applications to G-networks. Performance Evaluation 57(3): 379–408.Google Scholar
48.Harrison, P.G. & Lee, T.T. (2005). Separable equilibrium state probabilities via time reversal in Markovian process algebra. Theoretical Computer Science 346(1): 161–182.CrossRefGoogle Scholar
49.Harrison, P.G. & Marin, A. (2014). Product-forms in multi-way synchronizations. Comp. J. 57(11): 1693–1710.Google Scholar
50.Hillston, J. (1996). A compositional approach to performance modelling. Cambridge, UK: Cambridge University Press.Google Scholar
51.Jackson, J.R. (1963). Jobshop-like queueing systems. Management Science 10: 131–142.CrossRefGoogle Scholar
52.Kelly, F. (1979). Reversibility and stochastic networks. New York: Wiley.Google Scholar
53.Kim, H. & Gelenbe, H. (2012). Stochastic gene expression modeling with hill function for switch-like gene responses. IEEE/ACM Transactions on Computational Biology and Bioinformatics 9(4): 973–979.Google Scholar
54.Kim, H., Park, T., & Gelenbe, E. (2014). Identifying disease candidate genes via large-scale gene network analysis. IJDMB 10(2): 175–188.Google Scholar
55.Marin, A., Balsamo, S., & Harrison, P.G. (2012). Analysis of stochastic Petri nets with signals. Performance Evaluation 69(11): 551–572.Google Scholar
56.Marin, A. & Bulò, S.R. (2009). A general algorithm to compute the steady-state solution of product-form cooperating Markov chains. In Proceedings of MASCOTS, London, UK, September 2009, pp. 515–524.CrossRefGoogle Scholar
57.Marin, A., Rota Bulò, S., & Balsamo, S. (2012). A numerical algorithm for the decomposition of cooperating structured Markov processes. In Proceedings of MASCOTS, pp. 401–410.Google Scholar
58.Marin, A. & Vigliotti, M.G. (2010). A general result for deriving product-form solutions of Markovian models. In Proceedings of First Joint WOSP/SIPEW International Conference on Performance Engineering, San Josè, CA, USA: ACM, pp. 165–176.CrossRefGoogle Scholar
59.Muntz, R.R. (1972). Poisson departure processes and queueing networks. Yorktown Heights, New York, Technical Report. IBM Research Report RC4145.Google Scholar
60.Lazowska, E.D., Zahorjan, J.L., Graham, G.S., & Sevcick, K.C. (1984). Quantitative system performance: computer system analysis using queueing network models. Englewood Cliffs, NJ: Prentice-Hall.Google Scholar
61.Phan, H.T.T., Sternberg, M.J.E., & Gelenbe, E. (2012). Aligning protein-protein interaction networks using random neural networks. In Proceedings of IEEE International Conference on Bioinformatics and Biomedicine, BIBM, Philadelphia, PA, USA, pp. 1–6.Google Scholar
62.Plateau, B. (1985). On the stochastic structure of parallelism and synchronization models for distributed algorithms. SIGMETRICS Perform. Eval. Rev. 13(2): 147–154.CrossRefGoogle Scholar
63.Torsello, A., Rodolà, E., & Albarelli, A. (2011). Sampling relevant points for surface registration. In Proceedings of International Conference on 3D Imaging, Modeling, Processing, Visualization and Transmission, 3DIMPVT, Hangzhou, China, pp. 290–295.Google Scholar