WORK CONSERVING SCHEDULAR BASED ON RANKING

摘要

A work conserving scheduler can be implemented based on a ranking system to provide the scalability of time stamps while avoiding the fast search associated with a traditional time stamp implementation. Each queue can be assigned a time stamp that is initially set to zero. The time stamp for a queue can be incremented each time a data packet from the queue is processed. To provide varying weights to the different queues, the time stamp for the queues can be incremented at varying rates. The data packets can be processed from the queues based on the tier rank order of the queues as determined from the time stamp associated with each queue. To increase the speed at which the ranking is determined, the ranking can be calculate from a subset of the bits defining the time stamp rather than the entire bit set.

主权项

1. A method comprising:
calculating, by a computer processor, a tier rank for a first queue from a subset of most significant bits defining a time stamp value associated with the first queue, wherein the first queue contains a plurality of data packets; calculating, by the computer processor, a tier rank for a second queue, different than the first queue, from a subset of most significant bits defining a time stamp value associated with the second queue, wherein the second queue contains a plurality of data packets; determining, by the computer processor, that the tier rank for the first queue is higher than the tier rank for the second queue; and processing, by the computer processor, at least one of the plurality of data packets contained in the first queue.