Gebali F. Analysis Of Computer And Communication Networks

Подождите немного. Документ загружается.

14.11 Improved Logical Neighborhood (ILN) 541

Table 14.10 Possible SE

outputs based on the routing

vector r

Binary value of rC

000 x

001 x

010 x

100 x

011 x x

101 x x

110 x x

111 x x x

vector is r = 111. In that case, any of the cube connections could be used in any

order at each stage to eliminate any of the “1”s in any bit location.

The vector r carries information about the mismatch between the incoming ad-

dress and the destination address. This mismatch should decrease by one bit each

time the packet goes through each stage of the network.

As an example, let us attempt to move a packet from input 6 (110) to output 0

(000). The resulting routing vector is r = [

110

]. Figure 14.23 shows two possible

paths for routing a packet from input at row 6 to output at row 1 based on routing

vector r.

Stage 0:Wehaver = [

110

]. Thus we need to access ports C

or C

. Picking

the C

connection produces the updated routing vector r



= [

100

]. This

choice makes the packet travel from row 6 to row 4 at stage 1. On the other

hand, picking the C

connection produces the updated routing vector r



[

010

]. This choice makes the packet travel from row 6 to row 2 at stage 1.

Stage 1: If routing vector at this stage is r = [

100

], we choose port C

The updated routing vector becomes r



= [

000

]. This choice makes the

packet travel from row 4 to row 0 at stage 2. If routing vector at this stage

01 2 3

Stage:

Inputs

Outputs

Fig. 14.23 Paths chosen in the ILN network to route a packet from input at row 6 to output at row 0

542 14 Interconnection Networks

is r = [

010

], we choose port C

. The updated routing vector becomes



= [

000

]. This choice makes the packet travel from row 2 to row 0 at

stage 2.

Stage 2: Since our routing vector is r = [

000

], we have to choose the straight

connection to route the packet to the desired output at row 0 at stage 3.

As an illustration of the richness of paths from any input to any output, Fig. 14.23

shows the paths chosen to route a packet from input at row 6 to output at row 1.

14.11.2 Path Selection Issues

The routing algorithm chosen by each SE in the ILN network is based on choosing a

connection that will change an existing “1” in r to a “0”. It was also mentioned that

contention might force the routing algorithm to change a “0” bit to “1” to choose

an alternative path. These newly created “1”s will be corrected at later stages in the

network. Let us illustrate that using a simple example. Assume only two packets, a

and b, arrive at the inputs 0 and 4, respectively, at a given slot time. Both packets

are destined to output 0. In that case, packet a will choose the straight connection

throughout switching elements SE(0,0), SE(1,0), and SE(2,0). Packet b will choose

the C

connection for SE(0,4) and it will require the straight connection for switch-

ing elements SE(1,0) and SE(2,0). Thus, only one packet will be routed and the

others will be blocked even though there are many alternative routes to output 0.

The routing algorithm at each SE must be able to identify the alternative routes

at any stage in order to prevent this unnecessary contention and fully utilize the link

redundancy.

The intelligent routing algorithm, in effect, destroys some of the zero bits in r,

trusting that they will be returned back to zero value at later stages. The destruction

of 0-bits is equivalent to choosing alternative routes to reach the desired output.

Figure 14.24 shows the path chosen to route a packet from input at row 6 to

output at row 0 based on routing vector r.

Fig. 14.24 All possible paths

chosen in the ILN network to

route a packet from input at

row 6 to output at row 0

based on routing vector r

01 2 3

Stage:

Inputs

Outputs

14.11 Improved Logical Neighborhood (ILN) 543

14.11.3 Analysis of ILN Network

An N × N ILN network is built using 1-to-(n + 1) selectors in the input stage

(i = 0), (n + 1) × (n + 1) crossbar SEs in the n − 1 internal stages (0 < i < n),

and (n +1)-to-1 concentrators in the output stage (i = n). Therefore, we can use the

results we obtained for the banyan and ADMN networks after some modifications.

