Gebali F. Analysis Of Computer And Communication Networks

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

562 15 Switch Modeling

a banyan network, then m = 2. If we had an ADMN network, then m = 3. If we

had an ILN network, then m = lg N + 1, where N is the number of input ports of

the switch.

The packet arrival probability at each of the m links for an output queue is de-

noted by a

. We obtain a value for a

using the flow conservation principle which

states that

Total traffic into switching fabric ≈ Total traffic out of switching fabric

The above equation is true only if we ignore packet loss flow in the switch, which

is reasonable for most high-performance switches. Mathematically, we could write

this as

N × Th

≈ Nma

(15.45)

Therefore, a

is given by

(

1 −be

)

(15.46)

Thus, if we are able to determine the throughput of the input buffers, we will be

able to proceed with the study of the output queues.

The probability of i packets arriving at an output queue is given by





(1 −a

)

m−i

(15.47)

where m is the maximum number of packets that could arrive at an output queue in

one time step. The departure probability of the output queue is really simple

= 1 (15.48)

Output Queue State Transition Matrix

Having found the probability r

that i packets arrive at each output port, we are now

able to write down the state transition matrix for the tagged output queue. This is a

lower Hessenberg matrix of dimension

(

)

(

)

with m subdiagonals.

15.3 Output Queuing Switch 563

For the special case when m = 3 and B

= 6, P

is 7 ×7 and is given by

⎡

⎢

⎣

0000 0

000 0

000

0 r

00r

000r

0000r

⎤

⎥

⎦

(15.49)

where the terms p

at the bottom row are such that the sum of each column must

add to unity. It was assumed that packets could be served in the same time step at

which they arrive. This explains the double term for element p

of the matrix.

We are now able to derive the output queue performance once we solve for the

equilibrium distribution vector. The equation we have to solve is

s = s (15.50)

This is an eigenvalue problem or we can convert it to a system of homogeneous

linear equations:

(

−I

)

s = 0 (15.51)

Since we have a lower Hessenberg matrix, we use forward substitution by as-

suming a value for s

= 1, say. The above matrix gives us all the other components

of s. To get the true value for the state vector s, we use the normalizing equation



i=0

= 1 (15.52)

Let us assume that the sum of the components that we obtained for the vector s

gives



i=0

= x (15.53)

Then we must divide each value of s by x to get the true normalized vector that

we desire.

Output Queue Performance

The throughput of the output queue Th

(packets/time step) is obtained from the

equation

(

1 −e

)

(

1 −r

)

(15.54)

564 15 Switch Modeling

where e

is the probability that the output queue is empty. The first term on the RHS

is the probability that a packet leaves the queue, given that the output queue is not

empty. In that case, the statistics of packet arrival do not matter. The second term on

the right-hand side is the probability that a packet leaves the queue, given that it was

empty and one or more packets arrived at the output queue. Simplifying, we get

= 1 −r

packets/time step (15.55)

To find the efficiency of the output queue, we must estimate the input traffic at

that queue in units of packets/time step. The average number of packets arriving at

the tagged output is given by

a,2

(in) =



i=0

(15.56)

= a

m (15.57)

= Th

packets/time step (15.58)

The efficiency of the output queue is given by

a,2

(in)

1 −r

(

1 −be

)

(15.59)

According to our assumptions, packets are lost at an output queue if more than

one packet arrive when the queue is starting to fill. The maximum number of arriving

packets depends on the details of the interconnection network. To find the lost traffic

at the tagged output queue, 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:

a,2

(lost) = N

a,2

(in) − Th

= Th

−Th

packets/time step (15.60)

15.3 Output Queuing Switch 565

The packet loss probability is

a,2

(lost)

a,2

(in)

= 1 −

1 −r

(

1 −be

)

(15.61)

The average queue size is given by the equation



i=0

packets (15.62)

where s

is the probability that there are i packets in the output queue.

We can invoke Little’s result to estimate the average wait time (number of time

steps) a packet spends in the input queue before it is routed as

= W

×Th

packets (15.63)

where W

is the average number of time steps that a packet spends in the queue.

time steps (15.64)

15.3.3 Putting It All Together

The throughput of the switch per output port equals the throughput of the output

queue

Th = Th

= 1 −r

packets/time step (15.65)

The efficiency of the switch is given by

η =

a,2

(out)

a,1

(in)

1 −r

(15.66)

566 15 Switch Modeling

The lost traffic for the switch is given by

(lost) = N

a,1

(in) − N

a,2

(out)

= a − Th

= a − 1 +r

packets/time step (15.67)

Because the events of packet loss in the input buffer and output queue are not

mutually exclusive, the total packet loss probability is given by

L = L

+ L

− L

(lost)

(in)

= 1 −

1 −r

(15.68)

The average queue length is given by

= Q

+ Q

packets (15.69)

The total delay of packets within the switch is given by

W = W

+ W

time steps (15.70)

15.3.4 Performance Bounds on Output Queuing Switch

Under full load conditions, the input queue switch becomes full and we can assume

a → 1 (15.71)

→ 0 (15.72)

→ p

/m (15.73)

→  (15.74)

→ B

(15.75)

→ B

(15.76)

where 0 < 1.

The maximum throughput is found from (15.65) when e

=  and a = 1:

Th(max) = 1 −



1 −



≈ 1 − e

−p

packets/time step (15.77)

15.3 Output Queuing Switch 567

The minimum efficiency of the switch is given from (15.66) by

η(min) =

Th(max)

(in)

max

= 1 −



1 −



≈ 1 − e

−p

(15.78)

The maximum lost traffic is given from (15.67) by

(lost)

max

= N

(in)

max

−Th(max)

= 



1 −



≈  e

−p

packets/time step (15.79)

where we assumed at maximum load N

(in)

max

= 1.

Maximum packet loss probability in (15.68) is be given by

L(max) =

(lost)

max

(in)

max

=  e

−p

(15.80)

The maximum queue size is given by

Q(max) = B

+ B

(15.81)

The maximum wait time is given from (15.70) by

W(max) =

1 − e

−p

(15.82)

We see the importance of designing a good switching fabric (i.e., high packet

acceptance probability p

→ 1) as a prerequisite for designing a high-performance

switch.

Example 15.2 Plot the output queuing switch performance for switches; one has

= 16 and B

= 64 and the other has B

= 4 and B

= 16. Assume the SF is an

ADMN network with packet acceptance probability p

= 0.7.

For an ADMN network, m = 3. Figure 15.6 shows the switch throughput,

efficiency, and loss probability for the switch with two input queue sizes. The solid

line is for a switch with B

= 16 and B

= 64. The dotted line is for a switch with

= 4 and B

= 16.

We note that the switch throughput saturates at a maximum value Th = p

soon as a approaches p

. This trend is the same irrespective of the buffer size.

568 15 Switch Modeling

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

Efficiency

0 0.5 1

−1

Input traffic

Delay

0 0.5 1

−20

−15

−10

−5

Input traffic

Loss probability

Fig. 15.6 Performance of an output 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 B

= 16 and B

= 64. The dotted line is for a switch with B

= 4andB

= 16. An ADMN

network is assumed with p

= 0.7

The switch efficiency is 100% for most of the input traffic as long as a ≤ p

When the input traffic is a ≈ p

, the efficiency of both switches decreases at ap-

proximately the same rate. However, the efficiency of the switch with smaller input

and output queues starts its decrease slightly before a approaches p

The delay of both switches increases with increased input traffic since the input

queues start to fill up. As soon as the arrival probability approaches the SF accep-

tance probability (a ≈ p

), we see that the delay of both switches saturates at its

maximum value. The switch with larger buffers shows higher delay as shown.

The switch with smaller input and output queues shows higher packet loss prob-

ability even for very small values of a. As soon as a ≈ p

, both switches give very

high and equal cell loss probabilities.

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

(15.83)

15.4 Shared Buffer Switch 569

