Abstract
The constructions of optical queues is one of the most critically sought after optical technologies in all-optical packet-switched networks, and constructing optical queues directly via optical Switches and fiber Delay Lines (SDL) has received a lot of attention recently in the literature. A practical and challenging issue in the constructions of optical queues is on the fault tolerant capability of such constructions. In this paper, we focus on the constructions of fault tolerant optical linear compressors and linear decompressors. The basic network element for our constructions is scaled optical memory cell, which is constructed by a 2 × 2 optical crossbar switch and a fiber delay line. We first obtain a fundamental result on the minimum construction complexity of a linear compressor by using fiber delay lines as the storage devices for the packets queued in the linear compressor. This result shows that one of our previous constructions of a linear compressor by a concatenation of scaled optical memory cells is an optimal construction in the sense of minimizing the construction complexity. However, such an optimal construction lacks the fault tolerant capability. To construct a linear compressor with fault tolerant capability, we give a multistage construction of a self-routing linear compressor by a concatenation of scaled optical memory cells, and show that if the delays, say d i 1, d i 2, ⋯, d M , of the fibers in the scaled optical memory cells satisfy a certain condition (specifically, the condition in (A2) given in Section IV-A), then our multistage construction can be operated as a self-routing linear compressor with maximum delay Σ M-F i=1 d i in the worst case even after up to F of the M scaled optical memory cells fail to function properly, where 0 ≤ F ≤ M-1. Furthermore, we prove that our multistage construction with the fiber delays d i 1, d i 2, ⋯, d i M given by the generalized Fibonacci sequence of order F is the best among all of the constructions of a linear compressor that can tolerate up to F faulty scaled optical memory cells by using M scaled optical memory cells. Similar results are also obtained for the constructions of fault tolerant linear decompressors. © 2009 IEEE.