Weighted fair queue having extended effective range

A scheduler for a network processor, the scheduler comprising a scheduling queue in which flows are enqueued according to the formula CP+((WF×FS)/SF) wherein:

• CP is a pointer for indicating a current position in the scheduling queue;
• WF is a weighting factor associated with a flow appointed for enqueuing;
• FS is a frame size associated with the flow appointed for enqueuing;
• and
• SF is a scaling factor;
• wherein the scheduling queue includes at least a first subqueue and a second subqueue, and the flow appointed for enqueuing is enqueued to the first subqueue if the value of the expression ((WF×FS)/SF) is less than a range of the first subqueue and the flow appointed for enqueuing is enqueued to the second subqueue if the value of the expression ((WF×FS)/SF) is greater than a range of the first subqueue.

A method of managing queuing of flows in a network processor, comprising:

• enqueuing a flow to a first subqueue if the expression ((WF×FS)/SF) has a value that is less than a range of the first subqueue;
• and
• enqueuing the flow to a second subqueue if the expression ((WF×FS)/SF) has a value that is greater than the range of the first subqueue, wherein:
• WF is a weighting factor associated with the flow;
• FS is a frame size associated with the flow;
• and
• SF is a scaling factor.

A method of dequeuing a flow from a scheduling queue in a scheduler for a network processor, comprising:

• searching a first subqueue of the scheduling queue to find a first winning flow in the first subqueue;
• determining a first queue distance corresponding to a distance between a current pointer and a slot in which the first winning flow is enqueued;
• searching a second subqueue of the scheduling queue to find a second winning flow in the second subqueue;
• determining a second queue distance corresponding to a distance between the current pointer and a slot in which the second winning flow is enqueued;
• comparing the first and second queue distances;
• and
• selecting for dequeuing one of the first and second winning flows based on a result of the comparing step.

A method of managing a scheduler having a scheduling queue adapted to define a sequence in which flows are to be serviced, the scheduling queue having at least a first subqueue and a second subqueue, the first subqueue having a first range and a first resolution and the second subqueue having a second range that is greater than the first range and a second resolution that is less than the first resolution, the method comprising:

• determining a distance from a current pointer at which a flow is to be attached;
• determining if the distance is less than the first range of the first subqueue, and if so, attaching the flow to the first subqueue;
• and
• determining if the distance is greater than the first range of the first subqueue, and if so, attaching the flow to the second subqueue.

A computer program product for use with a scheduler having a scheduling queue adapted to define a sequence in which flows are to be serviced, the scheduling queue having at least a first subqueue and a second subqueue, the first subqueue having a first range and a first resolution and the second subqueue having a second range that is greater than the first range and a second resolution that is less than the first resolution, the computer program product comprising:

• a medium readable by a computer, the computer readable medium having computer program code adapted to:
• determine a distance from a current pointer at which a flow is to be attached;
• determine if the distance is less than the first range of the first subqueue, and if so, attach the flow to the first subqueue;
• and
• determine if the distance is greater than the first range of the first subqueue, and if so, attach the flow to the second subqueue.

A computer program product for dequeuing a flow from a scheduling queue in a scheduler for a network processor, the computer program product comprising:

• a medium readable by a computer, the computer readable medium having computer program code adapted to:
• search a first subqueue of the scheduling queue to find a first winning flow in the first subqueue;
• determine a first queue distance
• corresponding to a distance between a current pointer and a slot in which the first winning flow is enqueued;
• search a second subqueue of the scheduling queue to find a second winning flow in the second subqueue;
• determine a second queue distance corresponding to a distance between the current pointer and a slot in which the second winning flow is enqueued;
• compare the first and second queue distances;
• and
• select for dequeuing one of the first and second winning flows based on a result of the comparison of the first and second queue distances.

A computer program product for managing queuing of flows in a network processor, comprising:

• a medium readable by a computer, the computer readable medium having computer program code adapted to:
• enqueue a flow to a first subqueue if the expression ((WF×FS)/SF) has a value that is less than a range of the first subqueue;
• and
• enqueue the flow to a second subqueue if the expression ((WF×FS)/SF) has a value that is greater than the range of the first subqueue, wherein:
• WF is a weighting factor associated with the flow;
• FS is a frame size associated with the flow;
• and
• SF is a scaling factor.