On Constructions of Optical Priority Queues Under a Priority-Based Routing Policy

In this paper, we consider Switched-Delay-Lines (SDL) constructions of optical priority queues by using optical (bufferless) crossbar switches and optical fiber delay lines. In a priority queue, each packet is associated with a priority upon its arrival, the highest-priority packet is sent out from the queue whenever there is a departure request, and the lowest-priority packet is dropped from the queue whenever there is a buffer overflow. Given any system for SDL constructions of optical priority queues, the main research problem is twofold: (i) the design of the routing policy performed by the optical crossbar switches; (ii) the choice of the delays of the optical fiber delay lines. Sarwate and Anantharam are the first to propose a feedback system consisting of an optical <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(M+2)\times (M+2)$ </tex-math></inline-formula> crossbar switch and M optical fiber delay lines (see <xref ref-type="fig" rid="fig1" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Figure 1</xref> in <xref ref-type="sec" rid="sec1" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Section I</xref>) for SDL constructions of optical priority queues, and they have shown that the largest buffer size that can possibly be achieved by using such a feedback system is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2^{M}$ </tex-math></inline-formula>. However, whether this theoretical buffer size <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2^{M}$ </tex-math></inline-formula> can be achieved or not remains an open research problem. Currently, the best result in the literature was obtained by Cheng et al. and the achieved buffer size is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2^{O(\sqrt {\alpha M})}$ </tex-math></inline-formula>, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula> is a constant that depends on the parameters used in their constructions. In this paper, we consider a discrete-time setting and use a feedback system consisting of an optical crossbar switch and multiple groups of optical first-in first-out (FIFO) multiplexers with delay one (FM1’s) for SDL constructions of optical priority queues under a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">priority</i>-based routing policy (see <xref ref-type="fig" rid="fig2" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Figure 2</xref> in <xref ref-type="sec" rid="sec1" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Section I</xref>). Our contributions are as follows: (i) We extend and generalize an important class of constructions that contains the optimal constructions in the work of Cheng et al. As a result, we achieve larger buffer sizes and less construction complexities/costs than those by Cheng et al. (ii) We obtain a closed-form expression for the maximum buffer size that is achieved by the optimal construction for the scenario that each group of FM1’s has the same number of FM1’s. (iii) Our constructions possess a salient feature, namely, fault-tolerant capability, that can tolerate the malfunctioning of some FM1’s by using the generalized results obtained in this paper. (iv) We show that our constructions can be implemented by using an optical <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(M+2)\times (M+2)$ </tex-math></inline-formula> crossbar switch and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</i> optical fiber delay lines, and achieve a buffer size <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2^{O(\sqrt {\alpha M})}$ </tex-math></inline-formula>, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula> is a constant that depends on the parameters used in our constructions and is better, i.e., larger, than that in the work of Cheng et al. in a very broad regime.