A Load-Balanced Switch with an Arbitrary Number of Linecards

The load-balanced switch architecture is a promising way to scale router capacity. It requires no centralized scheduler, requires no memory operating faster than the line-rate, and can be built using a fixed, optical mesh. In a recent paper we explained how to prevent packet mis-sequencing and provide 100% throughput for all traffic patterns, and described the design of a 100Tb/s router using technology available within three years. But there is one major problem with the load-balanced switch that makes the basic mesh architecture impractical: Because the optical mesh must be uniform, the switch does not work when one or more linecards is missing or has failed. Instead we can use a passive optical switch architecture with MEMS switches that are reconfigured only when linecards are added and deleted, allowing the router to function when any subset of linecards is present and working. In this paper we derive an expression for the number of MEMS switches that are needed, and describe an algorithm to configure them. We prove that the algorithm will always find a correct configuration in polynomial time, and show examples of its running time