Information Technology Reference
In-Depth Information
namely the survival probability related to a task of priority
x
. The dependence of
ψ
and
on the priority index
x
is due to the fact that the waiting time depends on the priority
level.
The average waiting time of a task with priority
x
is obtained by averaging over the
time
t
weighted with the priority-indexed waiting-time density
ψ(
,
)
x
t
,giving
∞
t
−
1
τ(
x
)
=
(
x
)
t
[
1
−
(
x
)
]
.
(6.29)
t
=
1
In the continuous-time notation the sum is replaced with an integral and we obtain
∞
∞
e
−
(
x
)
t
τ(
x
)
=
tdt
ψ(
x
,
t
)
=
tdt
(
x
)
,
(6.30)
0
0
so that introducing the new integration variable
θ
=
t
(
x
)
allows us to write
∞
0
θ
1
(
1
(
e
−
θ
=
τ(
x
)
=
d
θ
)
.
(6.31)
x
)
x
Therefore the average waiting time of a task of priority
x
is inversely related to the
probability that a task with that priority is carried out. Moreover, from the form of the
probability of a task of priority
x
being chosen (
6.25
) we have the inverse power-law
form for the average waiting time
1
x
γ
.
τ(
x
)
∝
(6.32)
According to (
6.32
) the probability density of waiting a time
τ
,
ψ(τ)
, is related to the
probability
π(
x
)
of selecting a given line of Figure
6.4
by means of the equality of
probabilities
π(
x
)
dx
=
ψ(τ)
d
τ.
(6.33)
Here we select the priority by randomly selecting a line in Figure
6.4
and therefore
choose
π(
x
)
=
1 to obtain
.
dx
d
ψ(τ)
=
(6.34)
τ
Consequently, from (
6.32
)wehave
1
ψ(τ)
∝
/γ
,
(6.35)
1
+
1
τ
so that the properties in the Einstein and Darwin correspondence in Figure
6.3
can be
explained by setting
γ
=
2
.
(6.36)
We note that this inverse power law (
6.32
) with an index of 3/2 was obtained by Barabási
[
8
] with the deterministic protocol
p
γ
=∞
.
Nothing in the above argument determines the roles of the arrival parameter
=
1 and is recovered by setting
λ
and
the servicing parameter
in the post-office lines of Figure
6.4
. Using queuing theory
Abate and Whitt [
1
] proved that the average waiting time is given by
ν