An Explicit Control Algorithm for Optical FIFO Queues

With the recent advances in optical technologies, it has become a challenge to build optical queues with minimal complexity. In [ChangCL06], it was shown that an optical FIFO queue can be constructed recursively by a concatenation of scaled optical memory cells, which in turn are made by 2 x 2 switches and fiber delay lines. However, as the construction is recursive, there is no explicit control algorithm for the 2 x2 switches in [ChangCL06]. The main contribution of this paper is to provide an explicit control algorithm for the 2 x2 switches in that construction. We show that our algorithm has O((log B)^2) space complexity and time complexity for an optical FIFO queue with buffer B