Earliest-deadline-first queuing cell switching architecture and method

Abstract

The cell switching architecture of the present invention uses at least one earliest deadline first (EDF) queue for each of the output ports in a cell switch so that no two output ports have a common earliest-deadline-first queue. Cells are arranged in each EDF queue according to deadline, but each EDF queue only contains cells for a single destination output port. Each input port also has an input queue with an EDF queue for each of the output ports, and each EDF queue arranges the cells for a single output port. Many equivalent cells may be represented by a single EDF queue entry, enabling large buffer capacity to be supported by small EDF queues. The architecture provides a method for switching cells between a plurality of input ports and a plurality of output ports. Cells are accepted from input ports into a plurality of corresponding input queues. Cells are sorted into groups according to the destination output port such that each group includes cells destined for a single output port. Within each input queue, at least one group is formed for every output port for which cells are available. Cells are arranged, within each group, according to deadline. By means of a central arbiter, output ports then choose cells to read in a read cycle from the earliest deadline cells in their corresponding cell groups in the input queues. An efficient method is used to select cells with the earliest deadlines.