Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
11.8 Pareto Traffic Distribution 409
3. The autocovariance functions of X and and X
(m)
are equal
E
[
(
X(n + k) −μ
)(
X(n) −μ
)
]
= E
X(n + k)
(m)
−μ
X(n)
(m)
−μ
(11.78)
A self-similar random process exhibits long-range dependence where the auto-
correlation function r
XX
(n) or the autocovariance function c
XX
(n) do not vanish
for large values of n. Distributions that have long-range dependence are sometimes
called heavy-tailed distributions. A random process that displays no long-range de-
pendence will have the autocorrelation, and autocovariance functions vanish for low
values of n. A typical random process that has no long-range dependence is the
Brownian motion.
Typically, self-similar phenomena are described using the Hurst parameter H
whose value lies in the range
0.5 < H < 1 (11.79)
The case H = 0.5 describes random walk problems or Brownian motion which
exhibit no self-similarity. As H → 1, the degree of self-similarity increases as well
as the long-range dependence.
One way to model self-similar traffic is to use pdf distributions for the interarrival
time that exhibit heavy-tailed distribution, as explained in the following section.
11.7 Heavy-Tailed Distributions
A heavy-tailed distribution gives rise to traffic that shows long-range dependence
like in compressed video traffic. A distribution is heavy-tailed if it exhibits the fol-
lowing characteristics
1. Its variance is high or infinite.
2. Its cdf has the property
1 − F(x) = p
(
X > x
)
∼
1
x
α
x →∞ (11.80)
where 0 <α<2 is the shape parameter and X is a random variable.
11.8 Pareto Traffic Distribution
The Pareto distribution that we studied in Section 1.20 on page 19 is used here to
describe realistic traffic sources that have bursty behavior. The Pareto distribution is
described by the pdf
f
(
x
)
=
ba
b
x
b+1
(11.81)
410 11 Modeling Network Traffic
where a is the position parameter, b is the shape parameter, and the random variable
X has values limited in the range a ≤ x < ∞. The Pareto distribution cdf is given
by
F
(
x
)
= 1 −
a
x
b
(11.82)
Notice that the Pareto distribution satisfies condition 2 of heavy-tailed distribu-
tions defined in Section 11.7.
The mean and variance for X are
μ =
ba
b −1
(11.83)
σ
2
=
ba
2
(
b −1
)
2
(
b −2
)
(11.84)
The mean is always positive as long as b > 1. The variance is meaningful only
when b > 2. The variance of the Pareto distribution could be made high by properly
choosing the shape parameter b to be close to 1 as the above equation indicates.
The Hurst parameter corresponding to the Pareto distribution is given by the
equation
H =
3 −b
2
(11.85)
Table 11.1 shows the relation between the source burstiness and the two param-
eters H and Pareto distribution shape parameter b.
From the table, we conclude that in order to describe self-similar traffic using
the Pareto distribution, we must have the shape parameter b close to one—typically
H is chosen within the range 0.7–0.8 which would correspond to b values in the
range 1.4–1.6. By proper choice of b, we can satisfy all the conditions defining
heavy-tailed distributions defined in Section 11.7.
From 11.82, we can write
P(X > x) = 1 − F(x) =
a
x
b
(11.86)
which means that the probability that the random variable has a value greater than x
decreases at a rate that depends on the shape parameter b.Ifb ≈ 1, the distribution
has very large mean and variance [15].
Table 11.1 Relation between
the source burstiness and the
two parameters H and Pareto
distribution shape
parameter b.
Traffic statistics H value b value
Long-range dependent H → 1 b → 1
Short-range dependent H → 0.5 b → 2
11.8 Pareto Traffic Distribution 411
A realistic bursty source is typically described using some or all of these
parameter:
min
the minimum data rate
a
the average data rate
σ the maximum data rate expected from the source
Since we are talking about rates in terms of packets/second, we need to convert
these specifications into proper packet rates. The question becomes, how can we
write down an expression for a Pareto distribution that takes into account all of
these parameters?
We have two options:
1. Flow description: This option allows us to specify the randomness of the instan-
taneous data rate produced by the source.
2. Interarrival time description: This option allows us to specify the randomness of
the periods between adjacent packets produced by the source.
11.8.1 Flow Description
We start by writing the pdf for the instantaneous data rate in the form
f
⌳
() =
0 when <
min
ba
b
/
b+1
when ≥
min
(11.87)
where
min
is the minimum data rate, which could be zero, a is the position
parameter and b is the shape parameter that determines the steepness of the curve.
The values of the two parameters a and b can be found for a source with traffic
descriptors (
min
,
a
, σ ) as follows.
a =
min
(11.88)
b =
λ
a
a
−
min
(11.89)
To produce a bursty source, the value of b could be chosen close to 1, according
to the data in Table 11.1.
11.8.2 Interarrival Time Description
The interarrival time following the Pareto distribution has a pdf that is given by
f
T
(t) =
ba
b
t
b+1
with a ≤ t < ∞ (11.90)
412 11 Modeling Network Traffic
1 2 3 4 5 6 7 8 9 10
10
−5
10
−4
10
−3
10
−2
10
−1
10
0
t
Pareto pdf
Fig. 11.9 The pdf distribution for the case when a = 2andb = 3(solid line)andb = 7
(dashed line)
where a (units s) is the position parameter and b ≥ 1 is the shape parameter.
Figure 11.9 shows the pdf distribution for the case when a = 2 and b = 3 (solid
line), and b = 7 (dashed line). For the smaller value of shape parameter b, the pdf
becomes flatter and has higher values at larger values of t. This results in larger
variance in the interarrival time distribution.
11.8.3 Extracting Pareto Interarrival Time Statistics
A realistic source is typically described using some or all of these parameter:
λ
a
the average data rate
σ the maximum data rate expected from the source
The question we pose here is, how to find a Pareto distribution that best matches
the given source parameters? In a time period t, the maximum number of packets
that could be produced by the source is given by
N
m
= σ t (11.91)
11.8 Pareto Traffic Distribution 413
We use this estimate to calculate the minimum time between two adjacent packets
as follows.
a =
t
N
m
=
1
σ
s (11.92)
The position parameter depends only on the average packet size and burst rate.
In the time period t, the average number of packets that could be produced by
the source is given by
N
a
= λ
a
t (11.93)
The average time between two adjacent packets is given by
T
a
=
t
N
a
=
1
λ
a
s (11.94)
But from the Pareto pdf distribution, the average interarrival time is given by
T
a
=
∞
t=a
t
ba
b
t
b+1
dt =
ba
b −1
s (11.95)
From the above two equations, we are able to obtain a value for the shape
parameter b
1
λ
a
=
ba
b −1
(11.96)
Therefore, we have
b =
σ
σ − λ
a
(11.97)
The shape parameter depends only on the average rate λ
a
and burst rate σ . Fur-
thermore, the shape parameter lies between the following extreme values
b = 1 when σ λ
a
b →∞ when λ
a
→ σ
The first expression applies to a fairly bursty source, and the second expression
applies to a constant-bit-rate source, where the average data rate equals the burst
rate. Thus the range of the shape parameter b can be expressed as
1 ≤ b < ∞ (11.98)
414 11 Modeling Network Traffic
Lower values of b imply bursty sources and higher values of b imply sources
with little variations in the interarrival times since we would have a constant rate
source.
Example 11.12 A bursty source produces data at an average rate of 5 Mbps, and its
maximum burst rate is 20 Mbps. Estimate the Pareto parameters that best describe
that source, assuming that the average packet size is 400 bits.
The position parameter is
a =
A
σ
= 20 s
The average data rate is used to determine the shape parameter b
b =
σ
σ − λ
a
= 1.333
11.8.4 Pareto Distribution and Queuing Analysis
The previous subsection discussed how the Pareto distribution parameters can be
extracted, given the system parameters:
λ
a
the source data rate
σ the maximum data rate expected from the source
A Pareto distribution matching these given source parameters has position and
shape parameters:
a = 1/σ s (11.99)
b = σ/(σ − λ
a
) (11.100)
where we assumed the rates to be given in terms of packets/second.
In this section, we ask the question: Given a Pareto source with known parameters
that feeds into a queue, what is the packet arrival probability? There are two cases
that must be studied separately based on the values of the step size T and the position
parameter a.
Case When T ≤ a
When T ≤ a at most, one packet could arrive in one time step with probability x
that we have to determine.
11.8 Pareto Traffic Distribution 415
The number of time steps over a time period t is estimated as
n =
t
T
(11.101)
The average number of packets in time period t is given by
N
a
= λ
a
t
= λ
a
nT (11.102)
From the binomial distribution, the average number of packets that arrive during
time t is given by
N
a
= xn (11.103)
where x is the packet arrival probability in one time step.
From the above two equations, we get
x = λ
a
T (11.104)
We see in the above equation that as T gets smaller or as the source activity
is reduced (small λ
a
), the arrival probability is decreased, which makes sense. The
arrival probability for a Pareto distribution when T ≤ a is identical to the arrival
probability for the Poisson distribution.
Example 11.13 Estimate the Pareto parameters and the packet arrival probability
for a source with the following parameters. λ
a
= 10
3
packets/s and σ = 1.5 × 10
4
packets/s, Assume that the time step value is T = 0.1ms.
The position parameter is
a = 6.6667 ×10
−4
s
The shape parameter is
b = 1.0714
The arrival probability is
x = 0.1
Case When T > a
When T > a, more than one packet could arrive in one time step, and we have to
find the binomial distribution parameters that describe this situation.
416 11 Modeling Network Traffic
We start our estimation of the arrival probability x by finding the maximum num-
ber of packets that could arrive in one time step
N
m
=σ T (11.105)
The ceiling function was used here after assuming that the receiver will consider
packets that partly arrived during one time step. If the receiver does not wait for
partially arrived packets, then the floor function should be used. The average number
of packets arriving in the time period T is
N
a
=λ
a
T (11.106)
From the binomial distribution, the average number of packets in one time step is
N
a
= xN
m
(11.107)
From the above two equations, the packet arrival probability per time step is
x =
N
a
N
m
≤
λ
a
σ
(11.108)
The probability that k packets arrive at one time step T is given by the binomial
distribution
p(k) =
N
m
k
x
k
(1 − x)
N
m
−k
(11.109)
Example 11.14 A data source follows the Pareto distribution and has an average
data rate λ
a
= 2 ×10
3
packets/s and maximum burst rate of σ = 5 ×10
3
packets/s.
Find the Pareto pdf parameters that describe this source and find the packet arrival
probabilities if the time step chosen is equal to T = 2ms.
The Pareto parameters are
a = 2 ×10
−4
ms < T
The maximum number of packets that could arrive in one time step is
N
m
= 10
11.9 Traffic Data Rate Modeling with Arbitrary Source Distribution 417
The average number of packets that could arrive in one time step is
N
a
= 4
The packet arrival probability per time step is
x = 0.4
11.9 Traffic Data Rate Modeling with Arbitrary Source
Distribution
In this section, we attempt to model a traffic source that follows a general or arbi-
trary user-defined data rate traffic pattern. Assume that the probability mass function
(pmf) of the source data rate is shown in Fig. 11.10. The number of pmf points is
assumed K and the time resolution is T . The traffic model for this source is defined
by two K -component vectors:
v
p
=
p
0
p
1
··· p
K−1
t
(11.110)
v
λ
=
λ
0
λ
1
···λ
K−1
t
(11.111)
where the vector v
p
contains the pmf probabilities and the vector v
λ
contains the
corresponding data rate values. The peak and average data rates (packets/s) are
given by
σ = λ
K−1
(11.112)
λ
a
=
K−1
i=0
p
i
λ
i
(11.113)
Fig. 11.10 pmf distribution
for a source with arbitrary
user-specified data rate
statistics
Data Rate (λ)
...
p
0
p
1
p
2
p
K–1
λ
K–1
λ
2
λ
1
λ
0
p(
Λ
=
λ
)
418 11 Modeling Network Traffic
Fig. 11.11 The state
transition diagram for a
traffic source that follows a
particular pmf distribution
s
3
s
2
s
1
s
0
x
0
x
1
x
2
x
3
To generate traffic that obeys that general distribution, we construct the source
state transition diagram as shown in Fig. 11.11. State s
i
of the source states in
Fig. 11.11 corresponds to data rate λ
i
.
We need to calculate the state transition probabilities x
i
in the figure and see
how they are related to the source probabilities p
i
. We cannot just assume that the
probabilities x
i
are equal to p
i
without some proof. From pmf definition and the
figure, we can write the probability p
i
as
p
i
≡ s
i
(11.114)
The RHS of the above equation indicates that the probability that the source data
rate is λ
i
given by the probability that the source state is in state s
i
. At steady state,
we can write
s
i
= x
i
K−1
i=0
s
i
= x
i
(11.115)
And from the above two equations, we determine the state transition probabilities
x
i
as
x
i
= p
i
(11.116)
Although x
i
was proved to be equal to p
i
, this situation will not hold true for the
interarrival traffic model in Section 11.10.
11.10 Interarrival Time Traffic Modeling with Arbitrary Source
Distribution
In this section, we attempt to model a traffic source that follows a general or arbi-
trary user-defined interarrival time traffic pattern. Assume that the probability mass
function (pmf) of the interarrival time is shown in Fig. 11.12. The number of pmf
points is assumed K and the time resolution is T . The traffic model for this source
is defined by two K-component vectors: