Ripple scheduling for end-to-end global resource management

• US 6,446,125 B1
• Filed: 03/28/1997
• Issued: 09/03/2002
• 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): Rinehart, Mark H.
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US08/827,536
• Time in Patent Office: 1,985 Days
• Field of Search: 709/206, 709/226-228, 709/238, 709/101, 370/355, 370/468, 370/94.3, 370/386, 370/395, 370/17, 370/218, 370/13, 370/255, 370/60, 370/392, 370/232-235, 370/252, 370/254, 370/260, 370/84, 370/54, 370/85.7, 370/397, 370/289, 370/466, 371/32, 364/200, 395/575, 395/650, 395/330, 707/7, 707/10, 379/230, 706/10
• 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 resource manager for each node of a plurality of nodes of a distributed data processing system, wherein each node is capable of acting as a coordinator node, an intermediate node, and a leaf node, and wherein each node receives an arriving session to process, the resource manager comprising:

determining means for determining whether a node corresponding to the determining means can support the arriving session;

request sending means for sending, if the corresponding node is acting as a coordinator node or an intermediate node, a support request to child nodes which are to process the arriving session;

response sending means for sending, if the corresponding node is acting as an intermediate node or a leaf node, a response to a parent node, wherein the response indicates whether the arriving session can be supported; and

,

commit sending means for sending, if the corresponding node is acting as a coordinator node and if the arriving session can be supported by the nodes which are to process the arriving session, a commit message to the child nodes which are to process the arriving session.

2. The resource manager of claim 1 wherein the corresponding node processes an other session, wherein the other session has a QoS associated therewith, and wherein the determining means determines whether the corresponding node can support the arriving session based upon virtual shrinking of the QoS of the other session.

3. The resource manager of claim 2 wherein the commit sending means includes means for making the virtual shrinking of the QoS of the other session real if the child nodes can support the arriving session.

4. The resource manager of claim 2 wherein the commit sending means includes means for revoking the virtual shrinking of the QoS of the other session if the child nodes cannot support the arriving session.

5. The resource manager of claim 2 wherein the determining means attempts to lock the other session in order to prevent operations by another session on the other session to be locked.

6. The resource manager of claim 2 wherein the determining means determines whether the corresponding node can support the arriving session based upon virtual preemption of the other session.

7. The resource manager of claim 6 wherein the commit sending means includes means for revoking the virtual preemption of the other session if the child nodes cannot support the arriving session.

8. The resource manager of claim 6 wherein the commit sending means includes means for admitting a non-executing session if the corresponding node can support the arriving session and the non-executing session.

9. The resource manager of claim 6 wherein the determining means attempts to lock the other session in order to prevent operations by another session on the other session to be locked.

10. The resource manager of claim 6 wherein the commit sending means includes means for making the virtual preemption of the other session real if the child nodes can support the arriving session.

11. The resource manager of claim 1 wherein the corresponding node processes an other session, and wherein the determining means determines whether the corresponding node can support the arriving session based upon virtual preemption of the other session.

12. The resource manager of claim 11 wherein the commit sending means includes means for making the virtual preemption of the other session real if the child nodes can support the arriving session.

13. The resource manager of claim 11 wherein the commit sending means includes means for revoking the virtual preemption of the other session if the child nodes cannot support the arriving session.

14. The resource manager of claim 11 wherein the commit sending means includes means for admitting a non-executing session if the corresponding node can support the arriving session and the non-executing session.

15. The resource manager of claim 11 wherein the determining means attempts to lock the other session in order to prevent operations by another session on the other session to be locked.

16. The resource manager of claim 1 wherein the corresponding node processes an other session, wherein the other session has a QoS associated therewith, and wherein the determining means determines whether the corresponding node can support the arriving session based upon shrinking of the QoS of the other session.

17. The resource manager of claim 16 wherein the determining means attempts to lock the other session in order to prevent operations by another session on the other session to be locked.

18. The resource manager of claim 16 wherein the determining means determines whether the corresponding node can support the arriving session based upon preemption of the other session.

19. The resource manager of claim 18 wherein the determining means attempts to lock the other session in order to prevent operations by another session on the other session to be locked.

20. The resource manager of claim 16 wherein the commit sending means includes means for admitting a non-executing session if the corresponding node can support the arriving session and the non-executing session.

