Slot-by-Slot

Perhaps the most complex task that cell and packet switches must undertake is the scheduling of their cells or packets across the switch fabric. A slot-by-slot approach is used in some IP routers. But this leaves very little time available to compute maximum matching algorithms, whose complexity per slot can be as high as O(N³) for an NxN switch. Even simpler heuristic algorithms must still be computed for every time slot.

Frame-Based

An alternative approach is to extend the available computing time across an entire frame of cells or packets¹. This entails both the matching of multiple cells/packets between the input and output ports and the assignment of time slots to each individual cell/packet. Overall this has the benefit of reducing the computing complexity per time slot, allowing larger switches and networks with more ports (larger N) to be scheduled.

Multi-Stage Architectures

Scheduling algorithm complexity can also be reduced by extending switch and network fabrics to multiple stages of switching, such as in the load-balanced, two-stage Birkhoff-von Neumann switch². But great care must be taken to ensure that scheduling algorithms prevent cell/packet mis-sequencing.

Optical Packet Networks

All of the above relate to both switches and small-scale optical networks such as metropolitan optical packet networks, where buffering is readily available in electronic form³. But across wide-area networks (national, international) it will be desirable for optical packets to be buffered as little as possible, in order to minimise delays and network costs. New techniques for optical packet networks will become necessary, such as optical burst switching⁴, deflection routing, wavelength reassignment and resource reservation using signalling protocols.

                                                                                      back to Cell & Packet Switches

¹Source: A Bianco et al, HPSR 2002

²Source: C.-S. Chang, D.-S. Lee, Y.-S. Jou, “Load balanced Birkhoff-von Neumann switches,” Proceedings of IEEE HPSR ‘01, May 2001, Dallas, Texas.

³Source: L. Dittman, et al., “The European IST project DAVID: a viable approach towards optical packet switching”, IEEE J. Selected Areas in Commun., vol. 21, no. 7, Sept. 2003, pp. 1026–1040.

⁴Source: Jon Turner, Washington University, St. Louis, USA