Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
592 16 Examples of Switches
When N > 10 and B > 10, we can approximate the above equation as
Th(max) =
1
N
1 −
1
B
≈
1
N
packets/time step (16.32)
The efficiency in (16.19) of the VRQ switch will be
η(min) = 1 −
1
B
≈ 1 (16.33)
We note that the minimum efficiency of the VRQ switch depends on the local
buffer size and not on the switch size N. This is evidence that the VRQ switch
provides isolation between users.
The lost traffic in (16.20) will be
N
a
(lost) =
1
NB
packets/time step (16.34)
Maximum packet loss actually decreases with the buffer size and the switch size.
It is obvious that the VRQ switch actually performs better as its size increases.
Packet loss probability in (16.21) is given by
L =
1
B
(16.35)
The maximum packet loss probability depends only on the buffer size. This is,
again, further evidence of the user isolation properties of the VRQ switch.
The maximum delay is given from (16.22) by
W(max) =
NB
2
time steps (16.36)
Example 16.1 Plot the VRQ switch performance when the switch size is 10 × 10.
Choose two different buffer sizes. One switch has B = 64 and the other has
B = 16.
Figure 16.5 shows the switch throughput, efficiency, and loss probability for the
VRQ switch with two input buffer sizes. The solid line is for a switch with B = 64
and the dotted line is for a switch with B = 16.
We note that the switch throughput does not saturate even at full load. The two
switches show almost identical throughput but the one with smaller input buffers
shows slight throughput saturation near full load.
The switch efficiency is flat at its maximum value of 100% for most of the input
traffic range. The efficiency of the switch with bigger buffer size hardly shows any
Problems 593
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
10
0
10
1
10
2
10
3
Delay
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. 16.5 Performance of a 10 × 10 VRQ 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 B = 64 and the dotted line is for a switch with B = 16
signs of decreasing. The switch with smaller buffer shows slightly decreased effi-
ciency only at full load.
The delay of both switches increases slowly with increased input traffic since the
input buffers start to fill up. Near full load conditions, the switch with bigger buffer
shows higher delay because of its larger buffer size.
The switch packet loss performance is very impressive even when buffer size is
small. The switch with smaller buffer shows higher packet loss probability even for
very small values of input traffic. The switch with larger buffer hardly shows any
buffer loss for over one half of the range of input traffic.
Problems
Switch Design Strategies
16.1 What is congestion and how does it lead to degradation of throughput, packet
loss, delay, and efficiency?
594 16 Examples of Switches
16.2 What is contention within a switch and where are the major contention points
located?
16.3 What are the steps that could be taken to counteract switch performance loss
due to contention?
16.4 How can multiple service classes be supported in an input queuing switch,
output queuing switch, and shared buffer switch?
16.5 What is the main characteristic of next-generation switches compared to tra-
ditional switches?
16.6 Check and see other examples of high-performance network switches. Com-
pare some of those switches with the two described in this chapter from the
points of view of buffer speed, contention, and support of multiple service
classes.
16.7 An important requirement in switch buffers is the ability to do multiple write
or multiple read operations in one time step. Can you discover hardware
techniques to build two buffers. One that can support many read and one
write operations per time step. The other can support one write and many
read operations per time step.
16.8 Network switches require FIFO queues. Can you design a queue out of a
regular RAM? What would be the glue logic required?
16.9 Network switches sometimes require a collection of queues with flexible
sizes. How can this be implemented such that when a queue is close to being
filled, it can take from the locations of the queues that are not quite full?
Promina 4000 Switch
16.10 Explain how the Promina 4000 switch works.
16.11 Explain why the inputs of the Promina 4000 switch do not require any input
buffers, thereby circumventing the HOL problem.
16.12 Is there any limitation on the Promina 4000 scaling (size and speed) based
on input port operation?
16.13 How is the switch fabric of the Promina 4000 switch contentionless?
16.14 Is there any limitation on the Promina 4000 scaling (size and speed) based
on backplane bus operation?
16.15 Is there any limitation on the Promina 4000 scaling (size and speed) based
on output port operation?
16.16 Explain how the scheduling algorithm is implemented in the Promina 4000
switch.
VRQ Switch
16.17 Explain how the VRQ switch works.
16.18 Explain why the input buffers of the VRQ switch do not suffer from the HOL
problem.
References 595
16.19 Is there any limitation on the VRQ switch scaling (size and speed) based on
input port operation?
16.20 How is the switch fabric of the VRQ switch contentionless?
16.21 Is there any limitation on the VRQ switch scaling (size and speed) based on
backplane bus operation?
16.22 Is there any limitation on the VRQ switch scaling (size and speed) based on
output port operation?
16.23 Explain how the scheduling algorithm is implemented in the VRQ switch.
References
1. http://internet.net.com/techtop/adtmatm wp/home.html.
2. http://internet.net.com/products/.
3. F. Elguibaly, A. Sabaa, and D. Shpak, “A new shift-register based ATM switch”, The First An-
nual Conference on Emerging Technologies and Applications in Communications (ETACOM),
Portland, Oregon, pp. 24–27, May 7–10, 1996.
4. F. Elguibaly and S. Agarwal, “Design and performance analysis of shift register-based ATM
switch”, IEEE Pacific Rim Conference on Communications, Computers and Signal Processing,
Victoria, British Columbia, pp. 70–73, August 20–22, 1997.
5. A. Sabaa, F. Elguibaly, and D. Shpak, “Design and modeling of a nonblocking input-buffer
AT M s wit ch ”, Canadian Journal of Electrical & Computer Engineering, vol. 22, no. 3, pp.
87–93, 1997.
Appendix A
Summation of Series
A.1 Arithmetic Series
n−1
i=0
(a + id) =
n
2
(
a +l
)
where l = a + (n −1)d
A.2 Geometric Series
n−1
i=0
ar
i
=
a(1 −r
n
)
1 −r
∞
i=0
ar
i
=
a
1 −r
where r = 1 in the above two equations.
A.3 Arithmetic–Geometric Series
n−1
i=0
(
a + id
)
r
i
=
a(1 −r
n
)
1 −r
+
rd
1 −nr
n−1
+
(
n − 1
)
r
n
(
1 −r
)
2
597
598 A Summation of Series
where r = 1 in the above two equations. If −1 < r < 1, the series converge, and
we get
∞
i=0
(
a + id
)
r
i
=
a
1 −r
+
rd
(
1 −r
)
2
∞
i=0
i
2
r
i
=
r +r
2
(1 −r)
3
A.4 Sums of Powers of Positive Integers
n
i=1
i =
n(n +1)
2
(A.1)
n
i=1
i
2
=
n(n +1)(2n + 1)
6
(A.2)
n
i=1
i
3
=
n
2
(n + 1)
2
4
(A.3)
A.5 Binomial Series
n
i=0
n
i
a
n−i
b
i
= (a +b)
n
special cases
n
i=0
n
i
= 2
n
n
i=0
(−1)
i
n
i
= 0
n
i=0
n
i
2
=
2n
n
(1 + x)
q
= 1 +qx +
q(q − 1)
2!
x
2
+
q(q − 1)(q − 2)
3!
x
3
···
(1 + x)
−1
= 1 − x + x
2
− x
3
+ x
4
−···
where x < 1 in the above equations.
A.6 Other Useful Series and Formulas 599
A.5.1 Properties of Binomial Coefficients
n
i
=
n
n − i
n
i
=
n
i
n − 1
i −1
n
i
+
n
i −1
=
n + 1
i
n
n
=
n
0
= 1
n! ∼
√
2πn
n+
1
2
e
−n
Stirling’s formula
A.6 Other Useful Series and Formulas
n
i=0
i
n
i
a
i−1
b
n−i
= na(a + b)
n−1
n
i=0
i
2
n
i
a
i
b
n−i
= n(n − 1)a
2
(a + b)
n−2
+na(a + b)
n−1
n
i=1
n − 1
i −1
1
i
a
i
(1 −a)
n−i
=
1
n
1 −(1 −a)
n
∞
i=0
a
i
i!
= e
a
∞
i=0
(
i +1
)
a
i
i!
= e
a
(
a + 1
)
lim
n→∞
1 ±
x
n
n
= e
±x
lim
n→∞
x
n
n
i
= 0 |x| < 1
n
i
+
n
i −1
=
n + 1
i
lim
n→∞
1 −
a
n
n
= e
−a
lim
n→∞
n
i
a
i
(
1 −a
)
n−i
=
a
i
e
−a
i!
a < 1
The last equation is used to derive the Poisson distribution from the binomial
distribution.
Appendix B
Solving Difference Equations
B.1 Introduction
Difference equations describe discrete-time systems just as differential equations
describe continuous-time systems. We encounter difference equations in many fields
in telecommunications, digital signal processing, electromagnetics, civil engineer-
ing, etc.
In Markov chains and many queuing models, we often get a special structure for
the state transition matrix that produces a recurrence relation between the system
states. This appendix is based on the results provided in [1], [2], and [3]. We start
first by exploring simple approaches for simple situations; then we deal with the
more general situation.
B.2 First-Order Form
Assume we have the simple recurrence equation
s
i
= as
i−1
+b (B.1)
where a and b are given. Our task is to find values for the unknown s
i
for all values
of i = 0, 1, ··· that satisfy the above equation. This is a first-order form since each
sample depends on the immediate past value only.
Since this is a linear relationship, we assume that the solution for s
i
is composed
of two components, a constant component c and a variable component v that depend
on i. Thus, we write the trial solution for s
i
as
s
i
= v
i
+c (B.2)
Substitute this into our recursion to get
v
i
+c = a
(
v
i−1
+c
)
+b (B.3)
601
602 B Solving Difference Equations
We can group the constant parts and the variable parts together to get
c = ac +b (B.4)
v
i
= av
i−1
(B.5)
and the value of the constant component of s is
c =
b
1 −a
(B.6)
Assume a solution for v
i
in (B.5) of the form
v
i
=
i
(B.7)
Substitute this solution in the recursion formula (B.5) for v
i
to get
i
= a
i−1
(B.8)
which gives
= a (B.9)
and v
i
is given by
v
i
=
i
= a
i
(B.10)
Thus, s
i
is given from (B.2) as
s
i
= a
i
+
b
1 −a
(B.11)
This is the desired solution to the difference equation.
B.3 Second-Order Form
Assume that we have the simple recurrence equation
s
i+1
+as
i
+bs
i−1
= 0 (B.12)
This is a second-order form since each sample depends on the two most recent
past samples. Assume a solution for s
i
of the form
s
i
=
i
(B.13)
B.4 General Approach 603
The recursion formula gives
2
+a +b = 0 (B.14)
There are two possible solutions (roots) for , which we denote as α and β, and
there are three possible situations.
B.3.1 Real and Different Roots α = β
When the two roots are real and different, s
i
becomes a linear combination of these
two solutions
s
i
= Aα
i
+ Bβ
i
(B.15)
where A and B are constants. The values of A and B are determined from any
restrictions on the solutions for s
i
, such as given initial conditions. For example, if
s
i
represent the different components of the distribution vector in a Markov chain,
then the sum of all the components must equal unity.
B.3.2 Real and Equal Roots α = β
When the two roots are real and equal, s
i
is given by
s
i
=
(
A +iB
)
α
i
(B.16)
B.3.3 Complex Conjugate Roots
In that case, we have
α = γ + jθ (B.17)
β = γ − jθ (B.18)
s
i
is given by
s
i
= γ
i
[
A cos(i θ) + B sin(i θ)
]
(B.19)
B.4 General Approach
Consider the N-order difference equation given by
s
i
=
N
k=0
a
k
s
i−k
, i > 0 (B.20)
whereweassumeds
i
= 0 when i < 0.