Abstract
A finite-buffer queueing model with Poisson arrivals and exponential processing times is investigated. Every time when the system empties, the server begins a generally distributed single working vacation period, during which the service is provided with another (slower) rate. After the completion of the vacation period the processing is being continued normally, with original speed. The next working vacation period is being initialized at the next time at which the system becomes empty, and so on. The system of Volterra-type integral equations for transient queue-size distribution, conditioned by the initial level of buffer saturation, is built. The solution of the corresponding system written for Laplace transforms is given in a compact-form using the linear algebraic approach and the corresponding result obtained for the ordinary model (without working vacation regime). Numerical examples are attached as well.
Access provided by Autonomous University of Puebla. Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
Queueing models with finite buffer capacities are widely used in the analysis of real-life systems occurring in technical and economic sciences, and in transport and logistic problems, in which the phenomena of “queueing” of items [27, 28] (packets, calls, customers, jobs, etc.) and their losses due to buffer saturation can be observed. As it seems, particularly important are models in which different-type restrictions in access to the service station are implemented additionally. In practice, these restrictions are often a kind of energy saving mechanism (e.g., cyclic succession of listening and dormant modes in wireless networks, or switching off a machine in manufacturing process in the case of the traffic with low intensity), and are associated with temporary blocking the service of items despite their presence in the accumulation buffer. The scientific literature concerning such systems is already huge and still increasing. Servi and Finn proposed in [15] for the first time the model with the so called working vacation, in which the server, instead of total service stopping, offers the processing with another speed (usually lower). This model was originally motivated by a reconfigurable WDM (Wavelength-division multiplexing) optical access network in which a single token cyclically visits each queue, operating at two different rates (faster and slower ones), but it can be successfully used in modelling many phenomena typical for, e.g. computer and telecommunication networks or manufacturing engineering. In particular, we can use it
-
when the service station processes two types of packets with significantly different service speeds (e.g., different times of putting them in the link);
-
in the case of temporary throughput reductions, due to parallel launching another application;
-
in the situation of periodic reduction of the throughput of the production line (slower processing with lower power consumption).
As it is shown in [12, 29], a working vacation queueing system with two different processing rates can be successfully applied in modelling, e.g. the Ethernet Passive Optical Network (EPON), consisting of one optical line terminal (OLT), situated at the central office, and multiple optical network units (ONUs) situated at customer premises equipment (CPE), and a passive splitter/combiner. In EPON bi-directional transmissions are provided: in the downstream direction the OLT broadcasts to all ONUs and in the upstream direction (from ONUs to the OLT) the fiber channel is shared by all ONUs.
After the article [15] many papers were published on the analysis of stochastic characteristics of queueing models with working vacation mechanism. Working vacation models of GI/M/1 type are considered, e.g. in [2, 26] in the case of finite buffer capacity, and in [1, 13] for the infinite waiting room. Unfortunately, as one can see, most of the results relates only to the steady state of the system. Meanwhile, as it seems, in practice it is increasingly essential to investigate the system in the transient case. Such a study is of particular importance in the case of the observation the system shortly after its opening or applying new control mechanism. The high variability of the packet traffic (e.g., in the Internet) also can “force” the time-dependent analysis. In [18] the transient queue-size distribution for the infinite-sized M/M/1-type model with server working vacations is found. In [22] the study is extended for the multi-server case and multiple working vacation regime by using the matrix geometric method. Compact-form transient results for main stochastic characteristics of finite-buffer queues with different-type service restrictions can be found, e.g. in [7–10]. The case of infinite buffer is studied in [5, 6]. In [21] a processor-sharing model with limited total volume and probabilistic packet dropping is considered. In various data management systems (see [23]) we can find applications of queueing systems to enable faster requests management and therefore improved data mining (see e.g. [24, 25, 30, 31]).
The remaining part of the article is organized as follows. In the next Sect. 2 we give the precise description of the considered queueing model and state an auxiliary algebraic result which can be used in further analysis. Section 3 is devoted to the ordinary system (without server working vacation). The compact-form representation for the LT (=Laplace transform) of conditional transient queue-size distribution is derived there, and written by using the functional sequence recursively defined. In Sect. 4 we obtain the corresponding result for the original model with generally distributed working vacations, utilizing results from Sects. 2 and 3. In Sect. 5 numerical examples are attached and the last Sect. 6 contains a short summary and conclusions.
2 Model Description and Auxiliary Results
In the article we deal with the M/M/1/N-type queueing model with Poisson job arrivals with rate \( \lambda , \) exponential processing times with mean \( \mu^{ - 1} , \) and finite capacity \( N \ge 2 \) (\( N - 1 \) places in the buffer queue and one place “in service”). Every time when the system empties the server begins a generally distributed single working vacation period, during which the processing of jobs is carried out with another (slower) rate \( \mu^{*} < \mu \) (see Fig. 1 for the scheme of the system operation). We denote by \( G\left( \cdot \right) \) the CDF (=cumulative distribution function) of the working vacation period duration. After finishing the vacation period the service process is being continued normally, with original speed. The next working vacation period is being initialized at the next time at which the queue becomes empty, and so on.
The following theorem can be found in [11]:
Theorem 1.
Introduce two number sequences \( \left( {\alpha_{k} } \right), k \ge 0, \) and \( \left( {\psi_{k} } \right), k \ge 1, \) with the assumption \( \alpha_{0} \ne 0. \) Each solution of the following system of linear equations with respect to \( x_{n} , n \ge 1: \)
can be written in the form
where \( C \) is a constant independent on \( n, \) and \( \left( {R_{k} } \right) \) is connected with the sequence \( \left( {\alpha_{k} } \right) \) by the following formula:
Moreover, in [11] it is proved that successive terms of the sequence \( \left( {R_{n} } \right) \) (called a potential) can be found recursively as follows:
As it turns out, LTs of conditional queue-size distributions in the original system and in the ordinary one, satisfy systems of equations similar to (1). Hence, in solving these systems, we will use the formula (2), where the representation for \( C \) will be found from a boundary condition.
3 Conditional Transient Queue-Size Distribution in an Ordinary System
In this section we deal with the conditional queue-size distribution in the ordinary finite-buffer M/M/1/N-type model without working vacation discipline, corresponding to the original one, with \( \lambda \) and \( \mu^{*} \) being the arrival intensity and service speed, respectively, and find the representation for its LT in terms of “input” system parameters, writing it in a specific way, by using a recursively defined sequence, called a potential. Similar result was obtained in [3] for the generally-distributed service time, however it is written in another form. It should be mentioned here that transient solutions for the M/M/1/N-type queue were also obtained in [19] (see also [14]) by using the technique of eigenvalues and eigenvectors, in [16] by applying Chebyshev polynomials, in [17] by utilizing matrix technique and in [20] via LTs. Introduce the following notation:
where \( X^{O} \left( t \right) \) denotes the number of packets present in the ordinary system at time \( t. \) Since, due to exponential distributions of inter-arrival and service times, both arrival and service completion epochs are Markov moments, from the continuous version of the total probability formula written with respect to the first Markov moment after \( t = 0, \) we obtain the following system of integral equations:
where \( 1 \le n \le N - 1, \) and
where the notation \( \delta_{i,j} \) stands for the Kronecker delta function. Let us comment (6)–(8) briefly. Indeed, the first summands on the right side of (7) and (8) relate to the case in which, as the first one, a jump of the arrival Poisson process occurs, while the second ones - to the situation in which the jump of the service process is observed as the first one. The last summands on the right side of (7) and (8) present the case in that there is no jump of the arrival and service processes before \( t. \) The formula (6), written for the case of the system being empty at the opening, is obvious. Defining
we obtain from (6)–(8) the following equations:
and
We will obtain the solution of the system (10)–(12) by applying the algebraic-type approach based on Theorem 1 that allows for writing the representation for \( \tilde{p}_{k}^{O} \left( {s,m} \right) \) (at arbitrary \( k \)) via certain recursively-defined sequence (see (4)).
Let us note that, if we define
and, moreover,
where
then the Eqs. (11) and (12) can be rewritten as
and
Because (16) has the same form as (1) (now with \( \alpha_{\text{k}}^{ *} \) and \( \psi_{n}^{ *} \) being functions of \( s \) and \( \left( {s,m} \right), \) respectively), then the following representation holds true (compare (2)):
where now (see (4) and refer to (13)) for \( k \ge 1 \)
In order to find the explicit representation for \( C^{ *} \left( {s,m} \right) \), we will use the Eq. (17), treating it as a kind of boundary condition. Indeed, implementing (18) in (17), we obtain
Observe that, taking in (18) \( n = 1, \) we have
Substituting now (21) into (10), we get
where
Inserting (22) into (20), we eliminate \( C^{ *} \left( {s,m} \right) \) in the following form:
where we denote
and
Collecting the formulae (14), (18), (22) and (24), we can formulate the following:
Theorem 2.
The LT \( \tilde{p}_{n}^{O} \left( {s,m} \right) \) of transient queue-size distribution in the ordinary M/M/1/N-type queue, conditioned by the number \( 0 \le n \le N \) of jobs present in the system initially, can be expressed in the following way:
where \( {\Re }\left( s \right) > 0 \) and \( 0 \le m \le N, \) and the formulae for \( \phi_{k}^{*} \left( {s,m} \right), \) \( D_{k}^{*} \left( s \right), \) \( R_{k}^{*} \left( s \right), \) \( A^{*} \left( s \right), \) \( B^{*} \left( {s,m} \right), \) \( T^{*} (s,m) \) and \( \varDelta^{*} \left( s \right) \) are given in ( 15 ), ( 19 ), ( 23 ) ( 25 ) and ( 26 ), respectively.
4 Queue-Size Distribution in a Model with Working Vacations
Let us take into consideration the original model with generally-distributed server working vacation periods (each with a CDF \( G( \cdot ) \)) during which the processing of jobs is offered with a slower rate \( \mu^{*} < \mu , \) where \( \mu \) denotes the normal-mode service rate. Introduce the following notation:
where \( X\left( t \right) \) denotes the number of packets present in the system with working vacations (original one) at time \( t. \) Assume, firstly, that the system starts its evolution being empty. So, at \( t = 0 \) the working vacation period begins. Observe, that the following equation is then satisfied:
Indeed, the first summand on the right side of (30) presents the situation in which the working vacation period completes at time \( x < t. \) Hence, at time \( x \) the system starts the operation in normal mode with \( 0 \le k \le N \) packets with probability \( P_{0}^{O} \left( {x,k} \right) \). The second summand in (30) relates to the case in that the time epoch \( t \) is “inside” the working vacation period. If the number of packets equals \( 1 \le n \le N - 1 \) initially, we similarly obtain
Finally, \( n = N \) we have
The interpretation of (31) and (32) is the same as of (7) and (8). Defining
and, moreover (compare (13)–(15)),
and
where
we obtain from (30)–(32) the following system (see (10) ,(16) and (17)):
and
Since (38) has the same form as (1), then we can write (compare (18))
where here (see (19)) for \( k \ge 1 \)
and the sequence \( \left( {\alpha_{k} \left( s \right)} \right) \) is defined in (34).
Let us note that, if we define
and
where \( {\Re }\left( s \right) > 0, \) then (37) can be rewritten in the following way:
Inserting now in (44), instead of \( \tilde{p}_{k} \left( {s,m} \right) \), the right side of the representation (40), we obtain
and hence we get the following formula:
where
and
Having defined \( A(s) \) and \( B\left( {s,m} \right) \), we can execute successive steps of the procedure described for the ordinary system in (20)–(26) and formulate the following main theorem:
Theorem 3.
The LT \( \tilde{p}_{n} \left( {s,m} \right) \) of time-dependent queue-size distribution in the M/M/1/N-type queue with working vacation mechanism, conditioned by the number \( 0 \le n \le N \) of jobs present in the system initially, can be written in the following way:
where \( {\Re }\left( s \right) > 0 \) and \( 0 \le m \le N, \) and (compare ( 25 ) and ( 26 ))
Moreover, the formulae for \( \phi_{k} \left( {s,m} \right), D_{k} \left( s \right), R_{k} \left( s \right), A(s) \) and \( B(s,m) \) are given in ( 36 ), ( 41 ), ( 47 ) and ( 48 ), respectively.
Remark 1.
The formulae ( 49 ) and ( 50 ) allow for finding the LT of the queue-size distribution in the original system as functions of the appropriate distribution for the ordinary model (given in terms of LTs in ( 27 ) and ( 28 )), by \( L_{k} \left( s \right) \) and \( M(s,m) \) defined in ( 42 ) and ( 43 ), respectively.
Remark 2.
Having LTs of the probabilities \( \tilde{p}_{n} \left( {s,m} \right), \) we can easily find the stationary queue-size distribution \( \pi_{0} , \ldots , \pi_{N} , \) by using the well-known Tauberian theorem, namely
where \( n \) can be chosen arbitrarily between 0 and \( N. \)
Remark 3.
In the case of exponentially distributed working vacation period with mean \( \theta^{ - 1} , \) i.e. if \( G(t) = 1 - e^{ - \theta t} , t > 0, \) we can evaluate \( L_{k} \left( s \right) \) and \( M(s,m) \) explicitly. Indeed, we obtain
5 Numerical Examples
Let us consider a node of the wireless network in which packets of sizes 200 [B] arrive according to a Poisson process with intensity 600 [kb/s]. The normal throughput equals 800 [kb/s], but every time when the buffer empties the throughput is lower (500 [kb/s]) for a random exponential time with mean 0.1 [s]. Let us note that for such parameters the traffic load equals normally 0.75 and during the working vacation period 1.20 (so, in this case the link is overloaded). In Fig. 1 transient behaviour of probabilities \( P\{ X(t) = m\, | \,X(0) = 0\} \) is presented for \( m = 0, 2\, {\text{and 4}} \), where \( N = 4. \) In Fig. 2 transient behaviour of \( \varvec{P}\{ X(t) = 1 \, | \,X(0) = 0\} \) is visualized for different arrival rates: 200, 400 and 600 [kb/s], where the remaining system parameters are kept the same as in Fig. 1. As one can observe, for the lowest arrival rate, the time for the system stabilization is the shortest one. Figure 3 shows the behaviour of \( \varvec{P}\{ X(t) = 4\, | \,X(0) = 0\} \) at arrival rate 400 [kb/s] and normal service speed 800 [kb/s], for three different processing speeds during the WV (= working vacation) period (the case 800 [kb/s] denotes, in fact, no working vacation) (Fig. 4).
6 Conclusions and Closing Remarks
In the paper a single-server queueing model with finite buffer capacity, Poisson arrival stream and exponential processing times is investigated. The service process is governed by a FIFO discipline with working vacation algorithm, in which the service station, every time when the system empties, provide the processing with a slower rate during a generally distributed random time. The explicit formulae for the LT of transient conditional queue-size distribution are obtained. Numerical utility of the formulae is presented in examples motivated by real traffic in a node of the wireless network.
References
Baba, Y.: Analysis of a GI/M/1 queue with multiple working vacations. Oper. Res. Lett. 33, 201–209 (2005)
Banik, A.D., Gupta, U.C., Pathak, S.S.: On the GI/M/1/N queue with multiple working vacations - analytic analysis and computations. Appl. Math. Model. 31, 1701–1710 (2007)
Bratiichuk, M.S., Borowska, B.: Explicit formulae and convergence rate for the system Mα/G/1/N as N → ∞. Stochast. Models 18(1), 71–84 (2002)
Cohen, J.W.: The Single Server Queue. North-Holland Publishing Company, Amsterdam, New York, Oxford (1982)
Kempa, W.M.: The transient analysis of the queue-length distribution in the batch arrival system with N-policy, multiple vacations and setup times. In: Venkov, G., Kovacheva, R., Pasheva, V. (eds.) 36th International Conference Applications of Mathematics in Engineering and Economics (AMEE 2010), 5–10 June 2010, Sozopol, Bulgaria, pp. 235–242. American Institute of Physics, Melville (2010). (AIP Conference Proceedings, vol. 1293)
Kempa, W.M.: On transient queue-size distribution in the batch arrival system with the N-policy and setup times. Math. Commun. 17(1), 285–302 (2012)
Kempa, W.M.: A direct approach to transient queue-size distribution in a finite-buffer queue with AQM. Appl. Math. Inf. Sci. 7(3), 909–915 (2013)
Kempa, W.M.: On transient departure process in a finite-buffer queueing model with probabilistic packet dropping. In: Venkov, G., Pasheva, V. (eds.) 40th International Conference on Applications of Mathematics in Engineering and Economics (AMEE 2014), 8–13 June 2014, Sozopol, Bulgaria, pp. 42–49. American Institute of Physics, Melville (2014). (AIP Conference Proceedings, vol. 1631)
Kempa, W.M., Kurzyk, D.: Transient departure process in M/G/1/K-type queue with threshold server’s waking up. In: Proceedings of 23rd International Conference on Software, Telecommunications and Computer Networks (SoftCOM 2015), 16–18 September 2015, pp. 32–36. Split - Bol, Croatia (2015)
Kempa, W.M., Paprocka, I., Kalinowski, K., Grabowik, C.: On transient queue-size distribution in a single-machine production system with breakdowns. In: Carausu, C., Wróbel, A., et al. (eds.) Modern Technologies in Industrial Engineering II. Selected, Peer Reviewed Papers from the Modern Technologies in Industrial Engineering (ModTech 2014), 13–16 July 2014, Gliwice, Poland, pp. 505–510. Trans Tech Publications, Staffa-Zurich (2014). (Advanced Materials Research, vol. 1036)
Korolyuk, V.S.: Boundary-Value Problems for Compound Poisson Processes. Naukova Dumka, Kiev (1975)
Li, J.-H., Liu, W.-Q., Tian, N.-S.: Steady-state analysis of a discrete-time batch arrival queue with working vacations. Perform. Eval. 67, 897–912 (2010)
Li, J., Tian, N.: Performance analysis of a GI/M/1 queue with single working vacation. Appl. Math. Comput. 217, 4960–4971 (2011)
Morse, P.M.: Queues, Inventories and Maintenance. Wiley, New York (1958)
Servi, L.D., Finn, S.G.: M/M/1 queues with working vacations. Perform. Eval. 50, 41–52 (2002)
Sharma, O.P., Gupta, U.C.: Transient behaviour of an M/M/1/N queue. Stochast. Process. Appl. 13, 327–331 (1982)
Sharma, O.P., Maheswar, M.V.R.: Transient behaviour of a simple queue with discouraged arrivals. Optimization 27, 283–291 (1993)
Sudhesh, R., Raj, L.F.: Computational analysis of stationary and transient distribution of single server queue with working vacation. In: Krishna, P., Babu, M., Ariwa, E. (eds.) ObCom 2011, Part I. CCIS, vol. 269, pp. 480–489. Springer, Heidelberg (2012)
Takacs, L.: Introduction to the Theory of Queues. Oxford University Press, New York (1960)
Tarabia, A.M.K.: Transient analysis of M/M/1/N queue - an alternative approach. Tamkang J. Sci. Eng. 3(4), 263–266 (2000)
Tikhonenko, O., Kempa, W.M.: Queueing system with processor sharing and limited memory under control of the AQM mechanism. Autom. Remote Control 76(10), 1784–1796 (2015)
Vijayashree, K.V., Janani, B.: Transient analysis of an M/M/c queue subject to multiple exponential working vacation. Appl. Math. Sci. 9(74), 3669–3677 (2015)
Woźniak, M., Gabryel, M., Nowicki, R.K., Nowak, B.: An application of firefly algorithm to position traffic in NoSQL database systems. In: Kunifuji, S., Papadopoulos, G.A., Skulimowski, A.M.J., Kacprzyk, J. (eds.) KICSS 2014. AISC, vol. 416, pp. 259–272. Springer, Heidelberg (2016). doi:10.1007/978-3-319-27478-2-18. ISSN 2194-5357
Woźniak, M., Marszałek, Z., Gabryel, M., Nowicki, R.K.: Preprocessing large data sets by the use of quick sort algorithm. In: Skulimowski, A.M.J., Kacprzyk, J. (eds.) KICSS 2013. AISC, vol. 364, pp. 111–121. Springer, Switzerland (2016). doi:10.1007/978-3-319-19090-7-9. ISSN 2194-5357
Woźniak, M., Marszałek, Z., Gabryel, M., Nowicki, R.K.: Modified merge sort algorithm for large scale data sets. In: Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L.A., Zurada, J.M. (eds.) ICAISC 2013, Part II. LNCS, vol. 7895, pp. 612–622. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38610-7-56
Zhang, M., Hou, Z.: Steady state analysis of the GI/M/1/N queue with a variant of multiple working vacations. Comput. Ind. Eng. 61, 1296–1301 (2011)
Damaševičius, R., Vasiljevas, M., Šalkevičius, J., Woźniak, M.: Human activity recognition in AAL environments using random projections. Comput. Math. Methods Med. 2016, Article ID 4073584, 17 p. (2016). doi:10.1155/2016/4073584
Capizzi, G., Lo Sciuto, G., Wozniak, M., Damaševičius, R.: A clustering based system for automated oil spill detection by satellite remote sensing. In: Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L.A., Zurada, J.M. (eds.) ICAISC 2016. LNCS, vol. 9693, pp. 613–623. Springer, Heidelberg (2016). doi:10.1007/978-3-319-39384-1_54
Kempa, W.M., Wozniak, M., Nowicki, R.K., Gabryel, M., Damaševičius, R.: Transient solution for queueing delay distribution in the GI/M/1/K-type mode with “queued” waking up and balking. In: Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L.A., Zurada, J.M. (eds.) ICAISC 2016. LNCS, vol. 9693, pp. 340–351. Springer, Heidelberg (2016). doi:10.1007/978-3-319-39384-1_29
Połap, D., Woźniak, M., Napoli, C., Tramontana, E.: Real-time cloud-based game management system via cuckoo search algorithm. Int. J. Electron. Telecommun. 61(4), 333–338 (2015). doi:10.1515/eletel-2015-0043. De Gruyter Open Ltd
Połap, D., Woźniak, M., Napoli, C., Tramontana, E.: Is swarm intelligence able to create mazes? Int. J. Electron. Telecommun. 61(4), 305–310 (2015). doi:10.1515/eletel-2015-0039. De Gruyter Open Ltd
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Kempa, W.M., Kobielnik, M. (2016). Transient Solution for Queue-Size Distribution in a Certain Finite-Buffer Model with Server Working Vacations. In: Dregvaite, G., Damasevicius, R. (eds) Information and Software Technologies. ICIST 2016. Communications in Computer and Information Science, vol 639. Springer, Cham. https://doi.org/10.1007/978-3-319-46254-7_34
Download citation
DOI: https://doi.org/10.1007/978-3-319-46254-7_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-46253-0
Online ISBN: 978-3-319-46254-7
eBook Packages: Computer ScienceComputer Science (R0)