Ripple scheduling for end-to-end global resource management

• US 6,446,126 B1
• Filed: 05/12/1999
• Issued: 09/03/2002
• Est. Priority Date: 03/28/1997
• Status: Expired due to Fees

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Huang, Jiandong, Wang, Yuewei
• Primary Examiner(s): Rinehart, Mark H.
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US09/307,803
• Time in Patent Office: 1,210 Days
• Field of Search: 370/230, 370/235, 370/278, 370/473, 370/54, 370/256, 370/85.7, 370/84, 370/62, 370/234, 370/469, 370/229, 370/232, 370/392, 709/228, 709/245, 709/233, 709/226, 709/101, 709/200, 709/223, 709/234, 709/235, 709/224, 709/227, 714/19, 379/120, 705/37
• US Class Current: 709/226
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/245 using preemption
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/745 Reaction in network
• CPC Class Codes: H04L 47/765 triggered by the end-points
• CPC Class Codes: H04L 47/782 Hierarchical allocation of resources, e.g. involving a hierarchy of local and centralised entities
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data

Abstract

A global resource manager is provided for each node of a plurality of nodes of a distributed data processing system. Each node can be a coordinator node, an intermediate node, and a leaf node depending on the node at which a session arrives for global processing. In response to the arriving sessions, the global resource managers implement ripple scheduling by conducting a global QoS negotiation and adaptation, and preemption if necessary, in order to determine if the arriving session is supportable by the distributed data processing system. More specifically, the resource managers of all nodes determine whether their corresponding nodes can support the arriving session. The resource managers of the coordinator node and all intermediate nodes request their child nodes to indicate whether the child nodes can support the arriving session. The resource managers of all intermediate nodes and all leaf nodes respond to their coordinating or intermediate nodes with an indication of supportability. The resource manager of the coordinator node sends a commit message if all nodes can support the arriving session.

Claims

1. A method of managing a session by global resources in first and second phases, the method comprising the following steps:

a) negotiating among first, second, and third nodes for a QoS of the session during the first phase by ripple scheduling the session down from the first node to the second node and from the second node to the third node and then up from the third node to the second node and from the second node to the first node;

b) if the first, second, and third nodes can execute the session, sending a commit message during the second phase from the first node to the second node and from the second node to the third node; and

,

c) if the first or second or third node cannot execute the session, sending an abort message during the second phase from the first node to the second node and from the second node to the third node.

2. The method of claim 1 wherein step a) comprises the following steps:

a1) testing local resources of the first node during the first phase to determine if the first node can execute the session;

a2) if the first node can execute the session, sending a first session request during the first phase from the first node to the second node;

a3) in response to the first session request, testing local resources of the second node during the first phase to determine if the second node can execute the session;

a4) if the second node can execute the session, sending a second session request during the first phase from the second node to the third node;

a5) in response to the second session request, testing local resources of the third node during the first phase to determine if the third node can execute the session; and

,

a6) sending a response during the first phase from the third node to the second node to the first node.

3. The method of claim 2 wherein step c) comprises the step of sending an abort message during the second phase from the first node to the second node and from the second node to the third node if the first node cannot execute the session and sending an abort message during the second phase from the first node to the second node and from the second node to the third node if the first node receives a No response from the second node or the third node.

4. The method of claim 2 wherein step a2) comprises the step of sending a first session request during the first phase from the first node to the second node only if the first node can execute the session, and wherein step a4) comprises the step of sending a second session request during the first phase from the second node to the third node only if the second node can execute the session.

5. The method of claim 1 wherein step a) comprises the step of virtually shrinking a QoS of the session at the first, second, and third nodes.

6. The method of claim 5 wherein step b) comprises the step of making the virtual shrinking of the QoS of the session real.

7. The method of claim 5 wherein step c) comprises the step of revoking the virtual shrinking of the QoS of the session.

8. The method of claim 1 wherein the session is a first session, and wherein step a) comprises the step of virtually preempting a second session in order to determine a supportable QoS for the first session at the firsts, second, and third nodes.

9. The method of claim 8 wherein step b) comprises the step of making the virtual preemption of the second session real.

10. The method of claim 8 wherein step c) comprises the step of revoking the virtual preemption of the second session.

11. The method of claim 1 wherein step a) comprises the step of expanding a QoS of the session to a QoS supportable by the first, second, and third nodes.

12. The method of claim 11 wherein the commit message contains the expanded QoS.

13. The method of claim 1 wherein each of the first, second, and third nodes is capable of initiating the QoS negotiation, wherein each of the first, second, and third nodes is capable of initiating the sending of the commit message, wherein each of the first, second, and third nodes is capable of initiating the sending of the abort message, and wherein each of the first, second, and third nodes is capable of determining whether it can support a session.

14. A node arranged to conduct a ripple QoS negotiation of a session with other nodes through at least three layers of nodes, wherein the node is in one of the at least three layers, wherein the node sends a commit message through the at least three layers if, as a result of the ripple QoS negotiation, the session can be executed by the node and by the other nodes in the at least three layers, and wherein the node sends an abort message through the at least three layers if, as a result of the ripple QoS negotiation, the node or any of the other nodes in the at least three layers cannot execute the session.

15. The node of claim 14 wherein the node is in a first layer, wherein the node in the first layer is arranged to test local resources to determine if the node in the first layer can support the session, wherein the node in the first layer is arranged to send a session request if the node in the first layer can support the session, wherein the session request sent by the node in the first layer requests a node in a second layer to test local resources to determine if the node in the second layer can support the session, wherein the node in the second layer is arranged to send a session request if the node in the second layer can support the session, wherein the session request sent by the node in the second layer requests a node in a third layer to test local resources to determine if the node in the third layer can support the session, wherein the node in the second layer receives a response from the node in the third layer to the session request sent by the node in the second layer, and wherein the node in the first layer receives a response from the node in the second layer to the session request sent by the node in the first layer.

16. The node of claim 15 wherein the node in the first layer is arranged to send an abort message to the nodes in the second and third layers if the node in the first layer cannot support the session or if the node in the first layer receives a No response from the nodes in the second and third layers.

17. The node of claim 14 wherein the node is arranged to virtually shrink a QoS of the session in order to determine if the node can support the session.

18. The node of claim 17 wherein the node is arranged to make the virtual shrinking of the QoS of the session real only if the commit message is sent.

19. The node of claim 17 wherein the node is arranged to revoke the virtual shrinking of the QoS of the session only if the abort message is sent.

20. The node of claim 14 wherein the session is a first session, and wherein the node is arranged to virtually preempt a second session in order to determine a supportable QoS for the first session.

21. The node of claim 20 wherein the node is arranged to make the virtual preemption of the second session real only if the commit message is sent.

22. The node of claim 20 wherein the node is arranged to revoke the virtual preemption of the second session only if the abort message is sent.

23. The node of claim 14 wherein the node is arranged to expand the QoS of the session to a QoS supportable by the node and other nodes.

24. The node of claim 23 wherein the commit message contains the expanded QoS.

25. The node of claim 14 wherein, during the ripple QoS negotiation, the node is arranged to implement QoS shrinking, preemption, and QoS expansion as necessary in order to determine if the node can support the session.