Ripple scheduling for end-to-end global resource management

• US 6,751,666 B1
• Filed: 05/12/1999
• Issued: 06/15/2004
• Est. Priority Date: 03/28/1997
• Status: Expired due to Fees

• Current Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Original Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Inventors: Huang, Jiandong, Wang, Yuewei
• Primary Examiner(s): Harvey, Jack B.
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US09/310,798
• Time in Patent Office: 1,861 Days
• Field of Search: 709/227, 709/203, 709/219, 709/264, 709/222, 709/223-226, 709/228, 709/604, 370/17, 370/54, 370/410, 370/230, 370/232, 370/235, 370/260, 370/395, 370/352, 370/257, 370/419, 370/440, 370/432, 370/412, 705/8, 707/7, 707/14, 707/10, 707/4, 395/653, 364/514, 379/230, 348/7, 710/36, 714/57
• 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 global resource manager for communicating locally with a local resource manager that locally manages an application session and for communicating globally with another global resource manager in order to globally manage the application session, wherein the global resource manager globally manages the application session according to a criticality level, a timing requirement, and a QoS of the session.

2. The global resource manager of claim 1 wherein the global resource manager is arranged to cause the shrinking of a QoS of the application session and of at least some concurrent sessions.

3. The global resource manager of claim 2 wherein the global resource manager is arranged to preempt the application session, if necessary.

4. The global resource manager of claim 3 wherein the global resource manager is arranged to cause the expansion of the QoS of the application session and of at least some of the concurrent sessions.

5. The global resource manager of claim 1 wherein the timing requirement comprises rate and latency requirements.

6. The global resource manager of claim 1 wherein the global resource manager is arranged to permit an application user to re-specify the criticality level for the application session after execution of the application session has started.

7. The global resource manager of claim 1 wherein the global resource manager is arranged to permit an application user to re-specify the timing requirement for the application session after execution of the application session has started.

8. The global resource manager of claim 1 wherein the global resource manager is arranged to permit an application user to re-specify a QoS for the application session after execution of the application session has started.

9. The global resource manager of claim 1 wherein the global resource manager is arranged to implement QoS shrinking, session preemption, and QoS expansion of concurrent sessions in order to determine whether to admit an arriving session.

10. The global resource manager of claim 1 wherein the global resource manager preempts the application session according to the criticality level of the session.

11. The global resource manager of claim 1 wherein the global resource manager admits the application session according to the criticality level of the session.

12. A processing node of a distributed data processing system comprising:

a local resource manager arranged to manage a local resource in response to a test-and-hold instruction; and

,

a global resource manager, wherein the global resource manager is arranged to conduct a peer-to-peer global QoS negotiation and adaptation with other global resource managers of the distributed data processing system through a test-and-hold instruction, wherein the global resource manager is arranged to initiate a test-and-hold instruction to the local resource manager, wherein the global resource manager is arranged to receive a response from the local resource manager indicating whether its local resource can support a session, and wherein the global resource manager is arranged to interface with different types of local resource managers.

13. The processing node of claim 12 wherein the global resource manager is arranged to send a commit message to another global resource manager if the response from the local resource manager indicates that the local resource can support the session.

14. The processing node of claim 12 wherein the global resource manager is arranged to send an abort message to another global resource manager if the response from the local resource manager indicates that the local resource cannot support the session.

15. A processing node of a distributed data processing system comprising:

a local resource manager arranged to manage a local resource in response to a test-and-hold instruction;

an operating system, wherein the operating system is arranged to operate the local resource; and

,

a global resource manager, wherein the global resource manager is arranged to conduct a peer-to-peer global negotiation with other global resource managers of the distributed data processing system through a test-and-hold instruction, wherein the global resource manager is arranged to initiate a test-and-hold instruction to the local resource manager, wherein the global resource manager is arranged to receive a response from the local resource manager indicating whether its local resource can support a session, and wherein the global resource manager sits on top of the operating system.

16. The processing node of claim 15 wherein the global resource manager comprises:

QoS shrinking means for shrinking a QoS of each of a plurality of executing sessions and a QoS of an arriving session;

preempting means for preempting, as necessary, the executing sessions which have criticality levels that are lower than a criticality level of the arriving session; and

,

QoS expanding means for expanding the QoS of any sessions.

17. The processing node of claim 16 wherein the QoS shrinking means shrinks the QoS of each of the executing sessions and shrinks the QoS of the arriving session to corresponding minimums.

18. The processing node of claim 16 wherein the preempting means includes determining means for determining a schedulable criticality level with respect to the executing sessions.

19. The processing node of claim 18 wherein the QoS expanding means expands the QoS of each session to a maximum QoS supportable by the local resource.

20. The processing node of claim 16 wherein the QoS expanding means expands the QoS of each session to a maximum QoS supportable by the local resource.

21. A method of globally managing a plurality of sessions executing at a plurality of distributed processing nodes comprising:

determining whether a local resource can support an arriving session by shrinking a QoS for each of the executing sessions and preempting one or more of the executing sessions, as necessary, to admit the arriving session; and

,

if it is determined that the local resource can support the arriving session, sending a message to the distributed processing nodes indicating that the local resource can support the arriving session.

22. The method of claim 21 wherein the message includes a QoS supportable by the local resource.

23. The method of claim 21 further comprising expanding the QoS of each executing session following QoS expansion and possible preemption.

24. The method of claim 21 further comprising transmitting an abort message if the arriving session cannot be supported.

25. The method of claim 21 wherein only those executing sessions having a lower criticality than a criticality of the arriving session are preempted if necessary.