A New Upper Bound on the Buffer Sizes of SDL Constructions of Optical Priority Queues

In this work, we obtain a new upper bound on the buffer sizes of Switched-Delay-Lines (SDL) designs of optical priority queues (PQs) that use a feedback architecture comprised of an optical switch and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M$</tex> fiber delay lines (FDLs). Currently, the best designs available in the literature with such an architecture have a buffer size of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{O(\sqrt{M})}$</tex>. To understand how close the best known designs are to the best possible designs of optical PQs, we need to know the maximum buffer size that is implemented with such an architecture. The contribution of this work is to obtain a new upper bound of 2M -1 on the buffer sizes that can be implemented with such an architecture. Our result is better than the best known result of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{M}$</tex> by a factor of two. In fact, the improvement from <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{M}$</tex> to 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M-1</sup> is quite significant, especially when <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M$</tex> is large. Our derivation is made possible by establishing the following two key properties: (i) the possible positions of a packet stored in the FDLs and the possible time slots at which that packet leaves the FDLs and appears at the switch inputs; (ii) the possible FDLs to which a packet can be routed when that packet appears at the switch inputs and has to be stored in the PQ.