# Performance Analysis of Novel Overload Control with Threshold Mechanism

Authors: Doo Il Choi; Dae-Eun Lim
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

We propose a novel overload control method with hysteresis property; that is, we analyze theM
/
G
/
1
/
K queueing system where the service and arrival rates are varied depending on the queue-length. We use two threshold values: L
1
(
≤
L
2
) and L
2
(
≤
K
). When the queue-length increases by an amount between L
1 and L
2, we apply one of the following two strategies to reduce the queue-length, either we decrease the mean service time or we decrease the arrival rate. If the queue-length exceeds L
2 with one strategy, we apply the other; thus, there are two models that depend on the method that was applied first. We derive the queue-length distribution at departure and at arbitrary epochs using the embedded Markov chain method and the supplementary variable method. We investigate performance measures including the loss probability and mean waiting time using various numerical examples.


---

## Body

## 1. Introduction

In systems with queues, various overload control mechanisms to alleviate congestion caused by an excessive number of customers have been investigated. Here, we investigate queue-length-dependent policies based on single or multiple threshold value(s) that depend on the system size. For example, consider an oscillating queue of Chydzinski [1], also known as a queue with a hysteretic control method. There are two threshold values: L
1
(
≥
0
) and L
2
(
≥
L
1
). Initially, the system is idle and the service rate is set to 1
/
μ
1. When the system size exceeds L
2, the service rate is changed to 1
/
μ
2, and it continues until the system size reduces to L
1. The service rate then returns to 1
/
μ
1, and the process is repeated. It is customary to assume that 1
/
μ
1
<
1
/
μ
2 in order to reduce the system size more quickly.Control mechanisms that are based simply on the system size have been applied to many applications, including manufacturing systems, telecommunications, and computer networks. Li and Zhu [2] and Li et al. [3] mentioned that techniques based on the input rate are usually employed due to high throughput demand. There have been several reports of telecommunication networks, including asynchronous transfer mode (ATM) networks, which support various types of traffic, including voice, data, and video. Important properties of such traffic include time correlation and burstiness, which may lead to network congestion due to unpredictable statistical fluctuations in the traffic streams. Overload control mechanisms can be applied to alleviate this congestion to ensure service quality is maintained; for further details, refer to B. D. Choi and D. I. Choi [4], Choi et al. [5, 6], and the references therein. Banik [7] recently reported the BMAP/G-G/1/N oscillating queueing system that can be used to model semiconductor manufacturing processes. Controlling the arrival rate and service rate has been also considered for potential applications in data centers [8]. The service rate is represented by the frequency of the processors, which was adapted to conserve energy by applying voltage control.Here, we propose two novel overload control methods, in which both the arrival and service rates are adapted depending upon the system size. A detailed description of our methods is given in Section3. Most existing models regulate only the service rate in accordance with the system size, whereas the arrival rate remains constant, or vice versa. In contrast, our overload control method changes the service and arrival rates depending upon the system size. In practice, it is common to apply two or more different overload control mechanisms either simultaneously or sequentially. For example, with congested road networks, one or more lanes can be reversed to improve the flow of traffic. Despite this measure, if the area remains congested, entering the section may be prohibited until the waiting times for cars decrease to a certain level. In semiconductor manufacturing systems, adaptation of the service and arrival rates are often considered together. To decrease the input rate to a particular processing tool, the arriving lots can be rerouted (i.e., sent to another machine). For the example of increasing the service rate in semiconductor manufacturing systems, refer to Banik [7].The remainder of this paper is organized as follows. In the subsequent section, we review the relevant literature; a description and analysis of the model is given in Section3; numerical results describing the performance of the model are then given in Section 4; Section 5 provides the conclusions of this paper.


## 2. Literature Review

Queueing models with queue-length-dependent overload control can be classified into two types depending upon the type of rate that is controllable, that is, the service or the arrival rate. The majority of research has assumed Markovian arrival (i.e., anM/G/1-type queueing model), where the service rate is adjusted.Nishimura and Jiang [9] introduced an M/G/1 queueing model with an adjustable service speed. The model had only one threshold; that is, when the number of customers exceeds (is less than) the threshold value, faster (ordinary) service is provided. Dudin [10] extended this model (with a single threshold) with one threshold by considering a batch arrival process. B. D. Choi and D. I. Choi [4] and Choi et al. [5] applied adjustable service rate schemes for telecommunications networks, extending Nishimura and Jiang’s model [9] by considering the arrival process as a Markovian modulated Poisson process (MMPP) (i.e., an MMPP/G/1 queue) or a finite M
/
G
/
1
/
K queueing model, respectively. Later, more complicated arrival processes are considered; Choi [11] analyzed a model with Markovian arrival process (MAP) and an M
X
/
G
/
1 queue with multiple threshold values (or service modes) is analyzed by Choi et al. [12]. Chydzinski [1, 13] and Zhernovyi and Zhernovyi [14, 15] analyzed oscillating queues (or queues with a hysteresis strategy). Oscillating queues with two thresholds differ from queues with multiple thresholds. Suppose a system has two threshold values L
1
(
≥
0
) and L
2
(
≥
L
1
) and that the number of customers is between L
1 and L
2. When hysteretic control is applied, the service modes can differ even for the same number of customers, when the number of customers is between two thresholds (refer to the example in Section 1). On the other hand, in queues with multiple thresholds and without a hysteresis control, the same service mode is applied for the same system size. Jain [16] analyzed a heterogeneous M
/
M
/
r queueing model where the number of working servers varied depending on the number of customers. On aggregate, the number of working servers can be considered as the service speed. Recently, Banik [7] extended the oscillating queueing model by considering a batch Markovian arrival process (BMAP). Gupta et al. [17] considered a DMAP/G/1/K queue with queue-length-dependent service rates. There are few examples of GI/M/1 queueing systems with adjustable service rates, outside of the work of Chydzinski [1].There have been fewer reports of systems with adjustable arrival rates than of systems with adjustable service rates. Gong et al. [18] introduced the M
/
G
/
1 queue with a queue-length-dependent arrival rate. Li and Zhu [2] considered vacations and Li et al. [3] considered the setup time. Chydzinski [19] analyzed an M
/
G
/1 queueing system with hysteretic control based on the arrival rates using potential method. More recently, Choi et al. [6] extended these models by considering an MMPP as an arrival process and multiple thresholds.Although there exist models that can adjust the arrival and service rates simultaneously, they are mostly based on Markov decision process (MDP) and the research interests they address differ from those addressed by our model. Thus, we claim that our model differs significantly from existing queueing models because both the arrival and service rates are controllable. However, the derivation is similar to the models of B. D. Choi and D. I. Choi [4] and Choi et al. [6].


## 3. Analysis

In this section, we describe the model and then analyze it. We derive the queue-length distribution at the departure epoch using the embedded Markov chain method. The queue-length distribution at an arbitrary time is then derived using the supplementary variable method.


### 3.1. Model Description

We consider anM
/
G
/
1
/
K queueing system with the overload control policies “Arrival First (AF)” and “Service First (SF).” The queueing system has a single server and a buffer with finite capacity K, including the customer in service. Customers arrive to the system according to a Poisson process and are served on a first-come-first-served (FCFS) basis. Customers that arrive when the buffer is full are blocked and hence lost. The arrival and service rates are dependent upon the queue-length. We place two thresholds L
1 and L
2 on the buffer, where L
1
≤
L
2. Suppose that the queue-length at the service initiation epoch of a customer is less than the threshold L
1. The arrival of customers follows a Poisson process with a rate λ
1, and the service time of customers is denoted by a random variable S
1, which has the distribution function G
1. When the queue-length is equal to or greater than L
1 at the service initiation epoch, either the arrival rate or the service time distribution changes depending upon the policy that is employed. With the AF policy, the arrival rate for a Poisson process is changed to λ
2
(
≤
λ
1
), while the service time distribution remains unchanged. With the SF policy, the service time of customers is changed and the arrival rate remains constant. The changed service time is denoted by a random variable S
2 with the distribution function G
2. Finally, assume that the queue-length at the service initiation epoch is equal to or greater than L
2
(
<
K
). In this case, the arrival of customers follows a Poisson process with a rate λ
2, and the service time of customers is S
2. We define μ
i as the mean and G
i
∗
(
s
) as the Laplace transform of S
i  (
i
=
1,2
).In this paper, we analyze a system with the AF policy first; a system with the SF policy is then discussed, as the derivations are similar.


### 3.2. Embedded Markov Chain

Letτ
n
(
n
≥
1
) be the epoch of successive departures with τ
0
=
0. The number of customers in a queue (excluding the customer in service) at time τ
n
+ (immediately after the nth departure) is denoted by N
n. The process {
N
n
,
n
≥
0
} forms a Markov chain with a finite state space {
0,1
,
…
,
K
-
1
}. To derive the stationary probability distribution of the Markov chain {
N
n
,
n
≥
0
}, we define the probabilities x
k as(1)
x
k
=
lim
n
→
∞
⁡
Pr
⁡
N
n
=
k
,
0
≤
k
≤
K
-
1
,
x
=
x
0
,
x
1
,
…
,
x
K
-
1
.We introduce the following probabilities to obtainx
k. First, a
n
r denotes the probability that there are n
(
≥
0
) arrivals via a Poisson process with a rate λ
r during the service time S
r; that is,(2)
a
n
r
=
∫
0
∞
e
-
λ
r
x
λ
r
x
n
n
!
d
G
r
x
,
r
=
1,2
.Let b
n
(
n
≥
0
) be the probability that there are n arrivals by a Poisson process with a rate λ
2 during the service time S
1, which is defined as follows (when the employed policy is AF; for the SF policy, refer to Remark 1): (3)
b
n
=
∫
0
∞
e
-
λ
2
x
λ
2
x
n
n
!
d
G
1
x
.We therefore have(4)
a
¯
n
r
=
∑
k
=
n
∞
a
k
r
,
r
=
1,2
,
b
¯
n
=
∑
k
=
n
∞
b
k
.For the Markov chain {
N
n
,
n
≥
0
}, we have the one-step transition probability matrix P as follows: (5)
P
=
a
0
1
a
1
1
a
2
1
⋯
a
L
1
-
1
1
a
L
1
1
a
L
1
+
1
1
⋯
a
L
2
-
1
1
a
L
2
1
a
L
2
+
1
1
⋯
a
K
-
3
1
a
K
-
2
1
a
¯
K
-
1
1
a
0
1
a
1
1
a
2
1
⋯
a
L
1
-
1
1
a
L
1
1
a
L
1
+
1
1
⋯
a
L
2
-
1
1
a
L
2
1
a
L
2
+
1
1
⋯
a
K
-
3
1
a
K
-
2
1
a
¯
K
-
1
1
0
a
0
1
a
1
1
⋯
a
L
1
-
2
1
a
L
1
-
1
1
a
L
1
1
⋯
a
L
2
-
2
1
a
L
2
-
1
1
a
L
2
1
⋯
a
K
-
4
1
a
K
-
3
1
a
¯
K
-
2
1
⋮
⋮
⋮
⋱
⋮
⋮
⋮
⋱
⋮
⋮
⋮
⋱
⋮
⋮
⋮
0
0
0
⋯
a
1
1
a
2
1
a
3
1
⋯
a
L
2
-
L
1
+
1
1
a
L
2
-
L
1
+
2
1
a
L
2
-
L
1
+
3
1
⋯
a
K
-
L
1
-
1
1
a
K
-
L
1
1
a
¯
K
-
L
1
+
1
1
0
0
0
⋯
b
0
b
1
b
2
⋯
b
L
2
-
L
1
b
L
2
-
L
1
+
1
b
L
2
-
L
1
+
2
⋯
b
K
-
L
1
-
2
b
K
-
L
1
-
1
b
¯
K
-
L
1
0
0
0
⋯
0
b
0
b
1
⋯
b
L
2
-
L
1
-
1
b
L
2
-
L
1
b
L
2
-
L
1
+
1
⋯
b
K
-
L
1
-
3
b
K
-
L
1
-
2
b
¯
K
-
L
1
-
1
⋮
⋮
⋮
⋱
⋮
⋮
⋮
⋱
⋮
⋮
⋮
⋱
⋮
⋮
⋮
0
0
0
⋯
0
0
0
⋯
b
1
b
2
b
3
⋯
b
K
-
L
2
-
1
b
K
-
L
2
b
¯
K
-
L
2
+
1
0
0
0
⋯
0
0
0
⋯
a
0
2
a
1
2
a
2
2
⋯
a
K
-
L
2
-
2
2
a
K
-
L
2
-
1
2
a
¯
K
-
L
2
2
0
0
0
⋯
0
0
0
⋯
0
a
0
2
a
1
2
⋯
a
K
-
L
2
-
3
2
a
K
-
L
2
-
2
2
a
¯
K
-
L
2
-
1
2
⋮
⋮
⋮
⋱
⋮
⋮
⋮
⋱
⋮
⋮
⋮
⋱
⋮
⋮
⋮
0
0
0
⋯
0
0
0
⋯
0
0
0
⋯
a
1
2
a
2
2
a
¯
3
2
0
0
0
⋯
0
0
0
⋯
0
0
0
⋯
a
0
2
a
1
2
a
¯
2
2
0
0
0
⋯
0
0
0
⋯
0
0
0
⋯
0
a
0
2
a
¯
1
2
.Remark 1.
The probabilityb
n for the SF policy is defined similarly, which is the probability that there are n arrivals by a Poisson process λ
1 during the service time S
2; that is, (6)
b
n
=
∫
0
∞
e
-
λ
1
x
λ
1
x
n
n
!
d
G
2
x
.To analyze systems, b
n in the matrix P should be computed properly.The stationary probability vectorx of the Markov chain {
N
n
,
n
≥
0
} can be obtained by solving the following equations: (7)
x
P
=
x
,
x
e
=
1
,where e
=
(
1,1
,
…
,
1
)
T.


### 3.3. Queue-Length Distribution at an Arbitrary Time

In this section, we derive the stationary queue-length distribution at an arbitrary time. At an arbitrary timet, let N
(
t
) be the queue-length including a customer in service, and let (8)
ξ
t
=
1
,
if the service time distribution is
S
1
at time
t
,
2
,
if the service time distribution is
S
2
at time
t
.We define the stationary probabilities as follows: (9)
y
n
=
lim
t
→
∞
⁡
Pr
⁡
N
t
=
n
,
0
≤
n
≤
K
.Then, from the key renewal theorem, we have (10)
y
0
=
1
E
x
0
1
λ
1
,where E
=
x
0
1
/
λ
1
+
μ
1
+
∑
n
=
1
L
2
-
1
‍
x
n
μ
1
+
∑
n
=
L
2
K
-
1
‍
x
n
μ
2 is the mean interdeparture time of customers.Remark 2.
For the SF case, we have(11)
E
=
x
0
1
λ
1
+
μ
1
+
∑
n
=
1
L
1
-
1
x
n
μ
1
+
∑
n
=
L
1
K
-
1
x
n
μ
2
.Using the supplementary variable method, we derive the stationary queue-length distribution{
y
n
,
n
≥
1
} at an arbitrary time when the server is busy. Note that the method of obtaining y
n is similar to that used by B. D. Choi and D. I. Choi [4] and Choi et al. [6]. Let T
^ denote the remaining service time and T
~ the elapsed service time for the customer in service. We define the joint probability distribution of the queue-length and the remaining service time for the customer in service as (12)
α
n
,
r
x
d
x
=
lim
t
→
∞
⁡
Pr
⁡
N
t
=
n
,
x
<
T
^
≤
x
+
d
x
,
ξ
t
=
r
,
r
=
1,2
.The Laplace transform of α
n
,
r
x
(
r
=
1,2
) is as follows: (13)
α
n
,
r
∗
s
=
∫
0
∞
e
-
s
x
α
n
,
r
x
d
x
.To calculate α
n
,
r
∗
(
s
), we must find the probability for arrivals during the elapsed service time T
~. Thus, we define the joint probabilities β
r
(
n
,
x
)
d
x and β
b
(
n
,
x
)
d
x as(14)
β
r
n
,
x
d
x
=
lim
t
→
∞
⁡
P
r
n
arrivals  during
T
~
by
λ
r
,
x
<
T
^
≤
x
+
d
x
,
ξ
t
=
r
,
r
=
1,2
,
(15)
β
b
n
,
x
d
x
=
lim
t
→
∞
⁡
P
r
n
arrivals  during
T
~
by
λ
2
,
x
<
T
^
≤
x
+
d
x
,
ξ
t
=
1
.Letβ
r
∗
(
n
,
s
) and β
b
∗
(
n
,
s
) be the Laplace transform of β
r
(
n
,
x
) and β
b
(
n
,
x
), respectively; that is, (16)
β
r
∗
n
,
s
=
∫
0
∞
e
-
s
x
β
r
n
,
x
d
x
,
r
=
1,2
,
β
b
∗
n
,
s
=
∫
0
∞
e
-
s
x
β
b
n
,
x
d
x
.From the basic property of the semi-Markov process, α
n
,
r
∗
(
s
) must satisfy two relations for α
n
,
1
∗
(
s
) and α
n
,
2
∗
(
s
). First, for 1
≤
n
<
L
2, we have(17)
α
n
,
1
∗
s
=
μ
1
E
x
0
β
1
∗
n
-
1
,
s
+
∑
k
=
1
min
⁡
n
,
L
1
-
1
x
k
β
1
∗
n
-
k
,
s
+
∑
k
=
L
1
min
⁡
n
,
L
2
-
1
x
k
β
b
∗
n
-
k
,
s
1
n
≥
L
1
,where 1
{
c
o
n
d
i
t
i
o
n
}
=
1 when the “condition” is true; otherwise 1
{
c
o
n
d
i
t
i
o
n
}
=
0. When L
2
≤
n
<
K, we have(18)
α
n
,
2
∗
s
=
μ
2
E
∑
k
=
L
2
n
x
k
β
2
∗
n
-
k
,
s
.Remark 3.
For the SF case, the definition ofβ
b
(
n
,
x
)
d
x in (15) is replaced by (19); that is,(19)
β
b
n
,
x
d
x
=
lim
t
→
∞
⁡
Pr
⁡
n
arrivals during
T
~
by
λ
1
,
x
<
T
^
≤
x
+
d
x
,
ξ
t
=
2
.In addition, (17) and (18) for α
n
,
1
∗
(
s
) and α
n
,
2
∗
(
s
) are replaced by (20) and (21), respectively; that is, for 1
≤
n
<
L
1, we have(20)
α
n
,
1
∗
s
=
μ
1
E
x
0
β
1
∗
n
-
1
,
s
+
∑
k
=
1
min
⁡
n
,
L
1
-
1
x
k
β
1
∗
n
-
k
,
s
,and for L
1
≤
n
<
K, we have(21)
α
n
,
2
∗
s
=
μ
2
E
∑
k
=
L
1
min
⁡
n
,
L
2
-
1
x
k
β
b
∗
n
-
k
,
s
+
∑
k
=
L
2
n
x
k
β
2
∗
n
-
k
,
s
1
n
≥
L
2
.By comparing the coefficients, which is the same method used by B. D. Choi and D. I. Choi [4] and Choi et al. [6], β
r
∗
(
n
,
s
) is given by (22)
β
r
∗
n
,
s
=
1
μ
r
∑
l
=
0
n
a
l
r
R
n
-
l
r
s
-
G
r
∗
s
R
n
r
s
,
r
=
1,2
,
β
b
∗
n
,
s
=
1
μ
1
∑
l
=
0
n
b
l
R
n
-
l
2
s
-
G
1
∗
s
R
n
2
s
,where R
n
r
(
s
)
=
(
s
-
λ
r
)
-
1
{
λ
r
(
λ
r
-
s
)
-
1
}
n.Remark 4.
For the SF case,β
b
∗
(
n
,
s
)
=
(
1
/
μ
2
)
∑
l
=
0
n
‍
b
l
R
n
-
l
1
(
s
)
-
G
2
∗
(
s
)
R
n
1
(
s
).By substitutingβ
r
∗
n
,
s  (
r
=
1,2
,
b
) into (17) and (18) and then setting s
=
0, we obtain the stationary queue-length probabilities at an arbitrary time for 1
≤
n
<
K; that is,(23)
y
n
=
α
n
,
1
∗
0
+
α
n
,
2
∗
0
=
1
λ
1
E
x
0
1
-
∑
l
=
0
n
-
1
a
l
1
+
∑
k
=
1
min
⁡
n
,
L
1
-
1
x
k
1
-
∑
l
=
0
n
-
k
a
l
1
+
1
λ
2
E
∑
k
=
L
1
min
⁡
n
,
L
2
-
1
x
k
1
-
∑
l
=
0
n
-
k
b
l
1
n
≥
L
1
+
1
λ
2
E
∑
k
=
L
2
n
x
k
1
-
∑
l
=
0
n
-
k
a
l
2
1
n
≥
L
2
,
(24)
y
K
=
1
-
∑
k
=
0
K
-
1
y
k
.Remark 5.
For the SF case,y
n  (
1
≤
n
<
K
) in (23) is defined as follows:(25)
y
n
=
1
λ
1
E
x
0
1
-
∑
l
=
0
n
-
1
a
l
1
+
∑
k
=
1
min
⁡
n
,
L
1
-
1
x
k
1
-
∑
l
=
0
n
-
k
a
l
1
+
1
λ
1
E
∑
k
=
L
1
min
⁡
n
,
L
2
-
1
x
k
1
-
∑
l
=
0
n
-
k
b
l
1
n
≥
L
1
+
1
λ
2
E
∑
k
=
L
2
n
x
k
1
-
∑
l
=
0
n
-
k
a
l
2
1
n
≥
L
2
.


### 3.4. Performance Measures

We obtain three performance measures using the stationary queue-length distribution{
y
n
,
n
≥
0
} in (23) or (25). First, the loss probability P
l
o
s
s (or blocking probability) is defined as (26)
P
l
o
s
s
=
y
K
.Second, the mean queue-length (excluding the customer in service) is (27)
L
q
=
∑
i
=
1
K
i
y
i
.Finally, from Little’s law, we obtain the mean waiting time in the system as follows: (28)
W
q
=
L
q
λ
∗
1
-
P
l
o
s
s
,where(29)
λ
∗
=
∑
k
=
0
L
1
-
1
x
k
λ
1
+
∑
k
=
L
1
K
-
1
x
k
λ
2
.Remark 6.
For the SF case, we have(30)
λ
∗
=
∑
k
=
0
L
2
-
1
x
k
λ
1
+
∑
k
=
L
2
K
-
1
x
k
λ
2
.


## 3.1. Model Description

We consider anM
/
G
/
1
/
K queueing system with the overload control policies “Arrival First (AF)” and “Service First (SF).” The queueing system has a single server and a buffer with finite capacity K, including the customer in service. Customers arrive to the system according to a Poisson process and are served on a first-come-first-served (FCFS) basis. Customers that arrive when the buffer is full are blocked and hence lost. The arrival and service rates are dependent upon the queue-length. We place two thresholds L
1 and L
2 on the buffer, where L
1
≤
L
2. Suppose that the queue-length at the service initiation epoch of a customer is less than the threshold L
1. The arrival of customers follows a Poisson process with a rate λ
1, and the service time of customers is denoted by a random variable S
1, which has the distribution function G
1. When the queue-length is equal to or greater than L
1 at the service initiation epoch, either the arrival rate or the service time distribution changes depending upon the policy that is employed. With the AF policy, the arrival rate for a Poisson process is changed to λ
2
(
≤
λ
1
), while the service time distribution remains unchanged. With the SF policy, the service time of customers is changed and the arrival rate remains constant. The changed service time is denoted by a random variable S
2 with the distribution function G
2. Finally, assume that the queue-length at the service initiation epoch is equal to or greater than L
2
(
<
K
). In this case, the arrival of customers follows a Poisson process with a rate λ
2, and the service time of customers is S
2. We define μ
i as the mean and G
i
∗
(
s
) as the Laplace transform of S
i  (
i
=
1,2
).In this paper, we analyze a system with the AF policy first; a system with the SF policy is then discussed, as the derivations are similar.


## 3.2. Embedded Markov Chain

Letτ
n
(
n
≥
1
) be the epoch of successive departures with τ
0
=
0. The number of customers in a queue (excluding the customer in service) at time τ
n
+ (immediately after the nth departure) is denoted by N
n. The process {
N
n
,
n
≥
0
} forms a Markov chain with a finite state space {
0,1
,
…
,
K
-
1
}. To derive the stationary probability distribution of the Markov chain {
N
n
,
n
≥
0
}, we define the probabilities x
k as(1)
x
k
=
lim
n
→
∞
⁡
Pr
⁡
N
n
=
k
,
0
≤
k
≤
K
-
1
,
x
=
x
0
,
x
1
,
…
,
x
K
-
1
.We introduce the following probabilities to obtainx
k. First, a
n
r denotes the probability that there are n
(
≥
0
) arrivals via a Poisson process with a rate λ
r during the service time S
r; that is,(2)
a
n
r
=
∫
0
∞
e
-
λ
r
x
λ
r
x
n
n
!
d
G
r
x
,
r
=
1,2
.Let b
n
(
n
≥
0
) be the probability that there are n arrivals by a Poisson process with a rate λ
2 during the service time S
1, which is defined as follows (when the employed policy is AF; for the SF policy, refer to Remark 1): (3)
b
n
=
∫
0
∞
e
-
λ
2
x
λ
2
x
n
n
!
d
G
1
x
.We therefore have(4)
a
¯
n
r
=
∑
k
=
n
∞
a
k
r
,
r
=
1,2
,
b
¯
n
=
∑
k
=
n
∞
b
k
.For the Markov chain {
N
n
,
n
≥
0
}, we have the one-step transition probability matrix P as follows: (5)
P
=
a
0
1
a
1
1
a
2
1
⋯
a
L
1
-
1
1
a
L
1
1
a
L
1
+
1
1
⋯
a
L
2
-
1
1
a
L
2
1
a
L
2
+
1
1
⋯
a
K
-
3
1
a
K
-
2
1
a
¯
K
-
1
1
a
0
1
a
1
1
a
2
1
⋯
a
L
1
-
1
1
a
L
1
1
a
L
1
+
1
1
⋯
a
L
2
-
1
1
a
L
2
1
a
L
2
+
1
1
⋯
a
K
-
3
1
a
K
-
2
1
a
¯
K
-
1
1
0
a
0
1
a
1
1
⋯
a
L
1
-
2
1
a
L
1
-
1
1
a
L
1
1
⋯
a
L
2
-
2
1
a
L
2
-
1
1
a
L
2
1
⋯
a
K
-
4
1
a
K
-
3
1
a
¯
K
-
2
1
⋮
⋮
⋮
⋱
⋮
⋮
⋮
⋱
⋮
⋮
⋮
⋱
⋮
⋮
⋮
0
0
0
⋯
a
1
1
a
2
1
a
3
1
⋯
a
L
2
-
L
1
+
1
1
a
L
2
-
L
1
+
2
1
a
L
2
-
L
1
+
3
1
⋯
a
K
-
L
1
-
1
1
a
K
-
L
1
1
a
¯
K
-
L
1
+
1
1
0
0
0
⋯
b
0
b
1
b
2
⋯
b
L
2
-
L
1
b
L
2
-
L
1
+
1
b
L
2
-
L
1
+
2
⋯
b
K
-
L
1
-
2
b
K
-
L
1
-
1
b
¯
K
-
L
1
0
0
0
⋯
0
b
0
b
1
⋯
b
L
2
-
L
1
-
1
b
L
2
-
L
1
b
L
2
-
L
1
+
1
⋯
b
K
-
L
1
-
3
b
K
-
L
1
-
2
b
¯
K
-
L
1
-
1
⋮
⋮
⋮
⋱
⋮
⋮
⋮
⋱
⋮
⋮
⋮
⋱
⋮
⋮
⋮
0
0
0
⋯
0
0
0
⋯
b
1
b
2
b
3
⋯
b
K
-
L
2
-
1
b
K
-
L
2
b
¯
K
-
L
2
+
1
0
0
0
⋯
0
0
0
⋯
a
0
2
a
1
2
a
2
2
⋯
a
K
-
L
2
-
2
2
a
K
-
L
2
-
1
2
a
¯
K
-
L
2
2
0
0
0
⋯
0
0
0
⋯
0
a
0
2
a
1
2
⋯
a
K
-
L
2
-
3
2
a
K
-
L
2
-
2
2
a
¯
K
-
L
2
-
1
2
⋮
⋮
⋮
⋱
⋮
⋮
⋮
⋱
⋮
⋮
⋮
⋱
⋮
⋮
⋮
0
0
0
⋯
0
0
0
⋯
0
0
0
⋯
a
1
2
a
2
2
a
¯
3
2
0
0
0
⋯
0
0
0
⋯
0
0
0
⋯
a
0
2
a
1
2
a
¯
2
2
0
0
0
⋯
0
0
0
⋯
0
0
0
⋯
0
a
0
2
a
¯
1
2
.Remark 1.
The probabilityb
n for the SF policy is defined similarly, which is the probability that there are n arrivals by a Poisson process λ
1 during the service time S
2; that is, (6)
b
n
=
∫
0
∞
e
-
λ
1
x
λ
1
x
n
n
!
d
G
2
x
.To analyze systems, b
n in the matrix P should be computed properly.The stationary probability vectorx of the Markov chain {
N
n
,
n
≥
0
} can be obtained by solving the following equations: (7)
x
P
=
x
,
x
e
=
1
,where e
=
(
1,1
,
…
,
1
)
T.


## 3.3. Queue-Length Distribution at an Arbitrary Time

In this section, we derive the stationary queue-length distribution at an arbitrary time. At an arbitrary timet, let N
(
t
) be the queue-length including a customer in service, and let (8)
ξ
t
=
1
,
if the service time distribution is
S
1
at time
t
,
2
,
if the service time distribution is
S
2
at time
t
.We define the stationary probabilities as follows: (9)
y
n
=
lim
t
→
∞
⁡
Pr
⁡
N
t
=
n
,
0
≤
n
≤
K
.Then, from the key renewal theorem, we have (10)
y
0
=
1
E
x
0
1
λ
1
,where E
=
x
0
1
/
λ
1
+
μ
1
+
∑
n
=
1
L
2
-
1
‍
x
n
μ
1
+
∑
n
=
L
2
K
-
1
‍
x
n
μ
2 is the mean interdeparture time of customers.Remark 2.
For the SF case, we have(11)
E
=
x
0
1
λ
1
+
μ
1
+
∑
n
=
1
L
1
-
1
x
n
μ
1
+
∑
n
=
L
1
K
-
1
x
n
μ
2
.Using the supplementary variable method, we derive the stationary queue-length distribution{
y
n
,
n
≥
1
} at an arbitrary time when the server is busy. Note that the method of obtaining y
n is similar to that used by B. D. Choi and D. I. Choi [4] and Choi et al. [6]. Let T
^ denote the remaining service time and T
~ the elapsed service time for the customer in service. We define the joint probability distribution of the queue-length and the remaining service time for the customer in service as (12)
α
n
,
r
x
d
x
=
lim
t
→
∞
⁡
Pr
⁡
N
t
=
n
,
x
<
T
^
≤
x
+
d
x
,
ξ
t
=
r
,
r
=
1,2
.The Laplace transform of α
n
,
r
x
(
r
=
1,2
) is as follows: (13)
α
n
,
r
∗
s
=
∫
0
∞
e
-
s
x
α
n
,
r
x
d
x
.To calculate α
n
,
r
∗
(
s
), we must find the probability for arrivals during the elapsed service time T
~. Thus, we define the joint probabilities β
r
(
n
,
x
)
d
x and β
b
(
n
,
x
)
d
x as(14)
β
r
n
,
x
d
x
=
lim
t
→
∞
⁡
P
r
n
arrivals  during
T
~
by
λ
r
,
x
<
T
^
≤
x
+
d
x
,
ξ
t
=
r
,
r
=
1,2
,
(15)
β
b
n
,
x
d
x
=
lim
t
→
∞
⁡
P
r
n
arrivals  during
T
~
by
λ
2
,
x
<
T
^
≤
x
+
d
x
,
ξ
t
=
1
.Letβ
r
∗
(
n
,
s
) and β
b
∗
(
n
,
s
) be the Laplace transform of β
r
(
n
,
x
) and β
b
(
n
,
x
), respectively; that is, (16)
β
r
∗
n
,
s
=
∫
0
∞
e
-
s
x
β
r
n
,
x
d
x
,
r
=
1,2
,
β
b
∗
n
,
s
=
∫
0
∞
e
-
s
x
β
b
n
,
x
d
x
.From the basic property of the semi-Markov process, α
n
,
r
∗
(
s
) must satisfy two relations for α
n
,
1
∗
(
s
) and α
n
,
2
∗
(
s
). First, for 1
≤
n
<
L
2, we have(17)
α
n
,
1
∗
s
=
μ
1
E
x
0
β
1
∗
n
-
1
,
s
+
∑
k
=
1
min
⁡
n
,
L
1
-
1
x
k
β
1
∗
n
-
k
,
s
+
∑
k
=
L
1
min
⁡
n
,
L
2
-
1
x
k
β
b
∗
n
-
k
,
s
1
n
≥
L
1
,where 1
{
c
o
n
d
i
t
i
o
n
}
=
1 when the “condition” is true; otherwise 1
{
c
o
n
d
i
t
i
o
n
}
=
0. When L
2
≤
n
<
K, we have(18)
α
n
,
2
∗
s
=
μ
2
E
∑
k
=
L
2
n
x
k
β
2
∗
n
-
k
,
s
.Remark 3.
For the SF case, the definition ofβ
b
(
n
,
x
)
d
x in (15) is replaced by (19); that is,(19)
β
b
n
,
x
d
x
=
lim
t
→
∞
⁡
Pr
⁡
n
arrivals during
T
~
by
λ
1
,
x
<
T
^
≤
x
+
d
x
,
ξ
t
=
2
.In addition, (17) and (18) for α
n
,
1
∗
(
s
) and α
n
,
2
∗
(
s
) are replaced by (20) and (21), respectively; that is, for 1
≤
n
<
L
1, we have(20)
α
n
,
1
∗
s
=
μ
1
E
x
0
β
1
∗
n
-
1
,
s
+
∑
k
=
1
min
⁡
n
,
L
1
-
1
x
k
β
1
∗
n
-
k
,
s
,and for L
1
≤
n
<
K, we have(21)
α
n
,
2
∗
s
=
μ
2
E
∑
k
=
L
1
min
⁡
n
,
L
2
-
1
x
k
β
b
∗
n
-
k
,
s
+
∑
k
=
L
2
n
x
k
β
2
∗
n
-
k
,
s
1
n
≥
L
2
.By comparing the coefficients, which is the same method used by B. D. Choi and D. I. Choi [4] and Choi et al. [6], β
r
∗
(
n
,
s
) is given by (22)
β
r
∗
n
,
s
=
1
μ
r
∑
l
=
0
n
a
l
r
R
n
-
l
r
s
-
G
r
∗
s
R
n
r
s
,
r
=
1,2
,
β
b
∗
n
,
s
=
1
μ
1
∑
l
=
0
n
b
l
R
n
-
l
2
s
-
G
1
∗
s
R
n
2
s
,where R
n
r
(
s
)
=
(
s
-
λ
r
)
-
1
{
λ
r
(
λ
r
-
s
)
-
1
}
n.Remark 4.
For the SF case,β
b
∗
(
n
,
s
)
=
(
1
/
μ
2
)
∑
l
=
0
n
‍
b
l
R
n
-
l
1
(
s
)
-
G
2
∗
(
s
)
R
n
1
(
s
).By substitutingβ
r
∗
n
,
s  (
r
=
1,2
,
b
) into (17) and (18) and then setting s
=
0, we obtain the stationary queue-length probabilities at an arbitrary time for 1
≤
n
<
K; that is,(23)
y
n
=
α
n
,
1
∗
0
+
α
n
,
2
∗
0
=
1
λ
1
E
x
0
1
-
∑
l
=
0
n
-
1
a
l
1
+
∑
k
=
1
min
⁡
n
,
L
1
-
1
x
k
1
-
∑
l
=
0
n
-
k
a
l
1
+
1
λ
2
E
∑
k
=
L
1
min
⁡
n
,
L
2
-
1
x
k
1
-
∑
l
=
0
n
-
k
b
l
1
n
≥
L
1
+
1
λ
2
E
∑
k
=
L
2
n
x
k
1
-
∑
l
=
0
n
-
k
a
l
2
1
n
≥
L
2
,
(24)
y
K
=
1
-
∑
k
=
0
K
-
1
y
k
.Remark 5.
For the SF case,y
n  (
1
≤
n
<
K
) in (23) is defined as follows:(25)
y
n
=
1
λ
1
E
x
0
1
-
∑
l
=
0
n
-
1
a
l
1
+
∑
k
=
1
min
⁡
n
,
L
1
-
1
x
k
1
-
∑
l
=
0
n
-
k
a
l
1
+
1
λ
1
E
∑
k
=
L
1
min
⁡
n
,
L
2
-
1
x
k
1
-
∑
l
=
0
n
-
k
b
l
1
n
≥
L
1
+
1
λ
2
E
∑
k
=
L
2
n
x
k
1
-
∑
l
=
0
n
-
k
a
l
2
1
n
≥
L
2
.


## 3.4. Performance Measures

We obtain three performance measures using the stationary queue-length distribution{
y
n
,
n
≥
0
} in (23) or (25). First, the loss probability P
l
o
s
s (or blocking probability) is defined as (26)
P
l
o
s
s
=
y
K
.Second, the mean queue-length (excluding the customer in service) is (27)
L
q
=
∑
i
=
1
K
i
y
i
.Finally, from Little’s law, we obtain the mean waiting time in the system as follows: (28)
W
q
=
L
q
λ
∗
1
-
P
l
o
s
s
,where(29)
λ
∗
=
∑
k
=
0
L
1
-
1
x
k
λ
1
+
∑
k
=
L
1
K
-
1
x
k
λ
2
.Remark 6.
For the SF case, we have(30)
λ
∗
=
∑
k
=
0
L
2
-
1
x
k
λ
1
+
∑
k
=
L
2
K
-
1
x
k
λ
2
.


## 4. Numerical Examples

In this section, we present numerical examples on the performance of our overload control method. We obtained various results, changing sets of the parametersλ
i, μ
i, L
i, and K, where i
=
1,2. The input rate, the mean service time, and K are assumed to, respectively, have a value listed in Table 1. Note that L
1 and L
2 are depending on the relation 0
≤
L
1
≤
L
2
<
K. We consider three service time distributions: the exponential and the Erlang distributions with a parameter of 2 or 9. It is assumed that the service time distribution itself is also changeable; for example, for the SF policy, the service time distribution when the system size is less than L
1 may differ from when the system size is greater than L
1. The Erlang distribution with a parameter of 2 and 9 and exponential distribution are denoted by “ERL2,” “ERL9,” and “EXP,” respectively. Suppose that the service time distribution before adjusting the mean service time is the Erlang distribution with a parameter 9, and the Erlang distribution with a parameter 2 is applied after the adjustment. It is then denoted by “ERL9-ERL2.”Table 1
Assumed values for each parameter.
Parameter
Values
K
10, 30, 50
The input rate
3, 5, 7, 9
The mean service time
0.1, 0.125, 0.167, 0.25We compare the mean system size (L
q) of an M
/
G
/
1
/
K queue with the AF policy and the same queue with the SF policy. The mean system size over the policies and the service time distribution is depicted in Figure 1. It is assumed that λ
1
=
7, λ
2
=
3, μ
1
=
0.25, μ
2
=
0.125, and K
=
30. Cases are the combinations of distributions and the policies. Note that the mean system size when L
1
=
L
2
=
0 corresponds to that of a standard M
/
G
/
1
/
K queue (without any policies). When L
1
=
L
2
(
>
0
), it corresponds to an M
/
G
/
1
/
K queue with a single threshold. In Figure 1, as expected, the mean system size gets larger as L
1 and L
2 values increase. It is also clear that the distribution with smaller coefficient of variation (CV) has the smaller mean system size for the identical policy; for example, in Figure 1(b), the CV values of the exponential distribution and the Erlang distribution with a parameter 9 are 1 and 1/3, respectively. Figure 2 also shows the mean system size when K
=
50, but graphs are represented in a different way. In this case, we assume that λ
1
=
7, λ
2
=
3, μ
1
=
0.167, and μ
2
=
0.125.Figure 1
The mean system size over the policies and the service time distributions (K
=
30).
(a)
(b)Figure 2
The mean system size over the policies and the service time distributions (K
=
50).
(a)
(b)In Figure3, the blocking probabilities over the policies (the AF or SF and combinations of L
1 and L
2) and the service time distributions are illustrated. In this example, we assume that λ
1
=
9, λ
2
=
5, μ
1
=
0.25, μ
2
=
0.167, and K
=
10.Figure 3
The blocking probability over the policies and the service time distributions.
(a)
(b)Based on Figures1, 2, and 3, it seems that the AF policy is more efficient in reducing L
q and P
l
o
s
s. That is, because the effective arrival rate (λ
∗) is smaller than that of the SF policy, referring to (29) and (30), it then can be concluded that λ
∗ of the AF policy is smaller given that λ
1 is reasonably larger than λ
2. However, the AF policy is not always superior considering the mean waiting time in the queue. Table 2 shows the performance measures when K
=
10, λ
1
=
9, λ
2
=
5, μ
1
=
0.25, and μ
2
=
0.167, and the same condition is used when illustrating Figure 3. The service time distribution is fixed to the exponential distribution and it is denoted by “EXP-EXP” using our notation. We can find out that the mean waiting time in the queue of the SF policy is not always larger. For more congested conditions (larger L
1 and L
2 values), the SF policy works better in terms of W
q.Table 2
Performance measures of anM/M/1/10 queue with the AF and SF policy.
(
L
1
,
L
2
)
L
q
W
q
P
l
o
s
s
λ
∗
AF
SF
AF
SF
AF
SF
AF
SF
(
0,0
)
3.3058
3.3058
0.6827
0.6827
0.0315
0.0315
5.0000
5.0000
(
0,2
)
4.0239
4.7729
0.8403
0.8705
0.0422
0.0559
5.0000
5.8078
(
0,4
)
4.7822
5.7890
1.0143
1.0158
0.0570
0.0827
5.0000
6.2127
(
0,6
)
5.6154
6.7887
1.2253
1.1806
0.0834
0.1294
5.0000
6.6050
(
0,8
)
6.4002
7.6390
1.4730
1.3330
0.1310
0.2121
5.0000
7.2734
(
2,2
)
5.2464
5.2464
1.0183
1.0183
0.0708
0.0708
5.5452
5.5452
(
2,4
)
5.5374
5.9766
1.1194
1.0800
0.0746
0.0889
5.3456
6.0742
(
2,6
)
6.1719
6.8886
1.3071
1.2147
0.0972
0.1328
5.2299
6.5395
(
2,8
)
6.8586
7.7052
1.5512
1.3545
0.1449
0.2148
5.1709
7.2444
(
4,4
)
6.4017
6.4017
1.2475
1.2475
0.1082
0.1082
5.7543
5.7543
(
4,6
)
6.7383
7.0971
1.3920
1.2970
0.1191
0.1423
5.4955
6.3803
(
4,8
)
7.3040
7.8399
1.6316
1.4040
0.1645
0.2216
5.3579
7.1742
(
6,6
)
7.4982
7.4982
1.5095
1.5095
0.1743
0.1743
6.0158
6.0158
(
6,8
)
7.8479
8.0775
1.7289
1.5189
0.2048
0.2409
5.7086
7.0057
(
8,8
)
8.4580
8.4580
1.8258
1.8258
0.3005
0.3005
6.6229
6.6229


## 5. Conclusion

We have analyzed theM
/
G
/
1
/
K queueing system with adjustable service and arrival rates depending on the queue-length. We derive the queue-length distributions at departure and at arbitrary epochs using the embedded Markov chain method and the supplementary variable technique. We presented performance measures including the mean system size and the blocking probabilities. The performance of our overload control method was then verified using numerical examples.We have identified three areas for further work. First, after defining the proper cost structure, it is possible to investigate the trade-off between maintaining a small sized system by changing the arrival and service rates early and the total cost, which includes the holding cost related to the system size and the operating cost related to the speed of service. Second, there has been little investigation of general input models (i.e., GI/M/1-type queues) with variable service or arrival rates; it is possible to analyze the GI/M/1 queueing models with various state-dependent policies. Lastly, it is possible to assume a queueing system adjusts the arrival and service rates immediately after the queue size reaches L
1 and L
2, not at the service completion epochs.



---

*Source: 7871624-2016-01-26.xml*