Skip to main content
SpringerLink
Log in

Analysis of a two-class single-server discrete-time FCFS queue: the effect of interclass correlation

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

In this paper, we study a discrete-time queueing system with one server and two classes of customers. Customers enter the system according to a general independent arrival process. The classes of consecutive customers, however, are correlated in a Markovian way. The system uses a “global FCFS” service discipline, i.e., all arriving customers are accommodated in one single FCFS queue, regardless of their classes. The service-time distribution of the customers is general but class-dependent, and therefore, the exact order in which the customers of both classes succeed each other in the arrival stream is important, which is reflected by the complexity of the system content and waiting time analysis presented in this paper. In particular, a detailed waiting time analysis of this kind of multi-class system has not yet been published, and is considered to be one of the main novelties by the authors. In addition to that, a major aim of the paper is to estimate the impact of interclass correlation in the arrival stream on the total number of customers in the system, and the customer delay. The results reveal that the system can exhibit two different classes of stochastic equilibrium: a “strong” equilibrium where both customer classes give rise to stable behavior individually, and a “compensated” equilibrium where one customer type creates overload.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Notes

  1. Notice the analogy with complex numbers calculus: for \(z=x+\imath y\) with \(x,y\in \mathbb {R}\), then \(f(z)+f(z^*)\in \mathbb {R}\), since this is an even function of \(\imath y\)

