Nonlinear Analysis 65 (2006) 2153–2168 www.elsevier.com/locate/na
Hybrid queueing systems with hysteretic bilevel control policies J.H. Dshalalow a,∗ , S. Kim a , L. Tadj b a Department of Mathematical Sciences, College of Science, Florida Institute of Technology, Melbourne FL, 32901, USA b Department of Statistics and Operations Research, College of Science, King Saud University, P.O.Box 2455,
Riyadh 11451, Saudi Arabia
Abstract This article analyzes a stochastic hybrid system with compound Poisson input, general batch service, and two vacation modes that operate in accordance with a so-called “bilevel hysteretic control.” In the context of queues with vacations, most stochastic systems function either under multiple or single vacation regimes and they are initiated whenever the queue length becomes zero. In this model we combine the two modes in one hybrid system that switches to a multiple or single vacation modes (which consists of multiple or single segments), respectively, whenever the queue drops below some r1 or falls into [r1 , r2 ) upon the end of a service. The servicing facility then assumes some other activities. The main service is restored when the queue length reaches or exceeds some N (≥ r2 ) upon the completion of a vacation segment. We use fluctuation analysis and semi-regenerative techniques to arrive at closed form functionals for the steady state probabilities of queueing processes both for discrete and for continuous time parameter processes and discuss special cases to demonstrate the applicability of the results. The latter can potentially be used to optimize the system with respect to parameters r1 , r2 and N. c 2006 Elsevier Ltd. All rights reserved. MSC: primary 60K10, 60K25; secondary 90B22, 90B25 Keywords: Hybrid stochastic system; Hysteretic control; N-policy; Queueing; Multiple vacations; Single vacations; Fluctuation theory; Random walk; Semi-regenerative process; Markov process
∗ Corresponding author.
E-mail addresses:
[email protected] (J.H. Dshalalow),
[email protected] (L. Tadj). c 2006 Elsevier Ltd. All rights reserved. 0362-546X/$ - see front matter doi:10.1016/j.na.2005.12.044
2154
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
1. Introduction A hybrid system is one that consists of two or more subsystems and a rule (or policy) that orchestrates switching among them. Hybrid systems occur in telecommunications, computer networks, power systems, dams, and electric circuits, to name but a few. Consequently, many real world situations can be modelled by hybrid systems, some of which can fit well into deterministic models, but for many others stochastic hybrid systems are more adequate options. Hybrid systems have become more and more prominent in engineering and technology. We mention just a few related works. Bohacek et al. [1] used hybrid systems to model and analyze the transient and steady-state behavior of multiple TCP flows that share a single common bottleneck link. Erbes [2] formulates the Dynamic Power Management problem, which refers to the strategies employed at system level to reduce energy expenditure, as a hybrid automaton control problem. Wirth et al. [3] use ideas from hybrid systems theory to model the dynamics of AIMD communication networks as switched, or time-varying, discrete time linear systems. Hespanha [4] constructs a stochastic hybrid model for on–off TCP flows that considers both the congestion-avoidance and slow-start modes and takes directly into account the distribution of the number of bytes transmitted. Savkin et al. [5] apply mathematical models in terms of hybrid dynamical systems to analyze the medium access control problem for a class of wireless communication networks. Julius et al. [6] develop a notion of approximate bisimulation for a class of stochastic hybrid systems, namely, the jump linear stochastic systems (JLSS). The bisimulation function quantifies the distance between a given JLSS and its abstraction, and hence quantifies the quality of the abstraction. Julius [7] generalizes Julius et al. [6] for jump linear stochastic systems (JLSS). He demonstrates that linear stochastic hybrid automata can be cast as a modified JLSS and modifies the procedure for constructing the stochastic bisimulation function accordingly. Barany and Krupa [8] use a stochastic hybrid system to determine the stability of multiple access network control schemes. Queues are less common in the growing stream of hybrid systems. Lestas and Vinnicombe [9] is among a few treatments to the best of our knowledge. (They analyze congestion control in data networks by modelling an M/M/1 queue with delayed feedback as a stochastic hybrid system and analyze the transient probability distribution of the states with partial differential equations.) This is because many queues with all kinds of switching modes were not recognized as hybrid systems and thus they fell into different categories. We consider in this paper a very practical and common stochastic hybrid system that arises in queueing and communication networks (cf. Hespanha [4] and Savkin et al. [5]). This system is characterized by a flow of units or signals arriving in packets at a single queueing node (referred to as a servicing facility or server) and being further processed. The system has a regular mode and two additional modes which the system is switched to, dependent on the status of the system at some selected decision epochs. (Instead of using the term a “subsystem” we will use the word “mode” which will better fit our model description.) Upon service completion of a packet, the system lets the server run in one of the three hybrid modes. The primary mode is when the line of signals at the node is long enough, say at least r2 units or longer, so that the server will go on with a next packet to be called from the buffer (or line). If the buffer content drops below some r1 (≤ r2 ) upon any service completion, the system is switched to vacation mode 1 (or long vacation mode) characterized by a different type of server activity. The latter can mean that the system undergoes some maintenance or has the server perform a different type of work, which is needed but which the system cannot afford whenever the buffer level is critically high. (Communication networks routinely do all kinds of maintenance services.
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
2155
Individual PC units can be programmed to do routine check-ups when the intensity of primary jobs slows down.) A type of activity in mode 1 that we have in mind is that the server will render a sequence of jobs up until the buffer fills, so that the server can be called back and resume its service of primary jobs. It is often assumed that the buffer content should be filled with N units (where N ≥ r2 ) to assure that they will keep the server busy long enough, thereby aiming to minimize the frequency of switches between modes, even though some occasional alternative activities are desired. This is known in communication and queueing as the “N-policy”. Consequently, in mode 1, the server performs a sequence of alternative jobs as long as needed for the buffer to fill in to N or higher. Any such second priority job may not be interrupted, even if the buffer attains the desired quantity of N. Such a “dynamic” priority rule is more realistic compared to the “absolute” priority rule when the server is called off in the middle of its maintenance. (Note that the absolute priority rule would require a simpler analytical solution to the problem.) In terms of communication and queueing, this is referred to as vacations of the server, and in fact, more specifically, multiple vacations (also referred to as a long vacation), as opposed to the single (or short) vacation case associated with mode 2 introduced below. The system is said to be in vacation mode 2 (or short vacation mode) when the buffer content drops below r2 (r1 ≤ r2 ≤ N) but not below r1 . In this case, the server takes one single vacation (or performs one single alternative job) and then returns to the system unconditionally, resting if the buffer content is still below N. While resting, the server is fully alert and ready to resume its primary work when the buffer content becomes large by breaking its rest immediately. It is obvious that leaving behind the buffer filled with more units than in mode 1, the server is expected to resume its main service sooner than from within mode 1. Virtually all parameters can be controlled to warrant the most optimal system performance. Our model generalizes most N-policy vacation queues, even those with hysteretic control. The latter refers to the rule when the server leaves on vacation when the queue drops below some r and it resumes its service when the queue accumulates to an N (≥ r ). In this case, the status of the system (i.e. when it is in busy, idle or vacation modes) cannot be determined whenever the queue length falls into the critical layer [r, N), as one needs to know how the system reached it: by falling or rising. This corresponds to the common physical notion of hysteresis. Now, among systems with server vacations (cf. Doshi [10,11] and Takagi [12]), there are a few with hysteretic control (Dshalalow [13,14], Teghem [15,16] and Loris-Teghem [17,18]), and in every one of them, the system either goes on multiple vacations, single vacations, or stays simply idle. Our model contains two models in one, thereby it is a hysteretic bilevel control hybrid system, with two critical layers, [r1 , r2 ), and [r2 , N), so that the status of the system will be determined based on two parameters: the queue length and rate, i.e. the queue length reveals the system status, only with the additional information about the direction the queue evolved from prior to attaining one of these layers. Thus, such a system is non-Markovian, regardless of the assumptions made on service and vacation distributions. The two types of vacation modes is just one of several ways to gain control over the system. In fact, the optimal design and control of queues is a popular contemporary issue that is receiving a lot of attention, as shown in the recent survey of Tadj and Choudhury [19]. Several control policies are also discussed by Dshalalow [25]. The hybrid queueing system with two types of vacation was first introduced by Zhang et al [20] who investigated the M/G/1 queue with vacation types and a two-threshold policy and developed a finite search algorithm to find the optimal values of the two thresholds r1 and r2 . Zhang et al. [21] generalize Zhang et al. [20] to the case of multiple (N ≥ 2) vacation types.
2156
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
They introduce a semi-Markov decision process in order to specify an optimal server policy. Ke [23] improves Zhang et al. [20] by incorporating server startup to the queueing system while Ke [22] generalizes Ke [23] to the case of compound Poisson process. In both articles [22,23], Ke developed the total expected cost function per unit time to determine the optimal values of the two thresholds. In this paper, we generalize the available literature on the topic to the case of bulk service queueing systems by allowing service of packets of units (i.e. batch service) instead of single service. We also use the theory of fluctuations (Dshalalow [14]) to obtain closed form functionals of the steady state queue length distributions, for both the discrete and the continuous time parameter processes. Fluctuations is a useful methodology in this case, because we deal with a random walk observed at random times by another stochastic process (corresponding to the history of the queueing process during vacation modes). Consequently, finding the first observed moment of time when the process exists the set [0, N) (the first passage time) is not a trivial task by itself and furthermore, the queue length at the first passage time when the server vacations are terminated is another element of fluctuation theory. Furthermore, when analyzing the continuous time parameter process, we need to “restore” some information on the input process in the vicinity of the first passage time and apply the techniques of “time sensitive functionals” in fluctuation theory, which have been initiated in Dshalalow [14]. Special cases demonstrate the utility of the results we claim to be tractable. The paper is organized as follows. In Section 2 we formalize our model. In Section 3 we bring all necessary information from fluctuation theory of two-variate renewal processes. In Section 4 we apply formulas of Section 3 to each of the two vacation modes. Sections 5 and 6 deal with discrete and continuous time parameter processes. Some special cases discuss tractability of the derived formulas. 2. Model description and notation In this section, we describe the hybrid queueing system with three modes and introduce some basic notation. All stochastic processes related to this hybrid system will be defined on some probability space (Ω , U, P). The system is of bulk arrival, bulk service, single server, infinite capacity type. The arrival, service processes, and hybrid disciplines are formalized as follows. 2.1. Arrival process Units arrive at epochs of time t1 , t2 , . . . in batches of variable sizes δ1 , δ2 , . . ., in accordance with a marked Poisson process δi ε t i , (2.1) Π = i
(where εa is the Dirac point mass) of rate λ, with position-independent marking. More specifically, δi ’s are independent and identically distributed (iid) random variables (r.v.’s) belonging to a stochastically equivalent class [δ] with a(z) = E[z δ ] as their common probability generating function (pgf) and a¯ = E[δ] as the mean batch size. Thus we use δ also to denote any representative of this class. 2.2. Service process Let T0 , T1 , T2 , . . . represent the service completion epochs, and let Q(t) and Q n = Q(Tn ) represent the number of units in the system at time t and at time Tn , respectively, with Q(t)
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
2157
being a right-continuous process. The time interval Cn = [Tn−1 , Tn ),
n = 1, 2, . . . ,
is referred to as the nth service cycle. The portion of queueing process over Cn begins with the number of units at the servicing facility right after the departure of the nth batch of units at Tn−1 and it is subject to variations over Cn to be described in Section 2.3. Units waiting in line are called for service in accordance with the FIFO rule, and once called, a group of them enters a (single) servicing facility (or server) of capacity R (which is the maximum number of units the server can take at a time). Consequently, the server takes a minimum of R or Q n−1 if the service at Tn−1 does begin. Its duration is σn . We assume that service times σ1 , σ2 , . . . are iid r.v.’s and independent of the arrival process. Let each σn belong to a stochastically equivalent class [σ ] of r.v.’s with a common Laplace–Stieltjes transform (LST) β(θ ) = E[e−σ θ ] and finite first mean σ¯ = E[σ ]. 2.3. Service cycle The nth service cycle Cn includes the nth service. However, besides service, the system can enter different vacation and idle modes dependent on the system’s status and thus the nth service cycle can be filled with various other server’s activities, referred to as hybrid (or vacation) modes. These are as follows and for convenience we will describe them on the first service cycle C1 (the same applies to any other service cycle). 2.4. Hybrid modes Let r1 , r2 and N be nonnegative integers such that r1 ≤ r2 ≤ N. If upon any service completion at T0 = 0 and the subsequent departure of a processed group of units, the queue length Q 0 ≥ r2 , service will continue and the server will pick up a batch in accordance with the above rule specified in Section 2.2. Such a cycle will consist of one service only and we will say that it belongs to the primary mode. If the queue length Q 0 at the beginning of the first service cycle drops below r1 , the server switches to vacation mode 1, which consists of maintenance or servicing of lower priority units or any other activities also referred as vacations. The server performs a series of vacation segments at τ0 = T0 = 0, τ1 , τ2 , . . . until the number of first priority units (the buffer content) reaches or exceeds N at the end of a vacation segment, say τν . (It is understood that no vacation segment is to be interrupted, in accordance with the dynamic priority rule.) Then the first service begins at τν . It lasts σ1 and ends at T1 = τν + σ1 . The server vacations in vacation mode 1 therefore form a terminating renewal process T =
ν
ετ j .
(2.2)
j =0
As for the renewal process, we have τ ∼ τ1 , τ2 − τ1 , · · ·, where [τ ] is the equivalence class of r.v.’s with the common LST v(θ ) and mean τ¯ (i.e. the LST and the mean of a vacation segment in the long vacation mode). The random variable ν will be defined in (2.6). The buffer content is observed upon completion of every vacation segment and it evolves as follows. Let V j be the number of the first priority units entering the system during the j th
2158
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
vacation segment [τ j −1, τ j ), j = 1, 2 · · ·. Obviously, V j ’s are iid r.v.’s stochastically equivalent to some r.v. V with the pgf E E[z V |τ ] = v(λ − λa(z)), (2.3) where v(θ ) is the LST of τ . It can also be easily shown that L k = V0 + V1 + · · · + Vk ,
k = 0, . . . , ν,
(2.4)
(V0 is the initial content of the buffer at τ0 = T0 = 0) forms a two-variate (or marked) terminating renewal process (L, T ) =
ν
V j ετ j .
(2.5)
j =0
The random variable ν is defined as ν = inf{k : L k ≥ N}.
(2.6)
Now, the system switches to vacation mode 2 when the number of all units in the system at time T0 = 0 drops below r2 but is greater than or equal to r1 . The server in this case performs a single external job other than regular service (of first priority units) and then it returns to the system. If upon its return, the buffer content is still below N units, the server rests until the queue crosses N with one of the arriving groups. The formalism of vacation mode 2 is then reduced to a terminating marked delayed Poisson process (S, T˜ ) =
ν˜
δ j ετ j .
(2.7)
j =0
The latter needs some more clarification. If the buffer content falls into interval [r1 , r2 ), the server undertakes a single vacation and then gets back to the system. Now, δ0 stands for the number of units that enter the system during the time interval: [0, t0 ], plus the initial content of the buffer at zero, i.e. Q 0 . The other intervals (t j , t j +1 ], j = 0, 1, . . ., are exponentially distributed with parameter λ and the rest of δ j ’s are the arriving batches at the t j ’s as per Section 2.1. The delayed process (S, T˜ ) has position independent marking except for (t0 , δ0 ). The terminating “index” ν˜ is defined as ν˜ = inf{ j : S j = δ0 + · · · + δ j ≥ N}.
(2.8)
Consequently, (S, T˜ ) is the original marked Poisson process Π modified and controlled by vacation mode 2. We also assume that t0 has v(θ ˜ ) as the LST and with mean t¯0 , where t0 is the first (and the only) vacation segment in the short vacation mode (or mode 2). 3. Preliminaries This section will present some basic results of fluctuation theory needed for the upcoming treatment of our hybrid queueing system. Let (A, τ ) = X i ετi (3.1) i
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
2159
be a generic marked delayed renewal process (random measure), generally, with position dependent marking. The latter roughly means that the sequence n (An , τn ) = X i , τn i=0
forms a two-variate renewal process, and while the vectors (X i , χi = τi − τi−1 ) are independent for all i , X i depends on χi = τi − τi−1 , for each i = 0, 1, . . . , τ−1 = 0. We also assume X i to be nonnegative-integer-valued, while χi are nonnegative-real-valued. Since (A, τ ) is delayed, (X 1 , χ1 ), (X 2 , χ2 ), . . . are identically distributed belonging to the equivalence class [(X, τ )] expressed through its joint transform γ (z, θ ) = E z X e−θτ , (3.2) while (X 0 , τ0 ) is distributed differently from (X, τ ) and we assume that its transform is γ0 (z, θ ) = E z X 0 e−θτ0 .
(3.3)
Let N be a positive integer. Define ν = inf{n : An ≥ N}.
(3.4)
We assume that the process (A, τ ) runs up until its “active” variant mark An exits the set [0, N). When this takes place at some of the epochs {τ j }, i.e. precisely at τν , the process (A, τ ) is considered to be terminated at τν , which is referred to as the first passage time of A or the first exit time of set [0, N) by (A, τ ). Therefore, the “terminating” version of (A, τ ) is (A, τ ) =
ν
X i ετi ,
(3.5)
i=0
for which we will be using the same character as in (3.1), for the sake of brevity. Now, let us denote ∂k 1 1 lim −1 (3.6) Dk (·) = k! x→0 ∂ x k 1 − x (·), k ≥ 0, 0, k < 0. (This is actually the inverse of an operator D introduced in Dshalalow [24], but for consistency and in agreement with [24,25], we will use the notation of (3.6).) Then [24],
γ0 (x z, θ ) E z Aν e−θτν = γ0 (z, θ ) − [1 − γ (z, θ )]D−1 (3.7) N−1 1 − γ (x z, θ ) . In particular, the marginal LST of τν is
E e
−θτν
=
γ0 (1, θ ) − [1 − γ (1, θ )]D−1 N−1
γ0 (x, θ ) , 1 − γ (x, θ )
which yields the mean value of the first passage time
γ0 (x) −1 E[τν ] = τ¯0 + τ¯ D N−1 , 1 − γ (x)
(3.8)
(3.9)
2160
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
where τ¯0 = E[τ0 ], τ¯ = E[τ ], and γ0 (z) and γ (z) are marginal pgf’s of their respective transforms γ0 (z, θ ) and γ (z, θ ). We will need one more result. Suppose Y : Ω → {0, 1, . . .} with bk = P{Y = k} and pgf g(z) and for some nonnegative integer R, let us define the operator H R on the space of all complex-valued functions analytic at zero as
−R (H R g)(z) = z −R g(z) + D−1 g(x z) . (3.10) g(x) − z R−1 Then by the Lemma of Dshalalow and Yellen [26], we have + E z (Y −R) = (H R g)(z),
(3.11)
where f + = sup{ f, 0}. Observe that H R is a linear operator. We will also use the modification of H R defined as φ R = z R H R . Then from (3.10),
R z g(x) − g(x z) . (φ R g)(z) = g(z) + D−1 R−1
(3.12)
4. Fluctuation processes in vacation modes We will apply the formulas of Section 3 for vacation modes 1 and 2, just to get the information about the buffer contents at the beginning of service within the first service cycle C1 . Consequently, some of the processes will be considered on probability space (Ω , U, (P i )i=0,1,··· ). Most of the transforms will be considered w.r.t. the probability measure P i (= P{·|Q 0 = i }) and the expectation w.r.t. P i will be denoted by E i . (i) Recall that in vacation mode 1, the server takes a “long vacation” when the total number of units in the system Q 0 is less than r1 . Then vacation mode 1 is activated and the server undertakes a series of vacation segments or jobs, during one of which the actual crossing of N will take place. However, since this terminal job will not be interrupted, the server will not be called off (in the middle of the job) until this job is completed. By then the buffer may well be far above N. (It should be noted that such lack of flexibility is more realistic, while analytically it is more challenging.) We will apply formula (3.7) to the component L of (L, T ) (see (2.5)) under the following considerations. (1) The initial state of the system Q 0 will be assigned to L 0 = V0 and τ0 will be set to 0. We will then have the marginal transform γ0 (z) = E z V0 = E z Q 0 . (2) γ (z) = E z V (V ∼ V1 , V2 , . . .) which by formula (2.3) is γ (z) = v(λ − λa(z)), (v(θ ) = E[exp(−θ τ )], cf. Section 2.4). Consequently, from (3.7) we have E Q 0 z L ν = z Q 0 − z Q 0 [1 − γ (z)]D−1 N−Q 0 −1 on {Q 0 < r1 } using the property that
−1 Dk−1 x j g(x) = Dk− j {g(x)}
(4.1)
1 1 − γ (x z)
(4.2)
(4.3)
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
2161
(cf. Dshalalow [25]). From (3.9) we also have the conditional mean value of the first passage time on {Q 0 < r1 }:
1 E Q 0 [τν ] = τ¯ D−1 (4.4) N−Q 0 −1 1 − γ (x) bearing in mind that τ0 = 0 a.s. and recalling that τ¯ = E[τ ]. (ii) In vacation mode 2, the server goes on a single vacation trip and then returns to the system unconditionally. It resumes service of the first priority units in the event that the buffer increases to at least N on its return. Otherwise, it rests until the buffer content rises to N or more on one of the arrivals. We apply formula (3.7) under the following interpretation. (1) The value δ0 will be composed of the initial value Q 0 of the system just prior to the server’s vacation leave, plus the number of units V˜0 that enter the system during this vacation period which lasts t0 . Thus we have on {Q 0 ∈ [r1 , r2 )}, (4.5) γ0 (z) = E Q 0 E z δ0 |t0 = ψ(z)z Q 0 , where ψ(z) := v(λ ˜ − λa(z))
(4.6)
v(θ ˜ ) = E[exp{−θ t0 }].
(4.7)
and
(2) Clearly, γ (z) = a(z). Similarly, from (3.7) we have on {Q 0 ∈ [r1 , r2 )} that
ψ(x z) E Q 0 [z Sν˜ ] = z Q 0 ψ(z) − z Q 0 [1 − a(z)]D−1 N−Q 0 −1 1 − a(x z) . From (3.9), the mean value of the first passage time is
ψ(x) 1 −1 Q0 ¯ E [τν ] = t0 + D N−Q 0 −1 , λ 1 − a(x)
(4.8)
(4.9)
(4.10)
where t¯0 = E[t0 ].
(4.11)
5. Embedded process As for most M/G/1 type systems, the queueing process Q(t), or more formally, (Ω , U, (P i )i=0,1,··· ; Q(t), t ≥ 0) → {0, 1, . . .}, is semi-regenerative relative to the sequence {Tn } of service completions and thus {Q n } is an embedded time homogeneous Markov chain, which is subject to the following transitions (Q 0 − R)+ + A1 , Q 0 ≥ r2 , Q 1 = (Sν˜ − R)+ + A1 , r1 ≤ Q 0 < r2 , (5.1) (L ν − R)+ + A1 , 0 ≤ Q 0 < r1
2162
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
where An is the quantity of units arriving in the system during the period of nth service. Obviously, {An } is a sequence of iid r.v.’s with the common LST (5.2) α(z) = E E z A1 |σ = β(λ − λa(z)), where β(θ ) is the LST of σ ∼ σ1 , σ2 , . . .. The embedded process {Q n } is ergodic if and only if ρ = λa¯ σ¯ < R, where a¯ and σ¯ are the means of arriving batches and service times, respectively. Under this condition, the invariant probability measure p = ( p0 , p1 , . . .) of {Q n }, in terms of its z-transform, P(z), satisfies the equation P(z) = pi Pi (z),
(5.3)
i≥0
where Pi (z) = E i [z Q 1 ],
(5.4)
and this is also the pgf of the i th row of the transition probability matrix P of {Q n }. From (5.1) and (3.11), having in mind (3.10), (4.2) and (4.9), we easily find + r2 ≤ i, α(z)z (i−R) , (5.5) Pi (z) = α(z)(H R E i [z Sν˜ ])(z), r1 ≤ i < r2 , α(z)(H R E i [z L ν ])(z), 0 ≤ i < r1 . Now, we substitute (5.5) into (5.3) to solve Eq. (5.3) w.r.t. the series T˜ (z) =
∞
pi z i−r2 .
(5.6)
i=r2
With the earlier assumption that R ≤ r2 (the case for R > r2 needs to be treated separately and it will be a routine elaboration of upcoming expressions with slightly less elegant forms), after straightforward algebra we get from (5.3) and (5.5) r 2 −1
T˜ (z) =
i=0 z r2
pi {Pi (z) − z i } − α(z)z r2 −R
.
(5.7)
Obviously, T˜ (z) is analytic inside a disk B(0, ε), with ε = ∞ i=r2 pi > 0. The denominator of (5.7) turns to zero r2 − R times at z = 0, i.e. inside B(0, ε). Due to analyticity of T˜ (z) inside that disk, the numerator N˜ (z) =
r 2 −1
pi {Pi (z) − z i }
(5.8)
i=0
of (5.7) must also have a zero at z = 0 of the same multiplicity. Therefore, this gives us exactly r2 − R equations if r2 > R: dk ˜ N (z) = 0, z→0 dz k lim
k = 0, . . . , r2 − R − 1.
(5.9)
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
Coming back to (5.3), we now solve it w.r.t. P(z) to have r 2 −1 α(z) [Ei (z) − z i ] pi , P(z) = R z − α(z) i=0 with the notation (φ R E i [z L ν ])(z), 0 ≤ i < r1 , Ei (z) := (φ R E i [z Sν˜ ])(z), r1 ≤ i < r2 ,
2163
(5.10)
(5.11)
and the utility of the operator defined in (3.12). Now, P(z) is analytic inside the open disk B(0, 1) and under the ergodicity condition, according to Abolnikov and Dukhovny (a version of Rouche’s theorem) [27], the function D(z) := z R − α(z)
(5.12)
has exactly R roots in the closure clB(0, 1), of which one root is z 1 = (1, 0) corresponding to the boundary condition P(1) = 1. Because P(z) is also continuous on the boundary ∂ B(0, 1), the function N(z) :=
r 2 −1
[Ei (z) − z i ] pi
(5.13)
i=0
is also analytic in B(0, 1) and continuous on its boundary. (Now, according to Dukhovny [28], if there are any roots of D(z) on ∂ B(0, 1), they are simple.) The roots of D(z) must also be the roots of N(z), with the same multiplicities. This will give us precisely R equations lim
z→z j
dk N(z) = 0, dz k
k = 0, . . . , m j − 1,
s
m j = R,
(5.14)
j =1
for finding pi ’s. If R is strictly less than r2 , then we have r2 − R more equations as per (5.8). Consequently, we have a total of r2 linear equations in pi ’s and the same number of unknowns. There are various methods for finding the R roots of D(z) even if it is not a polynomial. (cf. Atanassova [29].) Example. Although the formulas obtained may look cumbersome and symbolic, this is not the case and even the presence of nested operators φ R and Dn−1 is not a problem at all and they are in reality reducible to closed forms. We will demonstrate how to calculate φ R E i [z L ν ] for a special case. We let service and vacations be exponentially distributed and arrival batches be geometric, i.e. pz , p+q =1 (5.15) a(z) = E[z δ ] = 1 − qz and β(θ ) = E[e−θσ ] =
1 . 1 + σ¯ θ
(5.16)
The pgf of the number of arrivals during a service time is thus α(z) = β(λ − λa(z)) =
1 − qz . 1 − qz + λσ¯ (1 − z)
(5.17)
2164
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
The pgf of the number of arrivals during a vacation segment in mode 1 (with mean vacation time v) becomes γ (z) = v(λ − λa(z)) =
1 − qz . 1 − qz + λv(1 − z)
(5.18)
Recall that the pgf of the first excess of level N during the long vacations mode (mode 1) is
1 E i z L ν = z i − z i [1 − γ (z)]D−1 (5.19) N−i−1 1 − γ (x z) . Now, we substitute (5.18) in Eq. (5.19) to get
1 −1 D−1 N−i−1 1 − γ (x z) = D N−i−1 1−
1 1−q x z 1−q x z+λv(1−x z)
.
(5.20)
The expression 1 1−
1−q x z 1−q x z+λv(1−x z)
readily reduces to 1 1−
1−q x z 1−q x z+λv(1−x z)
=1+
q p 1 + . λv λv 1 − x z
(5.21)
Hence, D−1 N−i−1
1 1 − γ (x z)
=1+
p 1 − z N−i q + . λv λv 1 − z
Using the properties of the operator Dn−1 as (4.3) and that n 1 −1 zi Dn = 1 − xz i=0 we have that equation (5.19) becomes q p 1 − z N−i 1 − qz i Lν i i E z 1+ + = z −z 1− 1 − qz + λv(1 − z) λv λv 1 − z 1−z p 1 − z N−i q λv = zi − zi + 1 + . 1 + λv 1 − q+λv z λv λv 1 − z
(5.22)
(5.23)
(5.24)
1+λv
After simple algebra, (5.24) can be represented in the form E i z L ν = Az i + B
zi zN +C , 1 − bz 1 − bz
(5.25)
where A, B, b, C are some constants, which we do not specify, since we are merely aiming at the demonstration of the tractability of the formulas and not at immediate use. Expression (5.25) is brought to the form ready for yet another application of the operator Dn−1 (for some n) to yield:
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
1 1 −1 −1 + CDn−N Dn−1 E i x L ν = 1[i,∞) (n)A + BDn−i 1 − bx 1 − bx 1 − b n−i+1 1 − b n−N+1 + 1[N−1,∞) (n)C . = 1[i,∞) (n) A + B 1−b 1−b Now, the application of φ R defined as
R (φ R g)(z) = g(z) + D−1 g(x) − g(x z) z R−1
2165
(5.26)
(5.27)
to E i [z L ν ] will become a trivial exercise. Finally, the calculation of φ R E i [z Sν˜ ] will not be much more difficult and we leave the rest to the reader. 6. Hybrid model with continuous time parameter process The analysis of the continuous time parameter queueing process Q(t) that we propose is based on the theory of semi-regenerative processes and it essentially focuses on the evaluation of the semi-regenerative kernel being an infinite dimensional square matrix of the transition probabilities K (t) = {K ik (t) = P i {Q(t) = k, T1 > t}; i, k = 0, 1, . . .}
(6.1)
on the first service cycle C1 . The stationary probability measure π = (π0 , π1 , · · ·) of Q(t) exists under the same ergodicity condition ρ < R as that for the embedded Markov chain, regardless of the initial state of the system, and is sought in the form of its pgf π(z): π(z) =
1 ph(z), C¯
(6.2)
where C¯ is the mean value of the service cycle in the steady state as per C¯ =
∞
pi E i [T1 ].
(6.3)
i=0
The latter will be obtained in formula (6.20), while ph(z) is the dot product of the invariant probability measure p of {Q n } and vector h(z) = (h i (z); i = 0, 1, . . .) of the pgf’s of the respective rows of the integrated (over R+ ) semi-regenerative kernel K (t). (We skip all details regarding integrability of K (t), which are standard and can be found in many earlier papers and books on semi-regenerative processes.) Below we will be concerned with each of the three modes in greater detail. In the primary vacation mode, the server does not leave the system, as Q 0 ≥ r2 and it works on a group of units of size R (recalling the assumption that R ≤ r2 ). Since the continuous time parameter process Q(t) is semi-regenerative, its steady state probabilities are governed by the probabilities on the first service cycle C1 being [0, σ ] on {Q 0 ≥ r2 }. The key component of the pgf π(z) of the limiting probabilities of Q(t) is the functional h i (z) defined as ∞ ∞ zk K ik (t)dt (6.4) h i (z) = k=0
0
2166
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
and which for i ≥ r2 can equivalently be expressed through ∞ h i (z) = E i [z Q(t )1{σ >t } ]dt, i ≥ r2 .
(6.5)
0
The latter can be shown (cf. Dshalalow [14]) to equal h i (z) = z i ∆(z),
i ≥ r2 ,
(6.6)
where ∆(z) =
1 − α(z) . λ − λa(z)
(6.7)
Now we turn to vacation mode 1. When the server leaves the system, after the line drops below level r1 , it performs a series of secondary jobs lasting τ1 , τ2 , . . .. During this time, the system is being “nourished” by the incoming flow of units forming a marked Poisson process, as per Section 2. The system is observed only at the times τ1 , τ2 , . . . up until τ1 + · · · + τν , when the vacation series ends and the first service begins. Since the continuous time parameter queueing process Q(t) is semi-regenerative, to unfold the probability distribution of Q(t) at any moment of time in the steady state we need to obtain the information on Q(t) or equivalently, the input process Π , on the first service cycle C1 = [0, τν + σ ) given {Q 0 ∈ [0, r1 )}. Notice that for any t ∈ C1 , given {Q 0 ∈ [0, r1 )} Q(t) = Π ([0, t]) =: Nt .
(6.8)
For the continuous ∞ time parameter queueing process we need the following special case of the transformation 0 e−θt E i [z Q(t )1{τν +σ >t } ]dt, calculated in Dshalalow [14] and to be adapted to vacation mode 1: ∞ z i − α(z)E i [z L ν ] , i = 0, . . . , r1 − 1, h i (z) = E i [z Nt 1{τν +σ >t } ]dt = (6.9) λ − λa(z) 0 where from (4.2), E i z L ν = z i − z i [1 − γ (z)]D−1 N−i−1 Thus, h i (z) = z ∆(z) + z i
i
α(z)∆1 (z)D−1 N−i−1
1 , 1 − γ (x z)
1 , 1 − γ (x z)
i = 0, . . . , r1 − 1.
i = 0, · · · , r1 − 1,
(6.10)
(6.11)
where ∆(z) is defined in (6.7) and ∆1 (z) =
1 − γ (z) . λ − λa(z)
(6.12)
We turn to vacation mode 2. When the queue falls into [r1 , r2 ), the server leaves the system for one single trip and then returns to the system unconditionally. It will not perform service though, unless the line has increased to at least N units. If this is not the case, the server rests watching the flow of units at t1 , t2 , . . . enter the system. Now, a starting portion of the input process is “packed” into interval [0, t0 ], where t0 is the return from the server’s single trip. The follow up arrivals past t0 must normally be recounted
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
2167
with new subscripts. However, for the sake of simplicity and without loss of generality we will assign the first arrival moment past t0 as t1 and continue this all the way forward. Recall that during the server’s absence, the line increased from Q 0 to a total of δ0 , which we now assign to the initial value of the “delayed marked Poisson process” δi ε t i . (6.13) Π˜ = i≥0
Observe that the first service cycle under vacation mode 2 is C1 = [0, tν˜ + σ ) on {Q 0 ∈ [r1 , r2 )}, and for any t ∈ C1 , Q(t) = Π˜ ([0, t]) = N˜ t .
(6.14)
For the continuous time parameter queueing process we need the same special case of the transformation obtained in [14] and adapted to the vacation mode 2: ∞ z i − α(z)E i [z Sν˜ ] ˜ , i = r1 , . . . , r2 − 1, E i [z Nt 1{tν˜ +σ >t } ]dt = (6.15) h i (z) = λ − λa(z) 0 where according to (4.9),
ψ(x z) −1 i Sν˜ i i , = z ψ(z) − z [1 − a(z)]D N−i−1 E z 1 − a(x z)
i = r1 , . . . , r2 − 1.
(6.16)
Consequently, after some algebra
ψ(x z) 1 h i (z) = z i ∆(z) + z i α(z)∆2 (z) + z i α(z)D−1 N−i−1 1 − a(x z) , λ
i = r1 , . . . , r2 − 1, (6.17)
where ∆(z) is defined in (6.7) and ∆2 (z) =
1 − ψ(z) . λ − λa(z)
(6.18)
Now, we can find ph(z) from (6.5), (6.6), (6.11), (6.16) and (6.17):
r 1 −1 1 ph(z) = ∆(z)P(z) + α(z)∆1 (z) pi z i D−1 N−i−1 1 − γ (x z) i=0
r r 2 −1 2 −1 1 ψ(x z) i i −1 + α(z)∆2 (z) pi z + α(z) pi z D N−i−1 . λ 1 − a(x z) i=r i=r 1
(6.19)
1
¯ From We conclude π(z) with the evaluation of the stationary mean value of service cycle C. (6.3), (4.4) and (4.10) we have
r 1 −1 1 −1 ¯ − σ¯ C = pi τ¯ D N−i−1 1 − γ (x) i=0
r 2 −1 1 −1 ψ(x) ¯ + pi t0 − σ¯ + D N−i−1 + σ¯ . (6.20) λ 1 − a(x) i=r 1
2168
J.H. Dshalalow et al. / Nonlinear Analysis 65 (2006) 2153–2168
References [1] S. Bohacek, J.P. Hespanha, J. Lee, K. Obraczka, Analysis of a TCP hybrid model, in: Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing, October 2001. [2] T. Erbes, Stochastic learning feedback hybrid automata for dynamic power management in embedded systems, M.Sc. in Computer Engineering, Virginia Polytechnic Institute and State University, January 2004. [3] F. Wirth, R. Stanojevic, R. Shorten, D. Leith, Stochastic equilibria of AIMD communication networks, SIAM J. Matrix Anal. Appl. (in press). [4] J.P. Hespanha, A model for stochastic hybrid systems with applications to communication networks, Nonlinear Anal. 62 (2005) 1353–1383. [5] A.V. Savkin, A.S. Matveev, P.B. Rapajic, The medium access control problem for wireless communication networks modelled as hybrid dynamical systems, Nonlinear Anal. 62 (2005) 1384–1393. [6] A.A. Julius, A. Girard, G.J. Pappas, Approximate bisimulation for a class of stochastic hybrid systems, in: The Proc. of the American Control Conference 2006, Minneapolis, USA (in press). [7] A.A. Julius, Approximate abstraction of stochastic hybrid automata, in: Hybrid Systems: Computation and Control, in: LNCS, vol. 3927, Springer Verlag, 2006, pp. 318–332. [8] E. Barany, M. Krupa, Stability of multiple access network control schemes with carrier sensing and exponential backoff, Physica A 363 (2) (2006) 573–590. [9] I. Lestas, G. Vinnicombe, How good are deterministic models for analyzing congestion control in delayed stochastic networks? in: Proc. 43rd IEEE Conference on Decision and Control, December 2004. [10] B.T. Doshi, Queueing systems with vacations: A survey, Queueing Syst. 1 (1986) 29–66. [11] B.T. Doshi, Single server queues with vacations, in: H. Takagi (Ed.), Stochastic Analysis of Computer and Communication Systems, North-Holland, Amsterdam, 1990, pp. 217–265. [12] H. Takagi, Queueing Analysis - A Foundation of Performance Evaluation, vol. 1, Elsevier, Amsterdam, 1991. [13] J.H. Dshalalow, Queues with hysteretic control by vacation and post-vacation periods, Queueing Syst. 29 (1998) 231–268. [14] J.H. Dshalalow, Time dependent analysis of multivariate marked renewal processes, J. Appl. Probab. 38 (2001) 707–721. [15] J. Teghem, Optimal control of queues: removable servers [Tutorial paper XIX], Belgian J. Oper. Res. Stat. Comp. Sci. 25 (2–3) (1985) 99–128. [16] J. Teghem, Control of the service process in a queueing system, European J. Oper. Res. 23 (1986) 141–158. [17] J. Loris-Teghem, Hysteretic control of an M/G/1 queueing system with two service time distributions and removable server, in: Point Processes and Queueing Problems Colloquia Mathematica Societatis Janos Bolyai, Hungary, 24, 1978, pp. 291–305. [18] J. Loris-Teghem, Imbedded and non-imbedded stationary distributions in a finite capacity queueing system with removable server, Cah. Centr. d’Etud. Rech. Op´er. 26 (1–2) (1984) 87–94. [19] L. Tadj, G. Choudhury, Optimal design and control of queues, Top 13 (1) (2005) 359–414. [20] Z.G. Zhang, R.G. Vickson, M.J.A. van Eenige, Optimal two-threshold policies in an M/G/1 queue with two vacation types, Perform. Eval. 29 (1997) 63–80. [21] Z.G. Zhang, R.G. Vickson, C.E. Love, The optimal service policies in an M/G/1 queueing system with multiple vacation types, INFOR 39 (4) (2001) 357–366. [22] J.-C. Ke, The control policy of an M [x] /G/1 queueing system with server startup and two vacation types, Math. Methods Oper. Res. 54 (2001) 471–490. [23] J.-C. Ke, The optimal control of an M/G/1 queueing system with server startup and two vacation types, Appl. Math. Modelling 27 (2003) 437–450. [24] J.H. Dshalalow, On the level crossing of multidimensional delayed renewal processes, in: Stochastic Systems, J. Appl. Math. Stoch. Anal. 10 (4) (1997) 355–361 (special issue). [25] J.H. Dshalalow, Queueing systems with state dependent parameters, in: J.H. Dshalalow (Ed.), Frontiers in Queueing: Models and Applications in Science and Engineering, CRC Press, Boca Raton, 1997, pp. 61–116. [26] J.H. Dshalalow, J. Yellen, Bulk input queues with quorum and multiple vacations, Math. Probl. Eng. 2 (2) (1996) 95–106. [27] L. Abolnikov, A. Dukhovny, Markov chains with transition delta-matrix: ergodicity conditions, invariant probability measures and applications, J. Appl. Math. Stoch. Anal. 4 (4) (1991) 335–355. [28] A. Dukhovny, Multiple roots of some equations of queueing theory, Stoch. Models 10 (1994) 519–524. [29] L. Atanassova, Simultaneous determination of the zeros of an analytic function inside a simple smooth closed contour in the complex plane, J. Comput. Appl. Math. 50 (1–3) (1994) 99–107.
