Computer and Communication Networks (paperback)

2017-07-07 02:10:07

13.4. Nonblocking Switch Fabrics: Clos Networks

Figure 13.4 shows a Clos network with n = 8 inputs, d = 2, and k = 5. If the number of middle-stage crossbar switch elements k is greater than or equal to 2 d - 1, C ³ _{n , d , k} is strictly nonblocking. Let d and k be integers with 2 d k . The three-stage Clos network is defined by

Equation 13.8

Figure 13.4. A Clos network with n = 8 inputs, d = 2, and k = 5

The proof of this claim can be derived by first observing that a connection through the three-stage switch requires a middle-stage switch element having an idle link from the first stage and an idle link to the third stage, as shown in Figure 13.5. In C ³ _{n , d , k} , we search for a route realizing a connection request from input x to output y . Thus, the number of outputs of the stage 1 switch elements containing input x that are busy is at most d - 1. This means that there are at most d - 1 middle-stage switch elements that are not accessible form x . Similarly, there are at most d - 1 middle-stage switch elements that are not accessible from y .

Figure 13.5. Analysis of blocking in the three-stage Clos network

Clearly, there are at most 2 d - 2 middle-stage switches that are either not accessible from x or not accessible from y . Hence, the worst-case situation for blocking is that these two sets of middle-stage switch elements are unavailable for connection request ( x , y ). However, if one additional free middle-stage switch element exists as shaded in the figure, that element can be used to set up the connection ( x , y ). Hence if k = ( d - 1) + ( d - 1) + 1 = 2 d - 1, the switch is strictly nonblocking. More generally , at least one middle-stage switch that is accessible from both sides or a state that blocks connection request ( x , y ) can be found if k 2 d - 1. The complexity of the three-stage Clos network is

Equation 13.9

In order to find the complexity of the Clos network under nonblocking conditions, we can substitute k = 2 d - 1 in Equation 13.9. Thus, the complexity of a nonblocking network, , becomes

Equation 13.10

It is always useful to optimize the complexity of switching networks, especially for the nonblocking Clos networks, in which finding the best d would be beneficial. To achieve this goal, we can optimize the network by

Equation 13.11

This procedure releases , which is the absolute minimized value of d . The optimized crosspoint count under this optimization, therefore, is

Equation 13.12

However, the number of crosspoints for large three-stage switches is still quite prohibitive. Large switching systems typically use more than three stages to provide greater reductions in crosspoints. Three-stage Clos networks can be enhanced by substituting another three-stage Clos network for the middle-stage crossbars, resulting in a five-stage Clos network. We can continue in this fashion to construct networks with many stages.

13.4.1. Estimation of Blocking Probabilities

To estimate the internal blocking probability of a Clos network, consider d x k switch elements in the first stage. Figure 13.6 shows a probability graph of a three-stage network. All possible internal paths for an input/output connection pair are shown. For the middle-stage crossbars, the blocking-probability estimation for n parallel links, each with probability p , is generally B = p ⁿ ; for a series of n links, the blocking probability is generally B = 1 - (1 - p) ⁿ . To apply this rule, let p ₁ be the probability that an internal link is busy, as shown in the figure, and thus 1 - p ₁ is the probability that a link is idle. Then, B , the internal blocking probability of the switching network, or the probability that all paths are busy, is

Equation 13.13

Figure 13.6. A blocking model for Clos switching network

We want the traffic load to balance at both sides of each node. Specifically, at the first node, we want the external and internal traffic to be equal, such that kp ₁ = dp or p ₁ = p(d/k) . Using this and Equation (13.13) leads to B in terms of p :

Equation 13.14

Example.	For a Clos network with k = 8, d = 8, and p = 0.8, find the internal blocking probability.
Solution.	Obviously, k/d = 1, and therefore the internal blocking probability B = (1 - (1 - 0.8) ² ) ⁸ = 0.72.

Example.	For the Clos network presented in the previous example, if we add up to 100 percent more crossbar switches into the middle stage of the network, how much reduction in internal blocking probability do we obtain?
Solution.	Since k = 16, d = 8, and p = 0.8, then k/d = 2, and thus B = ( ( 1 - (1 - 0.8 x 1 / 2) ² ) ¹⁶ = 0.0008. The impact is remarkable , as the internal blocking probability is reduced 900 times.

13.4.2. Five-Stage Clos Networks

Figure 13.7 shows a five-stage Clos network obtained by replacing every middle-stage switch element in a three-stage Clos network. This structure provides less complexity, as the complexity of each middle three-stage network has been reduced as was explained for a three-stage network. Note that this statement can be true only if a five-stage switch is strictly nonblocking, where k ₁ 2 d ₁ - 1 and also k ₂ 2 d ₂ - 1. This type of design is especially useful for large-scale switching systems, in which a substantial reduction in the overall complexity of a network is targeted . The blocking probability of a five-stage network is modeled in Figure 13.8 and is determined as follows :

Equation 13.15