A brief overview of Back Plane interconnects is discussed in this section. The blog will utilize the Crossbar Switch as the back-plane interconnect for all future references. If you are already familiar with crossbar switches, then feel free to wait for Part 3.
In the early days, transferring packets from one port to another port required transmission across a shared bus that only allowed one port could transmit at a time across the backplane, like is illustrated in Figure 2.
Figure 2: Simple Shared Backplane Bus Router
This worked well when the sum of all the ports bandwidth was much lower than the backplane bus bandwidth. As the number of port grew and the bandwidth of those ports grew, the shared bus backplane could not keep up. The net result was HOLB, where 1 port would be stalled waiting for another port to finish its transfer across the bus. These stalls would eventually lead to loss of transmission bandwidth on the output port. Once you lose a transmit opportunity on the output port, you can never get it back (at least until we invent time travel). There were some stop gap measures, such as adding more shared buses to the system and/or cellifying the data across the bus.
Crossbar Switches (CS)
Most of the high-speed routers begin to use some form of a crossbar switch (CS) fabric for their backplane interconnect. Illustrated in Figure 3, is basic building block, 2x2 Crossbar Switch, for a backplane switch fabric. The advantage of a crossbar switch is that it allows multiple inputs to send data to multiple outputs simultaneously. The rules of the 2x2 CS operation are pretty simple: an input (A or B) can send to one output (X or Y) and an output (X or Y) can be receiving from only one input (A or B) at any given instance in time. This is best illustrated by a truth table as is shown in Table 1 Simple 2x2 Crossbar Switch Truth Table.
Figure 3 Simple 2x2 Crossbar Switch
Table 1 Simple 2x2 Crossbar Switch Truth Table
Note: the illustration and discussion around crossbar switches imply that traffic is always left to right or A/B towards X/Y. This is only to simplify the discussion as the opposite data path exists and is a mirror image.
From this truth table, we can see that we can dramatically improve the HOLB over the shared bus technology as now the input port can reach the output port 75% of the time versus the shared bus that was 50% (essentially the first and last row of truth table). While the CS did not eliminate HOLB, because as the truth table illustrates that when both inputs are targeting the same output port, then one of them has to wait.
Now of course we need to build more complex switch fabrics than a 2x2 CS. But the 2X2 CS can be used to build the larger switch fabrics, like the one shown in Figure 4. Note that it required an extra stage in the switch fabric in order to allow any port to get to any other port. The four crossbar switches are labeled CS-1 thru CS-4. These four CS are then connected via 4 cross links labeled CL-1 thru CL-4. I think one can visually see how any port can connect to any other port in the system. For example, external port A can reach external port Z, by first traversing the crosslink CL-14 to CS-4. This arrangement of 2x2 CS has a fairly large flaw, can you spot it?
Figure 4 Simple 2-Stage 8x8 Crossbar Switch
The flaw is there are actually more HOLB blocking scenarios. Take for example the case where A wants to send to X while B wants to send to Y. This worked for the 2x2 case, but doesn’t for the 4x4 case. The reason is that the CS-1, which connects to ports A & B, has only one connection CL-13 to CS-3, which is connected to ports X and Y. Thus, only A or B can connect to X or Y at any instance in time.
This can be solved by adding a third stage to the switch fabric as is shown in Figure 5. This is often referred to as a CLOS switch fabric. There are other switch fabric designs, such as Benes. I’ll leave it to the reader to work out that this arrangement of 2x2 crossbar switches provides the equivalent non-blocking characteristics of a single 2x2 crossbar switch, in that blocking only occurs when two or more inputs target a single output.