21. The resource manager of claim 1 wherein the corresponding node processes an other session, and wherein the determining means determines whether the corresponding node can support the arriving session based upon preemption of the other session.

22. The resource manager of claim 21 wherein the determining means attempts to lock the other session in order to prevent operations by another session on the other session to be locked.

23. The resource manager of claim 1 wherein the commit sending means includes means for admitting a non-executing session if the corresponding node can support the arriving session and the non-executing session.

24. The resource manager of claim 1 wherein the commit sending means sends, if the corresponding node is a coordinator node, an abort message to the child nodes if one of the child nodes cannot support the arriving session.

25. The resource manager of claim 1 further comprising means for permitting an application user to specify on-line a criticality level for a session, to specify on-line a timing requirement for the session, and to specify on-line a QoS for the session.

26. A resource manager for each node of a plurality of nodes of a distributed data processing system, wherein each node is capable of acting as a coordinator node, an intermediate node, and a leaf node, and wherein each node receives an arriving session to process, the resource manager comprising:

determining means for determining whether a node corresponding to the determining means can support the arriving session;

request sending means for sending, if the corresponding node is acting as a coordinator node or an intermediate node and if the corresponding node can support the arriving session, a support request to child nodes which are to process the arriving session;

intermediate response sending means for sending, if the corresponding node is acting as an intermediate node, a YES response to a parent node if the corresponding node and its child nodes can support the arriving session and a NO response to the parent node if the corresponding node or at least one of its child nodes cannot support the arriving session;

leaf response sending means for sending, if the corresponding node is acting as a leaf node, a YES response to a parent node if the corresponding node can support the arriving session and a NO response to the parent node if the corresponding node cannot support the arriving session; and

,

commit sending means for sending, if the corresponding node is a coordinator node and if the arriving session can be supported by the nodes which are to process the arriving session, a commit message to the child nodes which are to process the arriving session.

27. The resource manager of claim 26 wherein the request sent by the request sending means includes a QoS for the arriving session.

28. The resource manager of claim 27 wherein the determining means determines whether the QoS for the arriving session can be supported by the corresponding node.

29. The resource manager of claim 28 wherein the leaf response sending means sends a YES response if the corresponding node can support the QoS for the arriving session and sends a NO response if the corresponding node cannot support the QoS for the arriving session.

30. The resource manager of claim 29 wherein the determining means determines a supportable QoS for the arriving session, wherein the supportable QoS can be supported by the corresponding node if the arriving is executed by the corresponding node, and wherein the YES response sent by the leaf response sending means includes the supportable QoS.

31. The resource manager of claim 28 wherein the intermediate response sending means sends a YES response if the corresponding node can support the QoS for the arriving session, wherein the YES response sent by the intermediate response sending means includes a supportable QoS for the arriving session, wherein the supportable QoS included in the YES response is a QoS supportable QoS by a corresponding intermediate node and its child nodes.

32. The resource manager of claim 26 wherein the commit sending means sends, if the corresponding node is a coordinator node, an abort message to the child nodes if one of the child nodes sends a No response.

33. The resource manager of claim 26 further comprising means for permitting an application user to specify on-line a criticality level for an executing session, to specify on-line a timing requirement for the executing session, and to specify on-line a QoS for the executing session.

34. A resource manager for a coordinator node of a distributed data processing system, wherein the coordinator node may receive an arriving session to process, the resource manager comprising:

determining means for determining whether the coordinator node can support the arriving session;

request sending means for sending, if the determining means determines that the coordinator node can support the arriving session, a support request to child nodes which are to process the arriving session; and

,

commit sending means for sending, if the coordinator node and all of the child nodes can support the arriving session, a commit message to the child nodes, wherein the commit message includes a globally supportable QoS for the arriving session.

35. The resource manager of claim 34 wherein the coordinator node processes an other session, and wherein the determining means includes preempting means for preempting the other session if the coordinator node can support the arriving session only with preemption.

36. The resource manager of claim 35 wherein the commit sending means sends an abort message to the child nodes if one child node cannot support the arriving session.

37. The resource manager of claim 35 wherein the globally supportable QoS is a QoS supportable by all child nodes of the coordinator node.

38. The resource manager of claim 34 wherein the commit sending means sends an abort message to the child nodes if one child node cannot support the arriving session.

39. The resource manager of claim 34 wherein the globally supportable QoS is a QoS supportable by all child nodes of the coordinator node.