Because we have 1-to-(n +1) selectors at stage 0, the packet arrival and departure

probabilities at the input and the outputs of each selector are given by

(in) = a (14.89)

(out) =

n + 1

(14.90)

For the SEs at the internal stages (0 < i < n), we use the expression for the

throughput in (14.5) with N = n + 1:

(in) = a

i−1

(out) (14.91)

(out) = 1 −



1 −

(in)

n + 1



(n+1)

(14.92)

At the output stage (i = n), we have (n + 1)-to-1 concentrators. For an ILN

network whose output concentrator accepts m packets (1 ≤ m ≤ n + 1), we can

write the arrival and departure probabilities at the output as

(in) = a

n−1

(out) (14.93)

(out) =

m−1



j=1

n+1



j=m

(14.94)

where 1 ≤ m ≤ n + 1 is the maximum number of packets that could be accepted at

the output in one time step and x

is the probability that j packets arrived



n + 1



(in)

[

1 −a

(in)

]

n+1−j

(14.95)

According to (14.3), we can write the traffic at the input of the banyan network as

(in) = a (14.96)

and the output traffic at the tagged output of the network is

(out) = a

(out) (14.97)

where a

(out) is given by (14.94).

544 14 Interconnection Networks

The throughput of the ILN network is given by

Th = N

(out) = a

(out) (14.98)

The packet acceptance probability for the ADMN network is given by

(in)

(14.99)

The delay of the ILN network is defined as the average number of attempts to

access the desired output. The probability that the packet succeeds after k tries is

given by the geometric distribution

p(k) = p

(

1 − p

)

(14.100)

The average delay time is

0 0.5 1

0.2

0.4

0.6

0.8

Input traffic

Throughput

0 0.5 1

0.2

0.4

0.6

0.8

Input traffic

Acceptance probability

0 0.5 1

0.2

0.4

0.6

0.8

Input traffic

Delay

Fig. 14.25 Variation of the throughput, the packet acceptance probability, and the delay with the

input traffic when N = 64 for the ILN network (solid line) and the similar-sized crossbar network

(dotted line)

Problems 545

∞



k=0

kp(k)

∞



k=0

(

1 − p

)

1 − p

(14.101)

Example 14.5 Plot the throughput (Th), the access probability (p

), and the average

delay (n

) for the ILN network versus the input traffic when the size of the network

is N = 64 and compare this with the similar-sized crossbar network. Assume an

output concentrator that accepts all the packets that arrive at its two inputs.

We evaluate the expressions for throughput, packet acceptance probability, and

delay when N = 64 and a is varied for both the ILN network and the crossbar

network. Figure 14.25 shows the variation of throughput, the packet acceptance

probability, and the delay with the input traffic when N = 64 for the ILN net-

work (solid line) and the crossbar network (dotted line). We see that the crossbar

network shows superior performance for the same number of input and output ports

as expected.

Problems

Interconnection Networks

14.1 What is the main function of an interconnection network and what are the

main performance requirements of the network?

14.2 Discuss the main issues related to synchronous data transfer in the switching

fabric and between the main components of a switch.

14.3 Assume two communicating modules in the switch using synchronous clock-

ing scheme. Construct a table explaining (a) the main signal lines required

between the two modules; (b) the direction of signal on each line; and (c) the

function of each signal.

Using a timing diagram show how a packet could move between the two

modules.

14.4 To maintain data integrity using a system-wide clock, clock skew must be

controlled and clock signal integrity must be maintained. How can clock skew

be controlled?

14.5 Assume two modules exchange data using a common clock. One option is to

use a two-phase clock and the other is to use single-phase clock. Explain the

two options using timing diagrams and explain the problem of clock skew in

both of them.

14.6 Discuss the main issues related to asynchronous data transfer in the switching

fabric and between the main components of a switch.

546 14 Interconnection Networks

14.7 Assume two communicating modules in the switch using asynchronous clock-

ing scheme. Construct a table explaining (a) the main signal lines required

