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_1, d_2,ldots, 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=1$and$d_i le d_i+1 le 2d_i$,$i=1,2, ldots, M-1$, is a necessary and sufficient condition on the delays$d_1, d_2,ldots,d_M$for such a feedback system to be operated as a 2-to-1 FIFO multiplexer with buffer$sum _i=1^M d_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$cal 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(sqrt B)$under the same feedback architecture (we note that their design is more general and works for priority queues).