CUBO A Mathematical Journal Vol.15, No¯ 02, (53–63). June 2013 About cumulative idle time model of the message switching system S. Minkevičius VU Institute of Mathematics and Informatics, Akademijos 4, 08663 Vilnius, Lithuania. Vilnius University, Faculty of Mathematics and Informatics, Naugarduko 24, 03225 Vilnius, Lithuania. minkevicius.saulius@gmail.com ABSTRACT The purpose of this research in the queueing theory is the theorem about the law of the iterated logarithm in multiphase queueing systems and its application to the mathematical model of the message switching system. First the law of the iterated logarithm is proved for the cumulative idle time of a customer. Finally we present an application of the proved theorem for the model of the message switching system. RESUMEN El propósito de esta investigación en la teoŕıa de colas es el teorema sobre la ley de logaritmo iterado en sistemas multifase y su aplicación al modelo matemático del sis- tema de interruptores de mensajes. Primero, la ley de logaritmo iterado se prueba para el tiempo ocioso acumulado de un cliente. Finalmente presentamos una aplicación del teorema probado para el modelo de sistema de interruptores de mensajes. Keywords and Phrases: mathematical models of technical systems, queueing theory, multiphase queueing systems, a law of the iterated logarithm, cumulative idle time of a customer. 2010 AMS Mathematics Subject Classification: 60K25, 60G70, 60F17. 54 S. Minkevičius CUBO 15, 2 (2013) 1 Introduction At first, the law of the iterated logarithm is considered by investigating the cumulative idle time of a customer in multiphase queueing systems. Interest in the field of multiphase queueing systems has been stimulated by the theoretical values of the results as well as by their possible applications in information and computing systems, communication networks, and automated technological processes (see, for example, [20]). The methods of investigation of single-phase queueing systems are considered in [2], [3], etc. The asymptotic analysis of models of queueing systems in heavy traffic is of special interest (see, for example, [9], [10], [4], [5], etc.). The papers [11], [18] and others desribed the beginning of the investigation of diffusion approximation to queueing networks. Intermediate models - multiphase queueing systems - are considered rarer due to serious technical difficulties (see, for example, book [7]). The works on cumulative idle time for the multiphase queueing systems and open Jackson networks in heavy traffic are also sparse. In one of the first papers of this kind, [16] used numerical methods to study values of the mean of the cumulative idle time in single-server queues. [22] obtained limit theorems for the cumulative idle time in the systems GI/G/1 andM/G/1. [12] presented expressions for the cumulative idle time of a server in the GI/G/1 system. [19] found the Laplace transform of the distribution of the cumulative idle time in a finite time interval for the GI/G/1 system. [8] conceived the Laplace transform of the expected cumulative idle time in an M/G/1 queue. [17] considered the moderate-deviation behaviour of the cumulative idle time with single-server queues. These results complement the existing results on the heavy traffic behaviour of this process. [23] established functional central limit theorems for a cumulative idle time process in a fluid queue. These limit processes have discontinuous sample paths (e.g., to be a non-Brownian stable process, or a more general Levy process). Let the cumulative idle time of a customer in the phases of a queueing system be unrestricted, the principle of service being “first come, first served”. All the random variables studied are defined on one basic probability space (Ω, F, P). We present some definitions in the theory of metric spaces (see, for example, [1]). Let C be a metric space consisting of real continuous functions in [0, 1] with a uniform metric ρ(x, y) = sup 0≤t≤1 |x(t) − y(t)|, x, y ∈ C . Let D be a space of all real-valued right-continuous functions in [0,1] having left limits and endowed with the Skorokhod topology induced by the metric d (under which D is complete and separable). Also, note that d(x, y) ≤ ρ(x, y) for x, y ∈ D. In this paper, we will constantly use an analog of the theorem on converging together (see, for example, [6]): CUBO 15, 2 (2013) About cumulative idle time model of the message switching system 55 Theorem 1.1. Let ε > 0 and Xn, Yn, X ∈ D. If P ( lim n→∞ d(X n , X) > ε ) = 0 and P ( lim n→∞ d(Xn, Yn) > ε ) = 0, then P ( lim n→∞ d(Yn, X) > ε ) = 0. (1) 2 Statement of the problem We investigate here a k-phase queue (i.e., after a customer has been served in the j-th phase of the queue, he is routed to the j + 1-th phase of the queue, and, after the service in the k-th phase of the queue, he leaves the queue). Let us denote by tn the time of arrival of the n-th customer; by S (j) n – the service time of the n-th customer in the j-th phase; zn = tn+1 − tn; and by τj,n+j - departure of the n-th customer from the j-th phase of the queue, j = 1, 2, · · · , k. Let interarrival times (zn) at the multiphase queueing system and service times (S (j) n ) in each phase of the queue for j = 1, 2, · · · , k be mutually independent identically distributed random variables. Next, denote by BIj,n the idle time of the n-th customer in the j-th phase of the multiphase queue; F̂j,n = n∑ l=1 BIj,l stands for a cummulative idle time of the n-th customer in the j-th phase of the multiphase queue, j = 1, 2, . . . , k. When j = 1, 2, . . . , k, let δj,n = { S (j) n−(j−1) − zn, if n ≥ k 0, if n < k. Let us denote Sj,n = ∑n−1 l=1 δj,l, S0,n ≡ 0, Ŝj,n = Sj−1,n − Sj,n, xj,n = τj,n − tn, x0,n ≡ 0, x̂j,n+1 = xj,n − δj,n+1, x̂0,n ≡ 0, zj,n = x̂j,n − Sj,n, αj = Mδj,n, α0 ≡ 0, Dzn = σ20, DS (j) n = σ2j , σ̃ 2 j = σ 2 0 + σ 2 j , S (0) n = zn, j = 1, 2, . . . , k, [x] as the integer part of number x. We assume that the following conditions are fulfilled: there exists a constant γ > 0 such that sup n≥1 M|S(j)n | 4+γ < ∞, j = 0, 1, 2, . . . , k (2) and αk < αk−1 < · · · < α1 < 0. (3) In this paper, we mostly use the equations presented in [13]: x̂j,n = max 0≤l≤n (x̂j−1,l − Sj,l) + Sj,n, x̂0,n ≡ 0, n ≥ k, j = 1, 2, . . . , k. (4) 56 S. Minkevičius CUBO 15, 2 (2013) 3 On the law of the iterated logarithm for the cumulative idle time of a customer First we investigate the law of the iterated logarithm for the cumulative idle time in multiphase queues. We prove such a theorem. Theorem 3.1. If conditions (2) and (3) are fulfilled, then P ( lim n→∞ F̂j,n − (−αj) · n σ̃j · a(n) = 1 ) = P ( lim n→∞ F̂j,n − (−αj) · n σ̃j · a(n) = −1 ) = 1, j = 1, 2, . . . , k and a(n) = √ 2n ln ln n. Proof. Denote random functions D as follows F̂nj (t) = F̂j,[nt] − (−αj) · [nt] a(n) , Ẑnj (t) = ẑj,[nt] − (−αj) · [nt] a(n) , Ŝnj (t) = (−Sj,[nt]) − (−αj) · [nt]√ n , j = 1, 2, . . . , k and 0 ≤ t ≤ 1. Using a triangle inequality we see that, for each fixed ε > 0, P ( lim n→∞ d(F̂nj , Ŝ n j ) > ε ) ≤ P ( lim n→∞ d(F̂nj , Ẑ n j ) > ε 2 ) + P ( lim n→∞ d(Ẑnj , Ŝ n j ) > ε 2 ) ≤ P ( lim n→∞ ρ(F̂nj , Ẑ n j ) > ε 2 ) + P ( lim n→∞ ρ(Ẑnj , Ŝ n j ) > ε 2 ) = P   lim n→∞ sup 0≤t≤1 |Fj,[nt] − ẑj,[nt]| a(n) > ε 2   + P   lim n→∞ sup 0≤t≤1 |ẑj,[nt] − (−Sj,[nt])| a(n) > ε 2   = P   lim n→∞ max 0≤l≤n |Fj,l − ẑj,l| a(n) > ε 2   + P   lim n→∞ max 0≤l≤n |ẑj,l − (−Sj,l)| a(n) > ε 2   , j = 1, 2, . . . , k. Thus, we have for each fixed ε > 0, P ( lim n→∞ d(F̂nj , Ŝ n j ) > ε ) ≤ P   lim n→∞ max 0≤l≤n |F̂j,l − ẑj,l| a(n) > ε 2  + P   lim n→∞ max 0≤l≤n |ẑj,l − (−Sj,l)| a(n) > ε 2   , j = 1, 2, . . . , k. (5) CUBO 15, 2 (2013) About cumulative idle time model of the message switching system 57 It is proved (see [14]) that, if conditions (3) are fulfilled, then, for each fixed ε > 0, P   lim n→∞ max 0≤l≤n |F̂j,l − ẑj,l| √ n > ε   = 0, j = 1, 2, . . . , k. Using similar method as in [14] can be proven that, for each fixed ε > 0, P   lim n→∞ max 0≤l≤n |F̂j,l − ẑj,l| a(n) > ε   = 0, j = 1, 2, . . . , k. (6) So the first term in (5) converges to zero. We will prove that second term in (5) also converges to zero. Using (4) we see that ẑj,n = max 0≤l≤n (x̂j−1,l − Sj−1,l + Sj−1,l − Sj,l) = max 0≤l≤n (ẑj−1,l + Sj,l), j = 1, 2, . . . , k. Thus, ẑj,n = max 0≤l≤n (ẑj−1,l + Sj,l), j = 1, 2, . . . , k, z0,· ≡ 0. (7) Also we see that ẑj,n − j∑ i=1 Ŝi,n ≥ ẑj−1,n + Ŝj,n − j∑ i=1 Ŝi,n = ẑj−1,n − j−1∑ i=1 Ŝi,n ≥ · · · ≥ ẑ1,n − Ŝ1,n = max 0≤l≤n (Ŝ1,n) − Ŝ1,n ≥ 0. So, ẑj,n − j∑ i=1 Ŝi,n ≥ 0, j = 1, 2, . . . , k. (8) But ẑj,n ≤ max 0≤l≤n (ẑj−1,l) + max 0≤l≤n Ŝj,l = ẑj−1,n + max 0≤l≤n Ŝj,l ≤ · · · ≤ j∑ i=1 { max 0≤l≤n Ŝi,l}. From it follows that ẑj,n ≤ j∑ i=1 { max 0≤l≤n Ŝi,l}, j = 1, 2, . . . , k. (9) Using (8) and (9) we get that 0 ≤ ẑj,n − j∑ i=1 Ŝi,n ≤ j∑ i=1 { max 0≤l≤n Ŝi,l − Ŝi,n}, j = 1, 2, . . . , k. (10) 58 S. Minkevičius CUBO 15, 2 (2013) Applying (9) we achieve for each fixed ε > 0, P      max 0≤l≤n |ẑj,l − j∑ i=1 Ŝj,l| a(n) > ε      = P      max 0≤l≤n (ẑj,l − j∑ i=1 Ŝj,l) a(n) > ε      ≤ P      j∑ i=1 max 0≤l≤n { max 0≤m≤l Ŝi,m − Ŝi,l} a(n) > ε      ≤ P      k∑ i=1 max 0≤l≤n { max 0≤m≤l Ŝi,m − Ŝi,l} a(n) > ε      ≤ k∑ i=1 P   max 0≤l≤n { max 0≤m≤l Ŝi,m − Ŝi,l} a(n) > ε k   = k∑ i=1 P   max 0≤l≤n { max 0≤m≤l (−Ŝi,l−m)} a(n) > ε k   = k∑ i=1 P   max 0≤l≤n { max 0≤m≤l (−Ŝi,m)} a(n) > ε k   ≤ k∑ i=1 P   max 0≤l≤n (−Ŝi,l) a(n) > ε k   , j = 1, 2, . . . , k. (11) Thus, we have that for each fixed ε > 0, P      max 0≤l≤n |ẑj,l − j∑ i=1 Ŝj,l| a(n) > ε      ≤ k∑ i=1 P   max 0≤l≤n (−Ŝi,l) a(n) > ε k   , j = 1, 2, . . . , k. (12) Note (see, for example, [14]) that for each fixed ε > 0, P   lim n→∞ max 0≤l≤n (−Ŝi,l) a(n) > ε   = 0, j = 1, 2, . . . , k, (13) if conditions (3) are fulfilled. Using relation k∑ i=1 Ŝi,n = −Sj,n, j = 1, 2, . . . , k and (12) - (13) we obtain that for each fixed ε > 0, P   lim n→∞ max 0≤l≤n |ẑj,l − (−Sj,l)| a(n) > ε   = 0 j = 1, 2, . . . , k. (14) Using the theorem on the law of the iterated logarithm for random functions Ŝnj (t), j = 1, 2, . . . , k (see, for example, [21]) we achieve that P ( lim n→∞ (−Sj,n) − (−αj) · n σ̃j · a(n) = 1 ) = 1 and P ( lim n→∞ (−Sj,n) − (−αj) · n σ̃j · a(n) = −1 ) = 1, j = 1, 2, . . . , k. (15) CUBO 15, 2 (2013) About cumulative idle time model of the message switching system 59 Thus, applying (1), (5), (6), (14) and (15) we obtain that P ( lim n→∞ F̂j,n − (−αj) · n σ̃j · a(n) = 1 ) = 1 and P ( lim n→∞ F̂j,n − (−αj) · n σ̃j · a(n) = −1 ) = 1, j = 1, 2, . . . , k. (16) The proof of Theorem 3.1 is complete. 4 On the model of switching facility In this part of the paper, we will present an application of the proved theorem - a mathematical model of message switching system. As noted in the introduction, multiphase queueing systems are of special interest both in theory and in practical applications. Such systems consist of several service nodes, and each arriving customer is served at each of the consecutively located node (frequently called phases). A typical example is provided by queueing systems with identical service. Such systems are very important in applications, especially to message switching systems. In fact, in many comunication systems the transmission times of the customers do not vary in the delivery process. So, we investigate a message switching system which consists of k phases and in which S j n = Sn, j = 1, 2, . . . , k (the service process is identical in phases of the system). Let δn = { Sn−k − zn, if n ≥ k 0, if n < k. Also, let us note α = Mδn, Dzn = σ 2 0, DSn = σ 2, σ̃2 = σ20 + σ 2, F̂j,n = n∑ l=1 BIj,l, j = 1, 2, . . . , k. We assume that the following conditions are fulfilled: there exists a constant γ > 0 such that sup n≥1 M|Sn| 4+γ < ∞ (17) and α < 0. (18) Similarly as in the proof of Theorem 3.1, we present the following theorem on the law of the iterated logarithm for the cumulative idle time of a data packet in message switching systems. 60 S. Minkevičius CUBO 15, 2 (2013) Theorem 4.1. If conditions (17) and (18) are fulfilled, then P ( lim n→∞ F̂j,n − (−α) · n σ̃ · a(n) = 1 ) = P ( lim n→∞ F̂j,n − (−α) · n σ̃ · a(n) = −1 ) = 1, j = 1, 2, . . . , k. We see that the cumulative idle time of data packet is the same in the all phases of system. 5 Computing example We see that Theorem 4.1 implies that for fixed ε > 0 there exists n(ε) such that for every n ≥ n(ε), with probability one (1 − ε) · σ̃ · a(n) − α · n ≤ F̂j,n ≤ (1 + ε) · σ̃ · a(n) − α · n, (19) where a(n) = √ 2n ln ln n, α = M(Sn − zn) < 0, σ̃ 2 = Dzn + DSn, j = 1, 2, . . . , k. From this we can obtain (1 − ε) · σ̃ · a(n) − α · n ≤ F̂j,n ≤ (1 + ε) · σ̃ · a(n) − α · n, |M(F̂j,n − (−α) · n) − {(1 − ε) · σ̃ · a(n)}| ≤ 2 · ε · σ̃ · a(n), |M ( F̂j,n − (−α) · n) σ̃ · a(n) ) − (1 + ε)| ≤ 2 · ε, j = 1, 2, . . . , k. (20) So from (20) we can get MF̂j,n ∼ (−α) · n + (1 + ε) · σ̃ · a(n), j = 1, 2, . . . , k. (21) MF̂j,n is average cumulative idle time of n-th message (time, which system is waiting for processing message until n-th message arrival to the system). We see from (21) that MF̂j,n consists of linear function and nonlinear slowly increasing function (1 + ε) · σ̃ · a(n), j = 1, 2, . . . , k. Now we present a technical example from the computer network practice. Assume that mes- sages arrive at the computer v1 at the rate λ of 20 per hour during business hours. These messages are served at a rate µ of 25 per hour in the computer v1. After service in the computer v1 messages arrive at the second computer v2. Also we note that messages are served at a rate µ of 25 per hour in the computer v2. So, messages is served in computers v1, v2,. . . ,vk, and after messages are served in computer vk, they leave computer network. So, Mzn = 1/λ = 1/20 = 0.05, MSn = 1/µ = 1/25 = 0.04, α = 0.04 − 0.05 = −0.01 < 0, Dzn = 1/λ = 1/20 = 0.05, DSn = 1/µ = 1/25 = 0.04, σ̃ 2 = 41/104, σ̃ ∼ 0.064, ε = 0.001, n ≥ 100. CUBO 15, 2 (2013) About cumulative idle time model of the message switching system 61 Thus, MF̂j,n ∼ (−α) · n + (1 + ε) · σ̃ · a(n) = (0.01) · n + (0.064) · a(n), j = 1, 2, . . . , k. (22) From (22) we get MF̂j,n n = (0.01) + (0.064) · √ 2 ln ln n n , j = 1, 2, . . . , k. (23) Now we present figure for MF̂j,n n , j = 1, 2, . . . , k, when 100 ≤ n ≤ 1000, ε = 0.001 (see (23) and Table 1). Time n MF̂j,n n , j = 1, 2, . . . , k 100 0.02118510415 200 0.01826415546 300 0.01689524794 400 0.01605525217 500 0.01547101209 600 0.01503369681 700 0.01469010032 800 0.01441067288 900 0.01417749453 1000 0.01397897294 Table 1 Summary of computing results. We see that when α = −0.01 < 0, computer network is busy 99 % of this time. Corollary 5.1. Average idle time of message system direcly depends of traffic coefficient α and time n and is the same in all phases of message system. Received: September 2010. Accepted: September 2012. References [1] Billinsley P. (1968). Convergence of probability measures. Wiley, New York. [2] Borovkov A. (1972). Stochastic Processes in Queueing Theory. Nauka, Moscow (in Russian). [3] Borovkov A. (1980). Asymptotic Methods in Theory of Queues. Nauka, Moscow (in Russian). 62 S. Minkevičius CUBO 15, 2 (2013) [4] Iglehart D.L., Whitt W. (1970a). Multiple channel queues in heavy traffic. I. Advances in Applied Probability, 2, 150-177. [5] Iglehart D.L., Whitt W. (1970b). Multiple channel queues in heavy traffic. II. Sequences, networks and batches. Advances in Applied Probability, 2, 355-369. [6] Iglehart D.L. (1971). Multiple channel queues in heavy traffic. IV. Law of the iterated loga- rithm. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 17, 168-180. [7] Karpelevich F.I., Kreinin A.I. (1994). Heavy traffic limits for multiphase queues. American Mathematical Society, Providence. [8] Kella O. (1992). Concavity and reflected Levy process. Journal of Applied Probability, 29(1), 209-215. [9] Kingman J. (1961). On queues in heavy traffic. J. R. Statist. Soc., 24, 383-392. [10] Kingman J. (1962). The single server queue in heavy traffic. Proc. Camb. Phil. Soc., 57, 902-904. [11] Kobyashi H. (1974). Application of the diffusion approximation to queueing networks. Journal of ACM, 21, 316-328. [12] Milch P., Waggoner M. (1970). A random walk approach to a shutdown queueing system. SIAM J. Appl. Math., 19, 103-115. [13] Minkevičius S. (1986). Weak convergence in multiphase queues. Lietuvos Matematikos Rinkinys, 26, 717-722 (in Russian). [14] Minkevičius S. (2005). On the full idle time in multiphase queues. Lietuvos Matematikos Rinkinys (in Russian, in appear). [15] Minkevičius S, Kulvietis G. (2004). A mathematical model of the message switching system. Proceedings of the Seventh International Conference ”Computer Data Analysis and Model- ing”, Minsk, September 6-10, 2004, 2, 96-100. [16] Pike M. (1963). Some numerical results for the queueing system D/Ek/1. J. R. Statist. Soc. Ser. B, 25, 477-488. [17] Puhalskii A. (1999). Moderate deviations for queues in critical loading. Queueing Systems Theory Appl., 31(3-4), 359-392. [18] Reiman M.I. (1984). Open queueing networks in heavy traffic. Mathematics of Operations Research, 9, 441-459. [19] Ridel M. (1976). Conditions for stationarity in a single server queueing system. Zastos. Mat., 15(1), 17-24. CUBO 15, 2 (2013) About cumulative idle time model of the message switching system 63 [20] Saati T., Kerns K. (1971). Analytic Planning. Organization of Systems. Mir, Moscow (in Russian). [21] Strassen V. (1964). An invariance principle for the law of the iterated logarithm. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 3, 211-226. [22] Takacs L. (1974). Occupation time problems in the theory of queues. In: Lecture Notes in Economics and Mathematical Systems, 98, Springer-Verlag, Berlin, Heidelberg, New York, 91–131. [23] Whitt W. (2000). Limits for cumulative input processes to queues. Probab. Engrg. Inform. Sci., 14(2), 123-150.