Tuesday, January 21, 2014

Telecommunication networks

1Crossbar switches¶

The simplest kind of telecommunication network is a crossbar switch. This is essentially a complete bipartite graph (aka a bipartite clique), with $N$ input ports, $N$ output ports, and each input port connected to each output port.

Clearly, this sort of switch can route any permutation (encoding a set of input/output port pairings). On the minus side, this sort of switch is quite expensive to build as you need $N^2$ connections. Furthermore, there is a large number of crossovers¹; this is also expensive and can even decrease performance.

To find how many crossovers there are, consider the following: every link from the top half of the input side to the bottom half of the output side crosses at least $N/2$. So there are at least $(N/2)^4$ crossovers. There may even be more - the top half can crossover with the top half. But there are at least $\Omega(N^4)$ crossovers. (It can't be $\Omega(N^5)$, since we're limited by the number of actual wires. I'm not entirely convinced by this reasoning but I can't find any information on it elsewhere so who knows.

1.1Clos networks¶

A Clos network is a network that incorporates many small crossbar switches, encoded in 3 stages. Example:

Let $r \times n = N$. We will use this new connection scheme to improve on the $N\times N$ crossbar switch scheme we saw earlier.

The crossbar stages are connected by 2 perfect matchings. Between stages 1 and 2, the output $i$ of crossbar $j$ connects to input $j$ of crossbar $i$. The same is true between stages 2 and 3.

Let's now analyse the cost of this network. Suppose $r = n = m = \sqrt{N}$, so that we have $N$ inputs and outputs. We would have $3\sqrt{N}$ crossbars total. Since each crossbar has $N$ edges, we'd get on the order of $N^2$ crossovers. So the total number of edges is $3\sqrt{N} \cdot N$ and the total number of crossovers is on the order of $3\sqrt{N} \cdot N^2$, thus, we have $O(N^{3/2})$ edges and $O(N^{5/2})$ crossovers.² (We also have $2N$ edges in between stages, but the $2N$ is negligible compared to the $3N^{3/2}$ so we omit it. Also, the crossovers from edges between stages is only $N^2$ at most, which is also negligible.) This is quite an improvement over the standard crossbar switch.

Now we have to prove that a Clos networks actually works, i.e., that any incoming packet can be routed to any output port. In other words, can we route any permutation $\Pi$ of $[N] = \{1, 2, \ldots, N\}$?

1.2Online routing¶

Suppose we're given some permutation $\Pi$ in pairs $(i, \Pi_i)$, one at a time. For example, if $\Pi = 365491827$, then we'd be given the pairs in some order, e.g., $(9, 7)$, $(2, 6)$, $(4, 4)$, etc.

We must decide on a path for a packet immediately when that pair arrives. For example, when we receive the pair $(9, 7)$, we must find a path from 9 to 7. All the paths that we choose must be vertex-disjoint, to prevent blockage.

Theorem: If $m = 2n-1$, then all packets can be routed online.

Proof: Suppose we have already routed $k \leq N-1$ packets, in a vertex-disjoint fashion. Take the new packet $s$, which has destination $\Pi_s = t$.

Suppose $s$ is in crossbar $A$ (in stage 1), and $t$ is in crossbar $B$ (in stage 3).

Now, $A$ has $\leq n-1$ inputs being used so far, and $m$ outputs total. The number of outputs that are free is given by $m - (n-1) = (2n-1) - (n-1) = n$, so there are $n$ outputs available in $A$.

Similarly, there are $\geq n$ inputs of $B$ available. There are $m$ crossbars in the middle. $n-1$ of them can't be used by $A$; $n-1$ can't be used by $B$. But $n$ are connected to $A$, and $n$ are connected to $B$. By the pigeonhole principle, at least one of the middle crossbars is connected to both $A$ and $B$. We call that crossbar $C$. Then we just route the packet from $A$ to $B$ through $C$. $\blacksquare$

1.3Offline routing¶

Suppose we are given the entire permutation at once and thus can decide all the paths at the same time (aka rearrangeable routing). Let $m = r = n = \sqrt{N}$. From $\Pi$, create an $r\times r$ bipartite graph, and create an edge between $i$ and $\Pi_i$ for each pair $(i, \Pi_i)$.

The resulting graph $G$ is $n$-regular. We showed earlier that we can apply Hall's theorem to regular bipartite graphs. So $G$ decomposes into $n$ perfect matchings. We can use one of the middle crossbars for each perfect matching, which gives us a valid routing, as desired.

1.4Benes networks¶

We saw that dividing a crossbar switch into 3 layers reduces the number of edges and crossovers. What if we were to divide each layer into sublayers? If we keep iterating until we get $2\times 2$ crossbars, then the result is a Benes network. I assume this will be covered next class.