Open Access Open Access  Restricted Access Subscription or Fee Access

Complete Computational Solution of Multi-Class Fluid Queueing Communication Network Models with Piecewise Constant Rate Inputs


(*) Corresponding author


Authors' affiliations


DOI: https://doi.org/10.15866/irecap.v12i3.22171

Abstract


This paper develops an explicit characterization and computation of the queueing processes associated with finite buffered multiclass fluid queues and their tandem networks under strict priority and with PieceWise Constant Rate (PWCR) inputs which arise in the performance analysis of communication networks. Analytical and exact computational solutions are developed for accepted arrival, fluid level and departure processes which allow solutions for all other queueing processes. A decomposition of the multiclass queue into a hierarchical sequence of single class queues, termed Virtual Queues, is established and the solutions of each class of the original queue are computed from those of the Virtual Queues taking into account the loosely coupled dynamics of these Virtual Queues. A uniform time sampling sequence, dynamically constructed from the input rate change instances and the boundary hitting times, is employed to develop the iterative transient sample path solutions of all the queueing processes. The processes of a multiclass queue with PWCR inputs are shown to be PWCR processes. The computational solution is extended to tandem networks of multiclass queues in which a class can have different static priorities along its path. The developed algorithm is applied to solve a tandem communication network with three-state Markov modulated voice source inputs. A parametric study of the voice network in terms of long-term time-averaged behaviour of its queueing processes is carried out.
Copyright © 2022 Praise Worthy Prize - All rights reserved.

Keywords


