Constructions of Optical Queues With a Limited Number of Recirculations-Part I: Greedy Constructions

One of the main problems in all-optical packet-switched networks is the lack of optical buffers, and one feasible technology for the constructions of optical buffers is to use optical crossbar Switches and fiber Delay Lines (SDL). In this two-part paper, we consid er 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 . We show that the constructions of certain types of optical queues, including linear compressors, linear de compressors, and 2-to-1 FIFO multiplexers, under a simple packet routing scheme and under the constraint of a limited number of recirculations can be transformed into equivalent integer representation pro blems under a corresponding constraint. Specifically, we show that the effective maximum delay of a linear compressor/decompressor and the effective buffer size of a 2-to-1 FIFO multiplexer in our constructions are equal to the maximum representable integer B(d M ;k) with respect to d M and k (defined in (4) in Section I), where d M = (d1,d2,...,dM) is the sequence of the delays of the M fibers used in our constructions and k is the maximum number of times that a packet can be routed through the M fibers. Given M and k, therefore, the problem of finding an optimal construction, in the sense of maximizing the maximum delay (resp., buffer size), among our constructions of linear compressors/decompressors (