Broadband Packet Switching Technologies

A TWO-STAGE MULTICAST OUTPUT-BUFFERED ATM SWITCH

167

Since replicated cells are assumed to be uniformly distributed to all M outputs in MGN2, the probability Bl that l cells are destined for a specific output port of MGN2 in a cell time slot is

							L1 M
				Bl s Ý Bl j Ij .
							jsl
The cell loss rate in MGN2, P2 , is
				L1 M
				Ý Ž l y L2 . Bl Ew Dx
P2 s				lsL	2q1					Ž6.13.
				Ew F1 x
		N					Ž1 y P1 . Ew F2 x
				K
									Ew Dx
							M
				L1 M
			Ý		Ž l y L2 . Bl
s			lsL 2q1					.
	Ew F1 x Ž1 y P1 . Ew F2 x

Here N Ew F1 xrK is the average number of cells destined for a concentrator in MGN1 from the inputs of the MOBAS, and N Ž Ew F1 xrK .Ž1 y P1 . is the average number of cells that have survived in this concentrator, which in turn becomes the average number of cells arriving at the correspond-

ing MGN2. Thus, the denominator in Ž6.13., N Ž Ew F1 xrK .Ž1 y P1 . Ew F2 xEw DxrM, is the average number of cells effectively arriving at a specific

output port. The numerator in Ž6.13., ÝL1 M Žl y L . B Ew Dx, is the average

lsL 2q1 2 l

number of cells effectively lost in a specific concentrator in MGN2, because the lost cell can be a cell that will be duplicated in the OPC.

Figure 6.21 shows the plots of the cell loss probability at MGN2 vs. L2 for various average duplication values and an effective offered load

Žs Ew F1 xEw F2 xEw Dx. of 0.9. The average fanout on MGN1 is assumed to be
1.0 Ž Ew F1 x s 1.0., the group size to be 32 Ž M s 32., and the expansion ratio
to be 2.0 Ž L1 s 2.0.. Since the traffic load on MGN2 decreases as the
average cell duplication Ž Ew Dx. increases,	the cell loss rate in MGN2 de-
creases as Ew Dx increases. Therefore, the	switch design parameter L2 is

more stringently restricted in the unicast case than in the multicast. Consequently, if MGN2 is designed to meet the performance requirement for unicast calls, it will also satisfy multicast calls’ performance requirement.

168 KNOCKOUT-BASED SWITCHES

Fig. 6.21 Cell loss probability vs. group expansion ratio L2 in MGN2.

6.3.4.3 Total Cell Loss Rate in the MOBAS The total cell loss rate in the MOBAS is

PT s Avg. no. of cells effectively lost in both MGN1 and MGN2 Avg. no. of cells effectively offered to MOBAS

1

N

N

s

Ý

Ž k y L1 M . Ak Ew F2 x Ew D x

N Ew F1 x Ew F2 x Ew Dx žM ksL 1 Mq1

/

L1 M

qN

Ý

Ž l y L2

. Bl

Ew Dx

.

Ž6.14.

lsL 2q1

The

first term of

the numerator in

Ž

.

Ž

.

N

Ž

k y L1 M

.

6.14 ,

NrM ÝksL 1 Mq1

Ak Ew F2 xEw Dx, is the average number of cells effectively lost in MGN1. The

second

term of the

L M

Ew Dx, is the

numerator in Ž6.14., N Ýls1 L 2q1Žl y L2 . Bl

average number of cells effectively lost in all of MGN2. The denominator in

A FAULT-TOLERANT MULTICAST OUTPUT-BUFFERED ATM SWITCH

169

Ž6.14., N Ew F1 xEw F2 xEw Dx, is the average number of cells effectively offered to the MOBAS.

In Ž6.14. L1 and L2 should be in a certain range to guarantee the required cell loss performance in the MOBAS. For example, in order to get the cell loss rate of 10y10 in the MOBAS with a very large size Ž N G 1024. and a group size of M Žs 32., L1 and L2 should be greater than 2 and 12, respectively. If either of them is less than the required number, the total cell loss rate in the MOBAS cannot be guaranteed, since the term of the numerator of Ž6.14., that is a function of the smaller number, dominates the total cell loss rate in the MOBAS.

6.4 A FAULT-TOLERANT MULTICAST OUTPUT-BUFFERED ATM SWITCH

Fault tolerance is an important issue when designing ATM switches for reliable communications. In particular, as line rates increase to 2.5 or 10 Gbitrs, the failure of a single switch element in the switch fabric will disrupt the service of all connections on the link that passes through the failure point. Several interconnection networks, along with some techniques, including time redundancy and the space redundancy, have been proposed to achieve network fault tolerance w1, 11, 27, 12, 15, 29, 17x. The time redundancy technique uses a multiple-pass routing strategy to obtain dynamic full access between inputs and outputs. More specifically, it permits each input to be accessible to any output in a finite number of recirculations through a switching network. The space redundancy technique provides multiple paths from each input to all outputs by using redundant hardware Žadditional switching elements, links, or stages. w16x. This additional hardware increases the system complexity and complicates the operations of the switch.

