Constructions of Optical 2-to-1 FIFO Multiplexers With a Limited Number of Recirculations

摘要

Recently, there has been a lot of attention in the literature on a less well-known aspect of queueing theory, the theory of the constructions of queues. Such an interest originates mainly from optical packet switching due to the lack of optical buffers. These constructions of optical queues are based on optical switches and fiber delay lines (SDL). Theoretical studies in the SDL constructions have been recently reported for the constructions of various types of optical queues, including output-buffered switches, first-in-first-out (FIFO) multiplexers, FIFO queues, last-in-first-out (LIFO) queues, priority queues, linear compressors, nonovertaking delay lines, and flexible delay lines. In this paper, we consider the constructions of optical 2-to-1 FIFO multiplexers with a limited number of recirculations through the fibers, which is a very important practical feasibility issue on the constructions of optical queues that has not been theoretically addressed before. Specifically, we consider the constructions of optical 2-to-1 FIFO multiplexers with buffer size at least 2n-1 by using a feedback system consisting of an (M+2)times(M+2) optical crossbar switch and M fiber delay lines under a simple packet routing policy and under the limitation that each packet can be recirculated through the M fibers at most k times. In one of our previous works, we have shown that this can be done by using n fibers with delays 1, 2, 22,..., 2n-1 if there is no limitation on the number of recirculations through the fibers. The main idea in our constructions in this paper is to use extra fibers (other than the n fibers with delays 1, 2, 22,..., 2n-1) with appropriately chosen delays to emulate the effective delays of the concatenations of some of the n fibers with delays 1, 2, 22,..., 2n-1 so that the number of recirculations is reduced by so doing. It turns out that the number of fibers needed and their delays a- - re determined based on a dynamic programming formulation obtained through a divide-and-conquer approach. We obtain a closed-form expression for the number of fibers needed in our constructions, and show that there are (r k) possible choices for the delays of the required fibers, where r is the remainder of n divided by k. Furthermore, we give the optimal choice of the fiber delays that achieves the maximum buffer size among the (r k) possible choices. Finally, we show that when n=k or nges2k, such an optimal choice also requires the minimum total fiber length among the (r k) possible choices