Construction of Subexponential-Size Optical Priority Queues With Switches and Fiber Delay Lines

摘要

All-optical switching has been considered as a natural choice to keep pace with growing fiber link capacity. One key research issue of all-optical switching is the design of optical buffers for packet contention resolution. One of the most general buffering schemes is optical priority queue, where every packet is associated with a unique priority upon its arrival and departs the queue in order of priority, and the packet with the lowest priority is always dropped when a new packet arrives but the buffer is full. In this paper, we focus on the feedback construction of an optical priority queue with a single $(M+2)imes (M+2)$ optical crossbar Switch and $M$ fiber Delay Lines (SDL) connecting $M$ inputs and $M$ outputs of the switch. We propose a novel construction of an optical priority queue with buffer $2{Theta (sqrt {M})}$ , which improves substantially over all previous constructions that only have buffers of $O(M{c})$ size for constant integer $c$ . The key ideas behind our construction include (i) the use of first in first out multiplexers, which admit efficient SDL constructions, for feeding back packets to the switch instead of fiber delay lines, and (ii) the use of a routing policy that is similar to self-routing, where each packet entering the switch is routed to some multiplexer mainly determined by the current ranking of its priority.