Patent ID: 7461159

Claim:
A method for scheduling entities in a system, comprising: receiving, at a scheduler, entities to be scheduled, an entity being associated with one of a plurality of sessions, a session comprising a share; associating a timestamp with each entity based at least in part upon a virtual time; determining a backlog rate representing a sum of shares for backlogged sessions, wherein determining said backlog rate comprises: associating a share sum and a next sum with the timestamp, the share sum representing a sum of shares for sessions for entities associated with the timestamp, and the next sum representing a sum of shares for sessions for an entity comprising the timestamp and at least one other entity associated with another timestamp that is greater than the timestamp; and determining said backlog rate representing said sum of shares for backlogged sessions based on the share sum and the next sum; maintaining the virtual time based at least in part upon the backlog rate; and computing timestamps for subsequently received entities based at least in part upon the virtual time.