Because of the property of a unique routing path between any input and output pair in binary self-routing networks, it is difficult to achieve fault tolerance without adding additional switching planes, stages, or switching elements. As shown in Figure 6.13, there are multiple paths between each input and output pair. Therefore, it is inherently robust against faulty switching elements and internal link failures. This section presents different techniques of fault diagnosis Žincluding fault detection and location. and system reconfiguration Žby isolating faulty switching elements. for the MOBAS w5x. The regular structure of the MOBAS also simplifies fault diagnosis and system reconfiguration when a fault occurs.

6.4.1 Fault Model of Switch Element

A fault in the SWE can happen in the control logic circuit or on the data link of the SWE. In the former case, the SWE will remain in either a cross state or a toggle state; these faults are called cross-stuck or toggle-stuck, respectively. If a data link is short-circuited or open-circuited, the output of the SWE is either at a high or low state; it is then called stuck-at-one Žs-a-1. or

170 KNOCKOUT-BASED SWITCHES

stuck-at-zero Žs-a-0.. Cells passing through the faulty links are always corrupted. The link failure can occur at either a vertical or a horizontal link; it is then called vertical-stuck or horizontal-stuck, respectively. Let SWEŽi, j. represent the switch element located at the ith row and the jth column in the SWE array. Denote by CSŽi, j., TSŽi, j., VSŽi, j., and HSŽi, j. a crossstuck, toggle-stuck, vertical-stuck, and horizontal-stuck fault at SWEŽi, j., respectively.

In the following, we only discuss single-fault failures, since they are much more likely to happen than multiple-fault failures in integrated circuits w2x.

6.4.1.1 Cross-Stuck (CS) Fault Figure 6.22 shows the cell routing in an SWE array with across-stuck SWEŽ4, 3. wthe shaded one, denoted CSŽ4, 3.x, where a cell from the north is always routed to the south, and a cell from the west to the east. If the CS fault occurs in the last column of the SWE array, as shown in Figure 6.22, cell loss performance is degraded. For instance, cell

Fig. 6.22 An example of cell loss due to a cross-stuck fault at SWEŽ4, 3., denoted CSŽ4, 3.. Ž 1994 IEEE..

A FAULT-TOLERANT MULTICAST OUTPUT-BUFFERED ATM SWITCH

171

X4 is discarded because of the cross-stuck SWEŽ4, 3.. If there are only three cells from the first to the fourth input destined for this output group, one of these three cells will be discarded at SWEŽ4, 3., which contributes to cell loss performance degradation.

However, if X4 is not the third cell destined for this group, or there are more than three Žthe number of output links. cells destined for this group, the CS in the last column does not contribute to cell loss performance degradation.

6.4.1.2 Toggle-Stuck (TS) Fault Figure 6.23 shows how a toggle-stuck SWEŽ4, 2. affects the cell routing in the SWE array. Unlike a cross-stuck fault, a toggle-stuck fault may result in cells being misrouted. If the west input of the toggle-stuck SWE in Figure 6.23 does not have a cell destined for this output, an output link is wasted because the link is mistakenly occupied by this input. Therefore, every input, except this input, may experi-

Fig. 6.23 An example of cell loss due to the toggle-stuck fault at SWEŽ4, 2., denoted TSŽ4, 2.. Ž 1994 IEEE..

172 KNOCKOUT-BASED SWITCHES

Fig. 6.24 A cell loss example due to the vertical stuck-at-1 or -0 fault at SWEŽ4, 2., denoted VSŽ4, 2.. Ž 1994 IEEE..

ence a cell loss performance degradation. For example, in Figure 6.23, cell X1 is discarded due to the fault of TSŽ4, 2..

6.4.1.3 VerticalrHorizontal-Stuck (VSrHS) Fault Figure 6.24 shows the cell routing in the SWE array when a fault of stuck-at-one Žor -zero. is found at the vertical link of SWEŽ4, 2.. Figure 6.25 shows a fault at the horizontal link. Cells passing through this faulty SWE are always corrupted at either the vertical or the horizontal link. This might cause data retransmission and increase the network load and the congestion probability.

6.4.2 Fault Detection

To detect a fault, it is assumed that the MTTs, the OPCs, and the horizontal outputs of the SWE array Žwhere cells are discarded. have simple logic circuits, called fault detectors ŽFDs., which are capable of detecting any

A FAULT-TOLERANT MULTICAST OUTPUT-BUFFERED ATM SWITCH

173

Fig. 6.25 A cell loss example due to a horizontal stuck-at-1 or -0 fault at SWEŽ4, 2., denoted HSŽ4, 2.. Ž 1994 IEEE..

misrouted cells in the switch modules and thus providing on-line fault detection capability. In addition, the MPMs and the ABs are assumed to be able to generate test cells to locate faulty SWEs once a fault is detected by the FDs.

The fault diagnosis and system reconfiguration can be carried out at any time when needed by retaining users’ cells at the IPCs and feeding test cells to the switch fabric. Because the test can be completed within a couple of cell slots, the overhead will not affect the switch’s normal operations.

