STOCHASTIC CONTROL OPTIMIZATION FOR SENDER-BASED FLOW CONTROL IN A DISTRIBUTED STATEFUL MESSAGING SYSTEM

• US 20080306888A1
• Filed: 06/07/2007
• Published: 12/11/2008
• Est. Priority Date: 06/07/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dorai, Chitra, Hwang, Jeong-Hyon, Strom, Robert Evan
• Granted Patent: US 7,761,401 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests

Abstract

A method and system for controlling message flow in distributed stream processing. State transition probabilities in a Markov model having one state per staleness value of data are determined for sending or withholding updates of data to subscribers using expected message rates from an information provider. A cost function annotates each state transition in the model with a state transition cost for each decision to “send” or “withhold”. A propagation policy specifying whether to send or withhold the message is determined for each state. The propagation policy is then deployed. If a new message comprising an update of data is received during a lapsed time unit, a staleness value of the data held by subscribers is increased. The propagation policy is used to determine whether to send or withhold the message. If the message should be sent, the message is propagated and the staleness value of the data is reset.

Claims

1. A computer implemented method for generating a propagation policy for controlling message flow in an information dissemination environment, the computer implemented method comprising:

identifying a Markov model having one state per staleness value of data;

determining state transition probabilities in the Markov model for a decision to send a new message comprising updates of data to information subscribers and for a decision to withhold the new message from the information subscribers using expected message rates from a information provider;

using a cost function to annotate each state transition in the Markov model with a state transition cost for the decision to send the new message and the decision to withhold the new message;

determining a propagation policy for each state, wherein the propagation policy specifies whether to send the new message to the information subscribers or to withhold the new message from information subscribers; and

deploying the propagation policy.

2. The computer implemented method of claim 1, wherein determining a propagation policy for each state includes applying a stochastic optimization algorithm to determine whether to send the new message to the information subscribers or to withhold the new message from information subscribers.

3. The computer implemented method of claim 2, wherein the stochastic optimization algorithm minimizes an average cost per tick over an indefinite period.

4. The computer implemented method of claim 1, wherein the state transition probabilities are derived from estimated or previously observed statistics regarding update rates.

5. The computer implemented method of claim 2, wherein using a cost function to annotate each state transition probability in the Markov model with a state transition cost further comprises:

computing the state transition cost using a propagation cost of propagating the new message toward the information subscribers and a penalty which is a function of the staleness value for the data.

6. The computer implemented method of claim 1, wherein the Markov model comprises:

(a) parameters which define a staleness value as a function of a current staleness, (b) a probability that a new message will arrive during a current time unit, and (c) costs per transition for each value of the decision whether to send or withhold a latest message during the current time unit.

7. A computer implemented method for controlling message flow in distributed stream processing, the computer implemented method comprising:

responsive to a lapse of a time unit, determining whether a new message comprising an update of data was received from an information provider during the time unit;

responsive to a determination that a new message was received during the time unit, increasing a staleness value of data held by information subscribers and associated with the new message;

determining whether to send or withhold the new message to the information subscribers based on a propagation policy; and

responsive to a determination to send the new message, propagating the new message toward the information subscribers and resetting the staleness value of the data held by the information subscribers and associated with the new message.

8. The computer implemented method of claim 7, wherein the staleness value is a number of time units that have passed since an unsent updated state has been received.

9. The computer implemented method of claim 7, wherein the propagation policy specifies sending the new message if the staleness value is above a threshold, and withholding the new message if the staleness value is below a threshold.

10. A computer program product for generating a propagation policy for controlling message flow in an information dissemination environment, the computer program product comprising:

a computer usable medium having computer usable program code tangibly embodied thereon, the computer usable program code comprising;

computer usable program code for identifying a Markov model having one state per staleness value of data;

computer usable program code for determining state transition probabilities in the Markov model for a decision to send a new message comprising updates of data to information subscribers and for a decision to withhold the new message from the information subscribers using expected message rates from a information provider;

computer usable program code for using a cost function to annotate state transitions in the Markov model with a state transition cost for the decision to send the new message and the decision to withhold the new message;

computer usable program code for determining a propagation policy for each state, wherein the propagation policy specifies whether to send the new message to the information subscribers or to withhold the new message from information subscribers; and

computer usable program code for deploying the propagation policy.

11. The computer program product of claim 10, wherein the computer usable program code for determining a propagation policy for each state includes applying a stochastic optimization algorithm to determine whether to send to or withhold the new message from information subscribers.

12. The computer program product of claim 11, wherein the stochastic optimization algorithm minimizes an average cost per tick over an indefinite period.

13. The computer program product of claim 10, wherein the state transition probabilities are derived from estimated or previously observed statistics regarding update rates.

14. The computer program product of claim 11, wherein the computer usable program code for using a cost function to annotate each state transition probability in the Markov model with a state transition cost further comprises:

computer usable program code for computing the state transition cost using a propagation cost of propagating the new message toward the information subscribers and a penalty which is a function of the staleness value for the data.

15. The computer program product of claim 10, wherein the Markov model comprises (a) parameters which define a staleness value as a function of a current staleness, (b) a probability that a new message will arrive during a current time unit, and (c) costs per transition for each value of the decision whether to send or withhold a latest message during the current time unit.

16. A computer program product for controlling message flow in distributed stream processing, the computer program product comprising:

a computer usable medium having computer usable program code tangibly embodied thereon, the computer usable program code comprising;

computer usable program code for determining, in response to a lapse of a time unit, whether a new message comprising an update of data was received from an information provider during the time unit;

computer usable program code for increasing, in response to a determination that a new message was received during the time unit, a staleness value of data held by information subscribers and associated with the new message;

computer usable program code for determining whether to send or withhold the new message to the information subscribers based on a propagation policy; and

computer usable program code for propagating the new message toward the information subscribers and resetting the staleness value of the data held by the information subscribers and associated with the new message in response to a determination to send the new message.

17. The computer program product of claim 16, wherein the staleness value is a number of time units that have passed since an unsent updated state has been received.

18. The computer program product of claim 16, wherein the propagation policy specifies sending the new message if the staleness value is above a threshold, and withholding the new message if the staleness value is below a threshold.