Maximal flow scheduling for a stream processing system
View Patent ↗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.
1. A method on an upstream processing node for processing data packets, the method comprising:
receiving an allocation for at least one computing resource, wherein receiving an 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 a resulting data packet;
prioritizing allocation of the at least one computing resource based on the weight which has been assigned, wherein prioritizing allocation of the at least one computing resource maximizes the information gained among the one or more upstream processing elements; and
allocating the at least one computing resource to at least one or more upstream processing elements based upon an allocation order determined from prioritizing allocation of the at least one computing resource;
receiving at least one data packet at the at least 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;
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, wherein at least two downstream processing elements of the plurality of processing elements include different input rates;
determining a fastest input rate from the input data rate received from the plurality of downstream processing elements;
transmitting, in response to the determining, the resulting data packet from the upstream processing element to the downstream processing element, wherein transmitting the resulting data packet further 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 closest to the fastest input rate of the plurality of downstream processing elements which has been determined; and
buffering a processed data packet in the output queue of the downstream processing element.