Even though many computational methods (recursive formulae) for blocking probabilities in finite-capacity M/D/1 queues have already been produced, these are forms of transforms or are limited to single-node queues. Using a distinctly different approach from the usual queueing theory, this study introduces explicit (transform-free) formulae for a blocking probability, a stationary probability, and mean sojourn time under either production or communication blocking policy. Additionally, the smallest buffer capacity subject to a given blocking probability can be determined numerically from these formulae. With proper selection of the overall offered load
ρ
, the approach described herein can be applicable to more general queues from a computational point of view if the explicit expressions of random vector
D_{n}
are available.
An M/D/1 queue, the simplest queue with deterministic service time, has been studied extensively and has a variety of applications in the performance evaluation of production management, telecommunications networks, and other areas. However, because blocking phenomena caused by finite capacity raise many difficulties and introduce complexity into evaluations of various performance measures, results regarding finite-capacity queues are small in number.With the exception of some special cases, such as Markovian queues (M/M/1/K), Erlang’s loss queues (no waiting room at all, M/G/c/c), M/G/1/1 and M/G/1/2 queues, and so on, it is very difficult to obtain explicit expressions for a blocking probability or a stationary distribution in finitecapacity queues (for example, see Gross and Harris [1] and Takagi [2]).On the one hand, the recursive formula for stationary distributions (or blocking probabilities) in M/G/c/K queues was first provided by Tijms [3]. Brun and Garcia [4] showed analytical (transform-free) solutions of steady-state probability distributions in finite-capacity M/D/1 queues via the use of the generating function (z-transform). Alouf and others [5] analytically derived the stationary distribution of the M/D/1/K queue using Cohen’s results — which were based on the Laplace-Stieltjes transform (LST) — of the M/G/1/K queue of the service time distribution (see Cohen [6]). On the other hand, most studies have introduced various approximation methods for more general queues. For instance, Perros [7] numerically demonstrated several relations between blocking policies and introduced a variety of approximation methods, all of which are forms of a weighted combination of exact (if available) expressions of two queues with deterministic and exponential distributions. Similarly, Smith [8] presented an approximation for an M/G/c/K queue based on closed-form expressions derived from finite-capacity exponential and deterministic queues. Sakasegawa and others [9] constructed an approximation formula for the overflow probability for GI/GI/c/N queues in terms of a queue-length distribution for the corresponding GI/GI/c/∞ queues.The blocking probability plays an important role in the analysis of finite-capacity queues. Once a blocking probability is obtained, we are able to compute various performance measures of interest, including carried load, stationary probabilities, (higher) moments of stationary waiting time and sojourn time, and so forth. However, normal queueing theory has limitations in applications to general queues with multi-node, multi-server, or generally structured queues.In an effort to overcome these shortcomings we adopt a different method from the usual queueing theory — namely, max-plus algebra. Many types of networks belonging to a class of queueing networks, the so-called max-plus linear system, can be modeled properly by timed event graphs, a special case of the Petri net. They can be analysed using maxplus algebra, which involves the use of only two operators: “max” and “+.” In brief, a max-plus linear system is a choicefree network of single-server queues with first-in first-out service discipline.Because it is clear that an M/G/1/K queue belongs to a max-plus linear system, a max-plus algebra is useful in analysing this finite-capacity queue. Additionally, constant service times render the series expressions (see section II) simple and tractable such that we focused solely on deterministic service times. The principal objective of this study is to demonstrate a closed-form (transform-free) expression of a blocking probability for an M/D/1/K queue under either communication or production blocking policy. In the case of communication blocking policy we can obtain the same expression as the one of Brun and Garcia [4] and Alouf and others [5], whereas in the case of production blocking policy we obtain a new formula. Moreover, other related expressions for stationary probability, mean system sojourn time, and an optimal buffer capacity are also provided. Similar to Sakasegawa and others [9], these expressions are written in terms of the blocking probability and the queuelength distribution of the corresponding M/D/1/∞ queue.This paper is organized as follows. Brief preliminaries on max-plus algebra and on waiting times in a max-plus linear system are provided in section II. Section III includes our principal results on the explicit expression of blocking probability in finite-capacity M/D/1 queues. We show other related expressions in section IV and end with some concluding remarks in section V.
II. Brief Preliminaries
The basic reference algebra used throughout this study is the so-called max-plus algebra on the real line ℝ ; namely the semi-field with the two operations (⊕, ⊗), in which the ⊕ refers to maximization and the ⊗ refers to addition for scalars and max-plus algebra product for matrices (see Baccelli and others [10]). The dynamics of a max-plus linear system with α nodes can be described by the α-dimensional vectorial recurrence equations$${X}_{n+1}={A}_{n}\otimes {X}_{n}\oplus {B}_{n+1}\otimes {T}_{n+1}$$with an initial condition of X_{0}, where {T_{n}} is a non-decreasing sequence of real-valued random numbers (for example, the epochs of the Poisson arrival process with rate λ), {A_{n}} and {B_{n}} are stationary and ergodic sequences of real-valued random matrices of size α × α and α × 1, respectively, and {X_{n}} is a sequence of α-dimensional state vectors. The components of the state vector X_{n} represent absolute times that grow to ∞ when n increases unboundedly; hence, one is more interested in the differences
W n i = X n i − T n
(like the waiting time of the nth customer until they join server i). Let τ_{n} = T_{n+1} - T_{n} with T_{0} = 0, and let C(x) be the α × α matrix with all diagonal entries equal to –x and all non-diagonal entries equal to –∞. By subtracting T_{n+1} from both sides of (1), the new state vector W_{n+1} can be expressed as$${W}_{n+1}={A}_{n}\otimes C({\tau}_{n})\otimes {W}_{n}\oplus {B}_{n+1},$$for n ≥ 0 and with the initial condition W_{0}. Baccelli and others [10] previously demonstrated that under certain conditions the dynamics of Poisson-driven max-plus linear systems could be described by vectorial recurrence equations (also see Heidergott [11]). For all λ < a^{−1} , where λ is the arrival rate and a is the maximal Lyapunov exponent of the sequence {A_{n}}, W is determined by the matrix series$$W={D}_{0}\oplus \underset{k\ge 1}{{\displaystyle \oplus}}\text{\hspace{0.17em}}C({T}_{-k})\otimes {D}_{k},$$with D_{0} = B_{0}, W_{0} = B_{0}, and k ≥ 1 .$${D}_{k}=(\underset{n=1}{\overset{k}{{\displaystyle \otimes}}}{A}_{-n})\otimes {B}_{-k}\mathrm{.}$$From this topology, Baccelli and Schmidt [12] derived a Taylor series expansion for mean stationary waiting time with regard to the arrival rate in a Poisson-driven max-plus linear system. Their approach was generalized to other characteristics of stationary and transient waiting times, such as higher moments, Laplace transforms, and tail probabilities by Baccelli and others [13]–[14] and Ayhan and Seo [15]–[16]. Later, Heidergott [11] established Taylor series expansions with regard to general parameters for max-plus linear systems with a renewal arrival process. The representation of the stationary waiting time in (2) and (3) holds for any max-plus linear system with a renewal arrival process. However, we assume the Poisson arrival process throughout this study to use the existing explicit results for the stationary waiting time. The reader can refer to the works of Baccelli and others [10] and Heidergott and others [17] for more details on basic max-plus algebra and to Baccelli and Schmidt [12], Baccelli and others [13]–[14], and Ayhan and Seo [15]–[16] for details on waiting times in a max-plus linear system.Once the explicit expression of the random vector D_{k} for a max-plus linear system is derived, we can compute various characteristics of transient and stationary waiting times by inputting it into the series expansions given in Baccelli and Schmidt [12], Baccelli and others [13]–[14], and Ayhan and Seo [15]–[16]. However, it is usually quite difficult to derive closed-form expressions for stationary waiting times. So, all authors in [12]–[16] assumed the ith element of the sequence {D_{k}} to be ‘ultimately periodic’; that is, in a class of max-plus linear systems with constant service times the ith element of {D_{n}} is given by$${D}_{n}^{i}=\{\begin{array}{ll}{\eta}_{n}^{i}\hfill & \text{\hspace{0.05em}\hspace{0.17em}for\hspace{0.17em}}n=\mathrm{0,}\text{\hspace{0.17em}\hspace{0.17em}...\hspace{0.17em}\hspace{0.17em}}\mathrm{,}{\xi}_{i}-1\u200a,\hfill \\ {\eta}_{{\xi}_{i}}^{i}+(n-{\xi}_{i}){a}_{i}\hfill & \text{\hspace{0.05em}\hspace{0.17em}for\hspace{0.17em}}n\ge {\xi}_{i},\text{\hspace{0.05em}}\hfill \end{array}$$for constant real numbers
0≤ η 0 i ≤ η 1 i ≤⋯≤ η ξ i i
, a_{i}, and some non-negative integers ξ_{i}. Not all deterministic max-plus linear systems fall into this category. However, this does cover many interesting queueing systems with deterministic service times, such as tandem queues with various types of blocking, forkand-join type queues, queuing networks embedded in Kanban systems, and so on. By placing the explicit expressions for
D n i
that satisfy the structure of (4) into the closed-form formulae given by Ayhan and Seo [15]–[16], we can compute the values of the Laplace transform of stationary waiting times, higher moments of stationary waiting times, and tail probability of stationary waiting times.Recently, Seo [18] applied the method used by authors in [12]–[16] to finite-capacity 2-node tandem queues with constant service times, in which he assumed the first node to have infinite capacity but the second to have finite capacity. For this model, he considered two blocking policies:communication (blocking before service) and production (blocking after service). Under communication blocking, a customer at node i cannot begin service unless there is a vacant space in the buffer at node j+1. On the other hand, under production blocking, a customer served at node j moves to node j+1 only if the buffer of node j+1 is not full; otherwise, the blocked customer remains in node j until a vacancy becomes available. During that time, node j is blocked from serving other customers.The aim of this study is to introduce explict expressions for blocking probabilities in M/D/1/K queues under two blocking policies. To the best of our knowledge, the explicit blocking formula under a production blocking policy has not been introduced, because it is not easy to handle with the usual queueing theory. However, there are a few results under a communication blocking policy in the literature, because it is more comfortable to treat.The random vector D_{n}, n ≥ 0 , plays an essential part in deriving and computing explicit expressions for a blocking probability and other related characteristics of interest, as shown in the section below.
III. Explicit Formulae for Blocking Probability
The following expressions of
D n i
, i = 1, 2, under either a communication or a production blocking policy are given in Seo [18]. For node i, i = 1, 2, let σ^{i} be a deterministic service time and K_{i} be a finite capacity with K_{1} = ∞ and K_{2} < ∞.• Production blocking policyIf K_{2} ≥ 1,$${D}_{n}^{1}=n{\sigma}^{1}\text{\hspace{0.05em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}for\hspace{0.17em}}0\text{\hspace{0.17em}}\le \hspace{0.17em}n\text{\hspace{0.17em}}\le \hspace{0.17em}{K}_{2}\mathrm{\u200a,}$$$${D}_{n}^{1}=\mathrm{max}\left\{n{\sigma}^{1}\mathrm{,}{\sigma}^{1}+(n-{K}_{2}){\sigma}^{2}\right\}\text{\hspace{0.05em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}for\hspace{0.17em}}n\hspace{0.17em}>\hspace{0.17em}{K}_{2}\text{\hspace{0.05em}}\mathrm{,}$$$${D}_{n}^{2}={\sigma}^{1}+\mathrm{max}\left\{n{\sigma}^{1}\mathrm{,}n{\sigma}^{2}\right\}\text{\hspace{0.05em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}for\hspace{0.17em}}n\ge 0.$$• Communication blocking policyIf K_{2} = 1,$${D}_{n}^{1}=n({\sigma}^{1}+{\sigma}^{2})\text{\hspace{0.17em}\hspace{0.17em}\hspace{0.05em}\hspace{0.17em}for\hspace{0.17em}}n\hspace{0.17em}\ge \hspace{0.17em}\mathrm{0,}$$$${D}_{n}^{2}={\sigma}^{1}+n({\sigma}^{1}+{\sigma}^{2})\text{\hspace{0.05em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}for\hspace{0.17em}}n\ge \hspace{0.17em}0\text{\hspace{0.05em}}.$$If K_{2} ≥ 2,$${D}_{n}^{1}={\mathrm{n\sigma}}^{1}\text{\hspace{0.05em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}for\hspace{0.17em}}0\hspace{0.17em}\le \hspace{0.17em}n<{K}_{2}\text{\hspace{0.05em},}$$$$\begin{array}{l}{D}_{n}^{1}=\mathrm{max}\left\{n{\sigma}^{1}\mathrm{,}{\sigma}^{1}+(n-{K}_{2}+1){\sigma}^{2}\right\},\u200a\hspace{0.17em}\\ \text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{1em}\hspace{1em}for\hspace{0.17em}\hspace{0.17em}}n\hspace{0.17em}\ge \hspace{0.17em}{K}_{2}\mathrm{\u200a,}\end{array}$$$${D}_{n}^{2}={\sigma}^{1}+\mathrm{max}\left\{n{\sigma}^{1}\mathrm{,}n{\sigma}^{2}\right\}\text{\hspace{0.05em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}for\hspace{0.17em}}n\hspace{0.17em}\ge \hspace{0.17em}\mathrm{0\u200a.\u200a\hspace{0.17em}}$$The series expansion using max-plus algebra assumes the stability condition (ρ < 1) and unlimited capacity at the first node. Thus, an M/D/1/K queue must be transformed into the corresponding M/D/1/∞ queue, which can be tractable through existing results such as the explicit expressions for the moment and for the tail probability of stationary waiting times.Let σ be a deterministic service time and K (≥ 2) be a finite capacity for an M/D/1/K queue. To assess the finite-capacity M/D/1 queue, we extend it to a corresponding 2-node tandem queue by inserting a dummy node with zero service time and an infinite-capacity buffer in front of this M/D/1/K queue, both of which are depicted in Figs. 1 and 2 under communication blocking policy.
The corresponding extended 2-node tandem queue then has σ^{1} = 0, σ^{2} = σ, K_{1} = ∞, and K_{2} = K. By putting these σ^{i} and K_{i} into equations (5)–(7), and (10)–(12) we have, for K ≥ 2.• Production blocking policy$${D}_{n}^{1}=0\text{\hspace{0.05em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}for\hspace{0.17em}}0\hspace{0.17em}\le \hspace{0.17em}n\hspace{0.17em}\le \hspace{0.17em}K\mathrm{\u200a,}$$$${D}_{n}^{1}=(n-K)\sigma \text{\hspace{0.05em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}for\hspace{0.17em}}n\hspace{0.17em}>\hspace{0.17em}K\mathrm{\u200a,}$$$${D}_{n}^{2}=n\sigma \text{\hspace{0.05em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}for\hspace{0.17em}}n\hspace{0.17em}\ge \hspace{0.17em}0\u200a.$$• Communication blocking policy$${D}_{n}^{1}=0\text{\hspace{0.05em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}for\hspace{0.17em}\hspace{0.17em}}0\hspace{0.17em}\le \hspace{0.17em}n\hspace{0.17em}<\hspace{0.17em}K\mathrm{\u200a,}$$$${D}_{n}^{1}=(n-K+1)\sigma \text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}for\hspace{0.17em}}n\hspace{0.17em}\ge \hspace{0.17em}K\mathrm{\u200a,}$$$${D}_{n}^{2}=n\sigma \text{\hspace{0.05em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}for\hspace{0.17em}}n\hspace{0.17em}\ge \hspace{0.17em}0\u200a.$$We are now ready to present our main idea. A customer at the first node is blocked, either before service or after service, depending on the blocking policy. The customer must remain at the first node for a certain period of time (prior to moving to the second node) whenever there are K customers in the second node whose capacity is K. Recall that this blocking phenomenon is captured in the expression of D_{n}. On this point, the event that a customer’s waiting time is greater than zero at the first node in the corresponding extended 2-node tandem queue is equivalent to the event that there are K or more customers in the M/D/1/∞ queue. Recall that we assume the service time at the first node to be both deterministic and zero. Therefore, we can conclude the following: the probability E_{K}, that K or more customers are in an M/D/1/∞ queue at an arbitrary time, is equal to the probability that the stationary waiting time at the first node is greater than zero in the corresponding extended 2-node tandem queue. That is,$${E}_{K}={\displaystyle \sum _{j=K}^{\infty}}{\pi}_{j}^{\infty}=\mathrm{Pr}({W}^{1}>0),$$where
π j ∞
is a stationary probability that there are j customers in an M/D/1/∞ queue at an arbitrary time and W^{1} is a stationary waiting time at the first node in the corresponding extended 2-node tandem queue. More precisely, W^{1} is the elapsed time from the arrival until the beginning of service at node 1.The probability E_{K} performs an important role in this study. Now, we generate the following theorem from the well-known simple blocking formula (see, for example, Takagi [2]) and the explicit expression for the tail probability of stationary waiting times shown in Ayhan and Seo [16].Theorem 1. For an M/D/1/K queue with arrival rate λ and constant service time σ, the blocking probability P_{B} is given by$${P}_{B}=\frac{(1-\rho ){E}_{K}}{1-\rho {E}_{K}},$$where the offered load ρ = λσ < 1 and under a production blocking policy$${E}_{K}=1-(1-\rho ){\displaystyle \sum _{j=0}^{K}}\frac{{(-1)}^{j}{\rho}^{j}{(K-j)}^{j}{e}^{\rho (K-j)}}{j!}.$$Proof. Because (17) already shows the relation between the tail probability of stationary waiting times and the probability of E_{K}, it suffices to show the explicit expression of E_{K} for an M/D/1/∞ queue.From (13) and (14), the expression of the random vector
D n 1
for the corresponding extended 2-node tandem queue can be written as$${D}_{n}^{1}=\{\begin{array}{ll}0\hfill & \text{\hspace{0.05em}\hspace{0.17em}for\hspace{0.17em}}n=\mathrm{0,}\text{\hspace{0.17em}\hspace{0.17em}...\hspace{0.17em}\hspace{0.17em},}K,\hfill \\ (n-K)\sigma \hfill & \text{\hspace{0.05em}\hspace{0.17em}for\hspace{0.17em}}n\hspace{0.17em}\ge \hspace{0.17em}K+1.\text{\hspace{0.05em}}\hfill \end{array}$$Then, it satisfies the structure provided in (4), and we can see that ξ_{1} = K + 1, a_{1} = σ,
η n 1 =0
for 0 ≤ n ≤ K,
η ξ 1 1 =σ,
, and κ = K + 1 when t = 0. Therefore, it satisfies the second case of Theorem 2.3 in [16] because ξ_{1} = K + 1 > 0 and
η ξ 1 −1 1 = η K 1 =0.
Note that κ defined therein equals K when t = 0 since$$\begin{array}{l}\kappa =\mathrm{min}\left\{k\in (0,\mathrm{1,...}):k{a}_{1}>t-{\eta}_{{\xi}_{1}}^{1}+{\xi}_{1}{a}_{1}\right\}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=\mathrm{min}\left\{k\in (0,\mathrm{1,...}):k\sigma >0-\sigma +\left(K+1\right)\sigma \right\}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=K+1.\end{array}$$Thus, the probability E_{K} is expressed as$$\begin{array}{l}{E}_{K}=\text{Pr}({W}^{1}>0)\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=1-(1-\rho ){\displaystyle \sum _{j=0}^{K}}\frac{{(-1)}^{j}{\rho}^{j}{(K-j)}^{j}{e}^{\rho (K-j)}}{j!},\end{array}$$where ρ = λσ < 1.We can then compute the blocking probability PB for an M/D/1/K queue using the simple blocking formula in (18). □Our approach is also valid for a communication blocking policy. Similarly as above, we can obtain the following corollary without the proof. From (15) and (16), the expression of
D n 1
under a communication blocking policy can be written as
D n 1 ={ 0 for n=0, ... , K−1, σ+(n−K)σ for n ≥ K.
It also satisfies the structure given in (14). The fact that ξ_{1} = K, a_{1} = σ,
η n 1 =0
for 0 ≤ n ≤ K − 1 , and
η ξ 1 1 =σ
satisfies the second case of Theorem 2.3 in [16], because ξ_{1} = K > 0 and
η ξ 1 −1 1 = η K−1 1 =0.
The κ defined therein equals K when t = 0 yields the probability E_{K} as follows.Corollary 1. For an M/D/1/K queue with arrival rate λ and constant service time σ, the blocking probability P_{B} is given by$${P}_{B}=\frac{(1-\rho ){E}_{K}}{1-\rho {E}_{K}},$$where the offered load ρ = λσ < 1 and under a communication blocking policy$${E}_{K}=1-(1-\rho ){\displaystyle \sum _{j=0}^{K-1}}\frac{{(-1)}^{j}{\rho}^{j}{(K-j-1)}^{j}{e}^{\rho (K-j-1)}}{j!}\mathrm{.}$$For a production blocking policy there is no similar result to Theorem 1 in the literature. However, we can see that our formula for a communication blocking policy is equivalent to the ones provided in [3]–[5].Remark 1. Tijms [3] demonstrated that
we can readily obtain the equivalent expression to ours. Besides, the fact that E_{1} = ρ when K = 1 derives the same formula mentioned in Takagi [2] as follows:$${P}_{B}=\frac{(1-\rho ){E}_{1}}{1-\rho {E}_{1}}=\frac{(1-\rho )\rho}{1-{\rho}^{2}}=\frac{\rho}{1+\rho}\mathrm{.}$$Remark 2. Brun annd Garcia [4] introduced analytical solutions for the steady-state distribution in a finite-capacity M/D/1 queue by using the generating function, which is completely different from our approach. Their key measure b_{n} is defined as b_{0} = 1 and for n ≥ 1,$${b}_{n}={\displaystyle \sum _{j=0}^{n}}\frac{{(-1)}^{j}{\rho}^{j}{(n-j)}^{j}{e}^{\rho (n-j)}}{j!}\mathrm{.}$$It is easy to find the following relation between the two measures E_{n} and b_{n}:$${E}_{0}=1$$and$${E}_{n}=1-(1-\rho ){b}_{n-1}\text{\hspace{0.05em}\hspace{0.17em}for\hspace{0.17em}all\hspace{0.17em}}n\text{\hspace{0.17em}}\ge \text{\hspace{0.17em}}1\text{\hspace{0.05em}}.$$Remark 3. For the stationary distribution of the M/D/1/K queue, Alouf and others [5] defined a measure α_{j}(ρ) as α_{1}(ρ) = 1 and for j ≥ 2,$${\alpha}_{j}(\rho )={\displaystyle \sum _{i+k=j-2}}\frac{{(-1)}^{k}{\rho}^{k}{(i+1)}^{k}{e}^{\rho (i+1)}}{k!}\mathrm{.}$$The two measures E_{j} and α_{j}(ρ) are related as follows:$${E}_{1}=\rho $$and$${E}_{j}=1+(\rho -1){\alpha}_{j}(\rho )\text{\hspace{0.05em}\hspace{0.17em}for\hspace{0.17em}all\hspace{0.17em}}j\text{\hspace{0.17em}}\ge \text{\hspace{0.17em}}2\text{\hspace{0.05em}}.$$Remarks 2 and 3 show that our formula is equivalent to the ones provided in [4] and [5]. Thus, we could assert that our formula also works even when ρ > 1 without a mathematical proof because theirs hold regardless of the value of the offered load ρ. Such a proof will be carried out entirely differently from the approach described in [12] due to the stability condition — one of the fundamental assumptions of the Taylor series expansions.Remark 4. Let E_{K,C} and E_{K,P} be the E_{K} for a communication and a production blocking policy, respectively. For a given K and ρ, we can see from the expressions given in (19) and (20) and the definition of E_{K,C} that$${E}_{K,C}\ge {E}_{K+1,C}={E}_{K,P}.$$This relationship shows E_{K,P} ≤ E_{K,C}. For a given K and ρ, therefore, a production blocking policy provides less blocking probabilities than a communication blocking policy, since the blocking formula given in (18) is increaing in E_{K}.Our explicit expressions allow us to compute exact blocking probabilities under two blocking policies. Figure 3 compares the blocking probabilities with varying K when σ = 5 and λ = 0.19. It shows that the blocking after service (BAS) policy produces less blocking probabilities than the blocking before service (BBS) policy under the same environments; however, this difference becomes negligible as finite capacity increases.
Remark 5. Whereas the approaches used in [4] and [5] are restrictive in the number of queues, our method remains valid for single-server multi-node queues if the explicit expressions of the random vector D_{n} are available. For instance, Seo and others [19] numerically demonstrated that our approach is applicable to compute blocking probabilities in M/D/1/K_{1} → ·/D/1/K_{2} queues under a communication blocking policy. Table 1 shows the blocking probabilities, that is, (P_{B,S}) computed by simulation and (P_{B,P}) computed by our method when ρ = λ max{σ^{1}, σ^{2}} > 1, where σ^{1} and σ^{2} are the constant service times at node 1 and 2, respectively. Their computational results show that our approach works quite well as ρ increases. However, to obtain more accurate values of the blocking probabilities, further study is necessary to determine a method for the appropriate selection of an overall offered load ρ for single-server multi-node systems.
IV. Other Related Expressions
We can obtain the following explicit expressions of stationary distributions and mean system sojourn time in an M/D/1/∞ queue and an M/D/1/K queue, which are written in terms of the probability E_{K}. As we mentioned before, because the dynamic behaviors depending on a blocking policy are captured in the expression of D_{n}, we do not distinguish the two blocking policies in the below.
- 1. Explicit Formula for Stationary Probability
From the definition of E_{m} for all m ≥ 0, we have an explicit formula for the stationary probability
π m ∞
.Theorem 2. In the M/D/1/∞ queue with ρ = λσ < 1, the stationary probability
π m ∞
is given by$${\pi}_{m}^{\infty}={E}_{m}-{E}_{m+1}\text{\hspace{0.05em}\hspace{0.17em}for\hspace{0.17em}all\hspace{0.17em}}m\hspace{0.17em}\ge \hspace{0.17em}\mathrm{0\u200a},$$where
E m = ∑ j=m ∞ π j ∞ .
More precisely,$${\pi}_{m}^{\infty}\text{\hspace{0.05em}}=\hspace{0.17em}(1\text{\hspace{0.05em}}-\text{\hspace{0.05em}}\rho )[{\displaystyle \sum _{\ell =1}^{m}}\frac{{(-1)}^{\ell}{\rho}^{\ell}{(m\text{\hspace{0.05em}}-\text{\hspace{0.05em}}\ell )}^{\ell -1}{e}^{\rho (m-\ell )}}{\ell !}\times \{(m\text{\hspace{0.05em}}-\ell )\text{\hspace{0.05em}}+\frac{\ell}{\rho}\}\text{\hspace{0.05em}}+{e}^{\rho m}]\mathrm{.}$$Proof. It is clear that
π m ∞ = E m − E m+1
from the definition of
E j = ∑ n=j ∞ π n ∞ .
From the explicit expression of E_{K} in (13), along with some algebra, we can obtain the following:$$\begin{array}{l}{\pi}_{m}^{\infty}={E}_{m}-{E}_{m+1}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=\left[1-(1-\rho ){\displaystyle \sum _{j=0}^{m-1}}\frac{{(-1)}^{j}{\rho}^{j}{(m-j-1)}^{j}{e}^{\rho (m-j-1)}}{j!}\right]\\ \text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}-\left[1-(1-\rho ){\displaystyle \sum _{j=0}^{m}}\frac{{(-1)}^{j}{\rho}^{j}{(m-j)}^{j}{e}^{\rho (m-j)}}{j!}\right]\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=(1-\rho )[{\displaystyle \sum _{j=0}^{m}}\frac{{(-1)}^{j}{\rho}^{j}{(m-j)}^{j}{e}^{\rho (m-j)}}{j!}\\ \text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}-{\displaystyle \sum _{\ell =1}^{m}}\frac{{(-1)}^{\ell -1}{\rho}^{\ell -1}{(m-\ell )}^{\ell -1}{e}^{\rho (m-\ell )}}{(\ell -1)!}]\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=(1-\rho )[{\displaystyle \sum _{j=1}^{m}}\frac{{(-1)}^{j}{\rho}^{j}{(m-j)}^{j}{e}^{\rho (m-j)}}{j!}+{e}^{\rho m}\\ \text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+{\displaystyle \sum _{\ell =1}^{m}}\frac{{(-1)}^{\ell}{\rho}^{\ell}{(m-\ell )}^{\ell -1}{e}^{\rho (m-\ell )}}{\ell !}(\frac{\ell}{\rho})],\end{array}$$which completes the proof. □Stationary probability at a departure time can be written as follows. We omitted the proof because it can be readily proven by Theorem 2. Then, stationary probabilities at an arbitrary time can be computed by the well-known relation P_{m} = (1 − P_{B})π_{m} (see [6] for an example). In an M/D/1/K queue, for 0 ≤ m ≤ K − 1, stationary probabilities P_{m} at an arbitrary time and π_{m} at a departure time are computed by$${\pi}_{m}=\frac{{E}_{m}-{E}_{m+1}}{1-{E}_{K}},$$where
E m = ∑ j=m ∞ π j ∞
- 2. Explicit Formula for Mean Sojourn Time
Before moving to the mean system sojourn time, we first demonstrate an expression written in terms of the probabilities E_{j}, j = 1, ... , K, for the expected number of customers in an M/D/1/∞ queue. This is the mean value of the number of customers truncated by K–1 and is useful in deriving expressions for the mean system sojourn time W in an M/D/1/K queue.Lemma 1.$$\sum _{j=1}^{K-1}}j{\pi}_{j}^{\infty}={\displaystyle \sum _{j=1}^{K}}{E}_{j}-K{E}_{K},$$where
E m = ∑ j=m ∞ π j ∞
and
π j ∞
is the probability at an arbitrary time that there are j customers in the M/D/1/∞ queue.Proof. With the help of relations
∑ j=1 ∞ j π j ∞ = ∑ j=1 ∞ E j
and
∑ j=K+1 ∞ (j−K) π j ∞ = ∑ j=K+1 ∞ E j
, we can see that$$\begin{array}{l}{\displaystyle \sum _{j=1}^{K-1}}j{\pi}_{j}^{\infty}={\displaystyle \sum _{j=1}^{\infty}}j{\pi}_{j}^{\infty}-{\displaystyle \sum _{j=K}^{\infty}}j{\pi}_{j}^{\infty}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}={\displaystyle \sum _{j=1}^{\infty}}{E}_{j}-\left(K{\pi}_{K}^{\infty}+{\displaystyle \sum _{j=K+1}^{\infty}}j{\pi}_{j}^{\infty}\right)\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}={\displaystyle \sum _{j=1}^{\infty}}{E}_{j}-\left[K{\pi}_{K}^{\infty}+{\displaystyle \sum _{j=K+1}^{\infty}}(j-K){\pi}_{j}^{\infty}+K{\displaystyle \sum _{j=K+1}^{\infty}}{\pi}_{j}^{\infty}\right]\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}={\displaystyle \sum _{j=1}^{K}}{E}_{j}-K{E}_{K}\mathrm{,}\end{array}$$which completes the proof. □By using Little’s law and Lemma 1, we have the following explicit expressions for a mean system sojourn time W in an M/D/1/K queue, which are written in terms of E_{K}. The mean system size (the number of customers in the system) is also computed via this expression.Theorem 3. The expected system sojourn time W in an M/D/1/K queue is expressed as follows:$$W=\frac{1}{\lambda}\left(\frac{1}{1-{E}_{K}}\right)\left({\displaystyle \sum _{j=1}^{K}}{E}_{j}\right)+\frac{K}{\lambda}\left(1-\frac{1}{1-{E}_{k}}\right)\rho \mathrm{.}$$Proof. Let L be the mean number of customers of an M/D/1/K queue. From Little’s law and the proportional relation between state probabilities in M/G/1/∞ and M/G/1/K, we have$$\begin{array}{l}W=\frac{L}{\lambda (1-{P}_{B})}=\frac{1}{\lambda (1-{P}_{B})}\left({\displaystyle \sum _{j=1}^{K}}j{P}_{j}\right)\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=\frac{1}{\lambda (1-{P}_{B})}\left({\displaystyle \sum _{j=1}^{K-1}}j{P}_{j}+K{P}_{K}\right)\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=\frac{1}{\lambda (1-{P}_{B})}\left\{{\displaystyle \sum _{j=1}^{K-1}}j{\pi}_{j}^{\infty}\left(\frac{{P}_{0}}{{\pi}_{0}^{\infty}}\right)+K{P}_{K}\right\}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=\frac{1}{\lambda (1-{P}_{B})}\left(\frac{{P}_{0}}{{\pi}_{0}^{\infty}}\right)\left({\displaystyle \sum _{j=1}^{K-1}}j{\pi}_{j}^{\infty}\right)+\frac{K}{\lambda (1-{P}_{B})}{P}_{K}\end{array}$$Since P_{0}=1−ρ(1−P_{B}),
π 0 ∞ = 1 − ρ,
and
1 − E K = (1 − ρ)(1 − P B ) 1 − ρ(1 − P B )
we have$$\frac{{P}_{0}}{{\pi}_{0}^{\infty}}\frac{1}{(1-{P}_{B})}=\frac{1-\rho (1-{P}_{B})}{(1-\rho )(1-{P}_{B})}=\frac{1}{1-{E}_{K}}\mathrm{.}$$Then, from Lemma 1 and P_{K} = P_{B} we have$$W=\frac{1}{\lambda}\left(\frac{1}{1-{E}_{K}}\right)\left({\displaystyle \sum _{j=1}^{K}}{E}_{j}-K{E}_{K}\right)+\frac{K}{\lambda (1-{P}_{B})}{P}_{B}\mathrm{.}$$The proof is completed by applying the following relation to the above equation:$$\left(\frac{{P}_{B}}{1-{P}_{B}}-\frac{{E}_{K}}{1-{E}_{K}}\right)=-\frac{\rho {E}_{K}}{1-{E}_{K}}=\left(1-\frac{1}{1-{E}_{K}}\right)\rho .\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\square $$
- 3. Minimal Buffer Capacity
Our closed-form blocking formulae given in Theorem 1 and Corollary 1 can be immediately applied to an optimal problem that determines the minimal buffer capacity K^{*} that satisfies the given blocking probability
P B *
. Clearly, E_{k} is monotonously decreasing in the finite buffer capacity k, since for any k ≥ 0, the steady-state probability
π k ∞
has a positive value and
E k − E k+1 = ∑ j=k ∞ π j ∞ − ∑ j=k+1 ∞ π j ∞ = π k ∞ ≥0.
Thus, we can numerically select the minimal buffer capacity. This optimization problem can be formulated as follows:$$\begin{array}{l}{K}^{*}=\mathrm{min}\left\{k\in (\mathrm{1,2,}\hspace{0.17em}\hspace{0.17em}...):{P}_{B}^{*}\ge \frac{(1-\rho ){E}_{k}}{1-\rho {E}_{k}}\right\}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=\mathrm{min}\left\{k\in (\mathrm{1,2,}\hspace{0.17em}\hspace{0.17em}...):{E}_{k}\le \frac{{P}_{B}^{*}}{1-\rho (1-{P}_{B}^{*})}\right\},\end{array}$$where E_{k} is the same as in (13) and ρ = λσ < 1.
V. Concluding Remarks
Unlike the usual queueing theory, in this study we used maxplus algebra to provide explicit formulae for a blocking probability, stationary distributions, and mean system sojourn times in M/D/1/K queues under two blocking policies: communication and production. Whereas we had equivalent results in the literature for a communication blocking policy, blocking formulae for a production blocking policy are a new achievement. Due to the stability condition of the (Taylor) series expansion, we limited an offered load (traffic intensity) of ρ < 1. However, our expression is also valid when ρ > 1 because it is equivalent to the formulae given in [4] and [5]. Moreover, we believe that our approach is applicable to finite-capacity multi-node tandem queues with properly chosen overall offered load ρ if the explicit expressions of the random vector D_{n} are available.It will be necessary to conduct further inquiries into more efficient computational algorithms when the capacity K and the offered load ρ are large. Additionally, our explicit expressions are also useful in obtaining better approximations for queues with general service times, since various existing approximation methods form the weighted combination of deterministic and exponential queues (see, for example, Smith [8] and Tijms [3]).
This research was supported by grant from Kyung Hee University in 2011 (KHU-20110900).
BIO
Dong-Won Seo is an associate professor at the School of Management, Kyung Hee University, Seoul, Rep. of Korea. He received his PhD degree from the School of Industrial and Systems Engineering at Georgia Institute of Technology, Atlanta, USA. His current research interests are stochastic processes, series expansions, max-plus algebra, performance evaluation, and applications of management science and simulation.
Alouf S.
,
Nain P.
,
Towsley D.
“Inferring Network Characteristics via Moment-Based Estimators,”
IEEE INFOCOM
Anchorage, AK, USA
Apr. 22-26, 2001
1045 -
1054
Smith J.M.
2003
“M/G/c/K Blocking Probability Models and System Performance,”
Performance Evaluation,
52
(4)
237 -
267
DOI : 10.1016/S0166-5316(02)00190-6
Sakasegawa H.
,
Miyazawa M.
,
Yamazaki G.
1993
“Evaluation of the Overflow Probability Using the Infinite Queue,”
Manag. Sci.
39
(10)
1238 -
1245
DOI : 10.1016/S0166-5316(02)00190-6
Baccelli F.
,
Schmidt V.
1996
“Taylor Series Expansions for Poisson Driven (Max,+)-Linear Systems,”
Ann. Appl. Probability
6
(1)
138 -
185
DOI : 10.1214/aoap/1034968069
Baccelli F.
,
Hasenfuss S.
,
Schmidt V.
1997
“Transient and Stationary Waiting Times in (Max, +)-Linear Systems with Poisson Input,”
Queueing Syst.
26
(3-4)
301 -
342
DOI : 10.1023/A:1019141510202
Baccelli F.
,
Hasenfuss S.
,
Schmidt V.
1998
“Expansions for Steady-State-Characteristics of (Max, +) Linear Systems,”
Stochastic, Models
14
(1-2)
1 -
24
DOI : 10.1080/15326349808807458
Ayhan H.
,
Seo D.-W.
2001
“Laplace Transform and Moments of Waiting Times in Poisson Driven (Max, +) Linear Systems,”
Queueing Syst.
37
(4)
405 -
438
DOI : 10.1023/A:1010845618420
Ayhan H.
,
Seo D.-W.
2002
“Tail Probability of Transient and Stationary Waiting Times in (Max, +)-Linear Systems,”
IEEE Trans. Autom. Contr.
47
(1)
151 -
157
DOI : 10.1109/9.981736
Seo D.-W.
2005
“Application of (Max, +)-Algebra to the Waiting Times in Deterministic 2-Node Tandem Queues with Blocking,”
J. KORMS Society
30
(1)
149 -
159
@article{ HJTODO_2014_v36n4_609}
,title={Explicit Formulae for Characteristics of Finite-Capacity M/D/1 Queues}
,volume={4}
, url={http://dx.doi.org/10.4218/etrij.14.0113.0812}, DOI={10.4218/etrij.14.0113.0812}
, number= {4}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Seo, Dong-Won}
, year={2014}
, month={Jun}
TY - JOUR
T2 - ETRI Journal
AU - Seo, Dong-Won
SN - 1225-6463
TI - Explicit Formulae for Characteristics of Finite-Capacity M/D/1 Queues
VL - 36
PB - Electronics and Telecommunications Research Institute
DO - 10.4218/etrij.14.0113.0812
PY - 2014
UR - http://dx.doi.org/10.4218/etrij.14.0113.0812
ER -
Seo, D. W.
( 2014).
Explicit Formulae for Characteristics of Finite-Capacity M/D/1 Queues.
ETRI Journal,
36
(4)
Electronics and Telecommunications Research Institute.
doi:10.4218/etrij.14.0113.0812
&
Seo, DW
2014,
Explicit Formulae for Characteristics of Finite-Capacity M/D/1 Queues,
ETRI Journal,
vol. 4,
no. 4,
Retrieved from http://dx.doi.org/10.4218/etrij.14.0113.0812
[1]
and
DW Seo
,
“Explicit Formulae for Characteristics of Finite-Capacity M/D/1 Queues”,
ETRI Journal,
vol. 4,
no. 4,
Jun
2014.
Seo, Dong-Won
and
.
“Explicit Formulae for Characteristics of Finite-Capacity M/D/1 Queues”
ETRI Journal,
4.
4
2014:
Seo, DW
Explicit Formulae for Characteristics of Finite-Capacity M/D/1 Queues.
ETRI Journal
[Internet].
2014.
Jun ;
4
(4)
Available from http://dx.doi.org/10.4218/etrij.14.0113.0812
and
Seo, Dong-Won
.
“Explicit Formulae for Characteristics of Finite-Capacity M/D/1 Queues.”
ETRI Journal
4
no.4
()
Jun,
2014):
http://dx.doi.org/10.4218/etrij.14.0113.0812