40. The resource manager of claim 34 wherein the coordinator node processes an other session, wherein the other session has a QoS, wherein the determining means includes QoS shrinking means for shrinking the QoS of the other session if the coordinator node can support the arriving session only with QoS shrinking.

41. The resource manager of claim 40 wherein the determining means includes preempting means for preempting the other session if the coordinator node can support the arriving session only with preemption.

42. The resource manager of claim 40 wherein the globally supportable QoS is a QoS supportable by all child nodes of the coordinator node.

43. A resource manager for an intermediate node of a distributed data processing system, wherein the intermediate node may be requested to process an arriving session, the resource manager comprising:

determining means for determining whether the intermediate node can support the arriving session;

request passing means for passing, if the intermediate node can support the arriving session, a request from an upstream node to downstream nodes which are to process the arriving session, wherein the request requests the downstream nodes to determine supportability of the arriving session; and

,

response sending means for sending a response to the request from the upstream node, wherein the response sending means sends the response to the upstream node, wherein the response is a YES response if the intermediate node and the downstream nodes can support the arriving session, and wherein the response is a NO response if the intermediate node or one of the downstream nodes cannot support the arriving session.

44. The resource manager of claim 43 wherein the response includes a QoS supportable by the intermediate node and by the downstream nodes.

45. The resource manager of claim 43 wherein the intermediate node processes an other session, and wherein the determining means includes preempting means for preempting the other session if the intermediate node can support the arriving session only with preemption.

46. The resource manager of claim 43 wherein the intermediate node processes an other session, wherein the other session has a QoS, and wherein the determining means includes QoS shrinking means for shrinking the QoS of the other session if the intermediate node can support the arriving session only with QoS shrinking.

47. The resource manager of claim 46 wherein the determining means includes preempting means for preempting the other session if the intermediate node can support the arriving session only with preemption.

48. A resource manager for a leaf node of a distributed data processing system, wherein the leaf node may be requested to process an arriving session, the resource manager comprising:

determining means for determining whether the leaf node can support the arriving session; and

,

response sending means for sending a response to a request from an upstream node, wherein the request asks whether the leaf node can support the arriving session, wherein the response sending means sends the response to the upstream node, wherein the response is a YES response if the leaf node can support the arriving session, and wherein the response is a NO response if the leaf node cannot support the arriving session, wherein the YES response includes a QoS supportable by the leaf node for the arriving session.

49. The resource manager of claim 48 wherein the leaf node processes an other session, and wherein the determining means includes preempting means for preempting the other session if the leaf node can support the arriving session only with preemption.

50. The resource manager of claim 48 wherein the leaf node processes an other session, wherein the other session has a QoS, and wherein the determining means includes QoS shrinking means for shrinking the QoS of the other session if the leaf node can support the arriving session only with QoS shrinking.

51. The resource manager of claim 50 wherein the determining means includes preempting means for preempting the other session if the leaf node can support the arriving session only with preemption.

52. A method performed by a processing node of a distributed data processing system, wherein the processing node is capable of acting as a coordinator node, an intermediate node, and a leaf node, and wherein the processing node receives an arriving session, the method comprising the following steps:

a) determining whether the arriving session can be supported;

b) if the processing node is acting as a coordinator node or an intermediate node, sending a request to downstream nodes, wherein the request asks whether the downstream nodes can support the arriving session;

c) if the processing node is acting as an intermediate node, sending a response to an upstream node in response to the request, wherein the response is a YES response if the processing node and the downstream nodes can support the arriving session, and wherein the response is a NO response if the processing node or one of the downstream nodes cannot support the arriving session;

d) if the processing node is acting as a leaf node, sending a response to an upstream node in response to the request, wherein the response is a YES response if the processing node can support the arriving session, and wherein the response is a NO response if the processing node cannot support the arriving session;

e) if the processing node is acting as a coordinator node and if the processing node and all of the downstream nodes can support the arriving session, sending a commit message to the downstream nodes which are to process the arriving session; and

,

f) if the processing node is acting as a coordinator node and if the processing node or one of the downstream nodes cannot support the arriving session, sending an abort message to the downstream nodes.

53. The method of claim 52 wherein the commit message includes a globally supportable QoS.

54. The method of claim 53 wherein the globally supportable QoS is a QoS contained in each response from the downstream nodes.

