> IC2008 <1

Performance Analysis of a Computer Communication Systemwith Time-out Scheme
Kentaro Hoshi1, Sumito Iijima1, Yoshitaka Takahashi2, and Naohisa Komatsu1
1Faculty of Fundamental Science and Engineering, Waseda University, 3-4-1, Ohkubo, Shinjuku, Tokyo 169-8555, Japan
2

Faculty of Commerce, Waseda University, 1-6-1, Nishi-waseda, Shinjuku, Tokyo 169-8050, Japan

Motivated by performance evaluation of a computer communication system, we consider a renewal input, general service time,
single-server, and infinite-capacity queuing system with generally distributed time-out threshold. We obtain two-moment
approximate formulas for the mean system performance measures (including the mean number of customers in the system and themean response time) by using the diffusion process with the reflecting barrier. Our tele-traffic model includes the standard G/G/1
system without time-out scheme as a special case. From performance comparisons between our diffusion approximation andsimulation results, we also provide refining formulas.

Index Terms— The G/G/1 queue, time-out scheme, tele-traffic analysis, performance evaluation, diffusion approximation

I. INTRODUCTIONQ

UEUEING models with time-out schemes are frequently
encountered in computer communication systems. By thetime-out scheme we mean that a customer arriving at a service
system has to leave the system when its waiting time reaches a
pre-assigned time limitation.
This pre-assigned time
limitation will be referred to as time-out threshold and denotedby Γ. The customer will receive the service if it’s waitingtime is less than Γ. The customer will be rejected if its
waiting time reaches Γ.
For instance, in a telephone system we can see a situation
where a call whose waiting time reaches the time-out
threshold Γ will be rejected by a switching node. In a
computer network an incoming packet to a processor buffer
can be also rejected due to a time out scheme. In a recentlydeveloped web service system, a user’s session connection
can also be cut off due to a time-out scheme; see Sery & Beale[17] for HTTP server operation.
We use the following queueing notation originallyintroduced by Kendall: A/B/c-T, where A stands for thearrival process, B the service time distribution, c the numberof servers, and the last (-T) stands for the time-out threshold
distribution. For example, M/M/1-D signifies a Poisson
arrival (exponential inter-arrival time), exponential service
time, single-server system with deterministic time-out
threshold. E2/G/1-M signifies a two-stage Erlang arrival,
general service time, single-server system with exponential
time-out threshold.
There has been much interest in exact approaches for thequeueing models with time-out schemes.
Barrer [3,4]presented the M/M/1-D system, Finch [6] treated the G/M/1-D
system, and Rao [16] analyzed the M/G/1-M system. Stanford[18] formulated the G/G/1-G system. However, these existing
results contain complicated numerical calculations including
integrals, and it is so hard to calculate a performance measure,e.g., the mean number of customers in the system via theseprevious results.
The goal of this paper is to present an approximate formulaon the mean performance measures (including the mean
number of customers in the system and the mean waiting time)
for the G/G/1-G system.
The rest of this paper is organized as follows. Section II
describes our queueing model in details. We introduce ourstochastic assumptions and key notations for the G/G/1-G
system. In Section III we approximate the queue-length
process by a diffusion process with a reflecting barrier (RB) as
in Heyman [8] who treated the standard G//G/1 system
without any time-out scheme. We determine the diffusion
parameters arising out of the diffusion (Fokker-Planck)equation, which is an essential part of this paper. We thenderive a simple approximate formula for the mean system
performance measure. The derived formula thru the diffusion
approximation is seen to be positive even if the offered traffic
is zero (arrival rate λ = 0). Thus we propose a refined
approximate formula which is reduced to zero whenever theoffered traffic is zero. Section VI verifies the accuracy of our
proposed formulas thru the simulation results. In Section V,
we summarize our results and mention future works toconclude our remarks.

> IC2008 <2
III. TELE-TRAFFIC ANALYSIS

II. OUR TELE-TRAFFIC MODEL
Let X be an independent, and identically distributed (iid)random variable (rv). The mean, variance, and squared
coefficient of variation (cv) for rv X are respectively denotedby E(X), σX2, and CX2. We have by definition

C X2 =

σ X2

(2.1)

E( X )2