The FDs in MTTs or OPCs of the kth SM examine the kth bit of a flattened address Žzero or one. to determine a misrouted cell. They also examine the source address in the test cell to locate a faulty SWE.

6.4.2.1 Cross-Stuck and Toggle-Stuck Fault Detection A TS fault can be detected by monitoring cells routed to MTTs or the OPCs. If a cell routed to an MTT or OPC has a FA of all zeros, it is considered a misrouted cell. This is because any cell with all zeros in the FA should not be routed to the

174 KNOCKOUT-BASED SWITCHES

south. As shown in Figure 6.23, when cell X4 is misrouted to the second output, the associated FD detects this misrouted cell because its FA is all 0s.

While the TS fault can be easily detected online, the CS fault cannot be detected online. This fault will not contribute to cell-loss performance degradation if it is not located in the last column. Even if it is in the last column, we do not care about the CS fault, since this kind of sticking is exactly the action we will take for fault isolation Ždetails are explained later..

6.4.2.2 Vertical-Stuck and Horizontal-Stuck Fault Detection VS and HS faults can be easily detected by checking if the outgoing signal from the SWE array is always one or zero. For instance, as shown in Figure 6.24, the signal from the second output link is always one Žor zero., which indicates that one of the SWEs in the second column must be a VS. Once a VS fault occurs, e.g., at SWEŽ4, 2., all the SWEs below the faulty one remain at the cross state, so that the s-2-0 and s-2-1 faults will display at the south output of the faulty column. Cells that reach the south outputs are either valid cells from the user or empty cells from the ABs. They do not have the pattern of all zeros or all ones in their headers Žconsisting of the FA and priority fields.. So, if a cell appears at a south output and has a pattern of all zeros or all ones, it must be a VS fault.

Figure 6.25 shows that the signal from the fourth discarding output is always one Žor zero., and that there must be an SWE HS fault in the fourth row. Once a HS fault occurs, e.g., at SWEŽ4, 2., all the SWEs on the right of the faulty one remain in the cross state, so that the s-a-0 and s-a-1 faults will display at the east output of the faulty row. Cells that reach the east outputs can be valid cells from the user, empty cells from the ABs, or idle cells from the IPCs. Let us assume the address field of the idle cells is set to all zeros while the priority field is set to all ones Žcorresponding to the lowest priority.. So, if a cell appears at an east output and has a pattern of all zeros or all ones, it must be a HS fault.

6.4.3 Fault Location and Reconfiguration

Once a fault is detected, we need more information to locate the fault and reconfigure the switching network. The fault detection itself provides partial information about the location of the faulty SWE Že.g., either the row or column identification.. In order to properly reconfigure the network, we need to exactly locate a HS SWE and a TS SWE. For the VS fault, we just need to know the column information. A test cell, consisting of a FA field, a new priority field, and an input source address field, is generated by the MPM or the AB to locate the fault. Its FA field has the same length as the regular cell format in the MOBAS. The new priority field is log2 2 L1 M bits long in MGN1 and log2 2 L2 bits in MGN2. The input source address field haslog2 N bits in MGN1 and log2 L1 M bits in MGN2.

A FAULT-TOLERANT MULTICAST OUTPUT-BUFFERED ATM SWITCH

175

6.4.3.1 Toggle-Stuck and Cross-Stuck Cases By performing fault detection for the TS, the location of the faulty column can be identified. In order to locate the faulty row, we define a location test Žcalled the TS test. for a TS fault. Figure 6.26 shows an example of the TS test. Cells coming from MPMs are forced to have a different FA than those from the AB; thus, all SWEs in the SWE array are set to a cross state. As aresult, fault-free condition cells from the MPMs all appear at the east side of the SWE array, while those from the AB appear at the south side. If there is a TS at SWEŽi, j., cells from the ith MPM will be delivered to the jth output link, while cells from the jth column of the AB are routed to the ith discarding output.

Once we have exactly located the TS fault, say at Ži, j., we can reconfigure the SWE array by setting SWEŽi, j. to a cross state, as shown in Figure 6.27.

Fig. 6.26 Fault location test for a toggle-stuck SWE by forcing all SWEs to a cross state.

176 KNOCKOUT-BASED SWITCHES

Fig. 6.27 Reconfiguration by forcing a toggle-stuck SWEŽ4, 2. to a cross state.

This reconfigured SWE array has the same cell-loss performance as the SWE array with a CS fault at Ži, j..

As mentioned before, a CS fault cannot be detected online. However, since a CS situation can be considered a reconfiguration of TS faults, we do not need to identify the location of the CS fault Žalthough it can be detected and located with a few steps of offline tests as described in the following..

If we add one more bit to the priority field and modify the setting of the priority fields of the test cells, we can offline detect and locate a CS fault in the SWE array. The method of locating a CS fault is to force all the SWEs in the shaded square block of SWEs in Figure 6.28 to a toggle state while the rest of the SWEs are set to a cross state. If there exists a CS SWE in the square block, we will be able to identify its location by monitoring the outputs. By moving the square block around in the SWE array and repeating the test procedure, we can determine if there is a CS fault and locate its position Žif any..