Using Banyan Networks for Load-Balanced Switches with Incremental Update
C.-M. Lien, Cheng‐Shang Chang, Jay Cheng, D.-S. Lee, J.-T. Liao · 2010
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 2M× 2Mdegenerated banyan network that only uses half of the 2M+1inputs/outputs in the classical 2M+1× 2M+1banyan network. We show how one can use the 2M× 2Mdegenerated 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 2Minput/output ports of the 2M× 2Mdegenerated banyan network. In special, when p = 2M, the 2M× 2Mdegenerated banyan network can also be used as a crosstalk-free 2M× 2Mrotator, where all the routing paths do not share a common node. As such, one can use a 2M+1× 2M+1banyan network as the switch fabric for a 2M× 2Mload-balanced switch that is capable of providing incremental update of the number of linecards.