Logo image
On Constructions of Optical Priority Queues Under a Priority-Based Routing Policy
期刊文章   同儕審查

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

Jay Cheng, Hsin-Hung Chou, Ling-Chieh Chang, Shin-Shiang Huang, Hsueh-Wen Tseng 和 Cheng-Hao Yang
IEEE transactions on information theory, 卷.71(1), 頁碼.698-736
01/2025
Web of Science ID: WOS:001385350800032

摘要

Delay lines Delays Fault tolerance Fault tolerant systems FIFO multiplexers Multiplexing Optical buffering optical buffers Optical feedback Optical fibers Optical packet switching optical queues Optical switches priority queues Routing
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> <tex-math notation="LaTeX"> (M+2)× (M+2)</tex-math></inline-formula> crossbar switch and M optical fiber delay lines (see <xref ref-type="fig" rid="fig1">Figure 1 in <xref ref-type="sec" rid="sec1">Section I ) 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> <tex-math notation="LaTeX"> 2ᴹ</tex-math></inline-formula>. However, whether this theoretical buffer size <inline-formula> <tex-math notation="LaTeX"> 2ᴹ</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> <tex-math notation="LaTeX"> 2^(O(√α̅ ̅M̅))</tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX"> α </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 priority -based routing policy (see <xref ref-type="fig" rid="fig2">Figure 2 in <xref ref-type="sec" rid="sec1">Section I ). 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> <tex-math notation="LaTeX"> (M+2)× (M+2)</tex-math></inline-formula> crossbar switch and M optical fiber delay lines, and achieve a buffer size <inline-formula> <tex-math notation="LaTeX"> 2^(O(√α̅ ̅M̅))</tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX"> α </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.

相關連結

詳細資料

Logo image