between the two modules; (b) the direction of signal on each line; and (c) the

function of each signal.

Using a timing diagram show how a packet could move between the two

modules.

14.8 Assume you need two transfer a packet between two blocks in the switch in

the least amount of time. What are your options and what are the advantages

and disadvantages of each option?

14.9 What are the main sources of power loss in a chip operating at very high data

rates? Is there much difference between using GaAs or CMOS logic at high

speeds?

Time Division Multiple Access (TDMA)

14.10 Explain the two main types of TDMA.

14.11 Discuss the advantages and disadvantages of static-assignment TDMA.

14.12 Discuss the advantages and disadvantages of random assignment TDMA.

Multiplexing Techniques (TDMA)

14.13 In time division switching, one media access protocol was mentioned, the

random assignment. What other types of MAC protocols could be used to

guarantee fair access to the medium in a reasonable time delay.

14.14 Perform numerical simulations of the random assignment TDS with N = 10

for variable arrival probability a between 0.1 and 1. Plot the average delay

for an input and plot the average throughput of any input.

14.15 Assume a TDS with a static priority protocol in which each user has a priority

equal to its index. Derive an expression for the probability of accessing the

medium for any user. Based on that, find the average delay that each user

experiences and the average throughput for each user.

Crossbar Interconnection Network

14.16 Explain how a path is established in the crossbar switch and explain why the

switch is nonblocking.

14.17 Discuss the need for arbitration in a crossbar network and propose some

techniques for resolving output contention. Discuss the advantages and dis-

advantages of the arbitration techniques you propose from the point of view

of hardware complexity and speed.

14.18 Assume we have N devices attached to a bus and each device has a priority

of accessing the bus equal to its index number. Thus device 0 has the least

probability, device 1 has higher probability than device 0, and so on. Derive

Problems 547

an expression for the probability that device i access the bus. Having done

that, derive an expression for the delay.

14.19 Derive expressions for channel usage efficiency of packet switching using

datagram versus virtual circuit switching. Assume each packet for datagram

is composed of n

header/trailer bytes and n

payload bytes. For virtual cir-

cuit switching, assume n

header/trailer bytes, n

payload bytes, and n

bytes

required for call establishment and tear down.

14.20 Prove equation (14.23) by estimating the probability of a packet transmitted

to the output of an SE as the sum of two probabilities:

(

)

only one packet

arrives on one of the input links;

(

)

packets arrive at both input links.

14.21 One of the necessary components of a switch is the FIFO. How can this be

implemented using an ordinary one-ported random-access memory?

14.22 One of the necessary components of a switch is a CAM (content address-

able memory). Discuss how a CAM could be implemented using specialized

hardware or using a random-access memory or groups of random-access

memories.

14.23 In input queuing switch, it was mentioned that HOL problem leads to re-

duced throughput and increased packet loss probability. Suppose a window-

ing scheme is used to examine w packets at the head of the queue instead of

only one. How can this scheme preserve the packet sequence?

14.24 In shared buffer switches, it was mentioned that the shared buffer must per-

form many read and write operations per time step. Discuss how this can be

implemented using a bank of one-ported memories that is accessible by all

inputs and outputs of the switch.

14.25 Perform numerical simulations for the crossbar network of size 8 × 8for

variable arrival probability a between 0.1 and 1. Plot the average delay for

an input and plot the average throughput of any input.

Generalized-Cube Network (GCN)

14.26 Sketch a 4 ×4 GCN network.

14.27 Sketch a 16 ×16 GCN network.

14.28 Find the path taken by a packet in an 8 × 8 GCN network if the source row

address is S = 2 and the destination row address is D = 1.

14.29 Find the path taken by a packet in an 8 × 8 GCN network if the source row

address is S = 7 and the destination row address is D = 0.

Banyan Interconnection Network

14.30 Prove (14.32) on page 524.

14.31 Prove (14.38) on page 525.

14.32 Prove (14.41) on page 525.

