Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
552 15 Switch Modeling
15.2 Input Queuing Switch
Figure 15.1 shows an input queuing switch where each input port has a queue that
accepts all incoming packets for the input line.
At the beginning of each time step, packets arrive at the inputs and are stored in
the input FIFO queues. The input controller services the packets at the head of each
queue – These packets are usually called head of line (HOL) packets. The controller
sets up a path to the desired output port for each HOL packet. Sometimes the path
cannot be established due to internal or output blocking as discussed in Chapter 14
and the blocked packets remain in their respective queues.
We make the following assumptions to simplify our analysis:
1. Each input queue has one input and one output.
2. The size of the input queue is B.
3. a is the packet arrival probability for any input of the switch.
4. p
a
is the packet departure probability from any input queue where p
a
is the
packet acceptance probability of the switching fabric.
5. Packets could be served in the same time step at which they arrive.
6. Each packet has equal probability 1/N of requesting an output port.
7. Data broadcast or multicast are not implemented.
8. Packets will be lost when a packet arrives at a full input queue whose HOL packet
cannot be routed in that time step.
Under these assumptions, we can model each input queue as an M/M/1/B queue.
The arrival probability for this queue is a and the departure probability c is given by
c = p
a
(15.1)
where p
a
is the packet acceptance probability of the interconnection network used.
Notice that if a path is established for the packet, we are assured the output will
accept it. This was part of our simplifying assumptions.
Figure 15.2 shows one input queue associated with an input port. The arrival
probability a and departure probability p
a
are shown at the queue input and output,
respectively.
Equation (15.1) poses a problem for us. From the results of Chapter 14, we know
that the switching fabric (SF) packet acceptance probability p
a
depends on the traf-
fic arriving at the inputs. In other words, we can determine p
a
only if we knew
Fig. 15.1 The input queuing
switch
SF
Input
Buffers
N
1
N
1
...
...
15.2 Input Queuing Switch 553
Fig. 15.2 The arrival and
departure probabilities for
one queue of an input
queuing switch
a
c = p
a
Input link To switching
fabric
Queue size = B
which input queues are occupied and demand to access the network. The state of
occupancy of the queues depends on the p
a
, and this is the circular argument that is
posing the problem.
Researchers and development engineers chose the easy way out by assuming the
switch fabric to have p
a
= 1 and dealt with each input queue in isolation. However,
this is a very optimistic assumption. We get around this problem by assuming a fixed
value for p
a
that we set depending on the type of SF we plan to use.
According to Equation (7.36) on page 235, we have the following expression for
the probability that the M/M/1/B queue is empty
s
0
=
1 −ρ
1 −ρ
B+1
(15.2)
where B is the size of the input queue and ρ was identified as the distribution index
which is given by
ρ =
ad
bc
=
ad
bp
a
(15.3)
with b = 1 −a and d = 1 − p
a
.
The throughput or output traffic for the input queuing switch is given by
Th = N
a
(out)
= ap
a
s
0
+
B
i=1
p
a
s
i
= ap
a
s
0
+ p
a
(
1 −s
0
)
packets/time step (15.4)
where s
i
is the probability that the queue has i packets. The first term on the RHS
is the probability that a packet arrives while the queue is empty and the second term
on the RHS is the probability that the queue has packets to transmit. Simplifying,
we get
Th = p
a
(
1 −bs
0
)
packets/time step (15.5)
The throughput in units of packets/s is
Th
=
Th
T
packets/s (15.6)
where T is the time step value.
554 15 Switch Modeling
To find the efficiency of the switch, we must estimate the input traffic in units of
packets/time step. The input traffic is given by
N
a
(in) = 1 ×a +0 ×b = a packets/time step (15.7)
The efficiency of the input queuing switch is defined as the ratio between output
traffic and input traffic:
η =
N
a
(out)
N
a
(in)
=
p
a
(
1 −bs
0
)
a
(15.8)
According to our assumptions, packets are lost in an input queuing switch when
a packet arrives on a full queue and no packet can leave the queue. To find the lost
traffic in the switch, we must first find the probability that the queue becomes full.
Using the traffic conservation principle, the average lost traffic N
a
(lost) is given by
N
a
(lost) = N
a
(in) − N
a
(out)
= a − p
a
(
1 −bs
0
)
packets/time step (15.9)
The average lost traffic per second is given by
N
a
(lost) =
N
a
(lost)
T
(15.10)
The packet loss probability L at the input queue is given by
L =
N
a
(lost)
N
a
(in)
= 1 −
p
a
(
1 −bs
0
)
a
(15.11)
The average queue size is given by the equation
Q
a
=
B
i=0
is
i
packets (15.12)
15.2 Input Queuing Switch 555
where s
i
is the probability that there are i packets in the input queue. s
i
is given by
the equation
s
i
=
(1 −ρ)ρ
i
1 −ρ
B+1
;0≤ i ≤ B (15.13)
The wait time, or delay, of the input queuing switch is mainly due to the input
queue. Using Little’s result, the switch delay is given by
Q
a
= W Th (15.14)
or
W =
Q
a
Th
time steps (15.15)
The delay in seconds is given by
W
= WT seconds (15.16)
15.2.1 Congestion in Input Queuing Switch
When the arrival probability starts to increase, congestion takes place due to the
unstable situation described below:
1. The increasing input traffic results in s
0
→ 0.
2. The queues start to demand access to the switching fabric.
3. The increased traffic sensed by the SF leads to decreased acceptance probabil-
ity p
a
.
4. Decreased p
a
will lead to decreased throughput at the switch outputs.
5. The decreased p
a
will lead to more filling of the queues.
6. Ultimately cell loss starts to occur.
15.2.2 Performance Bounds on Input Queuing Switch
Under full load conditions, the buffers of the input queuing switch become full and
we can assume
a → 1 (15.17)
s
0
→ 0 (15.18)
Q
a
→ B (15.19)
556 15 Switch Modeling
The maximum throughput is given, from (15.5), by
Th(max) = p
a
packets/time step (15.20)
The minimum efficiency of the switch is given, from (15.8), by
η(min) = p
a
(15.21)
The maximum lost traffic is given, from (15.9), by
N
a
(lost)
max
= 1 − p
a
packets/time step (15.22)
Packet loss probability is given, from (15.11), by
L(max) = 1 − p
a
(15.23)
The maximum wait time is given, from (15.15), by
W(max) =
B
Th(max)
(15.24)
=
B
p
a
(15.25)
We see the importance of designing a good switching fabric (i.e., high packet
acceptance probability p
a
→ 1) as a prerequisite for designing a high-performance
switch.
Example 15.1 Plot the input queuing switch performance for a 10 ×10 switch that
uses two different input buffer sizes B
1
= 16 and B
2
= 64 and assuming the SF
packet acceptance probability is p
a
= 0.7.
Figure 15.3 shows the switch throughput, efficiency, and loss probability for the
switch with two input buffer sizes. The dotted line is for B = 16 and the solid line
is for B = 64.
We note that the switch throughput saturates and becomes equal to the SF accep-
tance probability p
a
as soon as the input traffic a approaches p
a
= 0.7. This trend
is the same irrespective of the buffer size.
The switch efficiency is 100% as long as a < p
a
. However, when a ≈ p
a
,the
efficiency of both switches decreases at approximately the same rate.
The delay of both switches increases with increased input traffic since the input
buffers start to fill up. As soon as the arrival probability approaches the SF accep-
tance probability (a ≈ p
a
), we see that the delay of both switches saturates very
rapidly toward its maximum value. Of course, the switch with the smaller buffers
has lower delay as shown by the dotted line. Furthermore, the maximum delay of
each switch is governed by the expression
15.2 Input Queuing Switch 557
0 0.5 1
0
0.2
0.4
0.6
0.8
1
Input traffic
Throughput
0 0.5 1
0
0.2
0.4
0.6
0.8
1
Input traffic
Efficiency
0 0.5 1
0
20
40
60
80
100
Input traffic
Delay
0 0.5 1
10
–20
10
–15
10
–10
10
–5
10
0
Input traffic
Loss probability
Fig. 15.3 Performance of an input queuing switch versus the input traffic. Switch throughput,
efficiency, delay, and loss probability are plotted against input traffic. The solid line is for a switch
with input queue size B = 64 and the dotted line is for a switch with input queue size B = 16.
Switching fabric packet acceptance probability p
a
= 0.7
W(max) = B/ p
a
The packet loss probability is very small for both switches as long as the input
traffic is small. However, packet loss probability increases early on with increasing
traffic for the switch with smaller buffer size. As soon as a ≈ p
a
, both switches will
have large packet loss probability equal to its maximum value given by
L(max) = 1 − p
a
Although the previous example was crude and employed several simplifications,
we can make one very important conclusion. The throughput of the input queu-
ing switch is limited by the performance of the switch fabric it is using. The best
throughput we can hope to achieve is given by
Th(max) ≤ p
a
(15.26)
558 15 Switch Modeling
Furthermore, the maximum delay of each switch is governed by the expression
W(max) = B/ p
a
And the packet loss probability is given from the conservation of flow by
L = 1 −Th = 1 − p
a
(15.27)
15.3 Output Queuing Switch
Figure 15.4 shows an output queuing switch. In an output queuing switch, there are
input buffers and output queues.
At the beginning of each time step, packets arrive at the inputs and are stored
in the input buffers. The input controller services the packets by setting up a path
to the desired output port for each incoming packet. Sometimes the path cannot be
established due to internal or output blocking as discussed in Chapter 13. In that
case, the blocked packets remain in their buffers.
We make the following assumptions for our analysis.
1. Each input buffer has one input and one output.
2. The size of the input buffer is B
1
.
3. a is the packet arrival probability for any input of the switch.
4. p
a
is the packet departure probability from any input buffer, where p
a
is the
packet acceptance probability of the switching fabric.
5. Packets could be served in the same time step at which they arrive.
6. Each arriving packet has equal probability 1/N of requesting an output port.
7. Each output queue has m inputs and one output. m depends on the specific
design of the switch fabric.
8. The size of the output queue is B
2
.
9. The packet departure probability from the output queue is 1 assuming the queue
is not empty.
10. Data broadcast or multicast are not implemented.
11. Packets will be lost when a packet arrives at full input buffer or a full output
queue.
Fig. 15.4 The output queuing
switch
SF
Small Input
Buffers
N
1
N
1
...
...
Main Output
Queues
15.3 Output Queuing Switch 559
The last assumption implies that HOL packets travel through the interconnection
network to the output queue even if it is full. This assumption effectively decouples
the analysis of input buffers and output queue models.
Figure 15.5 shows one output queue associated with an input port and one output
queue associated with an output port. The arrival and departure probabilities for
each queue are shown.
15.3.1 Modeling the Input Buffer
Queuing analysis of the buffers at each input port is very similar to the analysis used
for the input queue switch previously discussed. The assumptions imply the input
buffer can be treated as M/M/1/B queue since only one packet can arrive per time
step and only one packet can depart. The arrival probability at an input buffer is
given by
a
1
= a (15.28)
where a is the packet arrival probability at one of the input ports. The departure
probability from an input buffer c
1
is given by
c
1
= p
a
(15.29)
where p
a
is the packet acceptance probability of the interconnection network used.
The probability that the input buffer is empty is given by
e
1
= s
0
=
1 −ρ
1
1 −ρ
B
1
+1
1
(15.30)
Fig. 15.5 The arrival and
departure probabilities for
one input buffer and one
output queue of an output
queuing switch
a
1
= a
c
1
= p
a
c
2
= 1
Input link To switching
fabric
Queue size
= B
1
Queue size = B
2
Input Queue
a
2
= Th
1
/m
From switching
fabric
Output link
Output Queue
...
1
2
m
560 15 Switch Modeling
where e
1
is the probability that the input buffer is empty, B
1
is the size of the input
buffer, and ρ
1
was identified as the distribution index which is given by
ρ
1
=
a
1
d
1
b
1
c
1
(15.31)
with b
1
= 1 −a
1
and d
1
= 1 −c
1
. Substituting the values of a
1
and c
1
, we get
ρ
1
=
ad
bp
a
(15.32)
where b = 1 −a and d = 1 − p
a
.
The throughput or output traffic for the input buffer is given by
Th
1
= N
a,1
(out)
= a
1
c
1
e
1
+
B
1
i=1
cs
i
= ap
a
e
1
+ p
a
(
1 −e
1
)
packets/time step (15.33)
where s
i
is the probability that the buffer has i packets. The first term on the RHS
is the probability that a packet arrives while the buffer is empty and the second term
on the RHS is the probability that the buffer has packets to transmit. Simplifying,
we get
Th
1
= p
a
(
1 −be
1
)
packets/time step (15.34)
The throughput in units of packets/s is
Th
1
=
Th
1
T
packets/s (15.35)
where T is the time step value.
To find the efficiency of the input buffer, we must estimate the input traffic in
units of packets per time step. The input traffic is given by
N
a
(in) = 1 ×a
1
+0 ×b
1
= a packets/time step (15.36)
The efficiency of the input buffer is defined as the ratio between output traffic
and input traffic:
η
1
=
Th
1
N
a
(in)
=
p
a
(
1 −be
1
)
a
(15.37)
where b = 1 −a.
15.3 Output Queuing Switch 561
The average lost traffic in the input buffer is given by
N
a,1
(lost) = N
a
(in) −Th
1
= a − p
a
(
1 −be
1
)
packets/time step (15.38)
The packet loss probability at the input buffer is given by
L
1
= 1 −η
1
= 1 −
p
a
(
1 −be
1
)
a
(15.39)
The average buffer size is given by the equation
Q
1
=
B
1
i=0
is
i
packets (15.40)
where s
i
is the probability that there are i packets in the input buffer. s
i
is given by
the equation
s
i
=
(1 −ρ
1
)ρ
i
1
1 −ρ
B
1
+1
1
;0≤ i ≤ B
1
(15.41)
The distribution index ρ
1
is obtained as usual for a M/M/1/B queue.
Using Little’s result, the input buffer delay is given by
Q
1
= W
1
Th
1
packets (15.42)
or
W
1
=
Q
1
Th
1
time steps (15.43)
The delay in seconds is given by
W
1
= W
1
T seconds (15.44)
15.3.2 Modeling the Output Queue
The assumptions we used for the switch imply that the output queue can be treated
as M
m
/M/1/B queue since a maximum of m packets can arrive per time step and
only one packet can depart. The value of m depends on the switching fabric (SF)
used and the maximum number of packets that could be accepted in one time step
by the output queue. For example, if we had a GCN network, then m = 1. If we had