Granted Patent B1

US 8,027,346 · App. 12/128,874 · Granted Sep 27, 2011

Abstract

Claims (86)

1. A method for scheduling data for dequeuing in a communication network having a hierarchy of interacting scheduling nodes including a child scheduling node and parent scheduling node, the child scheduling node being an eligible scheduling node, the eligible scheduling node having a scheduling context structure, an existence of data structure, and a data queue associated therewith, the method comprising:

responsive to determining that the eligible scheduling node does not contain at least one child identifier in the scheduling context structure and that an eligible child exists in the existence of data structure:

forwarding a message from the eligible scheduling node to the parent scheduling node, the message indicating the existence of an eligible child in the existence of data structure; and

and after forwarding the message, absorbing at least one eligible child from the existence of data structure into the scheduling context structure, absorbing the at least one eligible child including:

removing the child identifier from the existence of data structure; and

adding the child identifier to the scheduling context structure.

2. The method of claim 1 , further comprising:

responsive to determining that the eligible scheduling node contains at least one child identifier in the scheduling context structure:

selecting for dequeuing an eligible child from the scheduling context structure.

3. The method of claim 2 , further responsive to determining that the eligible scheduling node contains at least one child identifier in the scheduling context structure:

determining whether the eligible scheduling node contains at least one child identifier in the existence of data structure; and

responsive to determining that the eligible scheduling node contains at least one child identifier in the existence of data structure:

absorbing at least one eligible child from the existence of data structure into the scheduling context structure.

4. A method for scheduling data for dequeuing in a communication network having a hierarchy of interacting scheduling nodes including a child scheduling node and a parent scheduling node, the method comprising:

determining that one of the child scheduling node and a data queue is eligible for dequeuing;

setting an eligibility state for the one of the child scheduling node and the data queue to eligible;

determining whether an existence of data structure of the parent scheduling node for the one of the child scheduling node and the data queue is empty; and

responsive to determining that the existence of data structure of the parent scheduling node for the one of the child scheduling node and the data queue is not empty, adding an identifier for the one of the child scheduling node and a data queue to the existence of data structure of the parent scheduling node.

5. The method of claim 4 , further comprising:

responsive to determining that the existence of data structure of the parent scheduling node for the one of the child scheduling node and the data queue is empty:

adding an identifier for the one of the child scheduling node and the data queue to the existence of data structure of the parent scheduling node;

determining an eligibility state of the parent scheduling node before and after adding the child identifier, wherein the eligibility state is eligible when:

a child identifier is present in at least one of the existence of data structure of the parent scheduling node and a scheduling context structure of the parent scheduling node; and

the parent scheduling node is otherwise enabled for dequeuing; and

responsive to determining that the eligibility state of the parent scheduling node has changed from ineligible to eligible for dequeuing, setting the eligibility state for the parent scheduling node to eligible.

6. The method of claim 5 , further comprising:

responsive to setting the eligibility state of the parent scheduling node to eligible:

determining whether the eligible parent scheduling node has at least one ancestor scheduling node; and

responsive to determining that the eligible parent scheduling node has at least one ancestor scheduling node:

adding an identifier for the eligible parent scheduling node to an existence of data structure for each ancestor scheduling node of the at least one ancestor scheduling nodes; and

evaluating and propagating an eligibility state for each ancestor scheduling node of the at least one ancestor scheduling nodes.

7. The method of claim 5 , further comprising responsive to a request to the eligible parent scheduling node for data dequeue, selecting an eligible child for data dequeuing.

8. The method of claim 7 , further comprising:

determining whether the eligible parent scheduling node contains at least one child identifier in the scheduling context structure of the eligible parent scheduling node; and

responsive to determining that the eligible parent scheduling node does not contain at least one child identifier in the scheduling context structure of the eligible parent scheduling node:

selecting for dequeue one of a child node and a data queue with an identifier in the existence of data structure of the eligible parent scheduling node; and

absorbing a child identifier for at least one of an eligible child node and an eligible data queue from the existence of data structure of the eligible parent scheduling node into the scheduling context structure of the eligible parent scheduling node, wherein the at least one of an eligible child node and an eligible data queue includes the one of a child node and a data queue selected for dequeue, and wherein absorbing includes:

removing the child identifier for the at least one of an eligible child node and an eligible data queue from the existence of data structure of the eligible parent scheduling node; and

adding at least one corresponding child identifier to the scheduling context structure.

9. The method of claim 7 , further comprising:

determining whether the eligible parent scheduling node contains at least one child identifier in the scheduling context structure; and

responsive to determining that the eligible parent scheduling node contains at least one child identifier in the scheduling context structure of the eligible parent scheduling node:

selecting for dequeuing an eligible child from the scheduling context structure of the eligible parent scheduling node.

10. The method of claim 9 , further responsive to determining that the eligible parent scheduling node contains at least one child identifier in the scheduling context structure of the eligible parent scheduling node:

determining whether the eligible parent scheduling node contains at least one child identifier in the existence of data structure of the eligible parent scheduling node; and

responsive to determining that the eligible parent scheduling node contains at least one child identifier in the existence of data structure of the eligible parent scheduling node:

absorbing the child identifier for at least one eligible child from the existence of data structure of the eligible parent scheduling node into the scheduling context structure of the eligible parent scheduling node.

11. A system for scheduling data for dequeuing in a communication network having a hierarchy of interacting scheduling nodes including a child scheduling node and a parent scheduling node, the system comprising:

at least one data queue containing data for dequeuing;

at least one child communicatively coupled to the at least one data queue, the at least one child being one of a data queue and a child scheduling node;

at least one parent scheduling node communicatively coupled to the at least one child, the at least one parent scheduling node including:

a scheduling context structure; and

an existence of data structure; and

an eligibility updater communicatively coupled to the at least one data queue, the at least one child, and the at least one parent scheduling node, the eligibility updater operable to:

determine an eligibility state for a child;

responsive to determining that the eligibility state is eligible, set an eligibility state for the child to eligible; and

responsive to determining that the existence of data structure of the parent scheduling node is not empty, appending an identifier for the eligible child to the existence of data structure.

12. The system of claim 11 , wherein responsive to determining that the existence of data structure of a parent scheduling node of the child is empty, the eligibility updater is further operable to:

add an identifier for the eligible child to the existence of data structure of the parent scheduling node;

determine an eligibility state for the parent scheduling node; and

responsive to determining that the parent scheduling node is eligible, set an eligibility state for the parent scheduling node to eligible.

13. The system of claim 11 , further comprising:

at least one ancestor scheduling node communicatively coupled to the at least one parent scheduling node and the eligibility updater; and

wherein the eligibility updater is further operable to:

add an identifier for the at least one parent scheduling node to an existence of data structure for the at least one ancestor scheduling node;

determine an eligibility state for the at least one ancestor scheduling node; and

responsive to determining that the at least one ancestor scheduling node is eligible, set an eligibility state for the at least one ancestor scheduling node to eligible.

14. The system of claim 11 , wherein the at least one parent scheduling node upon selection by its ancestor is operable to:

select an eligible child from the at least one child for dequeuing.

15. The system of claim 14 , wherein the at least one parent scheduling node is further operable to:

determine whether the scheduling context structure contains at least one child identifier; and

responsive to determining that the scheduling context structure does not contain at least one child identifier:

select for dequeuing an eligible child from the existence of data structure;

absorb at least one eligible child from the existence of data structure into the scheduling context structure, wherein the at least one eligible child includes the child node selected for dequeuing, and wherein absorb includes:

removing the at least one child identifier for the at least one eligible child from the existence of data structure; and

adding the at least one child identifier to the scheduler context structure.

16. The system of claim 14 , wherein the at least one parent scheduling node is further operable to:

determine whether the scheduling context structure contains at least one child identifier; and

responsive to determining that the scheduling context structure contains at least one child identifier:

select an eligible child node from the scheduling context structure for dequeuing;

determine whether the existence of data structure contains at least one child identifier for at least one eligible child; and

responsive to determining that the existence of data structure contains at least one child identifier for at least one eligible child:

absorb at least one child of the at least one eligible child from the existence of data structure into the scheduling context structure.

17. The system of claim 14 , wherein:

the scheduling context structure stores data for child nodes and data queues that the at least one parent scheduling node knows to be eligible for dequeuing; and

the existence of data structure stores data for child nodes and data queues not currently known to the at least one parent scheduling node.

Assignments (23)