Section 13.1. Characteristics and Features of Switch Fabrics

13.1. Characteristics and Features of Switch Fabrics

The switching function takes place in the switching fabric. The switching structure depends on the need of network operation, available technology, and the required capacity. A switch fabric is an interconnected network of smaller switching units. Several factors can be used to characterize switching systems: buffering, complexity, capability of multipoint connections, speed, performance, cost, reliability, fault tolerance, and scalability. Here, we focus on the topology of the interconnection network as the heart of modern switching systems. The key factors for classifying switching networks are

• Single path versus multipath

• Fixed interstages versus variable interstages

• Deflection routing versus packet discard

• Blocking versus nonblocking

Switching networks are either single-path or multipath networks. A single-path network has exactly one route between each input port and output port. However, this property can be a source of traffic congestion and traffic blocking. In a multipath network, any connection can be established through more than one path. Each of these two groups of networks can be further classified as either single-stage or multistage networks. In a single-stage network, a connection is established through one stage of switching; in a multistage network, a packet must pass through several switching stages. In a multistage network, the number of stages often grows with increasing network size .

13.1.1. Blocking and Nonblocking Networks

A switching network is said to be blocking if an input port cannot be connected to an unused output port. Otherwise, the switching network is nonblocking . A nonblocking switching network can be either of two types. A network is wide-sense nonblocking if any input port can be connected to any unused output port without requiring a path to be rerouted. A network is rearrangeably nonblocking if, for connecting an input port to an unused output port, rearranging other paths may be required. A wide-sense nonblocking network is strictly nonblocking if there is an idle path from any idle input to idle output for all states of the network. Rearangeably nonblocking architectures have a more complex control algorithm to make connections, since fewer switches are used. The complexity of the routing algorithm is a trade-off with cost.

13.1.2. Features of Switch Fabrics

Switching networks have several features and options.

• Switching networks may be either buffered or unbuffered . Buffers may be used to reduce traffic congestion.

• To regulate the flow of packets and prevent buffer overflow, flow control can be provided between stages in a multistage network.

• Discard versus deflection . At each stage of a switching network, a conflict may arise if several packets request the same output. In networks without flow control, arriving packets that cannot be buffered can be either discarded or deflected . Or, these two methods can be combined in a switch.

• Modern switching networks are expected to have the capability of multicasting copying to any subset of the outputsalong with broadcasting .

13.1.3. Complexity of Switching Networks

A useful measure for approximating the cost of a network is to consider the number of crosspoints and links. In practice, the number of crosspoints has greater impact on the cost of the switching network. Thus, complexity refers to the total number of crosspoints used in a switching network. It is important to note that the integrated circuit pin constraints also influence implementation of large-scale networks, especially those with parallel data paths. Practically, a switching network or portions of a network can be placed entirely on a single integrated circuit package. In such cases, the area occupied by the circuits becomes an important complexity measure.

13.1.4. Definitions and Symbols

The topic of switch networking entails a number of definitions and symbols. Consider a network, N , with n inputs and m outputs. This network is referred to as an ( n , m ) network. An ( n , n ) network is referred to as an n network. A connection for a given network is identified by ( x , y ), where x is an input port and y is an output port. Inputs and outputs to a network are numbered in decimal or binary, starting from 0. Switch elements are labeled by ( i , j ), where i is the stage number of the switch, and j is the location of the switch in that stage. We use ( i , j) _h to identify input or output port h on switch ( i , j ).

A network is uniform if all switch elements have the same dimensions and is square if it has the same number of inputs and outputs. The mirror of a network N is denoted N ^m and is obtained by exchanging inputs and outputs and reversing the directions of all links. Consider network N ₁ with n ₁ outputs and network N ₂ with n ₂ inputs. The concatenation of two networks N ₁ and N ₂ is represented by N ₁ + N ₂ and is realized by using output i of N ₁ through input i of N ₂ . If i is a positive integer and N is an ( n , m ) network, i . N realizes the network obtained by taking i copies of N , without interconnecting them. The product term N ₁ x N ₂ is the series connection of N ₁ and N ₂ and is defined by

Equation 13.1

where _{n1, n2} is the permutation among n ₁ and n ₂ points. Similarly, for network N ₁ with n ₁ outputs, network N ₂ with n ₂ inputs and n ₃ outputs, and network N ₃ with n ₁ inputs, the product term N ₁ N ₂ N ₃ is defined as

Equation 13.2

and is called the parallel connection of N ₁ and N ₂ .