Maximal flow scheduling for a stream processing system

• US 20070299980A1
• Filed: 06/13/2006
• Published: 12/27/2007
• Est. Priority Date: 06/13/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Amini, Lisa D., Sehgal, Anshul, Silber, Jeremy I., Verscheure, Olivier, Wolf, Joel L.
• Granted Patent: US 7,493,406 B2
• Time in Patent Office: Days
• US Class Current: 709/231
• 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 49/90 Buffering arrangements
• CPC Class Codes: H04L 65/75 Media network packet handling

Abstract

Disclosed is a method, upstream processing node, and computer readable medium for processing data packets. The method includes receiving an allocation for at least one computing resource. At least one data packet at one or more upstream processing elements in an upstream processing node is received. The method also includes determining if at least one output queue of the upstream processing elements includes available space for processing of the data packet. The data packet is processed in response to the output queue including available space to form a resulting data packet. The method further includes determining that an input queue of at least one downstream processing element of a plurality of downstream processing elements includes available space for receiving the resulting data packet In response to the determining, the resulting data packet is transmitted from the upstream processing element to the downstream processing element.

Claims

1. A method on an upstream processing node for processing data packets, the method comprising:

receiving an allocation for at least one computing resource;

receiving at least one data packet at one or more upstream processing elements in an upstream processing node;

determining if at least one output queue of the upstream processing elements includes available space for processing of the data packet;

processing the data packet in response to the output queue including available space to form a resulting data packet;

determining that an input queue of at least one downstream processing element of a plurality of downstream processing elements includes available space for receiving the resulting data packet; and

transmitting, in response to the determining, the resulting data packet from the upstream processing element to the downstream processing element.

2. The method of claim 1, further comprising:

receiving at least one input rate data from the plurality of downstream processing elements communicatively coupled to the output queue of the upstream processing element;

determining a fastest input rate from the input data rate received from the plurality of downstream processing elements; and

wherein the transmitting includes transmitting data packets to each of the plurality of downstream processing elements communicatively coupled to the output queue of the upstream processing element at an average rate substantially similar to the fastest input rate of the plurality of downstream processing elements which has been determined.

3. The method of claim 2, wherein at least two downstream processing elements of the plurality of processing elements include different input rates.

4. The method of claim 1, further comprising:

buffering a processed data packet in the output queue of the downstream processing element.

5. The method of claim 1, wherein the receiving of the allocation of at least one computer resource further comprises:

assigning a weight to the one or more upstream processing elements based upon information gained from the one or more upstream processing elements during processing of the data packet to form the resulting data packet;

prioritizing allocation of the at least one computing resource based on the weight which has been assigned; and

allocating the at least one computing resource to the at least one or more upstream processing elements based upon an allocation order determined from the prioritization.

6. The method of claim 5, wherein the prioritizing maximizes the information gained among the one or more upstream processing elements.

7. An upstream processing node for processing data streams, the process node comprising:

a memory;

at least one upstream processing element communicatively coupled to the memory, wherein the processing element receives at least one data packet and forms a processed data packet therefrom;

a scheduler including;

a meta-scheduler communicatively coupled to the memory and the upstream processing element, the meta scheduler for allocating computing resources to the upstream processing element; and

a CPU scheduler communicatively coupled to the meta-scheduler and the upstream processing element for determining that an output queue of the upstream processing element includes available space for processing of the data packet and for determining that an input queue of at least one downstream processing element of a plurality of downstream processing elements includes available space for receiving the processed data packet; and

an output queue communicatively coupled to the upstream processing element for transmitting the processed data packet from the upstream processing element to the downstream processing element.

8. The upstream processing node of claim 7, wherein the CPU scheduler further comprises:

a receiver for receiving input rate data from each downstream processing element communicatively coupled to the output queue of the upstream processing element;

a comparator for determining a fastest input rate from the input data rate received from the plurality of downstream processing elements; and

wherein the output queue transmits the processed data packet to the plurality of downstream processing elements communicatively coupled to the output queue of the processing element at an average rate substantially similar to the fastest input rate of the plurality of downstream processing elements which has been determined.

9. The upstream processing node of claim 8, wherein at least two downstream processing elements of the plurality of downstream processing elements include different input rates.

10. The upstream processing node of claim 7, wherein the CPU scheduler buffers a processed data packet in the output queue of the upstream processing element.

11. The upstream processing node of claim 7, wherein meta-scheduler further comprises:

means for assigning a weight to at least one of the upstream processing elements based upon information gained from the at least one of the upstream processing elements during processing at least one data packet;

prioritizes allocation of the at least one computing resource based on the weight; and

allocates the at least one computing resource to the at least one of the upstream processing elements based upon an allocation order determined from the prioritization.

12. The upstream processing node of claim 11, wherein the prioritizing maximizes the information gain among the at least one of the upstream processing elements.

13. A computer readable medium for processing data packets, the computer readable medium comprising instructions for:

receiving an allocation for at least one computing resource;

receiving at least one data packet at one or more upstream processing elements in an upstream processing node;

determining if at least one output queue of the upstream processing elements includes available space for processing of the data packet;

processing the data packet in response to the output queue including available space to form a resulting data packet;

determining that an input queue of at least one downstream processing element of a plurality of downstream processing elements includes available space for receiving the resulting data packet; and

transmitting, in response to the determining, the resulting data packet from the upstream processing element to the downstream processing element.

14. The computer readable medium of claim 13, further comprising instructions for:

receiving at least one input rate data from the plurality of downstream processing elements communicatively coupled to the output queue of the upstream processing element;

determining a fastest input rate from the input data rate received from the plurality of downstream processing elements; and

wherein the transmitting includes transmitting data packets to each of the plurality of downstream processing elements communicatively coupled to the output queue of the upstream processing element at an average rate substantially similar to the fastest input rate of the plurality of downstream processing elements which has been determined.

15. The computer readable medium of claim 14, wherein at least two downstream processing elements of the plurality of processing elements include different input rates.

16. The computer readable medium of claim 14, further comprising instructions for:

buffering a processed data packet in the output queue of the downstream processing element.

17. The computer readable medium of claim 14, wherein the allocation of at least one computer resource comprises:

assigning a weight to the one or more upstream processing elements based upon information gained from the one or more upstream processing elements during processing the data packet to form the resulting data packet;

prioritizing allocation of the at least one computing resource based on the weight which has been assigned; and

allocating the at least one computing resource to the at least one or more upstream processing elements based upon an allocation order determined from the prioritization.

18. The computer readable medium of claim 17, wherein the prioritizing maximizes the information gained among the one or more processing elements.