Future University Hakodate Academic Archive

NASHAT, Dalia

1758

Jiang, Xiaohong

00345654

Kameyama, Michitaka

1759

Future University Hakodate Repository

English

Group Testing Based Detection of Web Service DDoS Attackers

Wang, Xiaoliang

1777

Horiguchi, Susumu

1778

New Bounds on the Feedfoward Design of Optical Output Buffer Multiplexers and Switches

Pattavina, Achille

1797

1798

Rearrangeable f-cast multi-log2 N networks

津田, 顕輝

Japanese

トランプ技術の習得を支援するカード型デバイスの提案

Liu, Jianming

1799

1800

IEEE COMMUNICATIONS LETTERS, VOL. 12, NO. 9, SEPTEMBER 2008 1
Recursive Formula for the Moments of
Queue Length in the M/M/1 Queue
Jianming Liu, Xiaohong Jiang, and Susumu Horiguchi, Senior Member, IEEE
Abstract—This letter presents the recursive formulas of the
moments of queue length for the M/M/1 queue and M/M/1/B
queue, respectively. The higher moments of queue length are
important for optimization problem. Our method provides an
alternative approach to derive the moments of queue length,
instead of taking the derivatives of the moment generating
function.
Index Terms—M/M/1 queue, queue length distribution, mo-
ments, recursive formula.
I. INTRODUCTION
THE M/M/1 queue is of great interest in queueing theorybecause of its concise properties. It has been widely used
in the traffic engineering of communication networks [1]-[5].
Much effort has thus been devoted to the study of both the
equilibrium and transient properties of this queue [6]-[8]. The
higher moments of queue length are important in optimization
problems [9]-[11] (e.g. using higher moments to construct
some performance bound or to analyze the system transient
behavior). Usually, we compute the moments of queue length
distribution from its Moment Generating Function (MGF). In
this letter, starting from the basic state transition equations of
the queue, we get the recursive formula of the moments of
queue length for both the M/M/1 and the finite M/M/1/B
queues. Our method to derive the recursive formulas can
also be applied to various of queueing systems to compute
the moments of queue length. For example, the M/M/c,
the queue with c servers; M/Er/1 queue, Er means the
r-stage Erlangian server; or the MMPP/M/1 queue, the
queue with Markov-Modulated Poisson arrival Process. We
will demonstrate the moment recursive formulas of the queue
length for the M/M/1 and M/M/1/B queues in Section II
and Section III, respectively.
II. MOMENT RECURSIVE FORMULA IN M/M/1 QUEUE
A. Brief review of M/M/1 queue
M/M/1 is the Kendall’s notation of a single server queue
with a Poisson arrival process and an exponential distribu-
tion for the service time [12]. Here, we assume the packet
Manuscript received May 3, 2008. The associate editor coordinating the
review of this letter and approving it for publication was J. Murphy. This work
was supported in part by the GCOE project of Tohoku University, JSPS Grant-
In-Aid of Scientific Research (C) 19500050, the National Natural Science
Foundation of China (60762002) and GuangXi province (0731024), the State
Key Laboratory for Novel Software Technology, Nanjing University, China.
The authors are with the Graduate School of Tohoku University, Sendai
980-8579, Japan. The first author is also with the School of Computer
and Control, GuiLin University of Electronic Technology, GuiLin, 541001,
GuangXi, P. R. China (e-mail: {jmliu, jiang, susumu}@ecei.tohoku.ac.jp;
jmliu@guet.edu.cn).
Digital Object Identifier 10.1109/LCOMM.2008.080700.
arrival to the queue is Poisson process with rate λ, and the
packet length is exponential distributed with mean 1/μ. Define
{Pn, n = 0, 1, 2, ...} as the equilibrium probabilities that the
queue contains n packets (including the one in service). Then,
they satisfy the following state transition equations [12]:{
μP1 = λP0
μPn+1 = (λ + μ)Pn − λPn−1 (n = 1, 2, 3...).
(1)
The offered load to the queue is ρ = λ/μ; only if ρ < 1,
the queue can be stable and approach to the equilibrium state.
P0 is the probability of system being empty, and from Little’s
law [12], we have
1 − P0 = λ
μ
= ρ. (2)
Based on equation (1) and (2), we can get the following results
for the number of packet in the queue [12]: Packet number
distribution
Pn = ρ(1 − ρ)n (n = 0, 1, 2, ...,∞). (3)
Average number of packet
N̄ =
∞∑
n=1
nPn =
ρ
1 − ρ . (4)
Moment generating function
P (z) =
1 − ρ
1 − ρz . (5)
By taking the derivatives of equation (5), we can obtain the
moments of queue length. In the following section, we will
present the recursive formula to compute the moments of
queue length.
B. Recursive formula in M/M/1 queue
Theorem 1: In an M/M/1 queue with arrival rate λ and
mean service time 1/μ, when the offered load ρ = λμ < 1, and
define M0 =
∑∞
n=0 Pn = 1, then the kth moment Mk(k ≥ 1)
of queue length satisfies
Mk =
k+1∑
l=2
(
k + l
l
) [
(−1)l + ρ] Mk+1−l − (−1)k+1 [1 − ρ]
(k + 1)(1 − ρ) .
(6)
Actually, from Theorem 1, we get
M1 =
ρ
1 − ρ , (7)
M2 =
1 + ρ
1 − ρM1, (8)
1089-7798/08$25.00 c© 2008 IEEE
2 IEEE COMMUNICATIONS LETTERS, VOL. 12, NO. 9, SEPTEMBER 2008
M3 =
3(1 + ρ)
2(1 − ρ)M2 − M1 +
ρ
2(1 − ρ) , (9)
and the arbitrary higher moments can be recursively computed.
Proof:
When k ≥ 1, define Mk =
∑∞
n=0 n
kPn. Multiplying nk+1
on both sides of the second equation of (1) yields
μnk+1Pn+1 = (λ + μ)nk+1Pn − λnk+1Pn−1. (10)
We can further write equation (10) as
μ [(n + 1) − 1]k+1 Pn+1
= (λ + μ)nk+1Pn − λ [(n − 1) + 1]k+1 Pn−1,
(11)
μ
[
k+1∑
l=0
(
k + 1
l
)
(n + 1)k+1−l(−1)l
]
Pn+1
= (λ + μ)nk+1Pn − λ
[
k+1∑
l=0
(
k + 1
l
)
(n − 1)k+1−l
]
Pn−1.
(12)
Now let n = 1, 2, 3, ...,∞, respectively in equation (12) and
sum up all these equations together, we obtain
μ
k+1∑
l=0
(
k + 1
l
)
(−1)l
[ ∞∑
n=1
(n + 1)k+1−lPn+1
]
= (λ + μ)
∞∑
n=1
nk+1Pn
−λ
k+1∑
l=0
(
k + 1
l
) [ ∞∑
n=1
(n − 1)k+1−lPn−1
]
,
(13)
μ
k+1∑
l=0
(
k + 1
l
)
(−1)l [Mk+1−l − P1] − (−1)k+1μP0
= (λ + μ)Mk+1 − λ
k+1∑
l=0
(
k + 1
l
)
Mk+1−l.
(14)
Noting that in the left side of (13), n starts from 1 to ∞,
which results in the minus terms related to P0 and P1 in (14).
Combining (14) with the first equation in (1), we can obtain
the formula to calculate Mk:
Mk =
k+1∑
l=2
(
k + 1
l
) [
(−1)lμ + λ] Mk+1−l − (−1)k+1 [μ − λ]
(k + 1)(μ − λ)
=
k+1∑
l=2
(
k + 1
l
) [
(−1)l + ρ]Mk+1−l − (−1)k+1 [1 − ρ]
(k + 1)(1 − ρ) .
(15)
Q.E.D.
III. MOMENT RECURSIVE FORMULA IN M/M/1/B
QUEUE
A. Brief review of M/M/1/B queue
The M/M/1/B queue can only accommodate at most
B packets, including the one in service, if any. The ar-
riving packet finding the system containing B packets will
be blocked. When B → ∞, we get the M/M/1 queue
as described in Section II. We can get the corresponding
equilibrium state transition equation as [12]:⎧⎨
⎩
μP1 = λP0
μPn+1 = (λ + μ)Pn − λPn−1 (n = 1, 2, 3..., B − 1)
μPB = λPB−1,
(16)
where P0 is the probability of system being empty, PB is the
packet blocking probability of this finite queue. From Little’s
law, we get
1 − P0 = (1 − PB)λ
μ
. (17)
When ρ < 1, from equation (16) and (17), we can obtain the
following results for the the number of packet [12]:
Packet number distribution
Pn =
(1 − ρ)ρn
1 − ρB+1 (n = 0, 1, 2, ..., B). (18)
Probability of system being empty
P0 =
1 − ρ
1 − ρB+1 . (19)
Packet blocking probability
PB =
(1 − ρ)ρB
1 − ρB+1 . (20)
Average number of packet
N̄ =
ρ
1 − ρ −
(B + 1)ρB+1
1 − ρB+1 . (21)
Moment generating function
P (z) =
1 − ρ
1 − ρB+1
[
1 − (ρz)B+1
1 − ρz
]
. (22)
By taking the derivatives of equation (22), we can obtain the
moments of queue length.
B. Recursive formula in M/M/1/B queue
Theorem 2: In an M/M/1/B queue with arrival rate λ and
mean service time 1/μ, when the offered load ρ = λμ < 1, and
define M∗0 =
∑B
n=0 Pn = 1, then the kth moment M
∗
k (k ≥ 1)
of queue length satisfies
M∗k =
k+1∑
l=2
(
k + l
l
) [
(−1)l + ρ]M∗k+1−l − (−1)k+1 [1 − ρ]
(k + 1)(1 − ρ)
−ρPB
[
(B + 1)k+1 − Bk+1 + (−1)k+1]
(k + 1)(1 − ρ) .
(23)
The correctness of equation (23) can be verified by setting
B → ∞, then PB → 0, equation (23) will approach to (6).
Actually, from Theorem 2, we get
M∗1 =
ρ
1 − ρ −
(B + 1)ρPB
1 − ρ , (24)
M∗2 =
(1 + ρ)M∗1
1 − ρ −
[
(B + 1)3 − B3 − 1] ρPB
3(1 − ρ) , (25)
LIU et al.: RECURSIVE FORMULA FOR THE MOMENTS OF QUEUE LENGTH IN THE M/M/1 QUEUE 3
M∗3 =
6(1 + ρ)M∗2 − 4(1 − ρ)M∗1 + 2ρ
4(1 − ρ)
−
[
(B + 1)4 − B4 + 1] ρPB
4(1 − ρ) .
(26)
Proof:
When k ≥ 1, define M∗k =
∑B
n=0 n
kPn. Multiplying nk+1
on both sides of the second equation of (16), using the same
method as in Theorem 1 yields
μ
k+1∑
l=0
(
k + 1
l
)
(−1)l
[
B−1∑
n=1
(n + 1)k+1−lPn+1
]
= (λ + μ)
B−1∑
n=1
nk+1Pn
−λ
k+1∑
l=0
(
k + 1
l
) [B−1∑
n=1
(n − 1)k+1−lPn−1
]
,
(27)
μ
k+1∑
l=0
(
k + 1
l
)
(−1)l [M∗k+1−l − P1] − (−1)k+1μP0
= (λ + μ)
[
M∗k+1 − Bk+1PB
]−
λ
k+1∑
l=0
(
k + 1
l
) [
M∗k+1−l − (B − 1)k+1−lPB−1 − Bk+1−lPB
]
(28)
Combining (28) with the first and the third equations in (16),
we obtain the formula to calculate M∗k :
M∗k =
k+1∑
l=2
(
k + l
l
) [
(−1)lμ + λ]M∗k+1−l − (−1)k+1 [μ − λ]
(k + 1)(μ − λ)
−λPB
[
(B + 1)k+1 − Bk+1 + (−1)k+1]
(k + 1)(μ − λ)
=
k+1∑
l=2
(
k + l
l
) [
(−1)l + ρ] M∗k+1−l − (−1)k+1 [1 − ρ]
(k + 1)(1 − ρ)
−ρPB
[
(B + 1)k+1 − Bk+1 + (−1)k+1]
(k + 1)(1 − ρ) .
(29)
Q.E.D.
It is known that each derivative operation on a fraction like
the MGF (22) will result in two new terms, if deriving the kth
derivative of (22) to compute the kth moment, the computation
complexity is O(2k); while from equation (29), the complexity
to compute the kth moment is only O(k2).
IV. CONCLUSION
This letter provides the recursive formulas to compute the
moments of queue length in the M/M/1 and M/M/1/B
queues. Our method to derive the recursive formula can
also be applied to more complex queueing systems, say, the
other birth-death queueing systems (e.g. M/M/c) or some
Markovian queues [12] (e.g. M/Er/1 queue), to get the
recursive relationship between the moments of queue length.
REFERENCES
[1] I. Cidon, A. Khamisy, and M. Sidi, “Analysis of packet loss processes in
high-speed networks,” IEEE Trans. Inform. Theory, vol. 39, pp. 98–108,
Jan. 1993.
[2] E. Altman and A. Jean-Marie, “Loss probabilities for messages with re-
dundant packets feeding a finite buffer,” IEEE J. Select. Areas Commun.,
vol. 16, no. 5, pp. 779–787, 1998.
[3] O. Gurewitz, M. Sidi, and I. Cidon “The ballot theorem strikes again:
packet loss process distribution,” IEEE Trans. Inform. Theory, vol. 46,
no. 7, Nov. 2000.
[4] E. Altman, C. Barakat, and V. M. Ramos, “Queueing analysis of simple
FEC schemes for IP telephony,” in Proc. IEEE Infocom 2001, vol. 2, Apr.
2001, pp. 796–804.
[5] J. M. Pitts, X. Wang, Q. Yang, and J. A. Schormans, “Excess-rate queuing
theory for M/M/1/RED with application to VoIP QoS,” Electron. Lett.,
vol. 42, no. 20, Sept. 2006.
[6] A. A. Lazar, “The throughput time delay function of an M/M/1 queue,”
IEEE Trans. Inform. Theory, vol. 29, no. 6, Nov. 1983.
[7] P. E. Cantrell and G. R. Beall, “Transient M/M/1 queue variance
computation using generalized Q functions,” IEEE Trans. Commun., vol.
36, no. 6, June 1988.
[8] J. Abate and W. Whitt, “Calculating time-dependent performance mea-
sures for the M/M/1 queue,” IEEE Trans. Commun., vol. 37, no. 10,
Oct. 1989.
[9] H. Heffes, “Moment formulae for a class of mixed multi-job-type
queueing networks,” Bell Syst. Tech. J., vol. 61, pp. 709–745, May 1982.
[10] I. F. Akyildiz and J. C. Strelen, “Moment analysis for load-dependent
mixed product form queueing networks,” IEEE Trans. Commun., vol. 39,
no. 6, June 1991.
[11] T. Oda, “Moment analysis for traffic associated with markovian queue-
ing systems,” IEEE Trans. Commun., vol. 39, no. 5, May 1991.
[12] J. Medhi, Stochastic Models in Queueing Theory. Academic Press,
second ed., 2003.


Recursive Formula for the Moments of Queue Length in the M/M/1 Queue

1846

Design of Optical Rearrangeable Nonblocking MINs Under Various Crosstalk Constraints

Le, Vinh Trong

1854

Ngo, Son-Hong

1855

1856

A novel dynamic survivable routing in WDM optical networks with / without sparse wavelength conversion

1867

1868

An Ant-based Approach for Dynamic RWA in Optical  WDM Networks

石井, 那由他

1889

白石, 陽

90396797

石塚, 宏紀

1890

戸辺, 義人

1891

空間補間による異種解像度センサデータの統合手法

Tobe, Yoshito

1898

OSOITE: Developing Database Architecture for Urban Sensing and Real-world Search

Future University Hakodate

Not a member yet