Constructions of Optical Queues With a Limited Number of Recirculations--Part I: Greedy Constructions

Details Constructions of Optical Queues With a Limited Number of Recirculations--Part I: Greedy Constructions Constructions of Optical Queues With a Limited Number of Recirculations--Part I: Greedy Constructions

2010-04-23

arxiv.org/abs/1004.4070v1

Computer Science

Information Theory

59 pages; 1 figure; This paper was presented in part at the IEEE International Conference on Computer Communications (INFOCOM'

Scientific paper

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 linear 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^M\in \Acal_M}B(\dbf_1^M;k)$ (resp., $B({\dbf^*}_1^M;k)=\max_{\dbf_1^M\in \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_M\subseteq \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).

Affiliated with

Also associated with

No associations

Rating

Constructions of Optical Queues With a Limited Number of Recirculations--Part I: Greedy Constructions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Constructions of Optical Queues With a Limited Number of Recirculations--Part I: Greedy Constructions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constructions of Optical Queues With a Limited Number of Recirculations--Part I: Greedy Constructions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-694200