1) The Probability Density Function
We approximate the queue-length process (the stochastic
process generated by the number of customers in the system attime t) { N(t) | t ≧ 0 } by a diffusion process with RB(Reflecting Barrier) boundary as in Heyman[8]. To be moreexact, if we denote by f(x,t) the probability density function(pdf) of N(t):f ( x, t )dx ≡ Pr {x < N (t ) < x + dx},

G (γ,CΓ2)Time out (γ)

the pdf f(x,t) satisfies the forward Kolmogorov (Fokker-

Single server

Planck) equation:

∂
∂
b ∂2
f = −af+f∂t∂x
2 ∂x 2Services

G (λ,CA2)

G (μ,CB2)

subject to the RB boundary condition:b ∂ ⎤⎡lim ⎢− af +
f =0
x →0
2 ∂x ⎥⎦⎣

Fig. 1 G/G/1-G queuing system with time-out scheme.

We consider a stochastic service system assuming thefollowings; see Figure 1.
i) Customers arrive independently each other at a singleserver system.
ii) The inter-arrival time of the customers is an iid rv, A. The
arrival rate is denoted by λ. We then have

λ=1
E ( A)(2.2)iii) The service time of a customer is an iid rv, B. The service
rate is denoted by μ. We also haveμ=1
E ( B)It should be noted that if we let the time-out threshold be
infinity (Γ = ∞) the time-out scheme model is reduced to thestandard queueing model without any time-out In other words,
the standard model is a very special case of the time-out
scheme.
We define the traffic intensity by

ρ =

λ
μ

reflecting barrier(2.5)

TIME (t)Fig. 2 Modeling via diffusion equation.

Assume the steady state from now on. We denote the steadystate pdf byf ( x) = lim f (x, t )
t →∞

(2.4)

(3.3)

Here, a and b be the infinitesimal mean and variance of theprocess, called as the diffusion parameters in short which will
be determined later.

(2.3)iv) The capacity of the waiting room is infinite.
v) A customer has to leave the system (or to be rejected)
whenever its waiting time reaches a time-out threshold Γ,which is an iid rv. The time-out threshold rate is denotedby γ. Also, we have

1γ=
E (Γ )(3.2)

NUMBER OF CUSTOMERS IN THE SYSTEM N(t)Arrivals

(3.1)

(3.4)

The diffusion equation and RB boundary condition becomesthe following equations:

d
b d2
f+
f
dx
2 dx 2b d ⎤⎡lim⎢− af +
f =0
x →0
2 dx ⎥⎦⎣
0 = −a

(3.5)
(3.6)

> IC2008 <3

Solving the equation (3.5) under the RB condition (3.6) for
f(x), we straightforwardly have:2af (x) = −2a b xeb(3.7)

The process {NΓ(t) , t≧0} is not always renewal, but, inheavy traffic (ρ is close to 1), the server is expected to beoccupied most of the time, so we can regard N Γ (t) as arenewal process. Thus, following the argument above, wehave

The mean number of customers in the steady state, E(N), canbe derived from the pdf f(x) as:∞

E ( N ) = ∫ xf ( x ) dx
0

=−

(3.8)

b
2a

The mean response time, E(R) is now obtained thru Little’s
formula [1,2] which links the mean number of customers inthe system (time-average) and the mean response time(customer-average):

E (R ) =E (N )

λ

= −

b
2aλ

(3.9)

N(t)
NB(t) + NΓ(t)

2
t

0
TIME

ｚFig.3 A sample path of the number of customers in the system.

σ ( NΓ (t ) )E (N Γ (t ) )= γ , lim
= γ 3σ Γ2
t →∞
t →∞
t
t
2

(3.15)

Similarly, we have

It remains to decide the diffusion parameters a and b. For
our G/G/1-G time-out model, we denote by N(t) the number ofcustomers in the system at time t. Similarly, we denote byNA(t), NΓ(t) and NB(t) the cumulative number of arrivals, thecumulative number of reaching time-out thresholds, and thecumulative number of departures during the time period(0, t] = {x ∈ R; c < x ≤ t}

(3.10)

N(t) = N(0) + NA (t) − NΓ (t) − NB (t)(3.11)For any renewal process {M(t), t ≧ 0} with mean m andvariance V of the inter-event time, we have

t
⎞
V⎟
3
m ⎠

(3.12)

