Greedy Constructions of Optical Queues With a Limited Number of Recirculations

One of the main problems in all-optical packet-switched networks is the lack of optical buffers, and currently the only known feasible technology for the constructions of optical buffers is to use optical crossbar Switches and fiber Delay Lines (SDLs). In this paper, we consider SDL constructions of optical queues with a limited number of recirculations through the optical switches and the fiber delay lines. Such a problem arises from practical feasibility considerations, such as crosstalk, power loss, amplified spontaneous emission from the Erbium doped fiber amplifiers, and the pattern effect of the optical switches. We first transform the design of the fiber delays in such SDL constructions into an equivalent integer representation problem. Specifically, given $1\leq k\leq M$ , we seek for an $M$ -sequence ${\mathbf{d}}_{M}=(d_{1},d_{2},\ldots, d_{M})$ of positive integers to maximize the number of consecutive integers (starting from 0) that can be represented by the ${\mathcal{ C}}$ -transform (a generalization of the well-known binary representation) with respect to ${\mathbf{d}}_{M}$ such that there are at most $k$ 1-entries in their ${\mathcal{ C}}$ -transforms. Then, we propose a class of greedy constructions of ${\mathbf{d}}_{M}$ , in which $d_{1},d_{2},\ldots, d_{M}$ are obtained recursively in a greedy manner so that the number of representable consecutive integers by using $d_{1},d_{2},\ldots, d_{i}$ is larger than that by using $d_{1},d_{2},\ldots, d_{i-1}$ for all $i$ . Finally, we show that every optimal construction (in the sense of maximizing the number of representable consecutive integers) must be a greedy construction. As a result, the complexity of searching for an optimal construction can be greatly reduced from exponential time to polynomial time by only considering the greedy constructions rather than performing an exhaustive search. The solution of such an integer representation problem can be applied to the constructions of optical 2-to-1 FIFO multiplexers with a limited number of recirculations. Similar results can be obtained for the constructions of optical linear compressors/decompressors with a limited number of recirculations.