Abstract
In this paper, we investigate multi-class multi-server queueing systems with global FCFS policy, i.e., where customers requiring different types of service—provided by distinct servers—are accommodated in one common FCFS queue. In such scenarios, customers of one class (i.e., requiring a given type of service) may be hindered by customers of other classes. The purpose of this paper is twofold: to gain (qualitative and quantitative) insight into the impact of (i) the global FCFS policy and (ii) the relative distribution of the load amongst the customer classes, on the system performance. We therefore develop and analyze an appropriate discrete-time queueing model with general independent arrivals, two (independent) customer classes and two class-specific servers. We study the stability of the system and derive the system-content distribution at random slot boundaries; we also obtain mean values of the system content and the customer delay, both globally and for each class individually. We then extensively compare these results with those obtained for an analogous system without global FCFS policy (i.e., with individual queues for the two servers). We demonstrate that global FCFS, as well as the relative distribution of the load over the two customer classes, may have a major impact on the system performance.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
This paper is an extended version of our conference paper [5].
References
Adan IJBF, Sleptchenko A, Van Houtum GJ (2009) Reducing costs of spare parts supply systems via static priorities. Asia Pac J Oper Res 26(4):559–585
Beekhuizen P, Resing J (2009) Performance analysis of small non-uniform packet switches. Perform Eval 66:640–659
Bruneel H, Kim BG (1993) Discrete-time models for communication systems including ATM. Kluwer Academic, Boston, USA
Bruneel H, Mélange W, Steyaert B, Claeys D, Walraevens J (2012a) Impact of blocking when customers of different classes are accommodated in one common queue. In Proceedings of the 1st International Conference on Operations Research and Enterprise Systems (ICORES), Villamoura, Portugal
Bruneel H, Mélange W, Steyaert B, Claeys D, Walraevens J (2012b) Influence of relative traffic distribution in nodes with blocking: an analytical model. In: Proceedings of the european simulation and modelling conference (ESM). Essen, Germany, pp 136–143
Bruneel H, Mélange W, Steyaert B, Claeys D, Walraevens J (2012c) A two-class discrete-time queueing model with two dedicated servers and global FCFS service discipline. Eur J Oper Res 223:123–132
Cardellini V, Colajanni M, Yu PS (1999) Dynamic load balancing on web-server systems. IEEE Internet Comput 3(3):28–39
Chen H, Zhang H (2000) Stability of multiclass queueing networks under priority service disiplines. Oper Res 48(1):26–37
Chou TCK, Abraham JA (1982) Load balancing in distributed systems. IEEE Trans Software Eng 8(4):401–412
De Vuyst S, Wittevrongel S, Bruneel H (2008) Place reservation: delay analysis of a novel scheduling mechanism. Comput Oper Res 35(8):2447–2462
Fiems D, Bruneel H (2002) A note on the discretization of Little’s result. Oper Res Lett 30:17–18
Gamarnik D, Katz D (2009) On deciding stability of multiclass queueing networks under buffer priority scheduling policies. Ann Appl Probab 19(5):2008–2037
Kesselman A, Kogan K, Segal M (2012) Improved competitive performance bounds for CIOQ switches. Algorithmica 63(1–2):411–424
Mélange W, Bruneel H, Steyaert B, Walraevens J (2011) A two-class continuous-time queueing model with dedicated servers and global FCFS service discipline.In: Proceedings of the 18th international conference on analytical and stochastic modeling techniques and applications (ASMTA). Venice, Italy, pp 14–27
Ngoduy D (2006) Derivation of continuum traffic model for weaving sections on freeways. Transportmetrica 2:199–222
Nishi R, Miki H, Tomoeda A, Nishinari K (2009) Achievement of alternative configurations of vehicles on multiple lanes. Phys Rev E 79:066119
Rubin I, Tsai Z (1989) Message delay analysis of multiclass priority TDMA, FDMA, and discrete-time queueing systems. IEEE Trans Inf Theory 35(2):637–647
Schoonderwoerd R, Bruten JL, Holland OE, Rothkrantz LJM (1996) Ant-based load balancing in telecommunications networks. Adapt Behav 5(2):169–207
Shah D, Tsitsiklis JN, Zhong Y (2011) Optimal scaling of average queue sizes in an input-queued switch: an open problem. Queueing Syst 68(3–4):375–384
Smith DR, Whitt W (1981) Resource sharing for efficiency in traffic systems. Bell Syst Tech J 60(1):39–55
Takagi H (1993) Queueing analysis: discrete-time systems, vol. 3. North Holland
Verloop IM, Ayesta U, Borst S (2010) Monotonicity properties for multi-class queueing systems. Discret Event Dyn Syst Theory Appl 20(4):473–509
Walraevens J, Fiems D, Bruneel H (2008) Time-dependent performance analysis of a discrete-time priority queue. Perform Eval 65:641–652
Yu H, Ruepp S, Berger MS (2011) Enhanced first-in-first-out-based round-robin multicast scheduling algorithm for input-queued switches. IET Commun 5(8):1163–1171
Acknowledgments
This research has been funded by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bruneel, H., Mélange, W., Steyaert, B. et al. Effect of global FCFS and relative load distribution in two-class queues with dedicated servers. 4OR-Q J Oper Res 11, 375–391 (2013). https://doi.org/10.1007/s10288-013-0246-z
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10288-013-0246-z