International Journal of Advanced Engineering Application

Analysing Delay Distributions in Multiclass Discrete-Time Tandem Communication Networks

Author(s):Padmanabhan Eshwar Iyer1, Savitri Mohan Naidu2, Siddharth Bala Murugan3

Affiliation: 1,2,3 Rajagiri School of Engineering & Technology, Kochi-India

Page No: 28-37

Volume issue & Publishing Year: Volume 1 Issue 7,Nov-2024

Journal: International Journal of Advanced Engineering Application (IJAEA)

ISSN NO: 3048-6807

DOI:

Download PDF

Abstract:
Communication networks serve as the backbone of modern digital infrastructure, connecting multiple source-destination pairs through paths comprising intermediate nodes. These networks often experience stochastic delays due to contention from other traffic streams, particularly in tandem network configurations where multiple queues are traversed sequentially. Accurate modelling and analysis of these delays are crucial for designing efficient networks and ensuring quality of service. This research focuses on multiclass discrete-time tandem queueing networks, where multiple traffic classes, including primary and cross-traffic streams, pass through a series of interconnected queues. A computational framework is developed to compute the delay distributions and inter-departure times of packets, employing an exact algorithm based on truncated Lindley recursions and the convolve-and-sweep method. This framework allows for the analysis of non-renewal arrival processes, which are prevalent in real-world network scenarios. The study introduces a systematic approach to calculate stationary delay distributions at each queue and their cumulative impact on end-to-end delay. Furthermore, it establishes a theoretical lower bound on the variance of the total delay by leveraging the association property of random variables. This algorithmic solution is implemented as an object-oriented framework, providing flexibility for analysing various network configurations. Simulation results validate the theoretical model, demonstrating its capability to accurately predict delay distributions under different traffic patterns, including both geometric and heavy-tailed batch arrival distributions. The findings highlight the effectiveness of the proposed method in evaluating network performance metrics, making it a valuable tool for network engineers and researchers. This work lays the groundwork for future research into more complex network topologies and dynamic traffic conditions.

Keywords: Discrete-time queueing networks, tandem networks, delay analysis, Lindley recursion, computational algorithms, multiclass systems, non-renewal arrivals.

Reference:

• [1] D. Bertsekas and R. Gallager, Data Networks, 2nd ed. Prentice-Hall, 1992.
• [2] A. Kumar, D. Manjunath, and J. Kuri, Communication Networks: An Analytical Approach. Academic Press, 2004.
• [3] H. Bruneel and B. G. Kim, Discrete-Time Models for Communication Systems Including ATM. Kluwer Academic, 1993.
• [4] T. Zhang and B. Liu, “Exposing end-to-end delay in software-defined networking,” Int. J. Reconfigurable Comput., 2019.
• [5] J. Walrand, An Introduction to Queueing Networks. Prentice-Hall, 1988.
• [6] A. S. Alfa, Applied Discrete-Time Queues. Springer, 2016.
• [7] R. L. Cruz, “A calculus for network delay,” IEEE Trans. Inf. Theory, vol. 37, no. 1, pp. 114–131, 1991.
• [8] C. S. Chang, Performance Guarantees in Communication Networks. Springer, 2000.
• [9] W. Whitt, Stochastic-Process Limits. Springer, 2002.
• [10] L. Kleinrock, Queueing Systems, Volume I: Theory. Wiley-Interscience, 1975.
• [11] H. Daduna, Queueing Networks with Discrete Time. Springer, 2001.
• [12] O. P. Vinogradov, “Delay analysis in tandem queueing systems,” Adv. Appl. Probab., 1995.
• [13] M. J. Neely, “Exact queueing analysis of discrete time tandem networks,” in Proc. IEEE ICC, 2004.
• [14] G. Hasslinger and E. S. Rieger, “Analysis of open discrete time queueing networks,” J. Oper. Res. Soc., vol. 47, 1996.
• [15] D. P. Bertsekas, Dynamic Programming and Optimal Control. Athena Scientific, 2005.
• [16] S. Shenker, “Fundamental design issues for the future Internet,” IEEE J. Sel. Areas Commun., vol. 13, no. 7, 1995.
• [17] A. S. Tanenbaum and D. J. Wetherall, Computer Networks. Pearson, 2011.
• [18] D. Yates and J. Kurose, “Per-session delay distributions in communication networks,” in Proc. ACM SIGCOMM, 1993.
• [19] V. Ramaswami, “A stable recursion for Markov chains of M/G/1 type,” Stochastic Models, 1990.
• [20] O. J. Boxma, “Tandem queues with batch arrivals,” Stochastic Process. Appl., 1980.
• [21] M. Zukerman, Introduction to Queueing Theory and Stochastic Teletraffic Models. arXiv:1307.2968, 2021.
• [22] J. D. Esary, F. Proschan, and D. W. Walkup, “Association of random variables with applications,” Ann. Math. Statist., 1967.
• [23] V. Sharma and N. D. Gangadhar, “Computational analysis of tandem queueing networks with cross traffic,” Can. Conf. Broadband Res., 1998.
• [24] H. Chen, Optimization in Queueing Networks. Springer, 1998.
• [25] T. G. Robertazzi, Computer Networks and Systems: Queueing Theory and Performance Evaluation. Springer, 2000.
• [26] J. W. Cohen, The Single Server Queue. North-Holland, 1982.
• [27] M. Kiefer, “Discrete-time queueing models in telecommunication systems,” Queueing Syst., 2001.
• [28] S. J. Golestani, “A class of service scheduling algorithms for network delay analysis,” IEEE J. Sel. Areas Commun., vol. 13, no. 6, 1995.
• [29] Q. Li and H. Zhang, “Delay and queueing analysis in Internet routers,” Comput. Netw., 2012.
• [30] Y. Afek and A. Bremler-Barr, “End-to-end delay in communication networks,” IEEE Trans. Netw., 2010.
• [31] R. Buyya, High-Performance Cluster Computing. Prentice-Hall, 1999.
• [32] V. Paxson and S. Floyd, “Wide-area traffic patterns and characteristics,” IEEE/ACM Trans. Netw., 1995.
• [33] P. Gupta and P. R. Kumar, “The capacity of wireless networks,” IEEE Trans. Inf. Theory, 2000.
• [34] A. J. Viterbi, “Recursive algorithms in tandem queueing systems,” Queueing Syst., 1996.
• [35] S. K. Walley, “Discrete-time tandem networks with batch arrivals and departures,” J. Appl. Probab., 1997.
• [36] K. Pahlavan and P. Krishnamurthy, Networking Fundamentals: Wide, Local and Personal Area Communications. Wiley, 2009.
• [37] Z. Zhang, “Delay analysis in software-defined networking environments,” J. Commun. Netw., 2015.
• [38] S. Iyer and L. Kleinrock, “End-to-end delay behavior in queueing networks,” Perform. Eval., 1998.
• [39] D. Towsley, “Approximate analysis of tandem queueing systems,” ACM SIGMETRICS, 1987.
• [40] N. K. Sharma and R. Kaur, “Queueing models and performance metrics in computer networks,” IEEE Commun. Surv. Tutor., 2020.