Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
11.10 Interarrival Time Traffic Modeling with Arbitrary Source Distribution 419
Fig. 11.12 pmf distribution
for a source with arbitrary
user-specified interarrival
time statistics
Interarrival Time
n
0
n
1
n
2
n
K–1
p
K–1
...
T
p
2
p
1
p
0
p
(N = n)
v
p
=
p
0
p
1
··· p
K−1
t
(11.117)
v
n
=
n
0
n
1
···n
K−1
t
(11.118)
where the vector v
p
contains the pmf probabilities and the vector v
n
contains the
corresponding interarrival time values. The peak and average data rates (packets/s)
are given by
σ =
1
n
0
T
(11.119)
λ
a
=
1
K−1
i=0
p
i
n
i
(11.120)
To generate traffic that obeys that general distribution, we construct the source
state transition diagram as shown in Fig. 11.13. We take the time step value T in the
Markov chain equal to the time resolution value in Fig. 11.12. Row i of the source
states in Fig. 11.13 corresponds to data arrival with an interarrival time value of t
i
.
The right-most state in each row is the state where data is actually generated.
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
. From pmf definition and the figure,
we can write the probability p
i
as
p
i
= n
i
s
i
(11.121)
Fig. 11.13 The state
transition diagram for a
traffic source that follows a
particular pmf distribution
s
1
s
2
s
3
s
3
s
3
s
3
s
3
s
2
s
2
s
2
s
1
s
0
s
0
s
1
x
0
x
1
x
2
x
3
1
1
1
1
1
1
1
1
1
1
420 11 Modeling Network Traffic
The RHS of the above equation indicates that the probability that the interarrival
time is n
i
given by the probability that the source state is any of the states in row i.
Thus we determine s
i
as
s
i
=
p
i
n
i
(11.122)
At steady state, we can write
s
i
= x
i
K−1
i=0
s
i
(11.123)
And from the above two equations, we determine the state transition probabilities
x
i
as
x
i
=
s
i
K−1
i=0
s
i
(11.124)
11.11 Destination Statistics
Data or traffic arriving at the inputs of a switch or a router need to be routed to
the desired output ports based on the information provided in the packet header and
the routing table of the switch. The distribution of packets among the output ports
is random, and we identify three types of destination statistics as discussed in the
following sections.
11.11.1 Uniform Traffic
For a switch with N inputs and N outputs, uniform traffic implies that an incom-
ing packet chooses a particular output port with probability 1/N. This is true for
any packet arriving at any input port. This model is referred to as the independent
uniform traffic model [16]. Most studies assume uniform traffic to simplify the anal-
ysis. This assumption is true for traffic at routers or switching nodes in the network
since the queuing and gradual release of the packets leads to randomization of the
addressing [17]. These results apply to Ethernet LAN traffic as well as to WAN IP
and ATM traffic.
11.11.2 Broadcast Traffic
If incoming traffic is such that an input port requests to access all output ports, we
get what is called broadcast traffic. This type of traffic occurs when a site is sending
data to many users at the same time or when a computer updates the databases of
many computers.
11.11 Destination Statistics 421
Assume an N × N switch with N input ports and N output ports. We assume
for simplicity that each input port carries two types of traffic flows: uniformly dis-
tributed traffic flow whose rate is λ
u
and broadcast traffic flow whose rate is λ
b
.
The traffic flows at each input and output port are given by
λ
in
= λ
u
+λ
b
(11.125)
λ
out
= λ
u
+ N λ
b
(11.126)
Note that each output port now has to carry more output traffic than what came
in on the average because of the amplification effect of data broadcast.
The total traffic flows at the input and output of the switch are given by
f (in) = N λ
u
+ N λ
b
(11.127)
f (out) = N λ
u
+ N
2
λ
b
(11.128)
The amount of traffic through the network increases due to data broadcast.
11.11.3 Hot-Spot Traffic
If incoming traffic is such that many input ports request one particular output port,
we get what is called hot-spot traffic. This type of traffic occurs when a popular
web site is being browsed by many users at the same time or when many computers
request access to the same server. Reference [18] models hot spot traffic as a fixed
fraction of the arrival rate or arrival probability.
Assume an N × N switch with N input ports and N output ports. We assume
for simplicity that each input port carries two types of traffic flows: uniformly dis-
tributed traffic flow whose rate is λ
u
and hot-spot traffic flow whose rate is λ
h
.
The traffic flow at each output port that is not the destination of the hot-spot
traffic is given by
λ
r
(out) = λ
u
(11.129)
The data rate at the output port that is the destination of the hot-spot traffic is
given by
λ
h
(out) = λ
u
+ Nλ
h
(11.130)
Note that hot-spot traffic effectively increases the traffic at the hot-spot port.
The overall traffic flow at the input of the switch is given by
f (in) = N λ
u
+ N λ
h
(11.131)
422 11 Modeling Network Traffic
The overall traffic flow at the output of the switch is given by
f (out) = N λ
u
+ N λ
h
(11.132)
The amount of traffic through the network does not increase due to hot-spot
traffic.
11.12 Packet Length Statistics
Unlike ATM, many protocols produce packets that have variable lengths. Examples
of protocols that have variable length packets are IP, Frame Relay- and Ethernet.
Knowledge of the packet size is essential if one wants to estimate the buffer space
required to store data having a certain arrival distribution statistics.
Poisson distribution could be used to provide a simple model for packet length
statistics. The probability of receiving a packet of length A is given by
p(A) =
μ
A
A!
e
−μ
(11.133)
where A = 1, 2, ··· units of length, and μ is the average packet length.
An exponential distribution could be used also in the form
f (A) =
1
μ
e
−A/μ
(11.134)
where μ is the average packet length. Alternatively, we could use the binomial dis-
tribution to describe the probability of receiving a packet of length A
p(A) =
N
A
x
A
(1 − x)
N−A
(11.135)
where N is the maximum packet length and x is the probability that one byte is
received. We could find the value of x if the average packet length μ is known:
x =
μ
N
(11.136)
If the packet length is highly irregular, then a Pareto distribution might be used
in the form
f (A) =
ba
b
A
b+1
(11.137)
11.13 Packet Transmission Error Description 423
where a is minimum packet length and b > 1 is a shape parameter. The average
packet length for this distribution is
μ =
ba
b −1
(11.138)
We could also use the MMPP models to describe packet length statistics as was
discussed in Section 11.2.3. In that model, we assume a Markov chain with N states
such that in state s
i
, the source produces a packet with length A
i
. The probability
of making transitions from one state to another is assumed based on experimental
observations or based on model assumptions.
11.13 Packet Transmission Error Description
The previous sections dealt with issues related to network traffic such as data rate
variation, packet length variation, and packet destination. When the packets are in
transit, they are corrupted due to channel impairment or they could be totally lost
due to congestion or address errors. We would like to model channel errors since
these will affect the performance of the overall data transmission.
Figure 11.14 shows a model for adding errors to traffic during transmission. We
have a data source that randomly generate frames as time progresses, such that the
interarrival time between the generated frames follows one of the distributions dis-
cussed earlier.
We could even add another degree of freedom by randomly assigning different
frame lengths. The number of packets per frame follows some distribution like Pois-
son, Bernoulli, or Pareto. The number of packets per frame is indicated in the figure
by the numbers n
1
, n
2
,etc.
An error source also randomly generates errors with time. The number of errors
per frame also follows some distribution like Poisson, Bernoulli, or Pareto. For ex-
ample, a bursty error source could follow the Pareto distribution to generate lengthy
error bursts. The number of packets in error per frame is indicated in the figure by
the numbers e
1
, e
2
, etc. When the number of errors is either 0 or 1, we have a binary
error source. When a Pareto distribution is used to generate the random numbers,
we get bursts of errors with high probability.
Fig. 11.14 Time series
sequence of generated data
and channel errors. A
received frame is in error if it
is generated at the same time
that an error is generated
e
1
e
2
n
2
n
3
n
1
e
3
Errors per frame
Generated frames
Time
424 11 Modeling Network Traffic
Example 11.15 Assume an on–off data source that generates equal length frames
with probability a per time step. Assume for simplicity that each frame contains
only one packet. The channel introduces errors in the transmitted frames such that
the probability of a packet is received in error is e. Perform a Markov chain analysis
of the system and derive its performance parameters.
The Markov chain model we use has four states:
State Significance
1 Source is idle
2 Source is retransmitting a frame that was in error
3 Frame is transmitted with no errors
4 Frame is transmitted with an error
Figure 11.15 shows the Markov chain transition diagram, and the associated tran-
sition matrix for the system is given by
P =
⎡
⎢
⎢
⎣
1 −a 010
0001
a(1 −e)1−e 00
ae e 00
⎤
⎥
⎥
⎦
The system throughput is given by
Th = s
3
The average number of lost packets per time step is given by
Fig. 11.15 State-transition-
rate diagram for transmitting
a frame on a channel that
introduces random errors
S
3
S
4
S
2
S
1
1-a
a (1-e)
1-e
e
a e
1
1
11.13 Packet Transmission Error Description 425
N
a
(lost) = N
a
(in) − N
a
(out)
= a −Th
= a −s
3
The probability that the packet will be transmitted is
p
a
=
Th
a
=
s
3
a
The packet loss probability is
L =
N
a
(lost)
a
= 1 −
s
3
a
The average number of retransmissions is given by
W =
1 − p
a
p
a
=
a
s
3
−1
Example 11.16 Assume in the above example that a = 0.7 and e = 0.1. Calculate
the performance of the system.
Figure 11.16 shows the variation of throughput (Th), delay (W), access proba-
bility (p
a
), and loss probability (L) versus the input traffic (a). Two values of error
probability are used e1 = 0.1 (solid line) and e2 = 0.6 (dotted line). We note that
there is a maximum value on the throughput of Th(max) = 0.5 and that the system
performance deteriorates rapidly when the error probability increases.
Fig. 11.16 Throughput (Th),
delay (W ), access probability
(p
a
), and loss probability (L)
versus the input traffic (a).
Two values of error
probability are used e1 = 0.1
(solid line)ande2 = 0.6
(dotted line)
0
0.2
0.20
0.4
0.4
0.6 0.8 1
0.6
0.8
1
Input traffic
0.20
0.4
0.6 0.8 1
Input traffic
0.20
0.4
0.6 0.8 1
Input traffic
0.20
0.4
0.6 0.8 1
Input traffic
Throughput
0
0.2
0.4
0.6
0.8
1
0
0.2
0.4
0.6
0.8
1
Access probability
Loss probability
0
1
2
3
4
Delay
426 11 Modeling Network Traffic
Problems
Traffic Modeling
11.1 Why do we need to develop models for network traffic?
11.2 What is meant when we say that a source is bursty?
11.3 What is meant by a point process in traffic modeling?
11.4 What is meant by a fluid flow model to describe network traffic?
Exponential Interarrival Time
11.5 Obtain (11.28) on page 394 when the source maximum data rate σ is given
in units of bits/second.
11.6 Obtain (11.33) on page 395 when the source maximum data rate σ and aver-
age data rate λ
a
are given in units of bits/second.
11.7 A Poisson packet source produces packets at the rate of 1500 packets/s. Find
the probability that a packet will be received within a 0.5 ms interval. What
is the average number of packets received within this same time interval?
11.8 A data source has the following parameters: λ
a
= 200 kbps and σ =
300 kbps. Find the pdf that describes the data rate distribution using the re-
sults of Example 11.5 on page 395.
11.9 Obtain the mean and variance for the random variable T for the exponential
interarrival time whose pdf distribution is given in (11.12)
11.10 A radioactive material has a half-life of 1 ms. Find the average time interval
between the emitted particles assuming a Poisson process. Write down an
expression for the probability of detecting 5 radiated particles in a period of
0.5 ms.
11.11 A radioactive material has an average decay time of 10 ms. An observer finds
that the material did not emit a particle after 20 ms, what is the probability
that it will radiate a particle after 1 ms?
11.12 Consider the position parameter a in (11.28) for a Poisson source. What are
the effects of the packet length and maximum burst rate? Is a high data rate
source characterized by a small or a large a value?
11.13 Consider the position parameter a in (11.33) for a Poisson source. What are
the effects of, the packet length, average rate, and maximum burst rate? Is a
bursty source characterized by a small or a large, b value?
11.14 Obtain expressions for the position parameter a and shape parameter b in
Equations (11.28) and (11.33), respectively, for exponential interarrival time
distribution when the source exhibits burst rate such that σ λ
a
.
11.15 Obtain expressions for the position parameter a and shape parameter b in
Equations (11.28) and (11.33), respectively, for exponential interarrival time
distribution when the source is a constant bit rate source (CBR) such that
σ = λ
a
. Comment on your results and sketch the resulting pdf distributions.
Problems 427
11.16 A Poisson source has an interarrival time pdf distribution with the following
two parameter values a = 1 ms and b = 5000 packets/s. Write down an
expression for the probability that the source produces 20 packets in a period
of 1 ms.
11.17 A data source follows the Poisson distribution and has an average data rate of
100 kbps and maximum burst rate of 500 kbps. Estimate the exponential dis-
tribution parameters that best describe that source assuming that the average
packet size is 0.5kB.
Discrete Exponential Interarrival Time
11.18 Because of the snow, the bus arrival times become messed up. Assume that
buses should arrive on the average each 10 min. However, because of the
snow, the probability that a bus arrives at this time on time is 30%. A passen-
ger just missed the bus, what is the probability that he/she will have to wait
for 1 h before the next bus arrives?
11.19 A data source has a exponential interarrival time pdf distribution with the
following two parameter values x = 0.1 and b = 5000. Write down an
expression for the probability that the source produces 20 packets in a period
of 20 time steps.
11.20 A data source follows the binomial distribution and has an average data rate
of 10 kbps and maximum burst rate of 100 kbps. Estimate the discrete ex-
ponential distribution parameters that best describe that source if packets are
being transmitted on an ATM network operating at OC-3 (155.52 Mbps).
11.21 A data source follows the binomial distribution and has an average data
rate of 10 packets/s and maximum burst rate of 100 packets/s. Estimate the
discrete exponential distribution parameters that best describe that source if
packets are being transmitted on an Ethernet network operating at 10 Mbps
where the average packet length is 1024 bytes.
Pareto Interarrival Time
11.22 Prove that the Pareto distribution is not memoryless. This implies that if a
burst is received, it is likely that the burst will continue.
11.23 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 the average packet size is 400 bits.
11.24 Find the average interarrival time for the source in the previous problem.
Packet Transmission Error Description
11.25 Use the results of Example 11.15 on page 424 to study the effect of channel
error on data transmission. Pick some value for a = 0.5, say, and vary the
428 11 Modeling Network Traffic
error probability between 0.001 < e < 0.9. Plot the system throughput and
comment on your results.
11.26 Consider Example 11.15 and suppose that there is an upper limit on the
number of retransmissions before the frame is considered lost. Obtain the
resulting Markov transition diagram and the associated transition matrix.
11.27 Consider Example 11.15 again and suppose that no transmissions are al-
lowed. This could be the case for real-time data or best-effort traffic. Obtain
the resulting Markov transition diagram and the associated transition matrix.
11.28 Consider Example 11.15 again, but this time assume that number of errors
per frame varies between 0 and 5. A forward error correction (FEC) scheme
is used and frame is considered to be error free if it contains up to two packets
in error. Obtain the resulting Markov transition diagram and the associated
transition matrix.
11.29 Assume an adaptive forward error correction (FEC) scheme where three lev-
els of error correction are employed:
FEC level 1: can correct one error in received frame only.
FEC level 2: can correct up to three errors.
FEC level 3: can correct up to five errors.
When the errors in the received frame can be corrected, the next frame is
transmitted using the next lower FEC level. When the errors in the received
frame cannot be corrected, the frame is retransmitted using the next higher
FEC level. Assume each frame to contain no more than five errors in it due
to packet size limitations. Derive the Markov chain transition diagram and
the associated transition matrix.
References
1. D. Denterneer and V. Pronk, “Traffic models for telecommunication”, 13th Symposium on
Computational Statistics, Bristol, Great Britain, pp. 269–274, 1998.
2. W. Leland, M. Taqqu, W. Willinger, and D. Wilson, “On the self-similar nature of Ethernet
traffic”, IEEE/ACM Trans. on Networking, vol. 2, pp. 1–15, 1994.
3. J. Beran, R. Sherman, M.S. Taqqu and W. Willinger, “Variable-bit-rate video traffic and long-
range dependence”, IEEE/ACM Transactions on Networking, vol. 2, pp. 1–15, 1994.
4. V. Paxson and S. Floyd, “Wide-area traffic: The failure of Poisson modeling”, Proceedings
of the conference on communications architectures protocols and applications, ACM Sig-
gcomm’94, pp. 257–268, 1994.
5. S. Molnar and A. Vidas, “On modeling and shaping self-similar ATM traffic, teletraffic con-
tributions for the information age”, Proc. 15th International Teletraffic Congress, Washington
D. C., June 1997, pp. 1409–1420, 1997.
6. Z. Sahinoglu and S. Tekinay, “On multimedia networks: Self-similar traffic and network per-
formance”, IEEE Communications Magazine, Jan. 1999.
7. M. Corvella and A. Bestavros, “Self-similarity in World Wide Web traffic: evidence and pos-
sible causes”, IEEE/ACM Transactions on Networking, vol. 5, pp. 835–846, 1996.
8. J.D. McCabe, Practical Computer Network Analysis and Design, Morgan Kaufmann, San
Francisco, 1998.
9. J.M. Pitts and J.A. Schormans, Introduction to ATM Design and Performance, John Wiley,
New York, 1996.