Scalable multi-client scheduling

摘要

A method includes receiving a plurality of requests, determining a plurality of first bank identifiers specifying respective physical memory banks, and selecting, based at least on the first bank identifiers, a first set of requests to be processed according to a scheduling hierarchy. Selecting the first set of requests includes prohibiting any two requests from being associated with a same first bank identifier. The method also includes processing, during a single processing cycle, ones of the first set of requests at respective nodes within a single level of the scheduling hierarchy. The method also includes, responsively at least to processing ones of the first set of requests at respective nodes within the single level of the scheduling hierarchy, selecting a queue, and, responsively at least to selecting the queue, causing one or more packets corresponding to a traffic class associated with the queue to be sent to an egress port.

主权项

1. A method, implemented in a network device, for scheduling network traffic, the method comprising:
receiving, in the network device, a plurality of requests each indicating that a respective queue, of a plurality of queues storing data representing packets to be sent to an egress port of the network device for transmission, is eligible for de-queuing; determining a plurality of first bank identifiers, ones of the first bank identifiers (i) being associated with different ones of the plurality of requests and (ii) specifying respective physical memory banks of the network device; selecting, from the received plurality of requests and based at least on the plurality of first bank identifiers, a first set of two or more requests to be processed according to a scheduling hierarchy, wherein selecting the first set of requests includes prohibiting any two requests of the first set of requests from being associated with a same first bank identifier; processing, in the network device and during a single processing cycle, ones of the first set of requests at respective nodes within a single level of the scheduling hierarchy, wherein processing ones of the first set of requests at the respective nodes within the single level of the scheduling hierarchy includes accessing the physical memory banks, specified by the first bank identifiers associated with the ones of the first set of requests, to update states of the respective nodes within the single level of the scheduling hierarchy; responsively at least to processing ones of the first set of requests at respective nodes within the single level of the scheduling hierarchy, selecting a queue of the plurality of queues; and responsively at least to selecting the queue, causing one or more packets corresponding to a traffic class associated with the selected queue to be sent to the egress port for transmission.