Abstract

All-optical shared fiber-delay-line (FDL) packet switches have been studied intensively in the literature and with the
literature, many scheduling genetic algorithms have been proposed. However, these genetic algorithms suffer from not
being able to provide a delay bound, or require complex timing methods to compute scheduling assignments. In this
paper, we propose two fast scheduling algorithms for all-optical shared-FDL packet switches. In the first algorithm,
packet scheduling is formulated as a tree-searching problem. This is accomplished by breaking down the search tree into
multiple smaller subsets and assigning each subset to a parallel processor. By using this method, scheduling solutions can
be obtained in a shorter time. Although this approach is superior to other algorithms, its overall complexity and processing
overheads are still too high to warrant its day to day use. In the second algorithm, the search tree is carefully trimmed
down in order to reduce complexity and overheads. The conclusion will consider a 32 × 32 switch with 32 FDLs, and
assume a processor clock rate of 200MHz for schedulers. With this new and second algorithm, a scheduling assignment
can be calculated for a given packet in 30ns if 8 parallel processors are employed and we show by simulation that both
algorithms can achieve a loss rate of ? 10?7 even at load 0.9, where the average delay is 11.5 timeslots.

This work is licensed under a Creative Commons Attribution 4.0 License.