where N(α,β2) signifies the normal distribution with mean α,variance β2, and ～ signifies the asymptotically equality in
distribution as time goes to infinity (t Æ ∞ ). See Hoshiet.al.[11] for the proof of (3.11).
Thus, we haveσ (M (t ) ) V
E (M (t ) ) 1
lim= , lim
= 3
t →∞
t →∞
t
m
t
m
2

(3.13)

Since {NA(t), t≧0} is a renewal process, we have from (3.12)σ ( N A (t ) )E ( N A (t ) )lim= λ , lim
= λ3σ A2
t →∞
t →∞
t
t
2

⎞
⎛
V ⇔ σ A2 ⎟⎜Q m ⇔λ⎠⎝σ ( N (t ) )E(N B (t ))lim= μ, lim B = μ 3σ Γ2
t →∞
t →∞
t
t
2

(3.16)The diffusion coefficients (a, b) have the following
relationship as in Newell [15]:σE ( N (t ) ), b = lim ( N ( t ) )a = lim
t →∞
t →∞
t
t
2

We then have

1

NA(t)

7

lim

3) Diffusion Parameters⎛ t
M (t ) ~ N ⎜ ,⎝m

NUMBER OF CUSTOMERS IN THE SYSTEM N(t)2) The Mean Performance Measures(3.14)(3.17)

It follows from (3.11),(3.13)-(3.17) that

E( N A (t )) − E(NΓ (t )) − E(N B (t ))(3.18)t= λ − μ − γ (a < 0)a = limt →∞Similarly, we haveb = limσ (2N ( t ) ) + σ (2N ( t ) ) + σ (2N ( t ) )
Γ

A

B

t

t→∞

= λ 3σ A2 + μ 3σ B2 + γ 3σ Γ2= λ C + μC + γC
2
A

2
B

(3.19)

2
ΓIn the M/M/1-M system, we can derive these diffusion
parameters (a, b) via a direct approach, see Appendix.
4) Approximate Formulae via Diffusion Process

> IC2008 <4

Substituting our obtained diffusion parameters (3.18), (3.19)
into (3.8) yields an approximate formula on the mean numberof customers in the system:

λC A2 + μC B2 + γCΓ22( μ + γ − λ )E ( N Diff ) =γ=0.01. We see the almost same accuracy of ourapproximations as in Figure 4.
M/M/1 Deterministic Time‐out γ(3.20)

10

0.01-Simulation
0.01-Diff Approx.
0.01-Ref Approx.
0.1-Simulation
0.1-Diff Approx.
0.1-Ref Approx.
0.5-Simulation
0.5-Diff Approx
0.5-Ref Approx

9

Similarly, substituting the diffusion parameters (3.18), (3.19)
into (3.9), we have an approximate formula on the mean
response time:

7

6

E(N)

γ
ρC + C + CΓ2
μ
E ( RDiff ) =2(λ + ργ − ρλ)
2
A

8

2
B

5

4

(3.21)

3

25) Refining Formulae

10Whitt[23] noted that refining the diffusion approximations isnecessary, since the diffusion approximations do not result in
the well-known explicit formulae for special cases. However,there are very few explicit formulas for our time-out scheme
models. Therefore, as for our refining, we adopt a trivial
situation where the mean number of customers [ E(N) ] shouldbe zero (the system should be idle) when the offered traffic iszero (ρ = 0). Observing this crucial but trivial point we havethe following refinement equation:

E(NRe f ) = E(NDiff ) −(1− ρ) ⋅ E(NDiff ) ρ=0

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

ρ
Fig. 4 M/M/1-D system performance.

M/M/1 Exponential Time‐out γ=0.01
109(3.22)

8

Simulation
Ref Approx.

7

Diff Approx.

Our refinement E(NPrpo) defined by the right-hand side of(3.20) is zero when the offered traffic is zero (ρ = 0),satisfying the trivial point as mentioned above.
The
refinement E(NPrpo) converges to our diffusion approximation
E(NDiff) as the traffic intensity tends to unity (ρ Æ 1).

E(N)

6

4
3
2

λC 2 + μCB2 + γCΓ2 (1 − ρ) ⋅ (μCB2 + γCΓ2 )(3.23)−E( NRe f ) = A
2(μ + γ − λ)2(μ + γ )C A2 +
E(RRe f ) =

CB2

ρ

γ
λ

1 γ
2( + − 1)

ρ

λ

(

1 1
( − ) ⋅ μCB2 + γCΓ2

+ CΓ2
−

λ

μ

2

λ

)

5

1
0
0.2

0.4

Fig. 5(3.24)

ρ

0.6

0.8

1

M/M/1-M system performance.

E2/E2/1 Erlang‐2 Time‐out γ=0.01(μ + γ )109Ref Approx..
7

Diff Approx

6

E(N)

We compare our approximation (diffusion approximation
and refined approximation) results with the simulated results.
We present the mean number of customers E(N) in the system
as a function of the traffic intensity ρ. Here, we assume thetime is normalized by the mean service time, i.e., μ =1.0.
Figure 4 considers the M/M/1-D system. We assume γ = 0.5,
0.1, 0.01. Our proposed refined approximation is seen to beaccurate very well. The diffusion approximation accuracy is
not bad except for light and moderate traffic.
Figure 5 considers the M/M/1-M system indicating the 95%
confidence interval via Student-t distribution. We assume

Simulation

8

IV. NUMERICAL EXAMPLES

5
4
3
2
1
0
0

0.2

0.4

0.6

ρ
Fig. 6 E2/ E2/1-E2 system performance.

0.8

1

> IC2008 <5

Figure 6 considers the E2/E2/1-E2 system. We also assume
γ=0.01.
We see the almost same accuracy of ourapproximations as in Figures 5 and 6.
It turned out that the proposal approximation is excellent
accuracy by these examples of the numerical value. It isshown that it is enough practicably accuracy at a heavy traffic
about a diffusion approximation formulae.

⎧1⎩0

π (0 , n ; n 0 ) = ⎨APPENDIX

A) An Alternative Derivation of the Diffusion

π (t , n ; n0 ) = 0

π (t , n; n0 ) = Pr{N (t ) = n |, N (0) = n0 }(A.1)

By using the Markov process theory [1,2], we have thefollowing equation:∂
π (t, n; n0 ) = λπ(t, n −1) + (μ + γ )π (t, n +1)∂t− (λ + μ + γ )π (t, n)(A.2)

for any time t > 0 and any nonnegative integer n=1,2,…. The
initial condition is given byifn ≠ n0

(A.3)

n<0

t≥0

(A.4)

For any bivariate function G, we have Taylor’s expansionasG(x + h, y + k)∂
1 ∂∂= G(x, y) + Gh+ Gk +G(x, y)h2∂x
2! ∂x2
∂y
+2

(A.5)

∂2
∂2
G(x, y)hk + 2 G( x, y)k 2∂y∂x∂y

Putting x=t, y=n, h=0 in (A.5), we have∂2∂
Gk + 2 Gk 2
∂x
∂x

(A.6)

1 ∂2
∂
G+
G
2 ∂x 2∂x
1 ∂2∂
G ( t , x + 1) = G ( t , x ) +G+G
2 ∂x 2∂x(A.7)

G (t , x + k ) = G (t , x) +G ( t , x − 1) = G ( t , x ) −Replacing G(t, x) by the transition probability π(t, n; n0) , andcomparing term by term (A.2) subject to (A.3)(λ + μ +γ ) ∂2 π∂∂
π = −(λ − μ −γ ) π +
2
∂t
∂x
∂x2

(A.8)

Note that equation (A.8) corresponds to the diffusion(Fokker-Planck) equation (3.2). Comparing the coefficientsof (A.8) and (3.2), we have the diffusion parameters (a, b) as
the followings:

a = λ − μ −γb = λ + μ +γ

Parameters for the M/M/1-M System
We consider an M/M/1-M system. Recall that customers
arrive according to a Poisson process with rate λ, and theservice-time is exponentially distributed with meanμ-1. The
time-out threshold is also exponentially distributed with meanγ-1.
Let N(t) denote the number of customers in the system attime t, and we introduce the transition probability asn = n0and the boundary condition is given by

