Clos network

Last updated

In the field of telecommunications, a Clos network is a kind of multistage circuit-switching network which represents a theoretical idealization of practical, multistage switching systems. It was invented by Edson Erwin [1] in 1938 and first formalized by the American [2] engineer Charles Clos [3] in 1952.

Contents

By adding stages, a Clos network reduces the number of crosspoints required to compose a large crossbar switch. A Clos network topology (diagrammed below) is parameterized by three integers n, m, and r: n represents the number of sources which feed into each of r ingress stage crossbar switches; each ingress stage crossbar switch has m outlets; and there are m middle stage crossbar switches.

Circuit switching arranges a dedicated communications path for a connection between endpoints for the duration of the connection. This sacrifices total bandwidth available if the dedicated connections are poorly utilized, but makes the connection and bandwidth more predictable, and only introduces control overhead when the connections are initiated, rather than with every packet handled, as in modern packet-switched networks.

When the Clos network was first devised, the number of crosspoints was a good approximation of the total cost of the switching system. While this was important for electromechanical crossbars, it became less relevant with the advent of VLSI, wherein the interconnects could be implemented either directly in silicon, or within a relatively small cluster of boards. Upon the advent of complex data centers, with huge interconnect structures, each based on optical fiber links, Clos networks regained importance. [4] A subtype of Clos network, the Beneš network, has also found recent application in machine learning. [5]

Topology

Clos networks have three stages: the ingress stage, the middle stage, and the egress stage. Each stage is made up of a number of crossbar switches (see diagram below), often just called crossbars. The network implements an r-way perfect shuffle between stages. Each call entering an ingress crossbar switch can be routed through any of the available middle stage crossbar switches, to the relevant egress crossbar switch. A middle stage crossbar is available for a particular new call if both the link connecting the ingress switch to the middle stage switch, and the link connecting the middle stage switch to the egress switch, are free.

Closnetwork.png

Clos networks are defined by three integers n, m, and r. n represents the number of sources which feed into each of r ingress stage crossbar switches. Each ingress stage crossbar switch has m outlets, and there are m middle stage crossbar switches. There is exactly one connection between each ingress stage switch and each middle stage switch. There are r egress stage switches, each with m inputs and n outputs. Each middle stage switch is connected exactly once to each egress stage switch. Thus, the ingress stage has r switches, each of which has n inputs and m outputs. The middle stage has m switches, each of which has r inputs and r outputs. The egress stage has r switches, each of which has m inputs and n outputs.

Blocking characteristics

The relative values of m and n define the blocking characteristics of the Clos network.

Strict-sense nonblocking Clos networks (m 2n1): the original 1953 Clos result

If m  2n1, the Clos network is strict-sense nonblocking, meaning that an unused input on an ingress switch can always be connected to an unused output on an egress switch, without having to re-arrange existing calls. This is the result which formed the basis of Clos's classic 1953 paper. Assume that there is a free terminal on the input of an ingress switch, and this has to be connected to a free terminal on a particular egress switch. In the worst case, n1 other calls are active on the ingress switch in question, and n1 other calls are active on the egress switch in question. Assume, also in the worst case, that each of these calls passes through a different middle-stage switch. Hence in the worst case, 2n2 of the middle stage switches are unable to carry the new call. Therefore, to ensure strict-sense nonblocking operation, another middle stage switch is required, making a total of 2n1.

The below diagram shows the worst case when the already established calls (blue and red) are passing different middle-stage switches, so another middle-stage switch is necessary to establish a call between the green input and output.

Strict-sense-nonblocking-clos-network.svg

Rearrangeably nonblocking Clos networks (mn)

If mn, the Clos network is rearrangeably nonblocking, meaning that an unused input on an ingress switch can always be connected to an unused output on an egress switch, but for this to take place, existing calls may have to be rearranged by assigning them to different centre stage switches in the Clos network. [6] To prove this, it is sufficient to consider m = n, with the Clos network fully utilised; that is, r×n calls in progress. The proof shows how any permutation of these r×n input terminals onto r×n output terminals may be broken down into smaller permutations which may each be implemented by the individual crossbar switches in a Clos network with m = n.

The proof uses Hall's marriage theorem [7] which is given this name because it is often explained as follows. Suppose there are r boys and r girls. The theorem states that if every subset of k boys (for each k such that 0 ≤ kr) between them know k or more girls, then each boy can be paired off with a girl that he knows. It is obvious that this is a necessary condition for pairing to take place; what is surprising is that it is sufficient.

In the context of a Clos network, each boy represents an ingress switch, and each girl represents an egress switch. A boy is said to know a girl if the corresponding ingress and egress switches carry the same call. Each set of k boys must know at least k girls because k ingress switches are carrying k×n calls and these cannot be carried by less than k egress switches. Hence each ingress switch can be paired off with an egress switch that carries the same call, via a one-to-one mapping. These r calls can be carried by one middle-stage switch. If this middle-stage switch is now removed from the Clos network, m is reduced by 1, and we are left with a smaller Clos network. The process then repeats itself until m = 1, and every call is assigned to a middle-stage switch.

