Dynamic stabilization for a stream processing system

• US 7,613,848 B2
• Filed: 06/13/2006
• Issued: 11/03/2009
• Est. Priority Date: 06/13/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Silber, Jeremy I., Verscheure, Olivier, Amini, Lisa D., Sehgal, Anshul
• Primary Examiner(s): Tsai; Henry W. H.
• Assistant Examiner(s): Snyder; Steven G
• Application Number:
  US11/451,947
• Publication Number:
  US 20080005392A1
• Time in Patent Office: 1,239 Days
• Field of Search: 710/29, 710/56, 710/57, 710/60, 370229-237
• US Class Current: 710/29
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/80 Responding to QoS

Abstract

Disclosed are a method, upstream processing node, and computer readable medium for dynamically stabilizing a stream processing system. The method includes receiving at least one computing resource allocation target. The method further includes determining that an input data flow rate of at least one upstream processing element varies. The computing resource is dynamically allocated to the upstream processing element in response to the input rate of the upstream processing element varying. Data flow is dynamically controlled between the upstream processing element and at least one downstream processing element.

Claims

1. A method on a current processing element for dynamically stabilizing a stream processing system, the method comprising:

receiving at least one computing resource allocation target;

determining that a plurality of downstream processing elements are communicatively coupled to at least one upstream processing element, wherein each of the downstream processing elements in the plurality of downstream processing elements consumes data packets produced by the upstream processing element received on an output stream associated with the upstream processing element, wherein each of the downstream processing elements and the upstream processing element are each associated with at least one input buffer, wherein each downstream processing element processes data packets as they arrive in the input buffer associated therewith;

determining that an input data flow rate of the upstream processing element varies;

dynamically allocating the computing resource to a current processing element in response to the input data flow rate of the upstream processing element, wherein the allocating the computing resource is based on;

an input buffer occupancy of the current processing element;

at least one long-term averaged CPU goal of the current processing element; and

a maximum input rate of the at least one downstream processing element.

2. The method of claim 1, further comprising:

determining a maximum input rate of the at least one downstream processing element according to;

3. The method of claim 1, wherein the current processing element is allocated a first set of computing resources if:

the input buffer occupancy of the current processing element is greater than zero and below a predefined threshold; and

the upstream processing element has available tokens to expend on the first set of computing resources.

4. The method of claim 1, wherein the current processing element is allocated a second set of computing resources if:

the input buffer occupancy of the current processing element is greater than a predefined threshold and the upstream processing element has available tokens to expend on the second set of computing resources.

5. The method of claim 1, wherein dynamically allocating the computing resource further comprises:

allocating at least one token to the upstream processing element in proportion to a long-term CPU goal of the upstream processing element, wherein the upstream processing element expends the token for the computing resource thereby allowing the upstream processing element to process at least one data packet in accordance with a maximum input rate of the downstream processing element.

6. The method of claim 1, wherein the dynamically controlling of data flow is based on:

a data processing rate of the upstream processing element,

an input buffer occupancy of the current processing element, and

a maximum input rate of the downstream processing element, wherein the downstream processing element transmits its maximum input rate to the upstream processing element.

7. The method of claim 1, wherein dynamically controlling of data flow further comprises:

dynamically adjusting an input data flow rate of the upstream processing element thereby preventing an output rate of the upstream processing element from exceeding a maximum input of the downstream processing element;

analyzing each input buffer of each downstream processing element in the plurality of downstream processing elements;

determining that at least one downstream processing element in the plurality of downstream processing elements has a vacancy the input buffer associated with the at least one downstream processing element; and

instructing, in response to the least one downstream processing element having a vacancy, the upstream processing element to transmit a data packet on the output stream destined to be processed by the at least one downstream processing element.

19. The method of claim 1, wherein each of the downstream processing elements and the upstream processing element are each associated with a separate and distinct input buffer, and wherein the allocating the computing resource to the processing element in response to the input data flow rate of the upstream processing element-varying.

8. An upstream processing node in a distributed stream processing system, the upstream processing node comprising:

at least one upstream processing element;

a processing element monitor communicatively coupled to the upstream processing element adapted to;

determine that a plurality of downstream processing element are communicatively coupled to the upstream processing element, wherein each of the downstream processing elements in the plurality of downstream processing elements consumes data packets produced by the upstream processing element received on an output stream associated with the upstream processing element, wherein each of the downstream processing elements and the upstream processing element are each associated with at least one input buffer, wherein each downstream processing element processes data packets as they arrive in the input buffer associated therewith; and

determine that an input data flow rate of the upstream processing element varies;

a scheduler including;

a meta-scheduler communicatively coupled to the upstream processing element for determining computing resource allocation targets; and

a CPU scheduler communicatively coupled to the upstream processing element and the meta-scheduler adapted to dynamically perform

allocating the computing resource to the upstream processing element in response to the input data flow rate of the upstream processing element, wherein the allocating the computing resource is based on;

an input buffer occupancy of the upstream processing element;

at least one long-term averaged CPU goal of the upstream processing element; and

a maximum input rate of the at least one downstream processing element.

9. The upstream processing node of claim 8, wherein the upstream processing element is allocated a first set of computing resources if:

the input buffer occupancy of the upstream processing element is greater than zero and below a predefined threshold; and

the upstream processing element has available tokens to expend on the first set of computing resources.

10. The upstream processing node of claim 8, wherein dynamically allocating the computing resource further comprises:

allocating at least one token to the upstream processing element in proportion to a long-term CPU goal of the upstream processing element, wherein the upstream processing element expends the token for the computing resource thereby allowing the upstream processing element to process at least one data packet in accordance with a maximum input rate of the downstream processing element.

11. The upstream processing node of claim 8, wherein the dynamically controlling of data flow is based on:

a data processing rate of the upstream processing element;

an input buffer occupancy of the upstream processing element; and

a maximum input rate of the downstream processing element;

wherein the downstream processing element transmits its maximum input rate to the upstream processing element.

12. The upstream processing node of claim 8, wherein dynamically controlling of data flow further comprises:

dynamically adjusting an input data flow rate of the upstream processing element thereby preventing an output rate of the upstream processing element from exceeding a maximum input of the downstream processing element;

analyzing each input buffer of each downstream processing element in the plurality of processing elements;

determining that at least one downstream processing element in the plurality of downstream processing elements has a vacancy the input buffer associated with the at least one downstream processing element; and

instructing, in response to the least one downstream processing element having a vacancy, the upstream processing element to transmit a data packet on the output stream destined to be processed by the at least one downstream processing element.

20. The upstream processing node of claim 8, wherein the dynamically allocating the computing resource further comprises dynamically controlling data flow between the upstream processing element and the current processing element.

13. A computer program product for dynamically stabilizing a stream processing system, the computer program product comprising:

a storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising;

receiving at least one computing resource allocation target;

determining that a plurality of downstream processing elements are communicatively coupled to at least one upstream processing element, wherein each of the downstream processing elements in the plurality of downstream processing elements consumes data packets produced by the upstream processing element received on an output stream associated with the upstream processing element, wherein each of the downstream processing elements and the upstream processing element are each associated with at least one input buffer, wherein each downstream processing element processes data packets as they arrive in the input buffer associated therewith;

determining that an input data flow rate of the upstream processing element varies;

dynamically allocating the computing resource to the current processing element in response to the input data flow rate of the upstream processing element, wherein the allocating the computing resource is based on;

an input buffer occupancy of the current processing element;

at least one long-term averaged CPU goal of the current processing element; and

a maximum input rate of the at least one downstream processing element.

14. The computer program product of claim 13, wherein the current processing element is allocated a first set of computing resources if:

the input buffer occupancy of the current processing element is greater than zero and below a predefined threshold; and

the upstream processing element has available tokens to expend on the first set of computing resources.

15. The computer program product of claim 13, wherein the

current processing element is allocated a second set of computing resources if:

the input buffer occupancy of the current processing element is greater than a predefined threshold and the upstream processing element has available tokens to expend on the second set of computing resources.

16. The computer program product of claim 13, wherein dynamically allocating the computing resource further comprises:

allocating at least one token to the upstream processing element in proportion to a long-term CPU goal of the upstream processing element, wherein the upstream processing element expends the token for the computing resource thereby allowing the upstream processing element to process at least one data packet in accordance with a maximum input rate of the downstream processing element.

17. The computer program product of claim 13, wherein the dynamically controlling of data flow is based on:

a data processing rate of the upstream processing element,

an input buffer occupancy of the current processing element, and

a maximum input rate of the downstream processing element,

wherein the downstream processing element transmits its maximum input rate to the upstream processing element.

18. The computer program product of claim 13, wherein dynamically controlling of data flow further comprises:

dynamically adjusting an input data flow rate of the upstream processing element thereby preventing an output rate of the upstream processing element from exceeding a maximum input of the downstream processing element;

analyzing each input buffer of each downstream processing element in the plurality of downstream processing elements;

determining that at least one downstream processing element in the plurality of downstream processing elements has a vacancy the input buffer associated with the at least one downstream processing element; and

instructing, in response to the least one downstream processing element having a vacancy, the upstream processing element to transmit a data packet on the output stream destined to be processed by the at least one downstream processing element.

21. The computer program product of claim 13, wherein the dynamically allocating the computing resource further comprises dynamically controlling data flow between the upstream processing element and the current processing element.