V. CONCLUSION
A computer communication system performance leads toour general (G/G/1-G) time-out model. Our queueing model
includes the previously treated queueing models [3,4,6,14,16]
as special cases, and it is identical to the one by Stanford [18].
However, Stanford’s approach does not enable us to obtainthe mean system performance measures (the mean number ofcustomers in the system, and the mean response time).
As our analytical approach we have taken the diffusion
approximation by Heyman [8] who treated the standard G/G/1
model without any time-out scheme. We have continued
Heyman’s effort, and determined the diffusion parameters forour time-out model. Based on the diffusion parameters, wehave derived the mean system performance measures. We
have further refined to propose approximate formulae on themean performance measures for the time-out model.
It is our main contribution to present two-moment very
simple approximate formulae on the mean performancemeasures for the (G/G/1-G) time-out model. It is left as a
future work to seek for more accurate formulae which areconsistent to the exact result for a special (i.e. M/M/1-M)
model. It also remains to apply our results for obtaining the
optimal time-out threshold.

if

(A.9)

REFERENCES[1]

H. Akimaru, and K. Kawashima, Teletraffic, Springer -Verlag, London,
1993[2] A.O. Allen, Probability, Statistics, and Queuing Theory with Computer
Science Applications, Academic Press, Boston, 1990.
[3] D.Y. Barrer, “Queueing with impatient customers and indifferent
clerks,” Oper. Res, vol.5, no.5, pp.644-649, October 1957.
[4] D.Y. Barrer, “Queueing with impatient customers and ordered service,”
Oper. Res, vol.5, no.5, pp.650-656, October 1957.
[5] D.R. Cox, Renewal Theory, Chapman & Hall, London: Methuen, 1962.
[6] P.D. Finch, “Deterministic customer impatience in the queueing system
GI/M/1,” Biometrika, vol.47 pp.45-52, 1960.
[7] E. Gelenbe, and I. Mitrani, Analysis and Synthesis of Computer Systems,
Academic Press, New York, 1980.
[8] D.P. Heyman, “A diffusion model approximation for the GI/G/1 queuein heavy traffic,” Bell Syst. Tech. J, vol.54, pp.1637-1646, 1975.
[9] T. Honma, “Introduction to statistical mathematics,” Morikita, Tokyo,
1984. (in Japanese)[10] K. Hoshi, S. Iijima, Y. Takahashi, and N. Komatsu, “A diffusion process
approximation for the GI/GI/1 queuing system with time-out scheme,”
Tech. Rept., vol.107, no.378, IN2007-103, pp.25-30, 2007. (in Japanese)

> IC2008 <[11] K. Hoshi, Y. Takahashi, and N. Komatsu, “A stochastic approach forderiving the parameters arising out of a diffusion model,” Tech. Rept,
vol.108, no.17, CQ2008-11, pp.59-64, 2008.(in Japanese)[12] S. Kasahara, “Internet traffic modeling : towards queueing theory for theinternet design,” Tech. Rept, Vol.101, No.647, pp.25-30, 2002. (inJapanese)[13] G. Kimura, and Y. Takahashi, “Traffic analysis for a token ring systemwith exhaustive or gated service -renewal batch inputs model-,” IEICE
Trans., vol.J71-B, pp.129-137, 1988.
[14] I.N. Kovalenko, “Some queuing problems with restrictions,” Theory ofProb. and its Appl. vol.6, no.2, pp.204-208, 1965.
[15] G.F. Newell, Application of Queuing Theory, Chapman and Hall,
London 1971.
[16] S.S. Rao, “Queueing with balking and reneging in M/G/1 systems,”
Metrika, vol.12, no.1, pp.174-188, 1968.
[17] P.G. Sery, and J. Beale, Red Hat Linux Internet Server, Willy, Indiana,
2003.
[18] R.E. Stanford, “Reneging phenomena in single server queues,” Math.
Oper. Res, vol.4, pp.162-178, 1979.
[19] A. Takahashi, Y. Takahashi, S. Kaneda, and N. Shinagawa, “Diffusion
approximations for the GI/G/c/K queue,” Proc. 16th ICCCN 2007,
pp.681-686, 2007.
[20] Y. Takahashi, “Diffusion approximation for the single server systemwith batch arrivals of multi-class calls,” IEICE Trans., vol.J 69-A,
pp.317-324, 1986.
[21] T. Takine, M. Murata, “Queue in communication network,” Oper. Res,
vol. 43, no. 5, pp.264– 271, 1998. (in Japanese)[22] W. Whitt, Heavy Traffic Limit Theory, Chapman and Hall, London, 1971.
[23] W. Whitt, “Refining diffusion approximations for queues” Oper. Res.
Letters, vol.1, no.5, pp. 165-169, 1982.

6