Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T10:14:37.896Z Has data issue: false hasContentIssue false
  • English
  • Français

A RANDOM ACCESS G-NETWORK: STABILITY, STABLE THROUGHPUT, AND QUEUEING ANALYSIS

Published online by Cambridge University Press:  11 June 2019

Ioannis Dimitriou Open the ORCID record for Ioannis Dimitriou [Opens in a new window]  and
Nikolaos Pappas
Ioannis Dimitriou
Affiliation:
Department of Mathematics, University of Patras, 26500 Patras, Greece E-mail: [email protected]
Nikolaos Pappas
Affiliation:
Department of Science and Technology, Linköping University, Campus Norrköping 60174, Norrköping, Sweden E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The effect of signals on stability, stable throughput region, and delay in a two-user slotted ALOHA-based random-access system with collisions is considered. This work gives rise to the development of random access G-networks, which can model security attacks, expiration of deadlines, or other malfunctions, and introduce load balancing among highly interacting queues. The users are equipped with infinite capacity buffers accepting external bursty arrivals. We consider both negative and triggering signals. Negative signals delete a packet from a user queue, while triggering signals cause the instantaneous transfer of packets among user queues. We obtain the exact stability region, and show that the stable throughput region is a subset of it. Moreover, we perform a compact mathematical analysis to obtain exact expressions for the queueing delay by solving a non-homogeneous Riemann boundary value problem. A computationally efficient way to obtain explicit bounds for the expected number of buffered packets at user queues is also presented. The theoretical findings are numerically evaluated and insights regarding the system performance are derived.

Keywords