References

  • Adan I, Kulkarni V (2003) Single-server queue with markov dependent inter-arrival and service times. Queueing Syst 45(2):113–134

    Article  Google Scholar 

  • Adan I, Sleptchenko A, Van Houtum G (2009) Reducing costs of spare parts supply systems via static priorities. Asia Pac J Oper Res 26(4):559–585

    Article  Google Scholar 

  • Asmussen S (2002) Applied probability and queues. Springer, New York

    Google Scholar 

  • Banik A, Chaudhry M, Gupta U (2008) On the finite buffer queue with renewal input and batch markovian service process: GI/BMSP/1/N. Methodol Comput Appl Probab 10:559–575

    Article  Google Scholar 

  • Boxma O, Bruin J, Fralix B (2009) Sojourn times in polling systems with various service disciplines. Perform Eval 66(11):621–639

    Article  Google Scholar 

  • Bruneel H (1988) Queuing behavior of statistical multiplexers with correlated inputs. IEEE Trans Commun 36(12):1339–1341

    Article  Google Scholar 

  • Bruneel H (1993) Performance of discrete-time queuing-systems. Comput Oper Res 20(3):303–320

    Article  Google Scholar 

  • Bruneel H, Kim B (1993) Discrete-time models for communication systems including ATM. Kluwer Academic, Boston

    Book  Google Scholar 

  • Bruneel H, Maertens T, Steyaert B, Claeys D, Fiems D, Walraevens J (2012a) Analysis of a two-class FCFS queueing system with interclass correlation. In: Proceedings of the 19th international conference on analytical and stochastic modelling techniques and applications (ASMTA’12), Grenoble, June 4–6

    Chapter  Google Scholar 

  • Bruneel H, Mélange W, Steyaert B, Claeys D, Walraevens J (2012b) 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 (2012c) A two-class discrete-time queueing model with two dedicated servers and global FCFS service discipline. Eur J Oper Res 223:123–132

    Article  Google Scholar 

  • Bruneel H, Maertens T, Walraevens J (2013) Interclass correlation in priority scheduling: an overlooked phenomenon. In: Proceedings of the eighth international conference on queueing theory and network applications (QTNA 2013), Taichung, Taiwan

  • Bruneel H, Maertens T, Walraevens J (2014) Class clustering destroys delay differentiation in priority queues. Eur J Oper Res 235(1):149–158

    Article  Google Scholar 

  • Chrysos N, Katevenis M (2011) Distributed WFQ scheduling converging to weighted max–min fairness. Comput Netw 55:792–806

    Article  Google Scholar 

  • Claeys D, Bruneel H, Steyaert B, Mélange W, Walraevens J (2012) Influence of data clustering on in-order multi-core processing systems. Electron Lett 49(1):28–29

    Article  Google Scholar 

  • De Clercq S, De Turck K, Steyaert B, Bruneel H (2011) Frame-bound priority scheduling in discrete-time queueing sytems. J Ind Manag Optim 7(3):767–788

    Article  Google Scholar 

  • De Clercq S, Laevens K, Steyaert B, Bruneel H (2013) A multi-class discrete-time queueing system under the FCFS service discipline. Ann Oper Res 202(1):59–73

    Article  Google Scholar 

  • De Vuyst S, Wittevrongel S, Bruneel H (2008) Place reservation: delay analysis of a novel scheduling mechanism. Comput Oper Res 35(8):2447–2462

    Article  Google Scholar 

  • Feng W, Umemura M (2009) Analysis of a finite buffer model with two servers and two nonpreemptive priority classes. Eur J Oper Res 192(1):151–172

    Article  Google Scholar 

  • Fiems D, Bruneel H (2002) A note on the discretization of Little’s result. Oper Res Lett 30:17–18

    Article  Google Scholar 

  • Frantti T, Jutila M (2009) Embedded fuzzy expert system for adaptive weighted fair queueing. Expert Syst Appl 36(8):11390–11397

    Article  Google Scholar 

  • Gonzáles M (1992) Classical complex analysis. Marcel Dekker, New York

    Google Scholar 

  • Gupta V, Burroughs M, Harchol-Balter M (2010) Analysis of scheduling policies under correlated job sizes. Perform Eval 67(11):996–1013

    Article  Google Scholar 

  • Jeffrey A (1992) Complex analysis and its applications. CRC Press, London

    Google Scholar 

  • Jin X, Min G (2007) Performance analysis of priority scheduling mechanisms under heterogeneous network traffic. J Comput Syst Sci 73(8):1207–1220

    Article  Google Scholar 

  • Jin X, Min G (2009) Analytical queue length distributions of GPS systems with long range dependent service capacity. Simul Model Pract Theory 17(9):1500–1510

    Article  Google Scholar 

  • Karsten M (2010) Approximation of generalized processor sharing with interleaved stratified timer wheels. IEEE ACM Trans Netw 18(3):708–721

    Article  Google Scholar 

  • Kim J, Kim J, Kim B (2011) Analysis of the M/G/1 queue with discriminatory random order service policy. Perform Eval 68(3):256–270

    Article  Google Scholar 

  • Kleinrock L (1975) Queueing systems, part I. Wiley, New York

    Google Scholar 

  • Lieshout P, Mandjes M (2008) Generalized processor sharing: characterization of the admissible region and selection of optimal weights. Comput Oper Res 35(8):2497–2519

    Article  Google Scholar 

  • Maertens T, Walraevens J, Bruneel H (2008) Performance comparison of several priority schemes with prioriy jumps. Ann Oper Res 180(3):1168–1185

    Article  Google Scholar 

  • Maertens T, Bruneel H, Walraevens J (2012) Effect of class clustering on delay differentiation in priority scheduling. Electron Lett 48(10):568–569

    Article  Google Scholar 

  • Mélange W, Bruneel H, Steyaert B, Claeys D, Walraevens J (2014) A continuous-time queueing model with class clustering and global FCFS service discipline. J Ind Manag Optim 10(1):193–206

    Google Scholar 

  • Mélange W, Bruneel H, Steyaert B, Claeys D, Walraevens J (2012) Impact of class clustering and global FCFS service discipline on the system occupancy of a two-class queueing model with two dedicated servers. In: Proceedings of 7th international conference on queueing theory and network applications

  • Min D, Yih Y (2010) An elective surgery scheduling problem considering patient priority. Comput Oper Res 37(6):1091–1099

    Article  Google Scholar 

  • Morrison J (2010) Two queues with vastly different arrival rates and processor-sharing factors. Queueing Syst 64(1):49–67

    Article  Google Scholar 

  • Morrison J, Borst S (2010) Interacting queues in heavy traffic. Queueing Syst 65(2):135–156

    Article  Google Scholar 

  • Ozawa T (2004) Analysis of queues with markovian service processes. Stoch Models 20(4):391–413

    Article  Google Scholar 

  • Réveil B, Claeys D, Maertens T, Walraevens J, Bruneel H (2014) Impact of class clustering in a multiclass fcfs queue with order-dependent service times. Comput Oper Res 51:90–98

    Article  Google Scholar 

  • Shortle J, Fischer M (2010) Approximation for a two-class weighted fair queueing discipline. Perform Eval 67(10):946–958

    Article  Google Scholar 

  • Verloop I, Ayesta U, Borst S (2010) Monotonicity properties for multi-class queueing systems. Discret Event Dyn Syst Theory Appl 20(4):473–509

    Article  Google Scholar 

  • Walraevens J, Steyaert B, Bruneel H (2004) Performance analysis of a GI-Geo-1 buffer with a preemptive resume priority scheduling discipline. Eur J Oper Res 157(1):130–151

    Article  Google Scholar 

  • Walraevens J, Steyaert B, Bruneel H (2005) A packet switch with a priority scheduling discipline: performance analysis. Telecommun Syst 28(1):53–77

    Article  Google Scholar 

  • Walraevens J, Fiems D, Bruneel H (2008) Time-dependent performance analysis of a discrete-time priority queue. Perform Eval 65:641–652

    Article  Google Scholar 

  • Walraevens J, Fiems D, Wittevrongel S, Bruneel H (2009) Calculation of output characteristics of a priority queue through a busy period analysis. Eur J Oper Res 198(3):891–898

    Article  Google Scholar 

  • Walraevens J, van Leeuwaarden J, Boxma O (2010) Power series approximations for two-class generalized processor sharing systems. Queueing Syst 66(2):107–130

    Article  Google Scholar 

  • Wang L, Min G, Kouvatsos D, Jin X (2010) Analytical modeling of an integrated priority and WFQ scheduling scheme in multi-service networks. Comput Commun 33:S93–S101

    Article  Google Scholar 

  • Zeltyn S, Feldman Z, Wasserkrug S (2009) Waiting and sojourn times in a multi-server queue with mixed priorities. Queueing Syst 61(4):305–328

    Article  Google Scholar 

  • Zhao J, Li B, Cao X, Ahmad I (2006) A matrix-analytic solution for the DBMAP/PH/1 priority queue. Queueing Syst 53(3):127–145

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. SMACS Research Group, Department of Telecommunications and Information Processing, Ghent University-UGent, Ghent, Belgium

    Herwig Bruneel, Tom Maertens, Bart Steyaert, Dieter Claeys, Dieter Fiems & Joris Walraevens

  2. Department of Industrial Systems Engineering and Product Design, Ghent University-UGent, Ghent, Belgium

    Dieter Claeys

Authors
  1. Herwig Bruneel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tom Maertens
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bart Steyaert
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dieter Claeys
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Dieter Fiems
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Joris Walraevens
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bart Steyaert.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bruneel, H., Maertens, T., Steyaert, B. et al. Analysis of a two-class single-server discrete-time FCFS queue: the effect of interclass correlation. TOP 26, 403–436 (2018). https://doi.org/10.1007/s11750-018-0480-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-018-0480-9

Keywords

Mathematics Subject Classification

Search

Navigation