| | |
| | |
Stat |
Members: 3645 Articles: 2'504'928 Articles rated: 2609
25 April 2024 |
|
| | | |
|
Article overview
| |
|
Constructions of Optical Queues With a Limited Number of Recirculations--Part I: Greedy Constructions | Jay Cheng
; Cheng-Shang Chang
; Sheng-Hua Yang
; Tsz-Hsuan Chao
; Duan-Shin Lee
; Ching-Min Lien
; | Date: |
23 Apr 2010 | Abstract: | 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^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). | Source: | arXiv, 1004.4070 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |