METHOD AND APPARATUS FOR RIPPLE RATE SENSITIVE AND BOTTLENECK AWARE RESOURCE ADAPTATION FOR REAL-TIME STREAMING WORKFLOWS

• US 20160050151A1
• Filed: 08/18/2014
• Published: 02/18/2016
• Est. Priority Date: 08/18/2014
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Kim, Hyun Joo, Gnanasambandam, Nathan, Jung, Gueyoung
• Granted Patent: US 9,674,093 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/788 Autonomous allocation of resources
• CPC Class Codes: H04L 47/83 based on usage prediction
• CPC Class Codes: H04L 65/80 Responding to QoS

Abstract

A method, non-transitory computer readable medium, and apparatus for adapting resources of the cluster of nodes for a real-time streaming workflow are disclosed. For example, the method receives a notification that a node of the cluster of nodes associated with an instance of a process of the real-time streaming workflow is predicted to be a bottleneck, identifies a number of hops to send a resource statement when the bottleneck is predicted that minimizes a ripple effect associated with transmitting the resource statement, transmits the resource statement to at least one or more nodes of the cluster of nodes within the number of hops, receives a response from one of the at least one or more nodes within the cluster of nodes and adapts a resource usage to the at least one of the one or more nodes within the cluster of nodes that the response was received from.

Claims

1. A method for adapting resources of the cluster of nodes for a real-time streaming workflow, comprising:

receiving, by a processor, a notification that a node of the cluster of nodes associated with an instance of a process of the real-time streaming workflow is predicted to be a bottleneck;

identifying, by the processor, a number of hops to send a resource statement when the bottleneck is predicted that minimizes a ripple effect associated with transmitting the resource statement;

transmitting, by the processor, the resource statement to one or more nodes of the cluster of nodes within the number of hops;

receiving, by the processor, a response from at least one of the one or more nodes within the cluster of nodes; and

adapting, by the processor, a resource usage to the at least one of the one or more nodes within the cluster of nodes that the response was received from.

2. The method of claim 1, wherein the resource usage comprises at least one of:

a memory resource or a processor resource.

3. The method of claim 1, wherein the predicting is based on D(L_i, t, p), wherein D is a data generation rate that is a function of an ith level L_i, at a time t of a process p and R(L_i, t, p), wherein R is data processing rate of the ith level L_i, at the time t of the process p.

4. The method of claim 1, wherein the number of hops is identified based on a difference between a desired load level and a current load level and a threshold value.

5. The method of claim 4, wherein the threshold value is based on a total delay comprising a sum of a round trip delay, a time required for evaluation and time to implement the adapting.

6. The method of claim 1, wherein the resource statement comprises a resource requirement and a location of a preceding node and a succeeding node.

7. The method of claim 6, wherein the resource requirement for an ith level, L_i, is a function of an inbound network bandwidth, a processing capability and an outbound network bandwidth.

8. The method of claim 1, wherein the response from the at least one of the one or more nodes within the cluster of nodes is based on an evaluation performed by the at least one of the one or more nodes within the cluster of nodes, wherein the evaluation is a comparison of an inbound network bandwidth, an outbound network bandwidth and a processing capability of the at least one of the one or more nodes within the cluster of nodes to an inbound network bandwidth, an outbound network bandwidth and a processing capability of the node.

9. The method of claim 1, wherein the adapting comprises a migration of the instance.

10. The method of claim 1, wherein the adapting comprises a duplication of the instance.

11. The method of claim 1, wherein the adapting is performed in serial when an adjacent node to the node is also predicted to be the bottleneck.

12. A non-transitory computer-readable medium storing a plurality of instructions which, when executed by a processor of an endpoint device, cause the processor to perform operations for adapting resources of the cluster of nodes for a real-time streaming workflow, the operations comprising:

receiving a notification that a node of the cluster of nodes associated with an instance of a process of the real-time streaming workflow is predicted to be a bottleneck;

predicting a bottleneck at the node based monitoring of the resource usage;

identifying a number of hops to send a resource statement when the bottleneck is predicted that minimizes a ripple effect associated with transmitting the resource statement;

transmitting the resource statement to one or more nodes of the cluster of nodes within the number of hops;

receiving a response from at least one of the one or more nodes within the cluster of nodes; and

adapting a resource usage to the one of the at least one or more nodes within the cluster of nodes that the response was received from.

13. The non-transitory computer-readable medium of claim 12, wherein the resource usage comprises at least one of:

a memory resource or a processor resource.

14. The non-transitory computer-readable medium of claim 12, wherein the number of hops is identified based on a difference between a desired load level and a current load level and a threshold value.

15. The non-transitory computer-readable medium of claim 14, wherein the threshold value is based on a total delay comprising a sum of a round trip delay, a time required for evaluation and time to implement the adapting.

16. The non-transitory computer-readable medium of claim 12, wherein the resource statement comprises a resource requirement and a location of a preceding node and a succeeding node.

17. The non-transitory computer-readable medium of claim 16, wherein the resource requirement for an ith level, L_i, is a function of an inbound network bandwidth, a processing capability and an outbound network bandwidth.

18. The non-transitory computer-readable medium of claim 12, wherein the adapting comprises a migration of the instance or a duplication of the instance.

19. The non-transitory computer-readable medium of claim 12, wherein the adapting is performed in serial when an adjacent node to the node is also predicted to be the bottleneck.

20. A method for adapting resources of the cluster of nodes for a real-time streaming workflow, comprising:

receiving, by a processor, a notification from an instance of a node of the cluster of nodes associated with the instance of a process of the workflow of continuously generated data that the instance is predicted to be a bottleneck, wherein the instance monitors an incoming data rate, an outgoing data rate and a processing rate and applies a Jackson network flow analysis or a Baskett-Chandy-Muntz-Palacios (BCMP) network flow analysis to predict the bottleneck;

identifying, by the processor, a number of hops to send a resource statement when the bottleneck is predicted that minimizes a ripple effect associated with transmitting the resource statement based a comparison of a different between a desired load level and a current load level to a threshold value;

transmitting, by the processor, the resource statement to all nodes of the cluster of nodes within the number of hops;

receiving, by the processor, a response from one or more of the all nodes within the cluster of nodes;

sending, by the processor, a notification to the one or more of the all nodes within the cluster of nodes to confirm that resources on the one or more of the all nodes within the cluster of nodes is still available;

receiving, by the processor, a confirmation in response to the notification; and

adapting, by the processor, a resource usage to the one or more of the all nodes within the cluster of nodes that the response and the confirmation were received from.