Clos Network

Recently, I heard a term as cloud native.  So I started to research what it means to the network architecture.  It turned out in the LAN or data center, it means to build and run a scalable non-blocking switch fabric with cost effective merchant silicon switches.

One key concept of building a non-blocking switch fabric is to build a Clos network with switches and inter-switch links. I heard about Clos network, but I never get the chance to look into it and to understand how it works.  In order to get that addressed, I spent sometime over the weekend to study the topic.

What is a Clos network?

According to Wikipedia, 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 in 1938 and first formalized by Charles Clos in 1952.

Without Clos network, the number of input lines (bars) and output lines (bars) simply limited the number of input and output of a crossbar switch (bars) a system can handle.  More input or more output will cause a longer line (bar), yet lots of cross points remain open during normal operations.  As you can tell it's difficult or even impossible to build a crossbar switch with lots of input lines and output line.

Sample Crossbar telephone exchange

To address the limitation of such a single stage crossbar telephone exchange, a multistage crossbar switch system was invented.  Each output of the first stage crossbar switch is connected to one of the input of one second stage crossbar switch.  The second stage and next stage.  The more stage the system has, the higher capacaity the system can have.  This eventually forms a Clos network.

Clos network

By introducing the Clos network, the total number of cross point reduced, which also means less building cost.  For example, imaging a system with 20 input line and 20 output line.  There will be 400 crosspoints, 20 each line.

20 x 20 Signgle Stage Crossbar

Now, let's build a three stage Clos network.  The first stage and the last stage are four 10 x 3 crossbar switches.  The second stage are three 2 x 2 crossbar switch.

Three Stage Clos Network

Each 10 x 3 crossbar switch has 30 cross-points, and each 2 x 2 crossbar switch has 4 cross-points.  With this network, there are 132 cross-points.  But please note, this is not a non-blocking Clos network though.

Nonblocking Clos Network

Strict-sense nonblocking Clos network

In order to build a strict-sense nonblocking Clos network, the relation between the number of the input for the first stage switch (n) and the number of the second stage switch (m) need to meet this formula: m ≥ 2n−1.  For a system having 20 input line and 20 output line, we can get this table for the different combinations of n and m.

Hence, in order to have minimum cross-points for the network, the switches for the first stage need to have 4 input lines.

Rearrangeable nonblocking Clos networks

If m ≥ n, 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.

The number of cross-points for the same sample Clos network will look like:

IP Clos Network

To build a scalable IP network, the same Clos network design was being borrowed to the design.  The difference is that now we're using network switches instead of crossbar switches.  The inter-switch links have different capacity as multiple traffic flows can share them.  In short term, the number of links is replaced by the capacity of the links when calculating.

Meta designed a multi stage Clos network as illustrated below to support their business. (see the article for more detailed information.)