boundary value problemsdelayg-networksstability analysisstable throughputrandom access
Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 35 , Special Issue 1: Learning, Optimization, and Theory of G-Networks , January 2021 , pp. 111 - 137
Copyright
Copyright © Cambridge University Press 2019

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1Abdelrahman, O.H. (2017). A Markov-modulated diffusion model for energy harvesting sensor nodes. Probability in the Engineering and Informational Sciences 31(4): 505–515.CrossRefGoogle Scholar
2Abramson, N. (1970). THE ALOHA SYSTEM: Another alternative for computer communications. In Proc., Fall Joint Computer Conference, AFIPS, NY, USA. ACM. pp. 281–285.CrossRefGoogle Scholar
3Artalejo, J. & Gomez-Corral, A. (1998). Analysis of a stochastic clearing system with repeated attempts. Communications in Statistics. Stochastic Models 14(3): 623–645.CrossRefGoogle Scholar
4Artalejo, J.R. & Gomez-Corral, A. (1999). On a single server queue with negative arrivals and request repeated. Journal of Applied Probability 36(3): 907–918.CrossRefGoogle Scholar
5Behroozi-Toosi, A.B. & Rao, R.R. (1992). Delay upper bounds for a finite user random-access system with bursty arrivals. IEEE Transactions on Communications 40(3): 591–596.10.1109/26.135729CrossRefGoogle Scholar
6Borst, S., Jonckheere, M., & Leskela, L. (2008). Stability of parallel queueing systems with coupled service rates. Discrete Event Dynamic Systems 18(4): 447–472.CrossRefGoogle Scholar
7Boucherie, R.J. & Boxma, O.J. (1996). The workload in the M/G/1 queue with work removal. Probability in the Engineering and Informational Sciences 10(2): 261–277.10.1017/S0269964800004320CrossRefGoogle Scholar
8Brun, O., Wang, L., & Gelenbe, E. (2016). Big data for autonomic intercontinental overlays. IEEE Journal on Selected Areas in Communications 34(3): 575–583.CrossRefGoogle Scholar
9Brun, O., Yin, Y., Gelenbe, E., Kadioglu, Y.M., Augusto-Gonzalez, J., & Ramos, M. (2018). Deep learning with dense random neural networks for detecting attacks against Iot-connected home environments. In Security in Computer and Information Sciences: First International ISCIS Security Workshop 2018, Euro-CYBERSEC 2018, London, UK, February 26–27, 2018. Lecture Notes CCIS No. 821, Springer Verlag.Google Scholar
10Caglayan, M.U. (2017). G-networks and their applications to machine learning, energy packet networks and routing: Introduction to the special issue. Probability in the Engineering and Informational Sciences 31(4): 381–395.CrossRefGoogle Scholar
11Chao, X. & Pinedo, M. (1993). On generalized networks of queues with positive and negative arrivals. Probability in the Engineering and Informational Sciences 7(3): 301–334.CrossRefGoogle Scholar
12Chen, Z., Pappas, N., Kountouris, M., & Angelakis, V. (2016). Throughput analysis of smart objects with delay constraints. In IEEE 17th International Symposium on A World of Wireless, Mobile and Multimedia Networks (WoWMoM), pp. 1–6.Google Scholar
13Chen, Z., Pappas, N., & Kountouris, M. (2017). Energy harvesting in delay-aware cognitive shared access networks. In IEEE International Conference on Communications Workshops (ICC Workshops), pp. 168–173.Google Scholar
14Chen, Z., Pappas, N., Kountouris, M., & Angelakis, V. (2018). Throughput with delay constraints in a shared access network with priorities. IEEE Transactions on Wireless Communications 17(9): 5885–5899.CrossRefGoogle Scholar
15Cohen, J. (1988). Boundary value problems in queueing theory. Queueing Syst. 3): 97–128.Google Scholar
16Cohen, J.W. (1992). Analysis of random walks. Amsterdam: IOS Press.Google Scholar
17Cohen, J. & Boxma, O. (1983). Boundary value problems in queueing systems analysis. Amsterdam, Netherlands: North Holland Publishing Company.Google Scholar
18Cramer, C. & Gelenbe, E. (2000). Video quality and traffic QoS in learning-based subsampled and receiver-interpolated video sequences. IEEE Journal on Selected Areas in Communications 18(2): 150–167.CrossRefGoogle Scholar
19Dimitriou, I. (2017). A queueing system for modeling cooperative wireless networks with coupled relay nodes and synchronized packet arrivals. Performance Evaluation 114: 16–31.CrossRefGoogle Scholar
20Dimitriou, I. (2017). A two class retrial system with coupled orbit queues. Probability in the Engineering and Information Sciences 31(2): 139–179.CrossRefGoogle Scholar
21Dimitriou, I. & Pappas, N. (2017). Stability and Delay Analysis of an Adaptive Channel-Aware Random Access Wireless Network. Cham: Springer International Publishing, pp. 63–80.Google Scholar
22Dimitriou, I. & Pappas, N. (2018). Stable throughput and delay analysis of a random access network with queue-aware transmission. IEEE Transactions on Wireless Communications 17(5): 3170–3184.CrossRefGoogle Scholar
23Dimitriou, I. & Pappas, N. (2019). Performance analysis of a cooperative wireless network with adaptive relays. Ad Hoc Networks 87: 157–173.CrossRefGoogle Scholar
24Dimitriou, I., Alouf, S., & Jean-Marie, A. (2015). A Markovian queueing system for modeling a smart green base station. In Beltrán, M., Knottenbelt, W. & Bradley, J. (eds.), Computer Performance Engineering. Cham: Springer International Publishing, pp. 3–18.CrossRefGoogle Scholar
25Do, T.V. (2011). An initiative for a classified bibliography on G-networks. Performance Evaluation 68(4): 385–394.CrossRefGoogle Scholar
26Ephremides, A. & Hajek, B. (1998). Information theory and communication networks: an unconsummated union. IEEE Transactions on Information Theory 44(6): 2416–2434.CrossRefGoogle Scholar
27Fayolle, G. & Iasnogorodski, R. (1979). Two coupled processors: The reduction to a Riemann-Hilbert problem. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 47(3): 325–351.CrossRefGoogle Scholar
28Fayolle, G., Gelenbe, E., Labetoulle, J., & Bastin, D. (1974). The stability problem of broadcast packet switching computer networks. Acta Informatica 4(1): 49–53.CrossRefGoogle Scholar
29Fayolle, G., Gelenbe, E., & Labetoulle, J. (1977). Stability and optimal control of the packet switching broadcast channel. J. ACM 24(3): 375–386.CrossRefGoogle Scholar
30Fayolle, G., Malyshev, V.A., & Menshikov, M. (1995). Topics in the constructive theory of countable Markov chains. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
31Fayolle, G., Iasnogorodski, R., & Malyshev, V. (2017). Random walks in the quarter-plane: Algebraic methods, boundary value problems, applications to queueing systems and analytic combinatorics. Berlin: Springer-Verlag.CrossRefGoogle Scholar
32Fourneau, J., Marin, A., & Balsamo, S. (2016). Modeling energy packets networks in the presence of failures. In 24th IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, MASCOTS 2016, London, United Kingdom, September 19–21, 2016, pp. 144–153.Google Scholar
33Fourneau, J.-M. & Ait El Majhoub, Y. (2017). Processor sharing G-queues with inert customers and catastrophes: A model for server aging and rejuvenation. Probability in the Engineering and Informational Sciences 31(4): 420–435.CrossRefGoogle Scholar
34Fourneau, J.-M. & Gelenbe, E. (2017). G-networks with adders. Future Internet 9(3): 34.CrossRefGoogle Scholar
35François, F. & Gelenbe, E. (2016). Towards a cognitive routing engine for software defined networks. In ICC 2016, IEEE, pp. 1–6.CrossRefGoogle Scholar
36Gakhov, F. (1966). Boundary value problems. Oxford: Pergamon Press.CrossRefGoogle Scholar
37Gelenbe, E. (1989). Random neural networks with negative and positive signals and product form solution. Neural Comput. 1(4): 502–510.CrossRefGoogle Scholar
38Gelenbe, E. (1991). Product-form queueing networks with negative and positive customers. Journal of applied probability 28(3): 656–663.CrossRefGoogle Scholar
39Gelenbe, E. (1992). Learning in the recurrent random neural network. In GELENBE, E. (ed.), Neural Networks. Amsterdam: North-Holland Publishing Company, pp. 1–12.Google Scholar
40Gelenbe, E. (1993). G-networks by triggered customer movement. Journal of Applied Probability 30(3): 742–748.CrossRefGoogle Scholar
41Gelenbe, E. (1993). G-networks with signals and batch removal. Probability in the Engineering and Informational Sciences 7(3): 335–342.CrossRefGoogle Scholar
42Gelenbe, E. (1994). G-networks: a unifying model for neural and queueing networks. Annals of Operations Research 48(5): 433–461.CrossRefGoogle Scholar
43Gelenbe, E. (2007). Steady-state solution of probabilistic gene regulatory networks. Physical review. E, Statistical, nonlinear, and soft matter physics 76(3 Pt 1): 031903.CrossRefGoogle ScholarPubMed
44Gelenbe, E. (2009). Steps toward self-aware networks. Communications of the ACM 52(7): 66–75.CrossRefGoogle Scholar
45Gelenbe, E. (2012). Energy packet networks: Adaptive energy management for the cloud. In CloudCP '12 Proceedings of the 2nd International Workshop on Cloud Computing Platforms, ACM, pp. 1.CrossRefGoogle Scholar
46Gelenbe, E. & Abdelrahman, O.H. (2018). An energy packet network model for mobile networks with energy harvesting. Nonlinear Theory and Its Applications, IEICE 9(3): 1–15.CrossRefGoogle Scholar
47Gelenbe, E. & Ceran, E.T. (2016). Energy packet networks with energy harvesting. IEEE Access 4: 1321–1331.CrossRefGoogle Scholar
48Gelenbe, E. & Cramer, C. (1998). Oscillatory corticothalamic response to somatosensory input. Biosystems 48(1–3): 67–75.CrossRefGoogle ScholarPubMed
49Gelenbe, E. & Labed, A. (1996). Esprit ltr project 8144 Lydia load balancing and G-networks: Design, implementation and evaluation. Technical Report, IHEI, Univ. Rene Descartes, Paris V.Google Scholar
50Gelenbe, E. & Labed, A. (1998). G-networks with multiple classes of signals and positive customers. European Journal of Operational Research 108(2): 293–305.Google Scholar
51Gelenbe, 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
52Gelenbe, E., Mao, Z., & Li, Y. (1999). Function approximation with spiked random networks. IEEE Trans. Neural Networks 10(1): 3–9.CrossRefGoogle ScholarPubMed
53Gelenbe, E. & Marin, A. (2015). Interconnected wireless sensors with energy harvesting. In Analytical and Stochastic Modelling Techniques and Applications – 22nd International Conference, ASMTA 2015, Albena, Bulgaria, May 26–29, 2015. Proceedings, pp. 87–99.CrossRefGoogle Scholar
54Gelenbe, E. & Morfopoulou, C. (2010). A framework for energy-aware routing in packet networks. The Computer Journal 54(6): 850–859.CrossRefGoogle Scholar
55Gelenbe, E. & Schassberger, R. (1992). Stability of product form G-networks. Probability in the Engineering and Informational Sciences 6(3): 271–276.CrossRefGoogle Scholar
56Gelenbe, E., Feng, Y., & Krishnan, K.R.R. (1996). Neural network methods for volumetric magnetic resonance imaging of the human brain. Proceedings of the IEEE 84(10): 1488–1496.CrossRefGoogle Scholar
57Georgiadis, L., Merakos, L., & Papantoni-Kazakos, P. (1987). A method for the delay analysis of random multiple-access algorithms whose delay process is regenerative. IEEE Journal on Selected Areas in Communications 5(6): 1051–1062.CrossRefGoogle Scholar
58Gómez-Corral, A. (2002). On a tandem G-network with blocking. Advances in Applied Probability 34(3): 626–661.CrossRefGoogle Scholar
59Grenet, I., Yin, Y., Comet, J.-P., & Gelenbe, E. (2018). Machine learning to predict toxicity of compounds. In 27th Annual International Conference on Artificial Neural Networks, ICANN18, accepted for publication. Springer Verlang.CrossRefGoogle Scholar
60Guillemin, F. & Pinchon, D. (2004). Analysis of generalized processor-sharing systems with two classes of customers and exponential services. Journal of Applied Probability 41(3): 832–858 09.CrossRefGoogle Scholar
61Harrison, P.G. & Pitel, E. (1995). Response time distributions in tandem G-networks. Journal of Applied Probability 32(1): 224–246.CrossRefGoogle Scholar
62Henderson, W., Northcote, B.S., & Taylor, P.G. (1994). State-dependent signalling in queueing networks. Advances in Applied Probability 26(2): 436–455.CrossRefGoogle Scholar
63Jain, G. & Sigman, K. (1996). Generalizing the Pollaczek-Khintchine formula to account for arbitrary work removal. Probability in the Engineering and Informational Sciences 10(4): 519–531.CrossRefGoogle Scholar
64Kadioglu, Y.M. (2017). Finite capacity energy packet networks. Probability in the Engineering and Informational Sciences 31(4): 477–504.CrossRefGoogle Scholar
65Kadioglu, Y.M. & Gelenbe, E. (2018). Product form solution for cascade networks with intermittent energy. IEEE Systems Journal, accepted for publication.Google Scholar
66Kim, H. & Gelenbe, E. (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 ScholarPubMed
67Kompella, S. & Ephremides, A. (2014). Stable throughput regions in wireless networks. Foundations and Trends in Networking 7(4): 235–338.CrossRefGoogle Scholar
68Laya, A., Alonso, L., & Alonso-Zarate, J. (2014). Is the random access channel of LTE and LTE-A suitable for M2M communications? A survey of alternatives. IEEE Communications Surveys and Tutorials 16(1): 4–16.CrossRefGoogle Scholar
69Loynes, R. (1962). The stability of a queue with non-independent inter-arrival and service times. Mathematical Proceedings of the Cambridge Philosophical Society 58: 497–520.CrossRefGoogle Scholar
70Luo, W. & Ephremides, A. (1999). Stability of N interacting queues in random-access systems. IEEE Transactions on Information Theory 45(5): 1579–1587.CrossRefGoogle Scholar
71Nain, P. (1985). Analysis of a two-node ALOHA-network with infinite capacity buffers. In Int. Seminar on Computer Networking and Performance Evaluation, pp. 49–63.Google Scholar
72Nauta, H. (1989). Ergodicity conditions for a class of two-dimensional queueing problems. PhD thesis, Math. Inst., Univ. of Utrecht.Google Scholar
73Naware, V., Mergen, G., & Tong, L. (2005). Stability and delay of finite-user slotted ALOHA with multipacket reception. IEEE Transactions on Information Theory 51(7): 2636–2656.CrossRefGoogle Scholar
74Nehari, Z. (1952). Conformal mapping. New York: McGraw-Hill.Google Scholar
75Osseiran, A., Boccardi, F., Braun, V., Kusume, K., Marsch, P., Maternia, M., Queseth, O., Schellmann, M., Schotten, H., Taoka, H., Tullberg, H., Uusitalo, M.A., Timus, B., & Fallgren, M. (2014). Scenarios for 5G mobile and wireless communications: the vision of the METIS project. IEEE Communications Magazine 52(5): 26–35.CrossRefGoogle Scholar
76Pappas, N. & Kountouris, M. (2014). Throughput of a cognitive radio network under congestion constraints: A network-level study. In 9th International Conference on Cognitive Radio Oriented Wireless Networks and Communications (CROWNCOM), pp. 162–166.Google Scholar
77Pappas, N. & Kountouris, M. (2019). Stable throughput region of the two-user interference channel. Ad Hoc Networks 85: 19–31.CrossRefGoogle Scholar
78Pappas, N., Kountouris, M., Ephremides, A., & Traganitis, A. (2015). Relay-assisted multiple access with full-duplex multi-packet reception. IEEE Transactions on Wireless Communications 14(7): 3544–3558.CrossRefGoogle Scholar
79Pappas, N., Kountouris, M., Jeon, J., Ephremides, A., & Traganitis, A. (2016). Effect of energy harvesting on stable throughput in cooperative relay systems. Journal of Communications and Networks 18(2): 261–269.Google Scholar
80Pappas, N., Dimitriou, I., & Chen, Z. (2018). Network-level cooperation in random access IoT networks with aggregators. In 2018 30th International Teletraffic Congress (ITC 30), volume 01, pp. 245–253.CrossRefGoogle Scholar
81Rao, R. & Ephremides, A. (1988). On the stability of interacting queues in a multiple-access system. IEEE Transactions on Information Theory 34(5): 918–930.CrossRefGoogle Scholar
82Sarigiannidis, P., Karapistoli, E., & Economides, A.A. (2017). Modeling the internet of things under attack: A G-network approach. IEEE Internet of Things Journal 4(6): 1964–1977.CrossRefGoogle Scholar
83Szpankowski, W. (1986). Bounds for queue lengths in a contention packet broadcast system. IEEE Transactions on Communications 34(11): 1132–1140.CrossRefGoogle Scholar
84Szpankowski, W. (1988). Stability conditions for multidimensional queueing systems with computer applications. Operations Research 36(6): 944–957.CrossRefGoogle Scholar
85Szpankowski, W. (1994). Stability conditions for some distributed systems: buffered random access systems. Advances in Applied Probability 26(2): 498–515.CrossRefGoogle Scholar
86Tong, L., Naware, V., & Venkitasubramaniam, P. (2004). Signal processing in random access. IEEE Signal Processing Magazine 21(5): 29–39.CrossRefGoogle Scholar
87Tsybakov, B.S. & Mikhailov, V.A. (1979). Ergodicity of a slotted ALOHA system. Problemy Peredachi Informatsii 15: 73–87.Google Scholar
88Wang, L. & Gelenbe, E. (2018). Adaptive dispatching of tasks in the cloud. IEEE Transactions on Cloud Computing 6(1): 33–45.CrossRefGoogle Scholar
89Yin, Y. (2017). Optimum energy for energy packet networks. Probability in the Engineering and Informational Sciences 31(4): 516–539.CrossRefGoogle Scholar
90Yin, Y. & Gelenbe, E. (2017). Single-cell based random neural network for deep learning. In Neural Networks (IJCNN), 2017 International Joint Conference, IEEE, pp. 86–93.CrossRefGoogle Scholar
91Zhang, Y. (2019). Optimal energy distribution with energy packet networks. Probability in the Engineering and Informational Sciences, pp. 1–17.CrossRefGoogle Scholar