Scheduling eligible entries using an approximated finish delay identified for an entry based on an associated speed group

One or more tangible computer-readable media containing computer-executable instructions for performing steps when executed by control logic or one or more processing elements, said steps comprising:

• maintaining a plurality of schedule entries, with each of the plurality of schedule entries respectively associated with a start time and a speed group of a plurality of speed groups, with each said speed group representing a range of at least two different scheduling rates and associated with a time value representing a single predetermined approximated finish delay for use in scheduling each scheduling entry associated with the corresponding said speed group;
• and
• identifying an approximated earliest finishing entry of a subset of the plurality of schedule entries that are currently eligible, the approximated earliest finishing entry having an earliest approximated finish time of the subset of the plurality of schedule entries, each said approximated finish time determined based on an entry's respective said start time and said approximated finish delay of its associated said speed group;
• initiating an action corresponding to the approximated earliest finishing entry in response to said identifying the approximated earliest finishing entry;
• and
• updating said start time of the approximated earliest finishing entry based on an amount corresponding to the action.

A method for scheduling by a particular machine, the method comprising:

• (a) maintaining a plurality of schedule entries, each of the plurality of schedule entries respectively associated with a start time and a speed group of a plurality of speed groups, each said speed group associated with an approximated finish delay;
• and
• (b) identifying an approximated earliest finishing entry of a subset of the plurality of schedule entries that are currently eligible, the approximated earliest finishing entry having an earliest approximated finish time of the subset of the plurality of schedule entries, each said approximated finish time determined based on an entry's respective said start time and said approximated finish delay of its associated said speed group;
• wherein each of the plurality of speed groups is associated with a respective range of scheduling rates;
• and wherein each of said schedule entries corresponds to an action of forwarding of a packet by the particular machine, and the approximated finish delay of each particular speed group of the plurality of speed groups is determined based on a largest packet size and a rate within said range of scheduling rates of said particular speed group;
• and
• wherein the rate is one of the boundary rates of said range of scheduling rates of said particular speed group.

A method for scheduling by a particular machine, the method comprising:

• (a) maintaining a plurality of schedule entries, each of the plurality of schedule entries respectively associated with a start time and a speed group of a plurality of speed groups, each said speed group associated with an approximated finish delay;
• and
• (b) identifying an approximated earliest finishing entry of a subset of the plurality of schedule entries that are currently eligible, the approximated earliest finishing entry having an earliest approximated finish time of the subset of the plurality of schedule entries, each said approximated finish time determined based on an entry's respective said start time and said approximated finish delay of its associated said speed group;
• wherein each of the plurality of speed groups is associated with a respective range of scheduling rates;
• and wherein each of said schedule entries corresponds to an action of forwarding of a packet by the particular machine, and the approximated finish delay of each particular speed group of the plurality of speed groups is determined based on a largest packet size and a rate within said range of scheduling rates of said particular speed group;
• and
• wherein the rate is the fastest of the boundary rates of said range of scheduling rates of said particular speed group.

A method for scheduling by a particular machine, the method comprising:

• (a) maintaining a plurality of schedule entries, each of the plurality of schedule entries respectively associated with a start time and a speed group of a plurality of speed groups, each said speed group associated with an approximated finish delay;
• and
• (b) identifying an approximated earliest finishing entry of a subset of the plurality of schedule entries that are currently eligible, the approximated earliest finishing entry having an earliest approximated finish time of the subset of the plurality of schedule entries, each said approximated finish time determined based on an entry's respective said start time and said approximated finish delay of its associated said speed group;
• wherein each of the plurality of speed groups is associated with a respective range of scheduling rates;
• and wherein each of said schedule entries corresponds to an action of forwarding of a packet by the particular machine, and the approximated finish delay of each particular speed group of the plurality of speed groups is determined based on a largest packet size and a rate within said range of scheduling rates of said particular speed group;
• and
• wherein the rate is the slowest of the boundary rates of said range of scheduling rates of said particular speed group.