55. The method of claim 54 wherein step a) includes the step of preempting the other session if the processing node can support the arriving session only with preemption.

56. The method of claim 52 wherein the commit message includes a QoS contained in each response from the downstream nodes.

57. The method of claim 56 wherein the processing node processes an other session, and wherein step a) includes the step of preempting the other session if the processing node can support the arriving session only with preemption.

58. The method of claim 52 wherein the processing node processes an other session, and wherein step a) includes the step of preempting the other session if the processing node can support the arriving session only with preemption.

59. The method of claim 52 wherein the processing node processes an other session, and wherein step a) includes the step of shrinking a QoS of the other session if the processing node can support the arriving session only with preemption.

60. A method performed at each node of a plurality of nodes of a distributed data processing system, wherein each node is capable of acting as a coordinator node, an intermediate node, and a leaf node, and wherein each node receives an arriving session to process, the method comprising the following steps:

a) determining whether a corresponding node can support the arriving session;

b) if the corresponding node is acting as a coordinator node or an intermediate node, sending a support request to child nodes which are to process the arriving session;

c) if the corresponding node is acting as an intermediate node or a leaf node, sending a response to a parent node, wherein the response indicates whether the arriving session can be supported; and

,

d) if the corresponding node is acting as a coordinator node and if the arriving session can be supported by the nodes which are to process the arriving session, sending a commit message to the child nodes which are to process the arriving session.

61. The method of claim 60 wherein the corresponding node processes an other session, wherein the other session has a QoS associated therewith, and wherein step a) comprises the step of determining whether the corresponding node can support the arriving session based upon virtual shrinking of the QoS of the other session.

62. The method of claim 61 wherein step d) comprises the step of making the virtual shrinking of the QoS of the other session real if the child nodes can support the arriving session.

63. The method of claim 61 wherein step d) comprises the step of revoking the virtual shrinking of the QoS of the other session if the child nodes cannot support the arriving session.

64. The method of claim 61 wherein step a) comprises the step of attempting to lock the other session in order to prevent operations by another session on the other session to be locked.

65. The method of claim 61 wherein step a) comprises the step of determining whether the corresponding node can support the arriving session based upon virtual preemption of the other session.

66. The method of claim 65 wherein step d) comprises the step of making the virtual preemption of the other session real if the child nodes can support the arriving session.

67. The method of claim 65 wherein step d) comprises the step of revoking the virtual preemption of the other session if the child nodes cannot support the arriving session.

68. The method of claim 65 wherein step d) comprises the step of admitting a non-executing session if the corresponding node can support the arriving session and the non-executing session.

69. The method of claim 65 wherein step a) comprises the step of attempting to lock the other session in order to prevent operations by another session on the other session to be locked.

70. The method of claim 60 wherein the corresponding node processes an other session, and wherein step a) comprises the step of determining whether the corresponding node can support the arriving session based upon virtual preemption of the other session.

71. The method of claim 70 wherein step d) comprises the step of making the virtual preemption of the other session real if the child nodes can support the arriving session.

72. The method of claim 70 wherein step d) comprises the step of revoking the virtual preemption of the other session if the child nodes cannot support the arriving session.

73. The method of claim 70 wherein step d) comprises the step of admitting a non-executing session if the corresponding node can support the arriving session and the non-executing session.

74. The method of claim 70 wherein step a) comprises the step of attempting to lock the other session in order to prevent operations by another session on the other session to be locked.

75. The method of claim 60 wherein the corresponding node processes an other session, wherein the other session has a QoS associated therewith, and wherein step a) comprises the step of determining whether the corresponding node can support the arriving session based upon shrinking of the QoS of the other session.

76. The method of claim 75 wherein step a) comprises the step of attempting to lock the other session in order to prevent operations by another session on the other session to be locked.

77. The method of claim 75 wherein step a) comprises the step of determining whether the corresponding node can support the arriving session based upon preemption of the other session.

78. The method of claim 75 wherein step a) comprises the step of attempting to lock the other session in order to prevent operations by another session on the other session to be locked.

79. The method of claim 75 wherein step d) comprises the step of admitting a non-executing session if the corresponding node can support the arriving session and the non-executing session.

80. The method of claim 60 wherein the corresponding node processes an other session, and wherein step a) comprises the step of determining whether the corresponding node can support the arriving session based upon preemption of the other session.