And the packet loss probability is given from the conservation of flow by

L = 1 −Th = 1 − p

(15.84)

15.4 Shared Buffer Switch

Figure 15.7 shows a shared buffer switch. In a shared buffer switch, there is one

common memory that is accessed by all input and output ports. The memory is

organized, using linked lists, into several FIFO queues such that each output port

has associated with it at least one queue. At the beginning of each time step, packets

arrive at the inputs and are temporarily stored in a small buffer at each input port

until the shared memory controller services them. The shared memory controller

scans each input port in turn and appends incoming packets to the correct FIFO

queue associated with each output port.

We make the following assumptions to simplify our analysis:

1. The shared buffer is divided into N linked lists (or queues) such that each linked

list is associated with an output port.

2. The maximum size of each linked list is B and the total size of the shared memory

is NB.

3. Each queue has N inputs and one output.

4. a is the packet arrival probability at any input of the switch.

5. Packet departure probability from any queue is 1.

6. Packets could be served in the same time step at which they arrive.

7. Each arriving packet has equal probability 1/N of being appended at the end of

any linked list associated with an output port.

8. Data broadcast or multicast are not implemented.

9. Packets will be lost when more than one packet are destined to an output port

whose linked list is full.

Shared Buffer

Write

Controller

Inputs

Outputs

Read

Controller

Fig. 15.7 The shared buffer switch

570 15 Switch Modeling

Fig. 15.8 The arrival and

departure probabilities for

one linked list associated

with an output port. The

arrival and departure

probabilities are shown

c = 1

Output lin

Queue size = B

...

x = a/N

Figure 15.8 shows one linked list associated with an output port. The arrival and

departure probabilities are shown.

Under these assumptions, we can model the shared buffer as a collection of inde-

pendent M

/M/1/B queues. We study one linked list belonging to an output port.

We call this the tagged output port. The probability that an input port has a packet

destined to the tagged output is

x =

(15.85)

The probability that the tagged output port receives i packets in one time slot is

given by





(1 − x)

N−i

(15.86)

where 0 ≤ i ≤ N.

According to our assumptions, the departure probability from the linked list is

c = 1 (15.87)

Having found the arrival and departure probabilities, we are now able to write

down the state transition matrix for the tagged linked list. This is a lower Hessenberg

matrix of dimension

(

B +1

)

(

B +1

)

with B subdiagonals.

For the special case when B = 6, P is given by

P =

⎡

⎢

⎣

00000

0000

000

0 p

⎤

⎥

⎦

(15.88)

where the terms p

at the bottom row are given by

= 1 −



j=0

(15.89)

15.4 Shared Buffer Switch 571

This ensures that that the sum of each column of the transition matrix is unity.

For example, p

is given by

= 1 −

(

)

(15.90)

The solution to the state vector is simply found by assuming a value for s

and

then using forward substitution to find all the other components. The normalizing

condition is invoked to obtain the true value for the state vector. Once the state

vector is determined using numerical techniques, the switch performance can be

calculated.

Shared buffer performance

The throughput of the tagged output Th is given by

Th = (1 −s

) +s

(1 −r

) (15.91)

where s

is the probability that the linked list is empty. The first term on the RHS is

the probability that a packet leaves the queue given that the queue is not empty. In

that case, the statistics of packet arrival do not matter. The second term on the RHS

is the probability that a packet leaves the queue, given that it was empty and one or

more packets arrived at the queue input. Simplifying, we get

Th = 1 −s

packets/time step (15.92)

To find the efficiency of the shared buffer switch, we must first find the traffic

arriving at the tagged linked list. The average number of packets arriving at the

tagged output is given by

(in) =



i=0

= xN

= a packets/time step (15.93)

The efficiency of the input queuing switch is defined as the ratio between output

traffic and input traffic:

η =

(out)

(in)

1 −s

(15.94)

According to our assumptions, packets are lost in a shared buffer switch if more

than one packet arrive when the tagged linked list is starting to fill. To find the lost