Abstract:

Constructions of optical buffers 

for conflict resolution among packets competing for the same resources

is one of the most important and challenging issue in all-optical packet-switched networks.

Priority queues is one of the most general and versatile buffering schemes,

and includes the most commonly used first-in first-out (FIFO) queues 

and last-in first-out (LIFO) queues as special cases.

The best constructions of optical priority queues 

currently available in the literature 

was given by Cheng \emph{et al.} 

by using a feedback system consisting of 

an optical $(\Sigma_{i=1}^{k}m_i n_i+2) \times (\Sigma_{i=1}^{k}m_i n_i+2)$ 

(bufferless) crossbar switch

and $k$ groups of optical FIFO multiplexers with delay one (FM1's),

where the $i^{\textrm{th}}$ group 

has $m_i$ parallel optical $n_i$-to-1 FM1's ($n_i$FM1's)

with the same buffer size $B_i$ ($B_i\geq 1$) for $i=1,2,\ldots,k$

(see \rfig{PQ-via-FM1} in \rsection{introduction}).

In this paper, we consider an important practical issue

in the constructions of optical priority queues:

the \emph{fault-tolerant capability}.

We consider the scenario that

each group of FM1's has the same number of FM1's,

say, $m_i=m$ for $1\leq i\leq k$,

and show that the optimal construction obtained by Cheng \emph{et al.}

possesses fault-tolerant capability

so that the feedback system can still be operated as 

an optical priority queue but with a \emph{smaller} buffer size 

after up to $f$ FM1's fail to function properly, 

where the fault-tolerant capability $f$ 

can be expressed in terms of the number $m$ of FM1's in each group 

and the numbers $n_1,n_2,\ldots,n_k$ of arrival links of the FM1's in the $k$ groups

as $f=\min_{1\leq i\leq k} \lfloor (m-1)/(n_i-1)\rfloor$.

Such a result can be used in the design of the parameters $m$ and $n_1,n_2,\ldots,n_k$

to provide quality of service (QoS) 

that guarantees a certain level of fault-tolerant capability.