Abstract
One of the main challenges in all-optical packet switching is to design optical buffers for packet conflict resolution. In this paper, we consider a very general type of buffering schemes, namely, optical N-to-K priority queues with time-varying service capacity, where each packet is associated with a unique priority upon its arrival, at time slot t at most c(t) highest-priority packets are sent out from the queue if there are packets in the queue and the service capacity c(t) (0 ≤ c(t) ≤ K) of the queue is not zero, and up to N lowest-priority packets are dumped from the queue if there is a buffer overflow. We extend and generalize our previous constructions [8] of optical priority queues under a priority-based routing policy from single input/output to multiple inputs/outputs. The main contributions of this paper are as follows: (i) The priority queues considered in this paper subsume those considered in all previous works as special cases. (ii) Our queueing model with time-varying service capacity is not only more general but also more realistic than that with fixed service capacity previously studied in the literature. (iii) For the special case that N = K = 1, our constructions in this paper subsume those in [8] as special cases. (iv) For the special case that N = K, we show that an optical N-to-N priority queue with buffer size {2^{O(sqrt {M/N} )}} (exponential in sqrt {M/N} ) can be constructed by using an optical (M+2N)×(M+2N) (bufferless) crossbar switch and M fiber delay lines, which substantially improves the best result O(M3/N2) (polynomial in M/N) in the literature.