Method for applying stochastic control optimization for messaging systems

• US 7,792,038 B2
• Filed: 05/06/2008
• Issued: 09/07/2010
• Est. Priority Date: 06/27/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Strom, Robert Evan
• Primary Examiner(s): Yao; Kwang B
• Assistant Examiner(s): BOKHARI, SYED M
• Application Number:
  US12/115,742
• Publication Number:
  US 20080239951A1
• Time in Patent Office: 854 Days
• Field of Search: 370/538, 370/238, 370/416, 370/230, 370/235, 709/220, 709/207, 709/224, 713/166, 714/4, 726/11
• US Class Current: 370/235
• 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, wherein the policy specifies a first set of conditions for sending a message immediately from an upstream transform in an upstream server device to a downstream transform in a downstream server device via a network link and a second set of conditions for suppressing sending the message from the upstream transform in the upstream server device to the downstream transform in the downstream server device via the network link;

setting by the downstream transform in the downstream server device a threshold for upstream filtering of the messages sent from a plurality of upstream transforms in a plurality of upstream server devices to the downstream transform in the downstream server device based upon the policy;

sending by the downstream transform in the downstream server device the threshold for the upstream filtering of the messages to the plurality of upstream transforms in the plurality of upstream server devices via the network link;

filtering the messages by the plurality of upstream transforms in the plurality of upstream server devices during stream processing by selecting which of the messages to send from the plurality of upstream transforms based upon the threshold for the upstream filtering sent by the downstream transform in the downstream server device; and

determining by the downstream transform in the downstream server device whether to change the threshold for the upstream filtering by the plurality of upstream transforms in the plurality of upstream server devices during the stream processing based on a current state of the downstream transform, wherein the current state is one of a plurality of states that include the threshold for the upstream filtering, a number of tuples currently available for the downstream transform, a penalty for having fewer than a predetermined number of tuples currently available for the downstream transform during a unit of time, and a number of time units during which the downstream transform has fewer than the predetermined number of tuples, and wherein the penalty is based upon the number of time units during which the downstream transform has fewer than the predetermined number of tuples.

2. The computer implemented method of claim 1, wherein the probability statistics specify a frequency and a distribution of values representing changes in tuples contained in the messages.

3. The computer implemented method of claim 1, wherein the plurality of upstream server devices and the downstream server device are part of a distributed network of servers.

4. The computer implemented method of claim 1, further 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 by a server device offline an infinite horizon stochastic optimization problem utilizing the probability statistics and the cost function 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 plurality of states include a weighted sum of a number of messages associated with the cost function during the unit of time.

9. 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.

10. The computer implemented method of claim 1, wherein each tuple includes a new value and an old value for a computed value, and wherein both the new value and the old value for the computed value included in the tuple are compared with the threshold for the upstream filtering, and wherein when either the new value or the old value for the computed value exceeds the threshold for the upstream filtering the message is sent immediately from the upstream transform in the upstream server device to the downstream transform in the downstream server device via the network link.

11. A data processing system for controlling when to send messages, comprising:

a storage device, wherein the storage device stores a set of instructions; and

a processing unit, wherein the processing unit executes the set of instructions to determine a policy utilizing probability statistics and a cost function, wherein the policy specifies a first set of conditions for sending a message immediately from an upstream transform in an upstream server device to a downstream transform in a downstream server device via a network link and a second set of conditions for suppressing sending the message from the upstream transform in the upstream server device to the downstream transform in the downstream server device via the network link;

set by the downstream transform in the downstream server device a threshold for upstream filtering of the messages sent from a plurality of upstream transforms in a plurality of upstream server devices to the downstream transform in the downstream server device based upon the policy;

send by the downstream transform in the downstream server device the threshold for the upstream filtering of the messages to the plurality of upstream transforms in the plurality of upstream server devices via the network link;

filter the messages by the plurality of upstream transforms in the plurality of upstream server devices during stream processing by selecting which of the messages to send from the plurality of upstream transforms based upon the threshold for the upstream filtering sent by the downstream transform in the downstream server device; and

determine by the downstream transform in the downstream server device whether to change the threshold for the upstream filtering by the plurality of upstream transforms in the plurality of upstream server devices during the stream processing based on a current state of the downstream transform, wherein the current state is one of a plurality of states that include the threshold for the upstream filtering, a number of tuples currently available for the downstream transform, a penalty for having fewer than a predetermined number of tuples currently available for the downstream transform during a unit of time, and a number of time units during which the downstream transform has fewer than the predetermined number of tuples, and wherein the penalty is based upon the number of time units during which the downstream transform has fewer than the predetermined number of tuples.

12. The data processing system of claim 11, wherein the policy is determined by the processing unit by solving offline an infinite horizon stochastic optimization problem utilizing the probability statistics and the cost function.

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

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

15. The data processing system of claim 13, wherein at each unit 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 non-transitory computer readable medium encoded with computer executable instructions for controlling messages in a stream processing system, the non-transitory computer readable medium comprising:

computer executable instructions for determining a policy utilizing probability statistics and a cost function, wherein the policy specifies a first set of conditions for sending a message immediately from an upstream transform in an upstream server device to a downstream transform in a downstream server device via a network link and a second set of conditions for suppressing sending the message from the upstream transform in the upstream server device to the downstream transform in the downstream server device via the network link;

computer executable instructions for setting by the downstream transform in the downstream server device a threshold for upstream filtering of the messages sent from a plurality of upstream transforms in a plurality of upstream server devices to the downstream transform in the downstream server device based upon the policy;

computer executable instructions for sending by the downstream transform in the downstream server device the threshold for the upstream filtering of the messages to the plurality of upstream transforms in the plurality of upstream server devices via the network link;

computer executable instructions for filtering the messages by the plurality of upstream transforms in the plurality of upstream server devices during stream processing by selecting which of the messages to send from the plurality of upstream transforms based upon the threshold for the upstream filtering sent by the downstream transform in the downstream server device; and

computer executable instructions for determining by the downstream transform in the downstream server device whether to change the threshold for the upstream filtering by the plurality of upstream transforms in the plurality of upstream server devices during the stream processing based on a current state of the downstream transform, wherein the current state is one of a plurality of states that include the threshold for the upstream filtering, a number of tuples currently available for the downstream transform, a penalty for having fewer than a predetermined number of tuples currently available for the downstream transform during a unit of time, and a number of time units during which the downstream transform has fewer than the predetermined number of tuples, and wherein the penalty is based upon the number of time units during which the downstream transform has fewer than the predetermined number of tuples.

17. The non-transitory computer readable medium of claim 16, wherein the probability statistics include statistical information about an expected frequency of each input message.

18. The non-transitory computer readable medium of claim 16, further comprising:

computer executable instructions 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 non-transitory computer readable medium of claim 16, wherein the computer executable instructions for determining a policy further comprises:

computer executable instructions for solving offline an infinite horizon stochastic optimization problem utilizing the probability statistics and the cost function to determine an optimum policy that minimizes average cost per stage.

20. The non-transitory computer readable medium of claim 16, further comprising:

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