Low-latency scheduling in large switches

Abstract

Embodiments of a scheduler for a switch, where the switch is configured to couple input ports to output ports are described. During operation, the scheduler may determine a schedule based on a group of requests, associated with multiple data streams, that are received for the output ports of the switch, where the schedule matches input ports to output ports of the switch for a given data cell time. Note that the schedule may be determined using an arbitration technique during a time interval. Moreover, the scheduler may assign an additional request, which was received at a time that precedes a current time by less than the time interval, to a portion of the switch which is available in the schedule, thereby reducing a latency of the scheduler.