14.33 Sketch a 4 ×4 banyan network.

14.34 Sketch a 16 ×16 banyan network.

548 14 Interconnection Networks

14.35 Find the path taken by a packet in an 8 ×8 banyan network if the source row

address is S = 2 and the destination row address is D = 1.

14.36 Find the path taken by a packet in an 8 ×8 banyan network if the source row

address is S = 7 and the destination row address is D = 0.

14.37 Assume a banyan network is built using 3 ×3 switching elements instead of

2 ×2. Plot the resulting network and derive an expression for the recurrence

formula.

14.38 Perform numerical simulation for an 8×8 banyan network for variable arrival

probability a between 0.1 and 1. Plot the average delay for an input and plot

the average throughput of any input.

ADMN Interconnection Network

14.39 Perform numerical simulation for an 8 × 8 ADMN network for variable ar-

rival probability a between 0.1 and 1. Plot the average delay for an input and

plot the average throughput of any input.

14.40 Perform numerical simulation for an 8 × 8 ILN network for variable arrival

probability a between 0.1 and 1. Plot the average delay for an input and plot

the average throughput of any input.

14.41 Sketch a 4 ×4 ADMN network.

14.42 Sketch a 16 ×16 ADMN network.

14.43 Find the paths taken by a packet in an 8 × 8 ADMN network if the source

row address is S = 2 and the destination row address is D = 1.

14.44 Find the paths taken by a packet in an 8 × 8 ADMN network if the source

row address is S = 7 and the destination row address is D = 0.

ILN Interconnection Network

14.45 Explore other alternative routes for the routing example given for the ILN

network.

14.46 Sketch a 4 ×4 ILN network.

14.47 Sketch a 16 ×16 ILN network.

14.48 Find the paths taken by a packet in an 8 × 8 ILN network if the source row

address is S = 2 and the destination row address is D = 1.

14.49 Find the paths taken by a packet in an 8 × 8 ILN network if the source row

address is S = 7 and the destination row address is D = 0.

References

1. F. Elguibaly, “Analysis and design of arbitration protocols”, IEEE Transactions on Computers,

vol. 38, no. 2, pp. 1168–1175, 1989.

2. R.J. Simcoe and T.-B. Pei, “Perspectives on ATM switch architecture and the influence of

traffic pattern assumptions on switch design”, Computer Communication Review, vol. 25,

pp. 93–105, 1995.

References 549

3. N. McKeown, “The iSLIP scheduling algorithm for input-queued switches”, IEEE/ACM

Transactions on Networking, vol. 7, pp. 188–201, 1999.

4. J. Duato, S. Yalamanchili, and L. Ni, Interconnection Networks: An Engineering Approach,

IEEE Computer Society Press, Los Alamito, California, 1997.

5. J. Walrand, Communication Networks: A First Course, McGraw-Hill, New York, 1998.

6. M. Swartz, Telecommunication Networks: Protocols, Modeling and Analysis, Addison Wesley,

Reading, Massachusetts, 1987.

7. S.W. Furhmann, “Performance of a packet switch with crossbar architecture”, IEEE Transac-

tions on Communications, vol. 41, pp. 486–491, 1993.

8. C. Clos, “A study of non-blocking switching networks”, Bell System Technology Journal,

vol. 32, pp. 406–424, 1953.

9. “Performing Internet routing and switching at gigabit speeds”, Cisco 12000 Series GSR Tech-

nical Product Description, Cisco Systems, San Jose, California [On line]. Available HTTP:

http://www.ieng.com/warp/public/cc/pd/rt/12000/

index.shtml

10. N. McKeown, M. Izzard, A. Mekkittikul, B. Ellersick, and M. Horowitch, “The tiny tera: A

small high-bandwidth packet switch core”, IEEE Micro, vol. 17, pp. 26–33, 1997.

11. C. Partridge, P.P. Carvey, E. Burgess, I. Castineyra, T. Clarke, L. Graham, M. Hathaway,

