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.

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 2X2 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 d1, d2, . . . , dM, 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 Sigmai=1M-Fdiin the worst case even after up to F of the M scaled optical memory cells fail to function properly, where 0 les Fles M - 1. Furthermore, we prove that our multistage construction with the fiber delays d1, d2, . . . , dMgiven 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.

Recently, there has been a lot of attention on the constructions of optical queues by using optical Switches and fiber Delay Lines (SDL). In this paper, we consider the constructions of optical queues with a limited number of recirculations through the fibers in such SDL constructions. Such a limitation on the number of recirculations comes from practical feasibility considerations, such as crosstalk, power loss, amplified spontaneous emission (ASE) from the Erbium doped fiber amplifiers (EDFA), and the pattern effect of the optical switches. We first transform the design of the fiber delays in such SDL constructions to an equivalent integer representation problem. Specifically, given 1 les k les M, we seek for an M-sequence dM1= (d1,d2,...,dm) of positive integers to maximize the number of consecutive integers (starting from 0) that can be represented by the C-transform relative to dM1such that there are at most k 1-entries in their C-transforms. Then we give a class of greedy constructions so that d1, d2,..., dMare obtained recursively and the maximum number of representable consecutive integers by using d1,d2,...,diis larger than that by using d1,d2,...,di-1for all i. Furthermore, we obtain an explicit recursive expression for d1, d2,..., dMgiven by a greedy construction. Finally, we show that an optimal M-sequence (in the sense of achieving the maximum number of representable consecutive integers) can be given by a greedy construction. The solution of such an integer representation problem can be applied to the construction of optical 2-to-l FIFO multiplexers with a limited number of recirculations. We show that the complexity of searching for an optimal construction under our routing policy can be greatly reduced from exponential time to polynomial time by only considering the greedy constructions instead of performing an exhaustive search. Similar results can be obtained for linear compressors and linear decompressors with a limited number of recirculations.

Optical queues, usually constructed by optical switches and fiber delay lines (SDL), are the key elements for conflict resolution in optical packet switching. It is recently shown in the work of Chang et al. (2006) that several optical queues constructed by SDL elements are indeed infinite dimensional switches in time and they can be constructed by many classical constructions in the switching theory. In particular, a (unicast) flexible delay line is a discrete-time infinite-server queue that corresponds to the nonblocking switch in the switching theory, and it can be constructed either by the three-stage Clos network or the Cantor network. In this paper, we propose two new constructions for multicast flexible delay lines that use the unicast flexible delay lines as the basic construction elements. The first one is constructed by using parallel unicast flexible delay lines. It is shown that a multicast flexible delay line with maximum delay d can be constructed by using O(radic/d) unicast flexible delay lines with maximum delay d. Our second construction is a recursive construction. We show that a multicast flexible delay line with maximum delay 2d-1 can be constructed by two unicast flexible delay lines with maximum delay d-1 and a multicast flexible delay line with maximum delay d-1. As an application, we show that multicast flexible delay lines can be used for the constructions of optical multicast switches with 100% throughput.

The constructions of optical buffers is one of the most critically sought after optical technologies in all-optical packet-switched networks, and constructing optical buffers directly via optical switches and fiber delay lines (SDL) has received a lot of attention recently in the literature. A practical and challenging issue of the constructions of optical buffers that has not been addressed before is on the fault tolerant capability of such constructions. In this paper, we focus on the constructions of fault tolerant linear compressors and linear decompressors. The basic network element for our constructions is scaled optical memory cell, which is constructed by a 2 x 2 optical crossbar switch and a fiber delay line. We give a multistage construction of a self-routing linear compressor by a concatenation of scaled optical memory cells. We also show that if the delays, say d1,d2,... ,dm, of the fibers in the scaled optical memory cells satisfy a certain condition (specifically, the condition in (A 2) given in Section I), then our multistage construction can be operated as a self-routing linear compressor with maximum delay SigmaM-Fi=1dieven after up to F of the M scaled optical memory cells fail to function properly, where 0 les F les M - 1. Furthermore, we prove that our multistage construction with the fiber delays d1, d2, ... , dMgiven by the generalized Fibonacci sequence of order F is the best among all 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.