Communication Network; Multiclass; Priority; Fluid Queue; Numerical Solution; Finite Buffer; Tandem Network; Voice Source; Markov modulated; Piecewise Constant Rate (PWCR

Full Text:

PDF


References


V. G. Kulkarni, Fluid Models for Single Buffer Systems, in Frontiers in Queueing: Models and Applications in Science and Engineering, J. H. Dshalalow, Ed. (CRC Press, 1997, pp. 321-338).

N. U. Prabhu, From Dams to Telecommunications: A Survey of Basic Models, in Advances on Methodological and Applied Aspects of Probability and Statistics, N. Balakrishnan, Ed. (Taylor and Francis, 2002, pp. 3-11).
https://doi.org/10.1201/9780203493212-1

G. F. Newell, Applications of Queueing (Chapman and Hall, 1982).
https://doi.org/10.1007/978-94-009-5970-5

N. U. Prabhu, Stochastic Storage Processes: Queues, Insurance Risk and Dams (Springer US, 1980).
https://doi.org/10.1007/978-1-4684-0113-4

S. Asmussen, Applied Probability and Queues, 2nd ed. (Springer-Verlag, 2003).

J. S. Vandergraft, A Fluid Flow Model of Networks of Queues, Management Science, vol. 29, (no. 10), pp. 1198- 1208, 1983.
https://doi.org/10.1287/mnsc.29.10.1198

Z. Xu, Y. Yin, X. Chao, H. Zhu, J. Ye, A Generalized Fluid Model of Ride-Hailing Systems, Transportation Research Part B: Methodological, vol. 150, pp. 587-605, 2021.
https://doi.org/10.1016/j.trb.2021.05.014

A. El-Baz, A. Tarabia, A. Darwiesh, Cloud Storage Facility as a Fluid Queue Controlled by Markovian Queue, Probability in the Engineering and Informational Sciences, vol. 36 (no. 2), pp. 237-253, 2021.
https://doi.org/10.1017/S0269964820000613

C. S. Chang, Stability, Queue length and Delay of Deterministic and Stochastic Queueing Networks, IEEE Transactions on Automatic Control, vol. 39, pp. 913-931, 1994.
https://doi.org/10.1109/9.284868

O. Boxma, B. Zwart, Fluid Flow Models in Performance Analysis, Computer Communication, vol. 131, pp. 22-25, 2018.
https://doi.org/10.1016/j.comcom.2018.07.009

J. G. Dai, Stability of Fluid and Stochastic Processing Networks, no. 9, MathPhySto Miscellanea Publication, (Center for Mathematical Physics and Stochastics, 1999).

W. Whitt, Stochastic Process Limits: An Introduction to Stochastic Process Limits and their Application to Queues (Springer Verlag, 2002).
https://doi.org/10.1007/b97479

M. Lelarge, Fluid Limit of Generalized Jackson Queue- ing Networks with Stationary and Ergodic Arrivals and Service Times, Journal of Applied Probability, vol. 42, pp. 491-512, 2005.
https://doi.org/10.1239/jap/1118777184

A. Kumar, D. Manjunath, J. Kuri, Communication Networking: An Analytical Approach (Academic Press, 2004).

D. Anick, D. Mitra, M. M. Sondhi, Stochastic The- ory of a Data-handling System with Multiple Sources, Bell Systems Technical Journal, vol. 61, pp. 1871-1894, 1982.
https://doi.org/10.1002/j.1538-7305.1982.tb03089.x

R. W. Brockett, W. B. Gong, Y. Guo, Stochastic Analysis for Fluid Queueing Systems, in Proceedings IEEE Conference on Decision and Control (CDC), pp. 3077-3082, 1999.

G. Latouche, G. Nguyen, Analysis of Fluid Flow Models, Queueing Models and Service Management, vol. 1, (no. 2), pp. 1-29, 2018.

S. Meyn, Control Techniques for Complex Networks ( Cambridge University Press, 2008).
https://doi.org/10.1017/CBO9780511804410

C. Maglaras, Discrete Review Policies for Scheduling Stochastic Networks: Trajectory Tracking and Fluid-Scale Asymptotic Optimality, Annals of Applied Probability, vol. 10, pp. 897-929, 2000.
https://doi.org/10.1214/aoap/1019487513

D. Shah, D. Wischik, Switched Networks with Maximum Weight Policies: Fluid Approximation and Multiplicative State Space Collapse, Annals of Applied Probability, vol. 22, (no. 1), pp. 70-127, 2012.
https://doi.org/10.1214/11-AAP759

Y. Fu, R. Williams, Asymptotic Behavior of a Critical Fluid Model for Bandwidth Sharing with General File Size Distributions, Annals of Applied Probability, Accepted, 2021.
https://doi.org/10.1214/21-AAP1723

Y. Liu, F. Lo Presti, V. Misra, D. Towsley, Y. Gu, Fluid Models and Solutions for Large-scale IP Networks, Performance Evaluation Review, vol. 31, (no. 1), pp. 91-101, 2003.
https://doi.org/10.1145/885651.781039

F. Baccelli, D. Hong, Flow Level Simulation of Large IP Networks, in Proc. of IEEE INFOCOM 2003, vol. 3, 2003, pp. 1911-1921.

J. Incera, R. Marie, D. Ros, G. Rubino, FluidSim: A Tool to Simulate Fluid Models of High-speed Networks, Performance Evaluation, vol. 44, (no. 1), pp. 25-49, 2001.
https://doi.org/10.1016/S0166-5316(00)00059-6

B. Liu, D. R. Figueiredo, Y. Guo, J. Kurose, D. Towsley, A Study of Networks Simulation Efficiency: Fluid Simulation vs. Packet-level Simulation, in Proc. IEEE INFOCOM 2001, vol. 3, 2001, pp. 1244-1253.

H. Kim, J. Lee, Variable Step Size Simulation for Communication Networks, in Proc. NETWORKING '06, Lecture Notes in Computer Science, vol. 3976, pp. 87-97, (Springer, 2006).
https://doi.org/10.1007/11753810_8

N. D. Gangadhar, G. R. Kadambi, Pathwise Transient Computational Solution of Single Class Finite Buffered Fluid Queues and Tandem Networks with Piecewise Constant Rate Input, Submitted, 2021.

N. D. Gangadhar, S. Krithika, G. R. Kadambi, Numerical Solution of Fluid Queueing Models for Communication Networks, in Proc. International Conference on Recent Innovations in Engineering and Technology (ICRIET 2020), IoP Conference Series: Materials and Engineering, vol. 1070, p. 012063, 2021.
https://doi.org/10.1088/1757-899X/1070/1/012063

O. Kella, W. Stadje, Markov-modulated Linear Fluid Networks with Markov Additive Input, Journal of Applied Probability, vol. 39, pp. 413-420, 2002.
https://doi.org/10.1239/jap/1025131438

R. L. Cruz, A Calculus for Network Delay. II. Network Analysis, IEEE Transactions on Information Theory, vol. 37, (no. 1), pp. 132-141, 1991.
https://doi.org/10.1109/18.61110

B. V. Gnedenko, I. N. Kovelenko, Introduction to Queueing Theory (Birkhauser, 1989).
https://doi.org/10.1007/978-1-4615-9826-8

M. H. A. Davis, Piecewise-deterministic Markov Processs: A General Class of Non-diffusion Stochastic Models, Journal of the Royal Statistical Society, Series B., vol. 46, pp. 353-388, 1984.
https://doi.org/10.1111/j.2517-6161.1984.tb01308.x

R. Azais, J.-P. Bardet, A. Genador, N. Krell, P.-A. Zitt, Piecewise Deterministic Markov Processs - Recent Results, EDP Sciences, vol. 44, pp. 276-290, 2014.
https://doi.org/10.1051/proc/201444017

D. Gamarnik, Fluid Models of Queueing Networks, in Wiley Encyclopedia of Operations Research and Management Science, J. J. Cochran, Ed., (Wiley, 2011, pp. 1-15).
https://doi.org/10.1002/9780470400531.eorms0329

S. Ahn, J. Jeon, V. Ramaswamy, Steady State Analysis for Finite Fluid Flow Models using QBDs, Queueing System, vol. 49, pp. 223-259, 2005.
https://doi.org/10.1007/s11134-005-6966-9

W. L. Cooper, V. Schmidt, R. M. Serfozo, Skorokhod-Lyons Characterizations of Queueing, Fluid and Inventory Processes, Queueing Systems, vol. 37, pp. 233-257, 2001.
https://doi.org/10.1023/A:1011052519512

L. Kruk, J. Lehoczky, K. Ramanan, S. Shreve, Double Skorokhod Map and Reneging Real-Time Queues, Institute of Mathematical Statistics Collections, 2008: 169-193 (2008).
https://doi.org/10.1214/074921708000000372

M. Bramson, Stability of Queueing Networks (Springer, 2008).
https://doi.org/10.1214/08-PS137

R. J. Williams, Diffusion Approximations for Open Multiclass Queueing Networks: Sufficient Conditions Involving State Space Collapse," Queueing Systems, vol. 30, pp. 27-88, 1998.
https://doi.org/10.1023/A:1019108819713

J. M. Harrison, Brownian Models for Performance and Control (New York: Cambridge University Press, 2013).
https://doi.org/10.1017/CBO9781139087698

W. N. Kang, F. P. Kelly, N. H. Lee, R. J. Williams, State Space Collapse and Diffusion Approximations for a Network Operating under Fair Bandwidth Sharing Policy, Annals of Applied Probability, vol. 19, (no. 5), pp. 1719-1780, 2009.
https://doi.org/10.1214/08-AAP591

M. H. Veatch, Using Fluid Solutions in Dynamic Scheduling, in Analysis and Modeling of Manufacturing Systems, S. B. Gershwin, Y. Dallery, C. T. Papadopoulos, J. M. Smith, Eds. (Kluwer Academic Publishers, 2003, pp. 399-426).
https://doi.org/10.1007/978-1-4615-1019-2_16

S. T. Maguluri, R. Srikant, Heavy Traffic Queue Length Behavior in a Switch under the MaxWeight Algorithm, Stochastic Systems, vol. 6, pp. 211-250, 2016.
https://doi.org/10.1287/15-SSY193

A. I. Elwalid, D. Mitra, Analysis, Approximations and Admission Control of a Multi-Service Multiplexing System with Priorities, in Proc. of IEEE INFOCOM '95, 1995, pp. 463-472.

A. d. S. Soares, G. Latouche, Matrix-analytic Methods for Fluid Queues with Finite Buffers, Performance Evaluation, vol. 63, pp. 295-314, 2006.
https://doi.org/10.1016/j.peva.2005.02.002

R. Cominetti, J. Correa, N. Olver, Long Term Behavior of Dynamic Equilibria in Fluid Queuing Networks, in Proc. IPCO, Lecture Notes in Computer Science (LNCS), vol. 10328, pp. 161-172 (Springer, 2017).
https://doi.org/10.1007/978-3-319-59250-3_14

J. A. Schwarz, G. Selinka, R. Stolletz, Performance Analysis of Time-Dependent Queueing Systems: Survey and Classification, Omega, vol. 63, pp. 170-189, 2016.
https://doi.org/10.1016/j.omega.2015.10.013

E. I. Tzenova, I. J. B. F. Adan, V. G. Kulkarni, Output Analysis of Multiclass Fluid Models with Static Priorities, Performance Evaluation, vol. 65, pp. 71-81, 2008.
https://doi.org/10.1016/j.peva.2007.03.002

B. Zwart, S. Bost, M. Mandjes, Exact Asymptotics for Fluid Queues fed by Multiple Heavy-tailed On-Off Flows, Annals of Applied Probability, vol. 14, pp. 903- 957, 2004.
https://doi.org/10.1214/105051604000000161

A. W. Berger, W. Whitt, Workload Bounds in Fluid Models with Priorities, Performace Evaluation, vol. 41, pp. 249-267, 2000.
https://doi.org/10.1016/S0166-5316(99)00075-9

S. L. Splitler, D. C. Lee, Proof of Monotone Loss Rate of Fluid Priority-Queue with Finite Buffer, Queueing System, vol. 51, pp. 77-87, 2005.
https://doi.org/10.1007/s11134-005-3749-2

N. D. Gangadhar, G. R. Kadambi, Pathwise Complete Solution of a Markov Modulated Tandem Fluid Queueing Model of a Voice Network, IEEE International Conference on Electronics, Computing and Communication Technologies (CONECCT) 2022, Accepted, 2022.
https://doi.org/10.1109/CONECCT55679.2022.9865843

N. D. Gangadhar, G. R. Kadambi, Delay Distributions in Discrete Time Multiclass Tandem Communication Network Models, International Journal of Electrical and Computer Engineering Systems, Vol. 13 No. 6 (2022), pp. 417-425.
https://doi.org/10.32985/ijeces.13.6.1

P. O'Reilly, S. Ghani, Data Performance in Burst Switching when the Voice Silence Periods have a Hyper- exponential Distribstion, IEEE Transactions on Commu nications, vol. COM-35, (no. 10), pp. 1109-1111, 1987.
https://doi.org/10.1109/TCOM.1987.1096675

R. A. Wolff, Stochastic Processes and Queueing Theory (Prentice Hall, Englewood Cliffs, NJ, 1989).


Refbacks

  • There are currently no refbacks.


Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize