Some light-traffic and heavy-traffic results for the GI/G/n/0 queue using the GM Heuristic
Проаналізовано ймовірность втрати вимоги в багатоканальній системі обслуговування з відмовами GI/G/n/0 як у випадку малого навантаження, так і великого. Аналіз оснований на евристиці GM , для якої випадок помірного навантаження детально вивчено раніше. Знайдено достатні умови для асимптотичної точно...
Saved in:
| Date: | 2010 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Series: | Кибернетика и системный анализ |
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45199 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Some light-traffic and heavy-traffic results for the GI/G/n/0 queue using the GM Heuristic / J.B. Atkinson, I.N. Kovalenko // Кибернетика и системный анализ. — 2010. — № 3. — С. 92-100. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-45199 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-451992025-02-09T23:42:15Z Some light-traffic and heavy-traffic results for the GI/G/n/0 queue using the GM Heuristic Деякі результати для системи обслуговування GI/G/n/0 з використанням евристики GM Atkinson, J.B. Kovalenko, I.N. Системный анализ Проаналізовано ймовірность втрати вимоги в багатоканальній системі обслуговування з відмовами GI/G/n/0 як у випадку малого навантаження, так і великого. Аналіз оснований на евристиці GM , для якої випадок помірного навантаження детально вивчено раніше. Знайдено достатні умови для асимптотичної точності евристики GM у випадку малого навантаження. Ця евристика має вказану властивість також у випадку великого навантаження, якщо число каналів n прямує до нескінченності. In this paper we carry out both light-traffic and heavy-traffic analyses for the calculation of steady-state loss probabilities in the general multi-server queueing loss system, the GI /G/n/0 queue. The analysis makes use of a heuristic approach called the GM Heuristic, for which a detailed analysis in normal traffic has previously been published. Sufficient conditions are given for the GM Heuristic to be asymptotically exact in light traffic. The heuristic is also shown to be asymptotically exact in heavy-traffic when the number of servers n tends to infinity. These results are illustrated numerically using two-phase Coxian distributions for both the inter-arrival time and service time. 2010 Article Some light-traffic and heavy-traffic results for the GI/G/n/0 queue using the GM Heuristic / J.B. Atkinson, I.N. Kovalenko // Кибернетика и системный анализ. — 2010. — № 3. — С. 92-100. — Бібліогр.: 8 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45199 519.872 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Atkinson, J.B. Kovalenko, I.N. Some light-traffic and heavy-traffic results for the GI/G/n/0 queue using the GM Heuristic Кибернетика и системный анализ |
| description |
Проаналізовано ймовірность втрати вимоги в багатоканальній системі обслуговування з відмовами GI/G/n/0 як у випадку малого навантаження, так і великого. Аналіз оснований на евристиці GM , для якої випадок помірного навантаження детально вивчено раніше. Знайдено достатні умови для асимптотичної точності евристики GM у випадку малого навантаження. Ця евристика має вказану властивість також у випадку великого навантаження, якщо число каналів n прямує до нескінченності. |
| format |
Article |
| author |
Atkinson, J.B. Kovalenko, I.N. |
| author_facet |
Atkinson, J.B. Kovalenko, I.N. |
| author_sort |
Atkinson, J.B. |
| title |
Some light-traffic and heavy-traffic results for the GI/G/n/0 queue using the GM Heuristic |
| title_short |
Some light-traffic and heavy-traffic results for the GI/G/n/0 queue using the GM Heuristic |
| title_full |
Some light-traffic and heavy-traffic results for the GI/G/n/0 queue using the GM Heuristic |
| title_fullStr |
Some light-traffic and heavy-traffic results for the GI/G/n/0 queue using the GM Heuristic |
| title_full_unstemmed |
Some light-traffic and heavy-traffic results for the GI/G/n/0 queue using the GM Heuristic |
| title_sort |
some light-traffic and heavy-traffic results for the gi/g/n/0 queue using the gm heuristic |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2010 |
| topic_facet |
Системный анализ |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/45199 |
| citation_txt |
Some light-traffic and heavy-traffic results for the GI/G/n/0 queue using the GM Heuristic / J.B. Atkinson, I.N. Kovalenko // Кибернетика и системный анализ. — 2010. — № 3. — С. 92-100. — Бібліогр.: 8 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT atkinsonjb somelighttrafficandheavytrafficresultsforthegign0queueusingthegmheuristic AT kovalenkoin somelighttrafficandheavytrafficresultsforthegign0queueusingthegmheuristic AT atkinsonjb deâkírezulʹtatidlâsistemiobslugovuvannâgign0zvikoristannâmevristikigm AT kovalenkoin deâkírezulʹtatidlâsistemiobslugovuvannâgign0zvikoristannâmevristikigm |
| first_indexed |
2025-12-01T21:07:14Z |
| last_indexed |
2025-12-01T21:07:14Z |
| _version_ |
1850341572720197632 |
| fulltext |
UDC 519.872
J.B. ATKINSON, I.N. KOVALENKO
SOME LIGHT-TRAFFIC AND HEAVY-TRAFFIC RESULTS
FOR THE GI/G/n/ 0 QUEUE USING THE GM Heuristic
Keywords: asymptotic analysis, heuristic, heavy traffic, light traffic, loss system, queue.
1. INTRODUCTION
In this paper we study a heuristic approach called the GM Heuristic [1] for the
numerical analysis of the general, multi-server queueing loss system, the GI G n/ / / 0
queue. The most important practical property of such systems is the loss probability,
ploss, which is the proportion of customers that are lost, or balk, in the long run. In
many applications, the value of this probability determines the number and cost of
resources needed to provide a given level of service. For a survey of methods
available to calculate exact or approximate values of ploss, see [1].
It was shown in Atkinson that the GM Heuristic gives values of ploss that are
sufficiently accurate for most practical purposes in normal traffic. The approximations also
satisfy certain experimental bounds that have potentially useful applications in practice.
Numerical examples illustrating the use of the GM Heuristic in conjunction with the
experimental bounds and in conjunction with alternative heuristic methods were also given.
In this paper we concentrate on the calculation of loss probabilities in light traffic
and heavy traffic. In Sec. 2 we introduce some background information. Section 3
summarises the steps of the GM Heuristic and Sec. 4 gives some illustrative numerical
results for the loss probability in light traffic. This is followed in Sec. 5 by a proof that,
when the GI G n/ / / 0 queue satisfies a specified set of sufficient conditions, the
GM Heuristic is asymptotically exact in light traffic. Section 6 gives some numerical
results in heavy traffic. This is followed in Sec. 7 by a proof that the GM Heuristic, under
very general conditions, is asymptotically exact in heavy traffic as the number of servers
n tends to infinity. Section 8 gives some brief concluding remarks.
2. BACKGROUND INFORMATION
2.1. Notation. The inter-arrival times are assumed to be positive, independent,
identically distributed random variables with distribution function A t( ) . Let the
Laplace–Stieltjes transform (LST) of A t( ) be �( )s where
�( ) ( )s e dA tst� �
�
�
0
.
Its mean ��1 is
��
�
� �
1
0
tdA t( ) .
We also assume that the service times are non-negative, independent, identically
distributed random variables with the distribution function B t( ) and the mean service
time ��1 is
��
�
� �
1
0
tdB t( ) .
The traffic intensity � is given by � � �� / .
The coefficient of variation of a random variable, c, is defined as the ratio of the
standard deviation to the mean. Let c
A
2 and c
B
2 be the squared coefficients of variation of
the inter-arrival time and service time respectively.
92 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
© J.B. Atkinson, I.N. Kovalenko, 2010
Let q A B n k nk ( / / , ) ( , , , )� � 01 � be the steady-state probability that an arriving
customer finds k customers ahead of itself in the A B n/ / / 0 queue having traffic intensity �.
Let � ( / / , )q A B nk � be the approximation to qk that is obtained when applying the
GM Heuristic to the same problem. Where the context is clear, we also use the terms
ploss and �ploss to represent the probabilities qn and �qn respectively.
Using �ploss as an approximation for ploss, the relative error (RE) is defined as
follows:
RE
p p
p
�
�� loss loss
loss
.
2.2. The Coxian C 2 distribution. The two-phase Coxian C2 distribution can be
defined as a probability density whose Laplace–Stieltjes transform (LST) is rational with
a denominator of degree 2 (see [2]). The C2 density has a squared coefficient of variation
c
X
2 that is at least 0.5. When c
X
2 1� , the C2 density is equivalent to the
hyperexponential ( )H2 density, which is a mixture of two distinct exponential densities,
and when c
X
2 1� , the C2 density is equivalent to the exponential density. The set of C2
densities for which 05 12. � �c
X
includes the two-phase generalised Erlangian density
( )GE2 , which is the density of a sum of two independent exponential random variables.
The unique C2 density for which c
X
2 05� . is the Erlang E2 density.
In general, the C2 density has three independent parameters but, in many applications,
this is reduced to two. In the gamma normalisation, for example, the third moment is set
equal to that of a gamma density with the same mean, E X( ) , and the same squared
coefficient of variation, c
X
2 . The parameters of the density are then expressed in terms of
E X( ) and c
X
2 ; see Appendix B of Tijms [7] for details. The gamma normalisation of the C2
density was used for both the inter-arrival time and service-time distributions in the numerical
work described below. The heuristic calculations for obtaining the � ( / / , )q C C nk 2 2 � values
were carried out according to the steps set out in Sec. 3. The method used for calculating the
corresponding exact values of q C C nk ( / / , )2 2 � are described in [1].
3. THE GM Heuristic
Here we summarise the general steps of the GM Heuristic based on [1] with some slight
changes in notation. In this heuristic we approximate the properties of the GI G n/ / / 0
queue using results from the corresponding GI M n/ / / 0 and GI G/ / /1 0 queues.
Based on our previous definition, q GI M nn ( / / , )� is the steady-state loss
probability for the GI M n/ / / 0 queue, and q GI M1 1( / / , )� is the steady-state loss
probability for the corresponding single-server queue.
Tak�cs [6] gives an algorithm for finding the q GI M nk ( / / , )� probabilities in terms
of � �( ),s , and �.
Step 1 of the GM Heuristic is to re-write Tak�cs’s algorithm so that the
q GI M nk ( / / , )� probabilities for the n-server queue are calculated in terms of the
q GI M1 1( / / , )� probability for the corresponding single-server GI M/ / /1 0 queue.
Following Tak�cs [6, Chapter 4, Theorem 2], with some changes in notation, we
have
q GI M n
r
k
Bk
r k
r k
n
r( / / , ) ( )� � �
��
�
��
�
�
� 1 , (1)
where Br is the rth binomial moment of the {qk } and is given by
B C
n
j C
n
j C
r r
j r
n
j
j
n
j
�
��
�
��
��
�
��
�
�
�
�
1
1
0
,
with C0 1� and
C
i
i
r nr
i
r
�
�
��
�
�� �
�
�
� �
� �
( )
( )
, , , ,
1
12
1
� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 93
For the single-server system, using (1) we can easily show that:
q GI M1 1( / / , ) ( )� � �� .
Now consider a version of the problem in which the random variable X ,
representing the inter-arrival time, is re-scaled to give a new random variable Y such that
Y iX� where i is a positive constant. The traffic intensity would then be equal to � / i,
and Y would have an LST equal to � �( )i . Hence, we have
q GI M i i1 1( / / , / ) ( )� � �� . (2)
The re-writing of Tak�cs’s algorithm involves using (2) to substitute for � �( )i in
(1), thus expressing q GI M nk ( / / , )� as a function of q GI M i1 1( / / , / )� ( , , , )i n� �12 .
Step 2 of the heuristic uses the above re-written version of Tak�cs’s algorithm. We
replace the q GI M i1 1( / / , / )� probabilities by the corresponding q GI G i1 1( / / , / )�
probabilities. The result of using (1) will then be the approximation � ( / / , )q GI G nk � .
We also mention here that the GM Heuristic is extremely fast. The calculations were
programmed in MATLAB on a P.C. with an AMD Athlon™ MP2200+, 1.80 GHz
processor, operating under Windows XP (2002). For example, a typical problem with
100 servers and a given value of � took 0.004 s to solve.
4. NUMERICAL RESULTS FOR THE C C n2 2 0/ / / QUEUE IN LIGHT TRAFFIC
USING THE GM Heuristic
The loss probability ( )ploss for the GI G n/ / / 0 queue in light traffic (i.e., as the traffic
intensity � � 0) has been widely studied because of its practical importance, for example
in the analysis of reliability models and emergency communication networks. Kovalenko
et al. in [5] give an extensive survey of relevant publications and analyse specific cases of
insensitivity in such queues; see also [4] and [1]. The form of insensitivity considered was
the property that the steady-state probabilities, including the loss probability, depend on the
service-time distribution only through its mean value. Such results are useful, for example,
in the approximate calculation of ploss values in light traffic.
In the present work, a number of experiments were carried out to investigate the
light-traffic properties of the GM Heuristic. Figure 1 shows ploss values for systems in
which c c
A B
2 22 4� �, or 20, and the number of servers n � 2 or 8. The relative errors
(R.E.), which decrease sharply as � decreases, suggest that the heuristic is asymptotically
exact in light traffic for these cases. The high level of accuracy of the heuristic is also
apparent from the graphs. It will be seen in the next section that the queueing systems in
Fig. 1 satisfy a set of sufficient conditions for which the GM Heuristic is asymptotically exact
in light traffic. We also detect, in the examples of Fig. 1, the approximate insensitivity of
ploss to the nature of the service-time distribution. This corresponds to Case 1 in [5]. Such
insensitivity results hold, in the C C2 2 0/ / queue, for those cases in which c
A
2 1� .
94 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
Fig. 1. (a): loss probabilities in light traffic when cA
2 4� for the GM Heuristic (dots and circles) compared to
exact values (lines); (b): the corresponding relative errors
ploss R.E. for ploss
�
10 7� 10 6� 10 5� 10 4� 10 3� 10 2�
100
10 10�
10 20�
10 30�
10 40�
10 50�
10 60�
10 7� 10 6� 10 5� 10 4� 10 3� 10 2�
10 1�
10 2�
10 3�
10 4�
10 5�
10 6�
10 7�
10 8�
a b
n cB� �2 42; (circle), cB
2 20� (dot)
n cB� �8 42; (circle),
cB
2 20� (dot)
n cB� �8 202;
n cB� �2 202;
n cB� �8 42;
n cB� �2 42;
This feature can be compared in Fig. 2 with results for systems in which c
A
2 05� .
(the Erlang-2 distribution) where again c
B
2 4� or 20 and n � 2 4, , or 8. For these cases the
relative error is now approximately constant in light traffic for a given queueing system.
In keeping with this result, it will be seen in the next section that such queueing systems
do not satisfy the set of sufficient conditions referred to above.
We also note that the relative errors for the ploss values in Fig. 1 are positive while
those in Fig. 2 are negative. These results agree with established empirical rules, for the
signs of the errors in the C C n2 2 0/ / / queue, which relate to the values of c
A
2 and c
B
2
and were given in [1].
5. SUFFICIENT CONDITIONS FOR THE GM Heuristic
TO BE ASYMPTOTICALLY EXACT IN LIGHT TRAFFIC
In this section, we show that the GM Heuristic is asymptotically exact in light traffic for
any GI G n/ / / 0 queue in which the set of conditions, (i) to (v) below, are satisfied.
One of the special cases of Theorem 1 from [5] can be formulated as follows.
Consider a family of queueing systems A B n/ / /� 0 where A is a fixed inter-arrival d.f.,
B� is a parameter �-dependent service time d.f. and n is a fixed number of channels.
Assume that each system is initially empty. Then let Jj� be the indicator of a loss of
customer j;
q Jn j� �� limE{ } as j � �
if such a limit exists. Assume that the following conditions hold true:
(i) ��
�
� � ��
1
0
xdA x( ) ;
(ii) 1 2 2 2
0
� � � �
�
�c x dA x
A
� ( ) ;
(iii) A x� � �( ) � 0 0 as x� 0 ;
(iv) � � � � � ��
�
�
� � � ��
1
0
0x dB x( ), , ;
(v) 1 12 2 2 2
0
� � � � � ��
�
�c x dB x c
B B
� � ( ) ,
where c
B
2 is a constant.
Then q
n
n
n
�
� �
~
( )
!
0 asymptotically as � � �.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 95
Fig. 2. (a): loss probabilities in light traffic when cA
2 0 5� . for the GM Heuristic (dots) compared to exact val-
ues (lines); (b): the corresponding relative errors
ploss R.E. for ploss
�
10 6� 10 5� 10 4� 10 3� 10 2�
100
10 20�
10 40�
10 60�
10 80�
10 100�
10 120�
10 6� 10 5� 10 4� 10 3� 10 2�
–10 2�
� �10 1
–100
a b
n cB� �4 202;
n cB� �4 42;
n cB� �8 202;
n cB� �8 42;
n cB� �2 42;
n cB� �2 202;
n cB� �8 42;
n cB� �8 202;
n cB� �4 202;
n cB� �4 42;
n cB� �2 202;
n cB� �2 42;
We note, with respect to the numerical examples in the previous section, that
condition (iii) is satisfied by the inter-arrival time distribution for the systems in Fig. 1
and it is not satisfied by the inter-arrival time distribution for the systems in Fig. 2.
To indicate the dependence of q� upon the parameters involved, one can write that
q A B n
n
n
n
� � �
� �
( / / , ) ~
( )
!
0 as � � 0 , (3)
the conditions (i) to (v) being satisfied.
Note that J j� can be treated as J
j
n
�
( ) , meaning that the jth arriving customer sees n
busy channels. Similarly, let J
j
k
�
( ) be the indicator of the event {customer j sees k busy
channels at the instant of its arrival}. Then let q Jk j
k
� �� �lim ( )
P{ }1 as j � � if such a
limit exists.
A proof following the same steps as those for the cited statement above yields the
following more general theorem.
Theorem 1. Under conditions (i) to (v),
q
k
k
k
�
� �
~
( )
!
0 as � � 0 (4)
for any k k n, 0 � � , and any n � 1.
Informally, the main point in the proof of relation (4) is the fact that, due to
condition (iii), the arrival process is nearly poissonian in a small interval of time.
It is worthwhile to note that the loss probability for a GI G/ / /1 0 loss system can be
evaluated directly, avoiding the heavy machinery of the arguments used in [5]. Indeed,
q A B H x dB x H x dB xA A1
0
1 1� � � ��( / / , ) ( ) ( ) ( ) ( )/� �
�
�
�
�
�
�
�
0
�
� , (5)
the H xA ( ) being the renewal function of the arrival process.
From condition (iii), given � � 0, a value � � 0 can be chosen such that
( ) ( ) ( )1 10 0� � � �� � � �x A x x (6)
as 0 � �x �. From a well-known inequality
H x A x H x xA A( ) ( ) ( ), ,� � � �1 0 �
and inequality (6), one obtains the double inequality
1 1 1 10 0� � � � � � �( ) ( ) ( )� � � �x H x xA
for 0 � �x �, where each of the parameters � �, , and �� can be chosen to be arbitrarily
small.
Now we can bound the integral in (5). Indeed,
H x dB x H x dB x x dB xA A( ) ( ) ( ( ) ) ( ) ( ) ( )� � �
�
� �� � � � � � ��1 1 1 1 0
000
�
��
�
� � � � �1 1
1
10
2 2( ) ( ( ))� � �
�
� c
B
. (7)
By condition (iii) and a well-known inequality,
H x x cA A
( ) ,� � �1 2�
one obtains
H x dB x xdB x x c dBA A
0
0
0
21 1 1
� �
� �� � � � � � �( ) ( ) ( ) ( ) ( ) (� � �� � � x) �
�
�
�
� � � � � � � �
��
�
��1 1 1
1
10
2 2
2
2( ) ( ) | | .� � � �
�
� �
c c
B A
(8)
96 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
As � �, , and �� can be chosen to be sufficiently small independently of �, inequalities
(7) and (8) yield the relation
H x dB x oA ( ) ( ) ( )� � � �� � �
�
� 1 0
0
as � � 0
which, due to (5), implies the relation
q A B1 01� � � � �( / / , ) ~ as � � 0.
In particular, one concludes that
� � � � �� �( ) ( / / , ) ~� q A M1 01 as � � 0
where the service time d.f.
M x e xx
�
�( ) ,/� � ��1 0 .
From this,
q A M
i i
1
01/ / , ~�
� � �
�
�
� as � � 0. (9)
Inserting (9) into [6], one gets
� ( / / , ) ~
( )
!
q A B n
k
k
k
� �
� �0 . (10)
Hence, the relation for the relative error of our approximation
� ( / / , )
( / / , )
q A B n
q A B n
k
k
�
�
�
�
� �1 0 as � � 0.
6. NUMERICAL RESULTS FOR THE C C n2 2 0/ / / QUEUE
IN HEAVY TRAFFIC USING THE GM Heuristic
The GI G n/ / / 0 queue in heavy traffic (i.e., as the traffic intensity � � �) has less
direct practical importance than the light-traffic case discussed above. However, methods
for the combination of light-traffic and heavy-traffic results, both numerical and analytic,
have been a fertile area of study for the approximation of various queues in normal
traffic. Examples include the interpolation approaches of Whitt [8] and Kimura [3].
A number of experiments were carried out to investigate the heavy-traffic properties
of the GM Heuristic. Figure 3 shows values of 1� ploss for systems in which c
A
2 2� and
c
B
2 4� or 20, while the number of servers n � 2 or 8. The absolute values of the relative
errors of 1� ploss are seen to decrease sharply as � increases, suggesting that the heuristic
is asymptotically exact in heavy traffic for these cases. Figure 4 shows comparable
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 97
Fig. 3. (a): loss probabilities in heavy traffic when cA
2 2� for the GM Heuristic (dots and circles) compared
to exact values (lines); (b): the corresponding relative errors
1 � ploss R.E. for 1 � ploss
�
101 102 103
100
10 1�
10 2�
10 3�
10 4�
10 12�
10 10�
10 8�
10 6�
10 4�
10 2�
a b
n cB� �2 42; (circle),
cB
2 20� (dot)
n cB� �8 42; (circle),
cB
2 20� (dot)
n cB� �2 42; (circle),
cB
2 20� (dot)
n cB� �8 42; (circle),
cB
2 20� (dot)
101 102 103
results for the otherwise equivalent cases in which the value of c
A
2 is changed from 2
to 0.5. Again, the heuristic appears to be asymptotically exact in heavy traffic. This is in
contrast to the previous results in light traffic, where there was a distinct difference
between the nature of the results obtained for the two cases, c
A
2 2� and c
A
2 05� . .
It will be noted that the relative errors for the values of 1� ploss in Fig. 3 are
negative while those in Fig. 4 are positive. These results agree with established empirical
rules, for the signs of the errors in the C C n2 2 0/ / / queue, which relate to the values of
c
A
2 and c
B
2 and were given in [1].
The high level of accuracy of the heuristic is again apparent from the graphs. It will
be seen in the next section that, for queueing systems such as those illustrated in Fig. 3
and 4, which satisfy certain general conditions, the GM Heuristic is asymptotically exact
in heavy traffic.
7. A HEAVY-TRAFFIC ANALYSIS OF THE GI/G/n/ 0 QUEUE AND THE GM Heuristic
Without loss of generality, let � � 1. Also let �
�
� �
� � �
1
nz, where z is a constant
and z � 1;
� � �
�
�
�
1 1
0
nz
B x B
nz
x( ) ,
where B x0 ( ) is a fixed d.f. with mean 1.
We assume the following analytical conditions:
(i) x dA x2
0
2( )
�
� � � � ;
(ii) A x( ) and B x0 ( ) are non-latticed d.f.
Let q q GI G nn n� ( , , , )� . Also note that, for the GI M n/ / / 0 queue, B x0 ( ) is given
by 1 0� ��e xx, . The purpose of this section is to discover the behavior of qn as n � �.
(Elementary) statement 1. The inequality
q
z
n � �1
1
(11)
holds true.
Proof. If there had not been intervals between service times then the system would
have serviced n T� customers in a large time T; hence q
n
z
n � � � �1 1
1�
�
.
98 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
Fig. 4. (a): loss probabilities in heavy traffic when cA
2 0 5� . for the GM Heuristic (dots and circles) compared
to exact values (lines); (b): the corresponding relative errors
1 � ploss
R.E. for 1 � ploss
�
100
10 1�
10 2�
10 3�
10 4�
10 2�
10 3�
10 4�
10 5�
10 6�
10 7�
10 8�
10 9�
10 10�
10 11�
a b
101 102 103
101 102 103
n cB� �8 42; (circle),
cB
2 20� (dot)
n cB� �2 42; (circle),
cB
2 20� (dot) n cB� �2 42; (circle),
cB
2 20� (dot)
n cB� �8 42; (circle),
cB
2 20� (dot)
Statement 2. The inequality limsup
n
nq
z��
� �1
1
holds true.
Proof. Any allocation of the input to specific groups of channels produces an
increase in qn . Thus, set n m m m m� � � � � �� , where m m m� � � 2 ; this means that the
channels are divided into groups of size m (and one of size m�) and each customer is
directed to an m-group with a probability m n/ or to the m�-group with a probability m n�/ .
Denote by �qm (respectively � �qm ) the loss probability for a group. The groups behave like
independent loss systems.
Then obviously
q q qn m m� � � �max( , ) . (12)
Denote by A xm ( ) the inter-arrival time d.f. for an m-group. We have the following
equation for its LST �m s( ) :
� �
�
m
k
k ks
m
n
m
n
s
m n s
m
n
( ) ( )
( / ) ( )
� �
�
�
� �
� �
��
�
��
1
11
1 1
�
� �( )s
. (13)
Let X m( ) be a generic r.v. with an LST given by (13); let Y be a generic service
time. We will change the scaling and pass to variables
m
n
X m( ) and
m
n
Y . By analysis of
the RHS of (13) or directly by R�nyi’s theorem one obtains that
P
m
n
X x e xm x( ) �
�
�
�
�
�
�
� � ��1 0, as n � �.
Further
P
m
n
Y x B
x
mz
�
�
�
�
�
�
�
�
�
�
�0 .
In the limit, as n � �, we have an M G m/ / / 0 system with a traffic intensity mz.
(The details of a proper continuity theorem are omitted here.) We have
� �
�
�
�
� �
��
�
�
�
q
mz
m
mz
k
m
i
m
m
m k
k
m
i
m
~
( )
!
( )
!
...
/
0
0
1
1
1
1
1
�
�
� / z i
. (14)
If we make m large enough, the RHS of (14) can be made arbitrarily close to 1
1
�
z
.
The same holds true for the m�-group.
Theorem 2. The inequality
q
z
nn � � � �1
1
as
holds true.
Proof. Apply (11) and (12).
Application of Tak�cs’s theory. As set out in Sec. 3, we have
� �( ) exp / ( ) ( ) ~� � �
�
�
0
1
1
{ }x nz dA x
nz
.
Thus � �
� �
( )
~
1� ( )
nz
and similarly � �
� �
( )
~ /
i
i
nz i
1� ( )
. (15)
Hence
C nz i
nz
j
j
i
j j
~ ( ) ~
( )
!
�
�
�
1
;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3 99
q GI M n B
C
j
nz
n n
j
n
n
j
j j
n
n
j
j
( , , , ) ~
!
( )
~� � �
�
� �
� �
1
1
1 1
1
1
0 0
C C
z z
z� �
�
1
1
1
2
...
~ .
Application of the GM Heuristic. The
�
q GI G n( , , , )� values will be computed using
the GM Heuristic, as set out in Sec. 3. In order to compute q GI G1 1( , , , )� , consider the
renewal function of the arrival process
H t A xk
k
( ) ( )*� �
�
�
�1
1
,
where A xk* ( ) is a k-fold convolution of A x( ) with itself. We start with the formula
q GI G1 1 1
1
( , , , )�
� � , (16)
where
�
�
� H x dB x( ) ( )
0
. (17)
Since 2 � �, an inequality | ( ) |H x x c� � holds true with a constant c. Hence
�
� � � �
1
| |nz c, so that, by (16), (17),
q GI G
nz
1 1 1
1
( , , , ) ~� �
and q GI G
i
q GI G
i
nz
i
1
1
1
1 1
( , , , )
( , , , )
~
�
�
�
. (18)
The RHSs of (15) and (18) are the same. We observe that
�
q GI G n
x
q GI G nn n( , , , ) ~ ~ ( , , , )� �1
1
� .
Therefore the GM Heuristic is asymptotically exact in the domain {n nx� � �, ,� x � 1}.
8. CONCLUDING REMARKS
It has been shown that the GM Heuristic is asymptotically exact in light traffic for
the GI G n/ / / 0 queue when the set of conditions (i) to (v) in Sec. 5 are satisfied.
Under more general conditions, the heuristic is also asymptotically exact in heavy
traffic as the number of servers n tends to infinity (for � � �nx x, 1). These results
were illustrated by numerical calculations. Since the GM Heuristic is extremely fast,
it is potentially useful for practical applications involving either light or heavy traffic.
REFERENCES
1. A t k i n s o n J . B . Two new heuristics for the GI G n/ / / 0 queueing loss system with examples based on
the two-phase Coxian distribution // J. Oper Res Soc. — 2009. — 60. — P. 818–830.
2. C o x D . R . A use of complex probabilities in the theory of stochastic processes // Proceedings of the Cam-
bridge Philosophical Society. — 1955. — 51. — P. 313–319.
3. K i m u r a T . Approximations for multi-server queues: System interpolations // Queueing Syst. — 1994. —
17. — P. 347–382.
4. K o v a l e n k o I . N . , A t k i n s o n J . B . Conditions for the light traffic insensitivity to the loss probabi-
lity in a GI G m/ / / 0 queueing system // Cybernetics and Systems Analysis. — 2002. — 38, N 6. —
P. 846–854.
5. K o v a l e n k o I . N . , A t k i n s o n J . B . , M y k h a l e v y c h K . V . Three cases of light-traffic insensi-
tivity of the loss probability in a GI G m/ / / 0 loss system to the shape of the service time distribution //
Queueing Syst. — 2003. — 45. — P. 245–271.
6. T a k � c s L . Introduction to the theory of Queues. Chapter 4. — New York: Oxford University Press,
1962.
7. T i j m s H . C . A first course in stochastic modelling. — Chichester: John Wiley & Sons, 2003.
8. W h i t t W . An interpolation approximation for the mean workload in a GI G/ / 1 queue // Operations Re-
search. — 1989. — 37. — P. 936–952.
Ïîñòóïèëà 06.11.2009
100 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 3
|