Ripple scheduling for end-to-end global resource management

• US 6,766,365 B1
• Filed: 05/12/1999
• Issued: 07/20/2004
• Est. Priority Date: 03/28/1997
• Status: Expired due to Fees

• Current Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Original Assignee: Honeywell International Inc.
• Inventors: Huang, Jiandong, Wang, Yuewei
• Primary Examiner(s): Harvey, Jack B.
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US09/310,289
• Time in Patent Office: 1,896 Days
• Field of Search: 709/218, 709/201, 709/228, 709/231, 709/232, 709/223, 709/203, 709/219, 709/222, 705/8.1, 370/86, 370/601, 370/252, 370/397, 370/229.54, 370/392, 370/84, 370/395, 345/302, 379/230, 379/115, 455/403
• US Class Current: 709/223
• 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 provided to a user of globally managing a session, wherein the session has a criticality level, a timing requirement, and a QoS associated therewith, the method comprising the following steps:

a) enabling the user to make an initial adjustment of at least one of the criticality level, the timing requirement, and the QoS for the session; and

,

b) enabling the user to make a subsequent adjustment of at least one of the criticality level, the timing requirement, and the QoS for the session, wherein the subsequent adjustment is made after partial execution of the session.

2. The method of claim 1 wherein the timing requirement comprises rate and latency requirements.

3. The method of claim 1 wherein the criticality level, the timing requirement, and the QoS of the session are substantially independent of one another.

4. The method of claim 1 wherein the criticality level is initially and subsequently adjusted by the user.

5. The method of claim 1 wherein the timing requirement is initially and subsequently adjusted by the user.

6. The method of claim 1 wherein the QoS is initially and subsequently adjusted by the user.

7. The method of claim 1 wherein the criticality level and the timing requirement are initially and subsequently adjusted by the user.

8. The method of claim 1 wherein the criticality level and the QoS are initially and subsequently adjusted by the user.

9. The method of claim 1 wherein the timing requirement and the QoS are initially and subsequently adjusted by the user.

10. The method of claim 1 wherein the timing requirement comprises a rate requirement.

11. The method of claim 1 wherein the timing requirement comprises a latency requirement.

12. A method of globally managing a session comprising:

a) specifying an initial value for at least one of a criticality level, a timing requirement, and a QoS for the session; and

,

b) after execution of the session has begun, specifying a subsequent value for at least one of the criticality level, the timing requirement, and the QoS for the session, wherein the specifications of the initial and subsequent values are made by a person.

13. The method of claim 12 wherein the criticality level, the timing requirement, and the QoS of the session are substantially independent of one another.

14. The method of claim 12 wherein the initial and subsequent values of the criticality level are specified by the person.

15. The method of claim 12 wherein the initial and subsequent values of the timing requirement are specified by the person.

16. The method of claim 12 wherein the initial and subsequent values of the QoS are specified by the person.

17. The method of claim 12 wherein the initial and subsequent values of the criticality level and the timing requirement are specified by the person.

18. The method of claim 12 wherein the initial and subsequent values of the criticality level and the QoS are specified by the person.

19. The method of claim 12 wherein the initial and subsequent values of the timing requirement and the QoS are specified by the person.

20. The method of claim 12 wherein the timing requirement comprises a rate requirement.

21. The method of claim 12 wherein the timing requirement comprises a latency requirement.

22. The method of claim 12 wherein the timing requirement comprises rate and latency requirements.

23. The method of claim 12 further comprising:

determining whether the session can be supported;

if the session can be supported and if a node making the determination is a coordinator node or an intermediate node, sending a support request message to a downstream node;

if the session can be supported and if a node making the determination is an intermediate node or a leaf node, sending to an upstream node an affirmative response to the support request message; and

,

if the session cannot be supported and if a node making the determination is an intermediate node or a leaf node, sending to the upstream node a negative response to the support request message.

24. The method of claim 23 wherein the support request message includes a supportable QoS.

25. The method of claim 23 wherein the affirmative response includes a supportable QoS.

26. The method of claim 12 further comprising:

determining whether downstream nodes can support the session;

if the downstream nodes can support the session, sending a commit message to the downstream nodes; and

,

if the downstream nodes cannot support the session, sending an abort message to the downstream nodes.

27. The method of claim 26 wherein the commit message includes a QoS supportable by the downstream nodes.

28. The method of claim 12 further comprising:

determining whether the session can be supported without QoS shrinking;

if the session can be supported without QoS shrinking, scheduling the session for execution;

if the session can be supported with QoS shrinking, determining whether the session can be supported without preemption;

if the session can be supported without preemption, performing QoS shrinking and scheduling the session for execution; and

,

if the session can be supported with QoS shrinking and with preemption, performing QoS shrinking and preemption and scheduling the session for execution.

29. The method of claim 12 further comprising scheduling the session for execution through the use of QoS shrinking, preemption and QoS expansion.