All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Description

IEEE COMMUNICATIONS LETTERS, VOL. 13, NO. 12, DECEMBER 2009
1
A State-Dependent Approximation for the Generalized Engset Model
Eric W. M. Wong, Senior Member, IEEE, Andrew Zalesky, and Moshe Zukerman, Fellow, IEEE
Abstract—The well-known Engset model has been widely used and studied. In this paper, we propose a new state dependent approximation for a special case of the generalized Engset model that considers packet/burst dumping. We also correct here several errors in [7] which considered th

Tags

Transcript

IEEE COMMUNICATIONS LETTERS, VOL. 13, NO. 12, DECEMBER 2009 1
A State-Dependent Approximation for the Generalized Engset Model
Eric W. M. Wong,
Senior Member, IEEE
, Andrew Zalesky, and Moshe Zukerman,
Fellow, IEEE
Abstract
—The well-known Engset model has been widely usedand studied. In this paper, we propose a new state dependentapproximation for a special case of the generalized Engset modelthat considers packet/burst dumping. We also correct here severalerrors in [7] which considered the same model. Numerical resultsover a wide range of parameters demonstrate the superiority of the new approximation over previous ones.
Index Terms
—Blocking probability, Engset formula, OBS,bufferless optical networks.
I. I
NTRODUCTION
I
N this paper, we consider one of Cohen’s generalizationsof the Engset model [2], [4] in which the time beforea source generates a new call is dependent on the successof the previous call. The concept of a
call
, which wasrelevant to telephony, was often used in classical work on theEngset model. In the context of modern networking researchit represents packets or bursts. In this paper, we will use calls,packets or bursts, interchangeably. In our modeling, they allrefer to jobs offered to a service system.This generalization is applicable to optical burst (or packet)switching [1], [3], [8], in which a blocked burst is dumped,and until the dumping is completed, a source cannot generate anew burst. The salient feature that distinguishes such a specialcase from the traditional Engset model is that a source mustcompletely transmit (i.e. dump) a blocked burst before a newburst can be generated. In contrast, the Engset model assumesa new burst can be generated immediately after a blockingevent which results in blocking probability overestimation.Therefore, it was proposed in [5], [6], [7] to increase thesource’s off-time to capture the burst dumping effect.In this paper, for a given source, the
mean effective off-time
(MEOT) refers to the mean time period between the endof transmission of a successful burst and the commencementof transmission of the next successful one. This period mayincorporate the dumping of blocked bursts. We consider hereMEOT for each source to be dependent on the number of busy channels, and demonstrate that this leads to an approxi-mation which is consistently more accurate than all previousproposals. In addition, we correct several errors made in [7].
Manuscript received May 22, 2009. The associate editor coordinating thereview of this letter and approving it for publication was M. Ma.E. W. M. Wong and M. Zukerman are with the Department of ElectronicEngineering, City University of Hong Kong, Hong Kong SAR, China (e-mail:ewong@ee.cityu.edu.hk; m.zu@cityu.edu.hk).A. Zalesky is with the University of Melbourne, Victoria 3010, Australia(e-mail: azalesky@unimelb.edu.au).The work described in this paper was supported by a grant from CityUniversity of Hong Kong (Project No. 7002478).Digital Object Identi
ﬁ
er 10.1109/LCOMM.2009.091115
II. T
HE
M
ODEL
We consider the loss model of [7], [8] involving
sourcesthat offer calls/packets/bursts to
channels/servers. Both
and
are assumed to be
ﬁ
nite integers. We assume the case
>
, but we do not consider the case
>>
, whichdegenerates to the Erlang system as
approaches in
ﬁ
nity. Onthe other hand, if
≤
, the call-congestion is equal to zero.Neither the case
>>
, nor the case
≤
, is of interestto us here. We assume that the packet transmission or dumpingtimes are independent and exponentially distributed with mean
1
/
. At any point in time, any of the
sources is eitheractive, idle or dumping. During an active period, a sourcewill transmit a successful packet. A source cannot generate anew packet during either an active or a dumping period. Theend of an active or dumping period is always a beginning of an idle period. The length of an idle period is assumed to beindependent and exponentially distributed with mean
1
/
. Assoon as an idle period ends, the source generates a new packet.The new packet is blocked if all
channels are already busy,which results in a dumping period. Otherwise, the new packetis successful, which results in an active period for that source.III. A S
TATE
-D
EPENDENT
A
PPROXIMATION
The aim here is to
ﬁ
nd the MEOT for each source which isdependent on the number of busy servers such that a single di-mensional Markov chain can be used to accurately predict theblocking probability. Having an accurate approximation basedon a single dimension is important because exact results forthe generalized Engset relies on a 2-dimensional Markov chainthat are not scalable for large
and
. Note that althoughsigni
ﬁ
cant computational improvement can be achieved usingMatrix methods [1], they are still not as scalable as a singledimensional solution.All the approximations considered in [7] were based onlengthening the off-period from
1
/
to
to compensatefor the time that packets or bursts are dumped immediatelyfollowing a blocking event. However, they all do not considerthe fact that during periods of higher carried traf
ﬁ
c load thereare more blocking and thus more dumping, so the MEOTs arelonger. Therefore, we propose here to achieve higher accuracyby considering the MEOT to be state-dependent. To this end,we de
ﬁ
ne
to be the MEOT in state
, namely when thereare
busy servers,
= 0
,
1
,
2
, ...,
.Note that in the traditional Engset model, bursts arrive atrate
(
−
)
/
in state
, where
=
= 1
/
for all
. The traditional model is therefore typically considered tobe state-dependent but the MEOT (for each source) is state-independent. In our new model, we allow the MEOT to bedependent on system state
(i.e.
∕
=
).
1089-7798/09$25.00c
⃝
2009 IEEE
2 IEEE COMMUNICATIONS LETTERS, VOL. 13, NO. 12, DECEMBER 2009
Let
be the probability of having
servers busy,
=0
,
1
,
2
, ...,
. The
and
values satisfy the followingsteady state equations.
+1
=
−
(
+ 1)
,
for
= 0
,
1
,
2
, ...,
−
1
,
(1)where the
values are set to increase linearly with
asfollows
=1
+(
+ 1)
.
(2)The choice of a linear relationship between
and the state
is made for simplicity. The constant
is obtained as follows.
+
=
∑
=0
(
−
)
.
(3)In the real system, an idle period of mean length
1
/
isalways followed by a transmission/dumping period of meanlength
1
/
. The true burst arrival rate per source is therefore
1
/
(
1
/
+ 1
/
)
and is thus independent of the blockingprobability. The left hand-side of (3), which is given bymultiplying this expression by
/
, is the
intended
offeredload in the real system.In (3), we equate the
intended
offered load, namely theoffered load in the real system of the on-off sources (includingthe dumped packets/bursts) to the offered load in the model.Substituting (2) into (1) and (3) and together with thenormalization equation
=0
= 1
, we have
+2
equationsand
+2
unknowns (i.e.
and
where
= 0
,
1
, ...,
)which form a set of
ﬁ
xed point equations and can be solvedby the algorithm provided in the next section.The blocking probability is then derived by
Π
= 1
−
carried loadoﬀered load
where
carried load =
−
1
=0(
−
)
.In the remaining part of this section, we prove that a uniquesolution exists for the set of coupled
ﬁ
xed-point equationsde
ﬁ
ned by (1), (2) and (3) together with the normalizationequation. This solution is our new state-dependent approx-imation for call congestion. As we cannot guarantee thatthe successive substitution algorithm [5] converges to theunique solution, we provide a binary search algorithm tonumerically compute the unique solution for the set of
ﬁ
xed-point equations and we prove its convergence. Finally, in thenext section, we numerically compare the accuracy of our newstate dependent approximation with Syskis approximation andthe approximations in [5] and [7].
A. Existence and Uniqueness of the Fixed Point Solution
By setting
=
in (2) and moving the left-hand side of (3) to the right, we de
ﬁ
ne the function
(
) =
∑
=0
(
−
)
(
)
−
+
,
(4)where we have written
(
)
instead of
to emphasize that
is functionally dependent on
through (2). Our task is toprove
(
) = 0
,
≥
0
, has a unique solution.
Algorithm 1
Calculate solution of
(
) = 0
for an absoluteerror criterion of
1:
−
←
0
,
+
←
Initial lower/upper bounds
2:
while
+
−
−
>
do
3:
←
(
+
+
−
)
/
2
Halve the search interval
4:
if
(
)
>
0
then
5:
−
←
Tighten lower bound
6:
else
7:
+
←
Tighten upper bound
8:
end if
9:
end while
10:
return
←
(
+
+
−
)
/
2
satis
ﬁ
ed, thus return
To establish solution existence, we observe that
(
)
iscontinuous and changes sign at least once for
≥
0
. Thisis because for
= 0
,
= 1
/
and the system degeneratesto the Engset system and hence
(0)
>
0
since in the Engsetsystem the offered load is larger than the
intended
offered loadfor
Π
>
0
. On the other hand, for
=
(
) =
∑
=0
(
−
)
1
+
+1
−
+
,
(5)
<
∑
=0
1
+
1
−
+
= 0
Therefore, a solution exists by the intermediate-value theorem.To establish solution uniqueness, suppose
(
1
) =
(
2
) =0
for
2
>
1
≥
0
.
The mean-value theorem requires theexistence of an
satisfying
(
2
)
−
(
1
) =
′
(
)(
2
−
1
)
or
′
(
) = 0
, where
1
≤
≤
2
. This provides us witha contradiction because simple calculations reveal
′
(
)
<
0
(the proof is provided in the Appendix). Therefore,
1
=
2
.
B. Binary Search Algorithm to Solve
(
) = 0
This is the well known binary search algorithm. The onlyreason we present it here is to correct our errors in the samealgorithm introduced in [7]. Let
∗
be the unique solutionof
(
) = 0
. Due to the monotonicity of
(
)
, at eachiteration of Algorithm 1, if
<
∗
, then
(
)
>
(
∗
) = 0
.Conversely, if
>
∗
, then
(
)
<
(
∗
) = 0
. Consequently,
∗
lies in the interval
[
−
,
+
]
at each iteration of Algorithm1. Furthermore, this interval halves at each iteration, therebyensuring
∗
is sandwiched within an interval whose eventuallength does not exceed
. Thus, Algorithm 1 converges to aunique solution of
(
) = 0
with error
.IV. N
UMERICAL
R
ESULTS
Figs. 1 and 2 show blocking probability versus normalizedtraf
ﬁ
c intensity
= (
/
)(
/
)
for
= 2
and
= 1
and for
= 6
and
= 3
, respectively. These
ﬁ
guresdemonstrate that the new state-dependent (SD) approximationis consistently more accurate than all previous proposals. See[9] for further numerical results that demonstrate advantagesof the MEOT state-dependent approach.
WONG
et al.
: A STATE-DEPENDENT APPROXIMATION FOR THE GENERALIZED ENGSET MODEL 3
00.511.5200.050.10.150.20.250.30.350.40.45N = 2, K = 1Normalized Traffic Intensity,
ρ
B l o c k i n g P r o b a b i l i t y
Syski’s ApproxApprox [5]SD ApproxExact SolutionApprox [7]
Fig. 1. Blocking probability versus normalized traf
ﬁ
c intensity
for
= 2
and
= 1
.
00.511.5200.050.10.150.20.250.30.35N = 6, K = 3Normalized Traffic Intensity,
ρ
B l o c k i n g P r o b a b i l i t y
Syski’s ApproxApprox [5]SD ApproxExact SolutionApprox [7]
Fig. 2. Blocking probability versus normalized traf
ﬁ
c intensity
for
= 6
and
= 3
.
V. C
ORRECTIONS TO
[7]In lines 5 and 7 in Algorithm 1 in the 3rd page of [7],the updated
−
/
+
should be set to
instead of
Γ(
)
.This change ensures the algorithm is a true “Binary SearchAlgorithm” as claimed in [7]. It guarantees convergence ina bounded number of steps. We cannot prove (or disprove)convergence if this change is not made. Also, some of thevalues reported in reported in Table 1 of [7] are in error.Speci
ﬁ
cally, all the rows in Table 1 listed as
= 0
.
9
actuallycorrespond to
= 0
.
8
. And the entire “New” column is inerror due to a programming bug. This resulted in incorrectconclusions reported in [7] about the superiority of the “New”approximation.VI. C
ONCLUSION
We have provided a new MEOT state-dependent approx-imation and corrected several errors in [7] for a versionof the generalized Engset model that considers packet/burstdumping. We have demonstrated numerically that the newapproximation is consistently more accurate than previousproposals.A
PPENDIX
: P
ROOF OF
′
(
)
<
0
Recall
=
(
) =
1
+
+1
.
(
)
can be written as
(
) =
∑
=0
(
−
)
−
+
=(
−
)
+
∑
=1
−
+
=(
−
)
+
∑
=1
∑
=
−
+
.
Proving
(
)
is decreasing in
or
means proving
=
is decreasing in
since
is increasing in
. Since
=
∏
=
where
= 0
,
1
,
2
, ...,
and
≜
(
+1)
−
for
= 0
,
1
,
2
, ...,
−
1
or
≜
1
/
for
=
,we have
∑
=
=
=
∏
=
=0
∏
=
=1
∑
−
1
=0
(
∏
=
)
∑
=
(
∏
=
)+ 1=1
∑
−
1
=0
(
∏
=
)
/
(
∏
=
)
∑
=
(
∏
=
)
/
(
∏
=
)+ 1=1
∑
−
1
=0
(
∏
=
)(
∏
−
1
=
)
∑
=
(
∏
=
)
(∏
−
1
=
1
)
+ 1
where
= 1
,
2
, ...,
and
∏
−
1
=
1
≜
1
. Since
>
0
,
−
1
=0
∏
=
∏
−
1
=
is increasing in
and
=
∏
=
∏
−
1
=
1
is decreasing in
,and hence
=
is decreasing in
. Therefore,
(
)
isdecreasing in
or
.R
EFERENCES[1] N. Akar and Y. Gunalay, “Stochastic analysis of
ﬁ
nite population buffer-less multiplexing in optical packet/burst switching systems,”
IEICE Trans. Commun.
, vol. E90-B, no. 2, pp. 342-345, 2007.[2] J. W. Cohen, “The generalized Engset formulae,”
Philips Telecommun. Rev.
, vol. 18, pp. 158-170, 1957.[3] H. Overby, “Performance modelling of optical packet switched networkswith the Engset traf
ﬁ
c model,”
Optics Express
, vol. 13, pp. 1685-1695,2005.[4] R. Syski,
Introduction to Congestion Theory in Telephone Systems
.North Holland, 1959.[5] H. L. Vu
et al.
, “Scalable performance evaluation of a hybrid opticalswitch,”
J. Lightwave Technol.
, vol. 23, pp. 2961-2973, Oct. 2005.[6] E. W. M. Wong and M. Zukerman, “Bandwidth and buffer tradeoffs inoptical packet switching,”
J. Lightwave Technol.
, vol. 24, no. 12, pp.4790-4798, Dec. 2006.[7] E. W. M. Wong, A. Zalesky, and M. Zukerman, “On generalizations of the Engset model,”
IEEE Commun. Lett.
, vol. 11, no. 4, pp. 360-362,Apr. 2007.[8] M. Zukerman, E. W. M. Wong, Z. Rosberg, G. M. Lee, and H. L. Vu,“On teletraf
ﬁ
c application to OBS,”
IEEE Commun. Lett.
, vol. 8, pp.116-118, Feb. 2004.[9] A. Zalesky, E. W. M. Wong, M. Zukerman, and H. L. Vu, “Engsetformula for bufferless OBS/OCS: when is and when isn’t lengthening theoff-time redundant?”
Proc. IEEE GLOBECOM 2009
, to be published.

Related Search

Previous Document

Next Document

Related Documents

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks