METHOD FOR APPLYING STOCHASTIC CONTROL OPTIMIZATION FOR MESSAGING SYSTEMS

• US 20080239951A1
• Filed: 05/06/2008
• Published: 10/02/2008
• Est. Priority Date: 06/27/2006
• Status: Active Grant

• Current Assignee: Robert Evan Strom
• Original Assignee: Robert Evan Strom
• Inventors: STROM, ROBERT EVAN
• Granted Patent: US 7,792,038 B2
• Time in Patent Office: Days
• US Class Current: 370/230
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests

Abstract

A computer implemented method, apparatus, and computer usable program code for controlling when to send messages in a stream processing system. A policy is determined by utilizing probability statistics and a cost function prior to stream processing. The policy specifies under which conditions a message is sent eagerly and under which other conditions the message is delayed. A filter is operated during stream processing that selects which of the messages to send from a sending transform based upon a threshold. A controller is operated during stream processing that observes a current state of a receiving transform and that applies the policy based on the current state to determine whether to change the threshold.

Claims

1. A computer implemented method for controlling when to send messages in a stream processing system, the computer implemented method comprising:

determining a policy utilizing probability statistics and a cost function prior to stream processing, wherein the policy specifies under which conditions a message is sent eagerly and under which other conditions the message is delayed;

operating a filter during stream processing that selects which of the messages to send from a sending transform based upon a threshold; and

operating a controller during stream processing that observes a current state of a receiving transform and that applies a policy based on the current state to determine whether to change the threshold.

2. The computer implemented method of claim 1, wherein the probability statistics specify frequency values and distribution values of the messages.

3. The computer implemented method of claim 1, wherein the messages are sent from the sending transform on a first server to the receiving transform on a second server, wherein the first server and the second server are part of a distributed network of servers.

4. The computer implemented method of claim 1, comprising:

receiving user input specifying the cost function, wherein the cost function indicates relative weights given to a cost of sending messages weighed against a cost of delaying delivering messages to clients.

5. The computer implemented method of claim 1, wherein the determining a policy step further comprises:

solving an infinite horizon stochastic optimization problem to determine an optimum policy that minimizes average cost per stage.

6. The computer implemented method of claim 5, wherein the solving step comprises:

using Bellman'"'"'s recurrence equation.

7. The computer implemented method of claim 5, wherein the optimum policy is chosen to minimize an expected cost per time period based on a weighted sum of costs due to message traffic and costs due to delays.

8. The computer implemented method of claim 1, wherein the current state is one of a plurality of states, and wherein the plurality of states include the threshold, a number of tuples available for a top-K transform, a weighted sum of a number of messages associated with the cost during a tick, and a penalty for having fewer than K tuples available during the tick.

9. The computer implemented method of claim 8, wherein the plurality of states includes a number of time units during which the stream processing system has fewer than K tuples, wherein the penalty depends upon the number of time units.

10. The computer implemented method of claim 5, wherein the cost function is supplied by a user, and wherein the optimum policy maps the current state to a decision whether and how much to change the threshold.

11. A system comprising:

a data processing system for receiving stream data from input streams, wherein the data processing system determines a policy utilizing probability statistics and a cost function, wherein the policy specifies under which conditions messages are sent eagerly and under which other conditions messages are delayed, to minimize an expected cost per time period for sending the messages, and distributes segments onto hosts for correlation processing; and

a plurality of hosts operably connected to the data processing system, wherein the messages are sent between each of the plurality of hosts;

wherein the data processing system sends the policy to the plurality of hosts for controlling when the messages are sent between the plurality of hosts,

wherein a sending host of the plurality of hosts operates a filter that selects which of the messages to send from a sending transform based upon a threshold, and

wherein a receiving host of the plurality of hosts includes a controller that senses the threshold and a current state of a receiving transform to implement the policy, and determines whether to change the threshold.

12. The system of claim 11, wherein the policy is determined by the data processing system by solving offline an infinite horizon stochastic optimization problem.

13. The system of claim 12, wherein an optimum policy is determined from solving the infinite horizon stochastic optimization problem specifies parameters for the controller within the data processing system, wherein the parameters are executed at run-time to determine how the messages are sent.

14. The system of claim 11, wherein the cost function calibrates how undesirable it is to send traffic over a network link versus how undesirable it is to have an unnecessary delay in displaying a result.

15. The system of claim 12, wherein at each tick of time, the controller observes states and applies the policy to the current state to compute an action from a set of possible actions.

16. A computer program product comprising a computer usable medium including computer usable program code for controlling messages in a stream processing system, the computer program product comprising:

computer usable program code for determining a policy utilizing probability statistics and a cost function prior to stream processing, wherein the policy specifies under which conditions a message is sent eagerly and under which other conditions the message is delayed;

computer usable program code for operating a filter during stream processing that selects which of the messages to send from a sending transform based upon a threshold; and

computer usable program code for operating a controller during stream processing that observes a current state of a receiving transform, and that applies a policy based on the current state to determine whether to change the threshold.

17. The computer program product of claim 16, wherein the probability statistics includes statistical information about an expected frequency of each input message.

18. The computer program product of claim 16, comprising:

computer usable program code for receiving user input specifying the cost function, wherein the cost function indicates relative weights given to a cost of sending messages weighed against a cost of delaying delivering messages to clients.

19. The computer program product of claim 16, wherein the computer usable program code for determining a policy further comprises:

computer usable program code for solving an infinite horizon stochastic optimization problem to determine an optimum policy that minimizes average cost per stage.

20. The computer program product of claim 16, further comprising:

computer usable program code for determining a utility metric in the policy specifying how undesirable it is to send traffic over a network link versus how undesirable it is to have an unnecessary delay in displaying a result