81. The method of claim 60 wherein the corresponding node processes an other session, and wherein step a) comprises the step of attempting to lock the other session in order to prevent operations by another session on the other session to be locked.

82. The method of claim 60 wherein step d) comprises the step of admitting a non-executing session if the corresponding node can support the arriving session and the non-executing session.

83. The method of claim 60 wherein step d) comprises the step of sending, if the corresponding node is a coordinator node, an abort message to the child nodes if one of the child nodes cannot support the arriving session.

84. The method of claim 60 further comprising the step of permitting an application user to specify on-line a criticality level for a session, to specify on-line a timing requirement for the session, and to specify on-line a QoS for the session.

85. A method performed at a coordinator node of a distributed data processing system, wherein the coordinator node receives an arriving session to process, the method comprising the following steps:

a) determining whether the coordinator node can support the arriving session;

b) if the coordinator node can support the arriving session, sending a support request to child nodes which are to process the arriving session; and

,

c) if the coordinator node and all of the child nodes can support the arriving session, sending a commit message to the child nodes, wherein the commit message includes a globally supportable QoS for the arriving session.

86. The method of claim 85 wherein the coordinator node processes an other session, and wherein step a) comprises the step of preempting the other session if the coordinator node can support the arriving session only with preemption.

87. The method of claim 86 wherein step c) comprises the step of sending an abort message to the child nodes if one child node cannot support the arriving session.

88. The method of claim 86 wherein the globally supportable QoS is a QoS supportable by all child nodes of the coordinator node.

89. The method of claim 85 wherein step c) comprises the step of sending an abort message to the child nodes if one child node cannot support the arriving session.

90. The method of claim 85 wherein the globally supportable QoS is a QoS supportable by all child nodes of the coordinator node.

91. The method of claim 85 wherein the coordinator node processes an other session, wherein the other session has a QoS, and wherein step a) comprises the step of shrinking the QoS of the other session if the coordinator node can support the arriving session only with QoS shrinking.

92. The method of claim 91 wherein step a) comprises the step of preempting the other session if the coordinator node can support the arriving session only with preemption.

93. The method of claim 91 wherein the globally supportable QoS is a QoS supportable by all child nodes of the coordinator node.

94. A method performed at an intermediate node of a distributed data processing system, wherein the intermediate node is requested to process an arriving session, the method comprising the following steps:

a) determining whether the intermediate node can support the arriving session;

b) if the intermediate node can support the arriving session, passing a request from an upstream node to downstream nodes which are to process the arriving session, wherein the request requests the downstream nodes to determine supportability of the arriving session; and

,

c) sending a response to the request to the upstream node, wherein the response is a YES response if the intermediate node and the downstream nodes can support the arriving session, and wherein the response is a NO response if the intermediate node or one of the downstream nodes cannot support the arriving session.

95. The method of claim 94 wherein the response includes a QoS supportable by the intermediate node and by the downstream nodes.

96. The method of claim 94 wherein the intermediate node processes an other session, and wherein step a) comprises the step of preempting the other session if the intermediate node can support the arriving session only with preemption.

97. The method of claim 94 wherein the intermediate node processes an other session, wherein the other session has a QoS, and wherein step a) comprises the step of shrinking the QoS of the other session if the intermediate node can support the arriving session only with QoS shrinking.

98. The method of claim 97 wherein step a) comprises the step of preempting the other session if the intermediate node can support the arriving session only with preemption.

99. A method performed at a leaf node of a distributed data processing system, wherein the leaf node may be requested to process an arriving session, the method comprising the following steps:

a) determining whether the leaf node can support the arriving session; and

,

b) sending a response to a request from an upstream node, wherein the request asks whether the leaf node can support the arriving session, wherein the response is sent to the upstream node, wherein the response is a YES response if the leaf node can support the arriving session, and wherein the response is a NO response if the leaf node cannot support the arriving session, wherein the YES response includes a QoS supportable by the leaf node for the arriving session.

100. The method of claim 99 wherein the leaf node processes an other session, and wherein step a) comprises the step of preempting the other session if the leaf node can support the arriving session only with preemption.

101. The method of claim 99 wherein the leaf node processes an other session, wherein the other session has a QoS, and wherein step a) comprises the step of shrinking the QoS of the other session if the leaf node can support the arriving session only with QoS shrinking.

102. The method of claim 101 wherein step a) comprises the step of preempting the other session if the leaf node can support the arriving session only with preemption.