The design of optical buffers for packet contention resolution has been recognized as a key issue in all-optical packet switching. One of the most general buffering schemes is priority queues, which includes first-in first-out (FIFO) queues and last-in first-out (LIFO) queues as special cases. In a priority queue, each packet is associated with a unique priority upon its arrival, the packet with thehighestpriority is sent out from the queue whenever there is a departure request and there are packets in the queue, and the packet with thelowestpriority is dumped from the queue whenever there is a buffer overflow. In this paper, we consider the constructions of optical priority queues by using a feedback system consisting of an optical (bufferless) crossbar switch and multiple optical FIFO multiplexers with delay one (FM1’s) in the feedback path for buffering packets and feeding packets back to the switch. Such a feedback system is a generalization of that used in one of the authors’ earlier attempt for the constructions of optical priority queues in Tanget al.(2020). We fix theno-bufferingproblem in Tanget al.(2020) by using optical FM1’s to replace the optical FIFO multiplexers (FM’s) in Tanget al.(2020), which enables us to successfully achieve an exact emulation of a priority queue. We improve the utilization of buffering capacity over that in Tanget al.(2020) by routing packets to the optical FM1’s according to theirbuffering tagsinstead of theirtagsas used in Tanget al.(2020). We also extend and generalize the construction in Tanget al.(2020) and obtain a much larger class of constructions of optical priority queues. Our constructions are made possible by showing that the highest-priority (resp., lowest-priority) packet is always available at the input links of the switch whenever it needs to be routed to the departure (resp., loss) link, and by showing that there is no collision and there is no buffer overflow at any FM1 at any time so that there is no internal packet loss at any time. Our complexity analysis shows that by using a feedback system consisting of an optical$(M+2) \times (M+2)$(bufferless) crossbar switch and$M$fiber delay lines, we can achieve a buffer size of$2^{O(\sqrt {\alpha M})}$, where$\alpha $is a constant that depends on the parameters used in our constructions. Furthermore, we show that the best buffer size that we can achieve is$2^{O(\sqrt {4M/15})}$. Our result (exponential in$\sqrt {M}$) substantially improves on the best known result (polynomial in$M$) in the literature. Our numerical results show that the construction complexity of our constructions is lower than that of the construction in Tanget al.(2020), and the actual saving, in terms of the number of$2\times 2$switches needed, by our constructions could be quite significant even in the tiny-buffer and small-buffer regimes.

One of the main problems in all-optical packetswitched 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 ≤ k ≤ M, we seek for an M-sequence dM= (d1, d2, ..., dM) of positive integers to maximize the number of consecutive integers (starting from 0) that can be represented by the C-transform (a generalization of the well-known binary representation) with respect to dMsuch that there are at most k 1-entries in their C-transforms. Then, we propose a class of greedy constructions of dM, in which d1, d2, ..., dMare obtained recursively in a greedy manner so that the number of representable consecutive integers by using d1, d2, . .., diis larger than that by using d1, d2, . .., di-1for 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.