Blocking probabilities: the Lee and Jacobaeus approximations

Real telephone switching systems are rarely strict-sense nonblocking for reasons of cost, and they have a small probability of blocking, which may be evaluated by the Lee or Jacobaeus approximations, [8] assuming no rearrangements of existing calls. Here, the potential number of other active calls on each ingress or egress switch is u = n1.

In the Lee approximation, it is assumed that each internal link between stages is already occupied by a call with a certain probability p, and that this is completely independent between different links. This overestimates the blocking probability, particularly for small r. The probability that a given internal link is busy is p = uq/m, where q is the probability that an ingress or egress link is busy. Conversely, the probability that a link is free is 1p. The probability that the path connecting an ingress switch to an egress switch via a particular middle stage switch is free is the probability that both links are free, (1p)2. Hence the probability of it being unavailable is 1(1p)2 = 2pp2. The probability of blocking, or the probability that no such path is free, is then [1(1p)2]m.

The Jacobaeus approximation is more accurate, and to see how it is derived, assume that some particular mapping of calls entering the Clos network (input calls) already exists onto middle stage switches. This reflects the fact that only the relative configurations of ingress switch and egress switches is of relevance. There are i input calls entering via the same ingress switch as the free input terminal to be connected, and there are j calls leaving the Clos network (output calls) via the same egress switch as the free output terminal to be connected. Hence 0 ≤ iu, and 0 ≤ ju.

Let A be the number of ways of assigning the j output calls to the m middle stage switches. Let B be the number of these assignments which result in blocking. This is the number of cases in which the remaining mj middle stage switches coincide with mj of the i input calls, which is the number of subsets containing mj of these calls. Then the probability of blocking is:

If fi is the probability that i other calls are already active on the ingress switch, and gj is the probability that j other calls are already active on the egress switch, the overall blocking probability is:

This may be evaluated with fi and gj each being denoted by a binomial distribution. After considerable algebraic manipulation, this may be written as:

Clos networks with more than three stages

Clos networks may also be generalised to any odd number of stages. By replacing each centre stage crossbar switch with a 3-stage Clos network, Clos networks of five stages may be constructed. By applying the same process repeatedly, 7, 9, 11,... stages are possible.

Beneš network (m = n = 2)

A rearrangeably nonblocking network of this type with m = n = 2 is generally called a Beneš network, even though it was discussed and analyzed by others[ who? ] before Václav E. Beneš. The number of inputs and outputs is N = r×n = 2r. Such networks have 2log2N 1 stages, each containing N/2 2×2 crossbar switches, and use a total of Nlog2NN/2 2×2 crossbar switches. For example, an 8×8 Beneš network (i.e. with N = 8) is shown below; it has 2log28 1 = 5 stages, each containing N/2 = 4 2×2 crossbar switches, and it uses a total of Nlog2NN/2 = 20 2×2 crossbar switches. The central three stages consist of two smaller 4×4 Beneš networks, while in the center stage, each 2×2 crossbar switch may itself be regarded as a 2×2 Beneš network. This example therefore highlights the recursive construction of this type of network.

Benesnetwork.png

See also

Related Research Articles

<span class="mw-page-title-main">Multiplexer</span> A device that selects between several analog or digital input signals

In electronics, a multiplexer, also known as a data selector, is a device that selects between several analog or digital input signals and forwards the selected input to a single output line. The selection is directed by a separate set of digital inputs known as select lines. A multiplexer of inputs has select lines, which are used to select which input line to send to the output.

<span class="mw-page-title-main">Crossbar switch</span> Collection of electronic switches arranged in a matrix

In electronics and telecommunications, a crossbar switch is a collection of switches arranged in a matrix configuration. A crossbar switch has multiple input and output lines that form a crossed pattern of interconnecting lines between which a connection may be established by closing a switch located at each intersection, the elements of the matrix. Originally, a crossbar switch consisted literally of crossing metal bars that provided the input and output paths. Later implementations achieved the same switching topology in solid-state electronics. The crossbar switch is one of the principal telephone exchange architectures, together with a rotary switch, memory switch, and a crossover switch.

In quantum computing, Grover's algorithm, also known as the quantum search algorithm, is a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just evaluations of the function, where is the size of the function's domain. It was devised by Lov Grover in 1996.

In machine learning, the perceptron is an algorithm for supervised learning of binary classifiers. A binary classifier is a function which can decide whether or not an input, represented by a vector of numbers, belongs to some specific class. It is a type of linear classifier, i.e. a classification algorithm that makes its predictions based on a linear predictor function combining a set of weights with the feature vector.

<span class="mw-page-title-main">Nonblocking minimal spanning switch</span>

A nonblocking minimal spanning switch is a device that can connect N inputs to N outputs in any combination. The most familiar use of switches of this type is in a telephone exchange. The term "non-blocking" means that if it is not defective, it can always make the connection. The term "minimal" means that it has the fewest possible components, and therefore the minimal expense.

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output are random variables.

In electronics, a banyan switch is a complex crossover switch used in electrical or optical switches.

In electronics, a crossover switch or matrix switch is a switch connecting multiple inputs to multiple outputs using complex array matrices designed to switch any one input path to any one output path(s). There are blocking and non-blocking types of cross-over switches.

A load-balanced switch is a switch architecture which guarantees 100% throughput with no central arbitration at all, at the cost of sending each packet across the crossbar twice. Load-balanced switches are a subject of research for large routers scaled past the point of practical central arbitration.

<span class="mw-page-title-main">Omega network</span> Form of network configuration

An Omega network is a network configuration often used in parallel computing architectures. It is an indirect topology that relies on the perfect shuffle interconnection algorithm.

The Number One Crossbar Switching System (1XB), was the primary technology for urban telephone exchanges served by the Bell System in the mid-20th century. Its switch fabric used the electromechanical crossbar switch to implement the topology of the panel switching system of the 1920s. The first No. 1 Crossbar was installed in the PResident-2 central office at Troy Avenue in Brooklyn, New York which became operational in February 1938.

<span class="mw-page-title-main">Number One Electronic Switching System</span> Defunct telecommunications node in the United States; part of the Bell System

The Number One Electronic Switching System (1ESS) was the first large-scale stored program control (SPC) telephone exchange or electronic switching system in the Bell System. It was manufactured by Western Electric and first placed into service in Succasunna, New Jersey, in May 1965. The switching fabric was composed of a reed relay matrix controlled by wire spring relays which in turn were controlled by a central processing unit (CPU).

<span class="mw-page-title-main">Data plane</span> Router architecture

In routing, the data plane, sometimes called the forwarding plane or user plane, defines the part of the router architecture that decides what to do with packets arriving on an inbound interface. Most commonly, it refers to a table in which the router looks up the destination address of the incoming packet and retrieves the information necessary to determine the path from the receiving element, through the internal forwarding fabric of the router, and to the proper outgoing interface(s).

Virtual output queueing (VOQ) is a technique used in certain network switch architectures where, rather than keeping all traffic in a single queue, separate queues are maintained for each possible output location. It addresses a common problem known as head-of-line blocking.

Multistage interconnection networks (MINs) are a class of high-speed computer networks usually composed of processing elements (PEs) on one end of the network and memory elements (MEs) on the other end, connected by switching elements (SEs). The switching elements themselves are usually connected to each other in stages, hence the name.

A time-slot interchange (TSI) switch is a network switch that stores data in RAM in one sequence, and reads it out in a different sequence. It uses RAM, a small routing memory and a counter. Like any switch, it has input and output ports. The RAM stores the packets or other data that arrive via its input terminal.

<span class="mw-page-title-main">Flip-flop (electronics)</span> Electronic circuit with two stable states

In electronics, flip-flops and latches are circuits that have two stable states that can store state information – a bistable multivibrator. The circuit can be made to change state by signals applied to one or more control inputs and will output its state. It is the basic storage element in sequential logic. Flip-flops and latches are fundamental building blocks of digital electronics systems used in computers, communications, and many other types of systems.

In computing, a logic block or configurable logic block (CLB) is a fundamental building block of field-programmable gate array (FPGA) technology. Logic blocks can be configured by the engineer to provide reconfigurable logic gates.

The STC104 switch, also known as the C104 switch in its early phases, is an asynchronous packet-routing chip that was designed for building high-performance point-to-point computer communication networks. It was developed by INMOS in the 1990s and was the first example of a general-purpose production packet routing chip. It was also the first routing chip to implement wormhole routing, to decouple packet size from the flow-control protocol, and to implement interval and two-phase randomized routing.

A capsule neural network (CapsNet) is a machine learning system that is a type of artificial neural network (ANN) that can be used to better model hierarchical relationships. The approach is an attempt to more closely mimic biological neural organization.

References

  1. USpatent 2244004
  2. "Place of birth New York", United States census,1940;New York, Queens; page 41-320-19A, line 17.
  3. Clos, Charles (Mar 1953). "A study of non-blocking switching networks". Bell System Technical Journal . 32 (2): 406–424. doi:10.1002/j.1538-7305.1953.tb01433.x. ISSN   0005-8580.
  4. Hogg, Scott (2014-01-11). "Clos Networks: What's Old Is New Again". Network World.
  5. Moore, Samuel (31 October 2018). "Flex Logix Says It Has Solved Deep Learning's DRAM Problem". IEEE . IEEE Spectrum . Retrieved 1 November 2018.
  6. Beneš, Václav E. (11 September 1965). Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press. ISBN   0-12-087550-0.
  7. Hall, Philip (January 1935). "On Representatives of Subsets" (PDF). Journal of the London Mathematical Society. s1. 10 (1): 26–30. doi:10.1112/jlms/s1-10.37.26 . Retrieved 2015-06-18.
  8. Hui, Joseph Y. (1990). Switching and Traffic Theory for Integrated Broadband Networks. Kluwer Academic. ISBN   0-7923-9061-X.