P. Herman, A. King, S. Kohalmi, T. Ma, J. Mcallen, T. Mendez, W.C. Milliken, R. Pet-

tyjohn, J. Rokosz, J. Seeger, M. Sollins, S. Storch, B. Tober, G.D. Troxel, D. Waitzman, and

S. Winterble, “A 50 Gb/s IP Router”, IEEE/ACM Transactions on Networking, vol. 6, no. 3,

pp. 237–248, 1998.

12. 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.

13. F. Elguibaly, and S. Agarwal, “Design and performance analysis of shift register-based ATM

switch”, IEEE Pacific Rim Conference on Communications, Computers and Signal Process-

ing, Victoria, B.C., pp. 70–73, August 20–22, 1997.

14. A. Sabaa, F. Elguibaly and D. Shpak, “Design and modeling of a nonblocking input-buffer

ATM switch”, Canadian Journal of Electrical and Computer Engineering, vol. 22, no. 3,

pp. 87–93, 1997.

15. V.E. Benes, Mathematical Theory of Connecting Networks and Telephone Traffic, Academic

Press, New York, 1965.

16. K. Hwang and F.A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill,

New York, 1984.

17. H.J. Siegel, Interconnection Networks for Large-Scale Parallel Processing: Theory and Case

Studies, Lexington Book, Lexington, Massachusetts, 1990.

18. D. Lawrie, “Access and alignment of data in an array processor”, IEEE Transactions on Com-

puters, vol. C-24, pp. 1145–1155, 1975.

19. L.R. Goke and G.J. Lipvski, “Banyan networks for partitioning multiprocessor systems”, First

Annual International Symposium on Computer Architecture, pp. 21–28, December 1973.

20. K. Pibulyarojana, S. Kimura, and Y. Ebihara, “A study on a hybrid dilated banyan network”,

IEICE Transaction on Communications, vol. E80 B, pp. 116–126, 1997.

21. J.H. Patel, “Performance of processor-memory interconnections for multiprocessors”, IEEE

Transaction on Computers, vol. C-30, pp. 771–780, 1981.

22. M. Abd-El-Barr, K. Al-Tawil, and O. Abed, “Fault-tolerant and reliability analysis of multi-

stage data manipulator networks”, International Conference on Distributed Computing,

pp. 275–280, 1995.

Chapter 15

Switch Modeling

15.1 Introduction

As we saw in Chapter 13, a packet switch must contain input (ingress) ports, output

(egress) ports, switch fabric, and control section. When a packet arrives at a switch,

it must be processed at the input before it can be routed to the proper switch output

port. Processing involves matching the packet header to information in a lookup

table to determine the destination and the priority and type of packet. These opera-

tions take time and the packets must be temporarily stored in input buffers.

Chapter 13 discusses several types of switches based on the placement of buffers

within each switch which includes.

1. Input queuing switch

2. Output queuing switch

3. Shared buffer switch

4. Multiple input queuing switch

5. Multiple output queuing switch

6. Multiple input and output queuing switch

7. Virtual routing/virtual queuing (VRQ) switch

The placement of the buffers and the priority queues in the switch has direct

impact on the overall switch performance.

The literature abounds with sophisticated models for all types of switches

[1–14]. Most of these models assumed an deal switch fabric in order to simplify

the analysis. This assumption is not true in reality. We saw in Chapter 14 that all the

interconnection networks in use today have limitations and the ability of a packet to

go through the SF decreases with increasing input traffic or increasing network size.

In this chapter, we illustrate how to model the performance of the three main

switch types taking into consideration the limitations of the switching fabric (SF).

We choose here to present simple and accurate analyses that take into consideration

the effect of the interconnection network. Having developed the relevant equations,

we derive expressions for the switch performance figures such as throughput, aver-

age buffer size, packet loss probability, and packet delay.

F. Gebali, Analysis of Computer and Communication Networks,

DOI: 10.1007/978-0-387-74437-7

15,



Springer Science+Business Media, LLC 2008

551