One of the main problems in all-optical packet-switched networks is the lack of optical buffers, and one feasible technology for the constructions of optical buffers is to use optical crossbar Switches and fiber Delay Lines (SDL). In this two-part pa
per, 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. In Part I, we have proposed a class of greedy constructions for certain types of optical queues, including linear compressors, linear decompressors, and 2-to-1 FIFO multiplexers, and have shown that every optimal construction among our previous constructions of these types of optical queues under the constraint of a limited number of recirculations must be a greedy construction. In Part II, the present paper, we further show that there are at most two optimal constructions and give a simple algorithm to obtain the optimal construction(s). The main idea in Part II is to use emph{pairwise comparison} to remove a sequence $dbf_1^Min Gcal_{M,k}$ such that $B(dbf_1^M;k)<B({dbf}_1^M;k)$ for some ${dbf}_1^Min Gcal_{M,k}$. To our surprise, the simple algorithm for obtaining the optimal construction(s) is related to the well-known emph{Euclids algorithm} for finding the greatest common divisor (gcd) of two integers. In particular, we show that if $gcd(M,k)=1$, then there is only one optimal construction; if $gcd(M,k)=2$, then there are two optimal constructions; and if $gcd(M,k)geq 3$, then there are at most two optimal constructions.
In this two-part paper, we consider SDL constructions of optical queues with a limited number of recirculations through the optical switches and the fiber delay lines. We show that the constructions of certain types of optical queues, including linea
r compressors, linear decompressors, and 2-to-1 FIFO multiplexers, under a simple packet routing scheme and under the constraint of a limited number of recirculations can be transformed into equivalent integer representation problems under a corresponding constraint. Given $M$ and $k$, the problem of finding an emph{optimal} construction, in the sense of maximizing the maximum delay (resp., buffer size), among our constructions of linear compressors/decompressors (resp., 2-to-1 FIFO multiplexers) is equivalent to the problem of finding an optimal sequence ${dbf^*}_1^M$ in $Acal_M$ (resp., $Bcal_M$) such that $B({dbf^*}_1^M;k)=max_{dbf_1^Min Acal_M}B(dbf_1^M;k)$ (resp., $B({dbf^*}_1^M;k)=max_{dbf_1^Min Bcal_M}B(dbf_1^M;k)$), where $Acal_M$ (resp., $Bcal_M$) is the set of all sequences of fiber delays allowed in our constructions of linear compressors/decompressors (resp., 2-to-1 FIFO multiplexers). In Part I, we propose a class of emph{greedy} constructions of linear compressors/decompressors and 2-to-1 FIFO multiplexers by specifying a class $Gcal_{M,k}$ of sequences such that $Gcal_{M,k}subseteq Bcal_Msubseteq Acal_M$ and each sequence in $Gcal_{M,k}$ is obtained recursively in a greedy manner. We then show that every optimal construction must be a greedy construction. In Part II, we further show that there are at most two optimal constructions and give a simple algorithm to obtain the optimal construction(s).
