摘要
The design of optical buffers for packet contention resolution has been recognized as a key issue in all-optical packet switching. One of the most general buffering schemes is priority queues, which includes first-in first-out (FIFO) queues and last-in first-out (LIFO) queues as special cases. In a priority queue, each packet is associated with a unique priority upon its arrival, the packet with the highest priority is sent out from the queue whenever there is a departure request and there are packets in the queue, and the packet with the lowest priority is dumped from the queue whenever there is a buffer overflow. In this paper, we consider the constructions of optical priority queues by using a feedback system consisting of an optical (bufferless) crossbar switch and multiple optical FIFO multiplexers with delay one (FM1&null) in the feedback path for buffering packets and feeding packets back to the switch. Such a feedback system is a generalization of that used in one of the authors&null earlier attempt for the constructions of optical priority queues in [19]. We fix the no-buffering problem in [19] by using optical FM1&null to replace the optical FIFO multiplexers (FM&null) in [19], which enables us to successfully achieve an exact emulation of a priority queue. We improve the utilization of buffering capacity over that in [19] by routing packets to the optical FM1&null according to their buffering tags instead of their tags as used in [19]. We also extend and generalize the construction in [19] and obtain a much larger class of constructions of optical priority queues. Our constructions are made possible by showing that the highest-priority (resp., lowest-priority) packet is always available at the input links of the switch whenever it needs to be routed to the departure (resp., loss) link, and by showing that there is no collision and there is no buffer overflow at any FM1 at any time so that there is no internal packet loss at any time. Our complexity analysis shows that by using a feedback system consisting of an optical (M + 2) &null (M + 2) (bufferless) crossbar switch and M fiber delay lines, we can achieve a buffer size of 2O(&null), where &null is a constant that depends on the parameters used in our constructions. Furthermore, we show that the best buffer size that we can achieve is 2O(&null). Our result (exponential in &null) substantially improves on the best known result (polynomial in M) in the literature. Our numerical results show that the construction complexity of our constructions is lower than that of the construction in [19], and the actual saving, in terms of the number of 2 &null 2 switches needed, by our constructions could be quite significant even in the tiny-buffer and small-buffer regimes.