Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
572 15 Switch Modeling
traffic at the tagged output linked list, we must first find the traffic at its input. It is
a lot more simpler to estimate the lost traffic using the traffic conservation principle
N
a
(lost) = N
a
(in) −Th
= a − (1 −s
0
r
0
) packets/time step (15.95)
The packet loss probability is given by
L = 1 −η = 1 −
1 −s
0
r
0
a
(15.96)
The average queue size is given by the equation
Q
a
=
B
i=0
is
i
packets (15.97)
where s
i
is the probability that there are i packets in the queue.
We can invoke Little’s result to estimate the average wait time (number of time
steps) a packet spends in the input buffer before it is routed as
Q
a
= W × Th (15.98)
where W is the average number of time steps that a packet spends in the queue.
W =
Q
a
Th
time steps (15.99)
15.4.1 Performance Bounds on Shared Buffer Switch
Under full load conditions, the buffer of the shared buffer switch becomes full and
we can assume
a → 1 (15.100)
s
0
→ (15.101)
Q
a
→ B (15.102)
where 1 . The maximum throughput is found from (15.92) when s
0
= and
a = 1:
Th(max) = 1 −
1 −
1
N
N
≈ 1 − e
−1
packets/time step (15.103)
15.4 Shared Buffer Switch 573
The minimum efficiency of the switch is given from (15.94) by
η(min) = 1 −
1 −
1
N
N
≈ 1 − e
−1
(15.104)
The switch efficiency is very close to 100% even at full load. Maximum packet
loss probability in (15.96) will be given by
L(max) =
1 −
1
N
N
= e
−1
(15.105)
The maximum lost traffic is
N
a
(lost)
max
= L × N
a
(in)
max
=
1 −
1
N
N
= e
−1
packets/time step (15.106)
where we assumed at maximum load N
a
(in)
max
= 1. The maximum wait time is
given by the approximate formula
W(max) =
B
Th(max)
=
B
1 −
1 −
1
N
N
=
B
1 − e
−1
(15.107)
Example 15.3 Find the performance of a 10 × 10 shared buffer switch for the two
cases when the size of the linked list per output port is limited to Q = 16 and
B = 4.
Figure 15.9 shows the switch throughput, efficiency, and loss probability for the
switch with two buffer sizes. The solid line is for a switch with B = 16 and the
dotted line is for a switch with B = 4.
We note that the switch throughput shows little signs of saturation. However, the
smaller buffer size results in slightly reduced throughput at high input traffic.
The switch efficiency is 100% for most of the operating range. However, when
a ≈ 1, the efficiency of the switch with the smaller buffer decreases slightly.
574 15 Switch Modeling
0 0.2 0.4 0.6 0.8 1
0
0.2
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
Input traffic
0 0.2 0.4 0.6 0.8 1
Input traffic
0 0.2 0.4 0.6 0.8 1
Input traffic
Efficiency
0
2
4
6
8
Delay
10
−15
10
−10
10
−5
10
0
Loss probability
Fig. 15.9 Performance of a shared buffer switch versus the input traffic. Switch throughput, effi-
ciency, delay, and loss probability are plotted against input traffic. The solid line is for a switch
with B = 16 and the dotted line is for a switch with B = 4
The delay of both switches increases with increased input traffic since the buffers
start to fill up. The switch with the larger buffer shows increased delay compared to
the switch with the smaller buffer.
The packet loss probability increases with input traffic. However, the switch with
the smaller buffer shows higher packet loss probability even for very small input
traffic.
15.5 Comparing the Three Switches
In this section, we attempt to compare the performance of the three types of switches
discussed earlier. For a full comparison, the switch parameters should be changed
over their practical ranges. However, our aim here is simplicity.
We assume that the input queuing switch has an input buffer of size B = 16 and
the packet acceptance probability of the switching fabric is p
a
= 0.7.
We assume that the output queuing switch has an input buffer of size B
1
= 4 and
an output queue of size B
2
= 16. The packet acceptance probability of the switching
15.5 Comparing the Three Switches 575
fabric is p
a
= 0.7. The switch fabric is such that only three packets can be accepted
by the output buffer at any time step (i.e., m = 3).
We assume that the shared buffer switch such that each output port has a queue
of size B = 16 and the switch is of size N = 10.
Under these conditions, the simplified models for the three switches produce the
performance curves shown in Fig. 15.10.
The throughput of all switch types are identical until the input traffic approaches
a ≈ p
a
. After that, the shared buffer switch shows increasing throughput but the
input and output queuing switches show signs of throughput saturation.
The efficiency of all switch types are identical and equal to unity until the in-
put traffic approaches a ≈ p
a
. After that, the shared buffer switch still has unity
efficiency but the input and output queuing switches show signs of decreasing effi-
ciency.
The shared buffer switch shows the least delay among the three switch types for
most of the input traffic range. On the other hand, the input and output queuing
switches show almost identical delays until a ≈ p
a
. After that, the input buffer
switch shows larger delay.
10
−4
10
−2
10
0
10
2
Delay
0 0.2 0.4 0.6 0.8 1
0
0.2
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
Input traffic
Efficiency
0 0.2 0.4 0.6 0.8 1
Input traffic
0 0.2 0.4 0.6 0.8 1
Input traffic
10
−20
10
−15
10
−10
10
−5
10
0
Loss probability
Fig. 15.10 Performance of an input buffered switch (solid lines), output buffer switch (dashed
lines), and shared buffer switch (dotted lines) versus the input traffic. Switch throughput, efficiency,
delay, and loss probability are plotted against input traffic
576 15 Switch Modeling
The packet loss probability is lowest for the shared buffer switch under the
assumed parameters. The output and input queuing switches showed the highest
packet loss probability.
15.6 Modeling Other Switch Types
It is possible to use the techniques developed in the previous sections to model
other switch types such as multiple input queuing, multiple output queuing, and
multiple input and output queuing. We leave this to the problems at the end of this
chapter.
Problems
Input Queuing Switch
15.1 Explain the HOL problem in input queuing switches.
15.2 In Chapter 13, it was mentioned that there are three sources of packet loss in
an input queuing switch. Explain why our model for that switch here assumed
only one source of packet loss.
15.3 Assume an input queuing switch with an “ideal” switching fabric (SF). De-
fine what you think an ideal SF should be and explain why there is still packet
blocking, HOL, and packet loss in the switch.
15.4 An input queuing switch suffers from HOL problem. It has been proposed to
monitor the top L packets at the head of the queue and route the first one that
was accepted by the network. Analyze this situation.
15.5 An input queuing switch has the following parameters: N = 8, a = 0.2,
p
a
= 0.5, and B = 16. Find the switch performance.
15.6 An input queuing switch has the following parameters: N = 4, a = 0.5,
p
a
= 0.5, and B = 16. Find the switch performance.
15.7 An input queuing switch has the following parameters: N = 4, a = 0.8,
p
a
= 0.5, and B = 64. Find the switch performance.
15.8 Write down the transition matrix for an input queuing switch with an ideal
SF where p
a
= 1 and the output can only accept one packet from any of its
inputs at a given time step.
15.9 Assume an input queuing switch with an ideal switch fabric and output ports
that can accept any number of packets destined to them from any input port.
Do you think we still need large input buffers? Under what circumstances
can we replace the input buffer with one that holds at most only one packet
so that the input port can process it.
Problems 577
Output Queuing Switch
15.10 In the output queuing switch we assumed that the output queue can accept
a maximum of L packets per time step. Based on that, do you think output
queuing has HOL problems just like input queuing switches? Explain your
answer.
15.11 In Chapter 13, it was mentioned that there are four sources of packet loss
in an output queuing switch. Explain why our model for that switch here
assumed only two sources of packet loss.
15.12 Equation (15.61) on page 565 for packet loss probability in the output queue
assumed that the maximum number of arriving packets is smaller than the
size of the buffer (m < B
2
). Write down the equation when m > B
2
.
15.13 Write down the transition matrix for an output queuing switch with an ideal
SF where p
a
= 1 and the output can only accept one packet from any of its
inputs at a given time step.
15.14 An output queuing switch has the following parameters: N = 8, a = 0.2,
p
a
= 0.5, B
1
= 4, and B
2
= 16. Find the switch performance.
15.15 An output queuing switch has the following parameters: N = 4, a = 0.5,
p
a
= 0.5, B
1
= 4, and B
2
= 16. Find the switch performance.
15.16 An output queuing switch has the following parameters: N = 4, a = 0.8,
p
a
= 0.5, B
1
= 16, and B
2
= 64. Find the switch performance.
15.17 In the output queue switch analysis, we effectively decoupled the input buffer
from the output queue by insisting that packets at the output buffer can move
to an output queue even if it were full. Can you remove this assumption and
analyze the switch?
Shared Buffer Switch
15.18 In Chapter 13, it was mentioned that there are two sources of packet loss in
a shared buffer switch. Explain why our model for that switch here assumed
only one source of packet loss.
15.19 Equation (15.96) on page 572 for packet loss probability in the linked list
assumed that the maximum number of arriving packets is smaller than the
size of the buffer (N < B). Write down the equation when N > B.
15.20 In the shared buffer switch, we assumed that the linked list for each output
can accept a maximum of N packets per time step. Based on that, do you
think shared buffering has HOL problems just like input queuing switches?
Explain your answer.
15.21 In a shared buffer switch, the linked list for each output can accept a max-
imum of one packet only per time step. Based on that, do you think shared
buffering has HOL problems just like input queuing switches? Explain your
answer.
578 15 Switch Modeling
15.22 Assume that the linked list for each output of a shared buffer switch can ac-
cept a maximum of m packets only per time step (1 ≤ m ≤ N). Write down
an expression for the transition matrix and derive the performance equations.
Other Switch Structures
15.23 Develop a Markov chain analysis of the multiple input queuing switch.
15.24 Develop a Markov chain analysis of the multiple output queuing switch.
15.25 Develop a Markov chain analysis of the multiple input and output queuing
switch.
References
1. H.J. Siegel, R.J. McMillen and P.T. Mueller, “A survey of Interconnection methods for recon-
figurable parallel processing systems”, Proc. AFIPS 1979, vol. 48, pp. 529–542, 1979.
2. F.A. Tobagi, “Fast packet switch architectures for broadband integrated services digital net-
works”, Proc. IEEE, vol. 78, pp. 133–166, 1990.
3. S.E. Butner and R. Chivukula, “On the limits of electronic ATM switching”, IEEE Networks,
vol. 10, no. 6, pp. 26–31, Nov./Dec. 1996.
4. A. Sabaa, F. Elguibaly and D. Shpak, “Design and modeling of a nonblocking input-buffer
AT M s wi tc h” , Canadian Journal of Electrical and Computer Engineering, vol. 22, pp. 87–93,
1997.
5. D. Present, C. Fayet, and G. Pujolle, “An optimal solution for ATM switches”, Computer
Networks and ISDN Systems, vol. 29, pp. 2039–2052, 1998.
6. R.Y. Awdeh and H.T. Muftah, “Survey of ATM switch architectures”, Computer Networks and
ISDN Systems, vol. 27, pp. 1567–1613, 1995.
7. J. Garcia-Haro and A. Jajszczyk, “ATM shared-memory switching architectures”, IEEE Net-
works, vol. 8, no. 4, pp. 18–26, Jul./Aug. 1994.
8. M. Murata, “Requirements on ATM switch architectures for quality-of-service guarantees”,
IEICE Transactions on Communications., vol. E81-B, pp. 138–151, 1998.
9. A. Patavinal, “Nonblocking architecture for ATM switching”, IEEE Communications Maga-
zine, pp. 38–48, Feb. 1993.
10. B. Patel, F. Schaffa, and M. Willebeek-LeMair, “The helix switch: A single chip cell switch
design”, Computer Networks and ISDN Systems, vol. 28, pp. 1791–1807, 1996.
11. “Design and evaluation of scalable shared-memory ATM switches”, IEICE Transactions on
Communications., vol. E81-B, pp. 224–236, 1998.
12. N. Endo, T. Kozaki, T. Ohuchi, H. Kuwahara, and S. Gohara, “Shared buffer memory switch
for an ATM exchange”, IEEE Trans. Commun., vol. 41, pp. 237–245, 1993.
13. J.-F. Lin and S.-D. Wang, “A high performance fault-tolerant switching network for ATM”,
IEICE Transactions on Communications., vol. E781-B, pp. 1518–1528, 1995.
14. S.-C. Yang and J.A. Silvester, “A reconfigurable ATM switch fabric for fault tolerance and
traffic balancing”, IEEE Journal on Selected Areas in Communications, vol. 9, pp. 1205–1217,
1991.
Chapter 16
Examples of Switches
16.1 Introduction
The different switch architectures discussed in Chapter 13 attempts to provide
simultaneous paths between any input to any output. The switch performance varied
depending on the location of the buffers/queues and depended on the type of switch-
ing fabric employed. As a result, different switches produced different throughput,
delay, and packet loss probability. In addition to high performance, a switch must be
able to provide extra features such as multiple service classes (differentiated service)
and multicast and broadcast capabilities.
Traffic through the switch encounters multiple contention points before a path to
the desired output could be found. The main contention points in a switch occur at
these locations:
1. At the input ports
2. Within the switching fabric
3. At the output port
Contentions lead to delay, packet loss, congestion, and reduced throughput. Like
a chain, the performance of the switch is as good as the performance of the worst-
managed contention point [1]. Multiple contention points may also introduce head
of line (HOL) blocking, a state in which a packet at the head of a queue loses
contention and so blocks packets behind it from traversing the switch fabric. In
an attempt to avoid HOL blocking, some architectures use feedback flow control.
This strategy references the available capacity of output buffers to control the flow
rate from input buffers. Multiple contention points may add complex overhead and
queue-management tasks, introducing the potential for performance degradation.
To counteract the effect of performance loss due to multiple contention points,
the switch designer must consider these approaches:
1. Increase buffer and queue sizes and place the queues at the output only.
2. Create multiple queues for each connection (per VC in ATM jargon) or service
class.
3. Employ selective packet discard based on the connection or service class.
F. Gebali, Analysis of Computer and Communication Networks,
DOI: 10.1007/978-0-387-74437-7
16,
C
Springer Science+Business Media, LLC 2008
579
580 16 Examples of Switches
4. Use a switching fabric that does not offer as much internal contention. Typically,
this is achieved through switching fabrics with multiple paths, dilating each link,
and speedup of the switch fabric operation.
5. Employ sophisticated routing algorithms through the switch fabric if possible.
6. Employ large buffers or queues at each contention point. This might not be prac-
tical if buffers are used within the switch fabric.
7. Use traffic shaping or flow control to reduce congestion by limiting the number
of packets coming from a certain input.
In an effort to support multiple service classes and certain quality of service
guarantees, a design might provide several queues at each input port. Each queue is
dedicated to a virtual circuit (VC) or flow. The total number of queues Q required
in the switch is given by
Q = NV (16.1)
where N is the number of ports and V is the number of virtual circuits, or flows,
supported per port. It is possible to have Q = 64 ×4000 or more.
Good switch architectures eliminate unnecessary points of contention by com-
bining a contentionless switch fabric with buffering on output which confines con-
tention to the output ports. And good switch performance is ensured only if the
output queues are managed with sophisticated traffic scheduling algorithms.
Next-generation switches are characterized by their lack of traditional switch
fabric and use of output queuing. These two features lead to single contention point
during accessing output ports. This chapter presents two next-generation designs:
the VRQ switch and N.E.T.’s Promina 4000
ATM switch.
16.2 Promina 4000 Switch
A block diagram of the Promina 4000 switch is shown in Fig. 16.1 [1, 2]. The switch
is an output queue switch since the queues are located at the output ports. This is
one of the main requirements of a high-performance switch. The switch fabric is
contention-free (contentionless) and is based on a broadcast matrix of dedicated
backplane buses.
The switch is composed of N input/output port cards and N backplane buses.
The input block in each module is a four-to-one multiplexer such that the output of
the multiplexer is connected to a dedicated backplane bus. The output block in each
module has N inputs and four outputs, as indicated. Each backplane bus is dedicated
to carry the traffic of one input port and is connected to one of the N inputs of each
output port.
16.2 Promina 4000 Switch 581
Fig. 16.1 Block diagram for
N.E.T.’s Promina 4000 ATM
switch
Input Mux
Module 0
0 N–1
Module N–1
Output
Queues
Time-Multiplexed
Backplane Buses
...
...
...
...
...
16.2.1 Input Port Operation
The input port accepts data from four 155 Mbps lines. A TDMA multiplexer places
those packets on the bus dedicated to the input port. The input data are broadcast to
all the outputs and each output selects the data destined to it. Note that the switch
does not require any input buffers, thereby circumventing the HOL problem. Input
buffers are not needed since each incoming packet is broadcast to all the output ports
and each output port decides whether to accept the packet or not.
16.2.2 Backplane Bus Operation
Each bus is dedicated to an input port. The bus operates at 622 Mbps and sends its
data to all the output ports. Thus, each bus can carry one 622 Mbps channel or four
155 Mbps TDMA channels.
16.2.3 Output Port Operation
Each input port accepts data from N buses at a maximum rate of 622 × N Mbps.
The output port has a common buffer that is used to queue the packets. However,
the switch maintains information about buffer occupancy for each connection (VC).
Thus, packet discard is performed on a per-VC basis which is fair to all other con-
nections and all the service classes supported by the switch.
We see that the switch is inherently modular in architecture since the inputs do
not communicate among themselves to do their operation. Similarly, we see that the
outputs do not communicate among themselves to do their operation.