Using Banyan Networks for Load-Balanced Switches with Incremental Update

Load-balanced switches have received a lot of attention lately as they are much more scalable than other existing switch architectures in the literature. One of the most salient features of load-balanced switches is its simplicity of implementing deterministic and periodic connection patterns for the switch fabrics. In particular, for an N × N load-balanced switch, its switch fabric only needs an N × N rotator that is capable of realizing all the powers of the circular shift permutation. In this paper, we consider the problem of incremental update of the number of linecards in load-balanced switches. For this, our idea is to consider a 2^M × 2^M degenerated banyan network that only uses half of the 2^M+1 inputs/outputs in the classical 2^M+1 × 2^M+1 banyan network. We show how one can use the 2^M × 2^M degenerated banyan network as a p × p rotator for any 2 ≤ p ≤ 2M. This is done by a specific rule of placing the p linecards in the 2^M input/output ports of the 2^M × 2^M degenerated banyan network. In special, when p = 2^M, the 2^M × 2^M degenerated banyan network can also be used as a crosstalk-free 2^M × 2^M rotator, where all the routing paths do not share a common node. As such, one can use a 2^M+1 × 2^M+1 banyan network as the switch fabric for a 2^M × 2^M load-balanced switch that is capable of providing incremental update of the number of linecards.