A Necessary and Sufficient Condition for the Construction of 2-to-1 Optical FIFO Multiplexers by a Single Crossbar Switch and Fiber Delay Lines

In this paper, we prove a necessary and sufficient condition for the construction of 2-to-1 optical buffered first-in-first-out (FIFO) multiplexers by a single crossbar switch and fiber delay lines. We consider a feedback system consisting of an (M+2)times(M+2) crossbar switch and M fiber delay lines with delays d₁,d₂,...,d_M. These M fiber delay lines are connected from M outputs of the crossbar switch back to M inputs of the switch, leaving two inputs (respectively, two outputs) of the switch for the two inputs (respectively, two outputs) of the 2-to-1 multiplexer. The main contribution of this paper is the formal proof that d₁=1 and d_i les d_i+1 les 2d _i, i=1,2,...,M-1, is a necessary and sufficient condition on the delays d₁,d₂,...,d_M for such a feedback system to be operated as a 2-to-1 FIFO multiplexer with buffer Sigma_i=1 ^Md_i under a simple packet routing policy. Specifically, the routing of a packet is according to a specific decomposition of the packet delay, called the C- transform in this paper. Our result shows that under such a feedback architecture a 2-to-1 FIFO multiplexer can be constructed with M=O(log B), where B is the buffer size. Therefore, our construction improves on a more complicated construction recently proposed by Sarwate and Anantharam that requires M=O(radicB) under the same feedback architecture (we note that their design is more general and works for priority queues)