US 8,150,994 B2Granted

Providing flow control and moderation in a distributed message processing system

AssigneeMicrosoft Corporation

InventorsWayne A. Clark, Lee B. Graber, Kartik Paramasivam, Siddhartha Roy, Sanjib Saha, Sumitra Sujanani

Life of this patent

Estimating the term…

Loading patent…

Abstract

Systems and methods for controlling the work load on a distributed system comprising a plurality of stages are provided. The capacity of a present stage is monitored, using either various resources of the present stage or rates of work completion and work receipt of the present stage. Information indicating the capacity of a succeeding stage are obtained and communicated to the present stage. The monitored capacity information of the present stage and the communicated information of the succeeding stage, either alone or in combination, are used to determine if a throttling action is necessary to control the load of work at the present stage. A provided throttling technique inserts an appropriate delay before the present stage to allow the present stage to process an amount of work without saturating the capacity of the present stage. This technique is applied at each stage of the distributed system to control the work load of the overall system by controlling the work load at each stage.

Claims13

Dependent claims

A method for implementing workflow in a distributed system, the method comprising:

performing workflow in a distributed system comprising a plurality of workflow stages operating in sequence to perform work associated with a given task, wherein each stage of the system performs a portion of the work associated with the given task and consumes one or more resources in performing such work;
and
performing a workflow control process to control workflow in the distributed system, wherein performing a workflow control process comprises:
each stage monitoring its own capacity to perform work by using a sliding window to monitor a first number of items of work transmitted to the each stage during the sliding window and a second number of items of work processed by the each stage during the sliding window and to predict a rate of new work received by the each stage and a rate at which work is being completed by the each stage, the monitored capacity to perform work is based on the rate at which work is being completed by the each stage and an overdrive factor such that the monitored capacity to perform work is greater than the rate at which work is being completed, the monitoring performed by the stage comprising:
comparing a state of a resource of the stage to a threshold value;
each stage obtaining information from a succeeding stage indicating a capacity of the succeeding stage to perform work;
and
each stage performing a throttling action based on a comparison between the information obtained from the succeeding stage, a quantitative threshold value maintained by the each stage, and said monitoring of its own capacity to perform work, the performing a throttling action by the stage comprising:
performing a throttling action if the rate of new work received by the stage is greater than the rate at which work is being completed by the stage, and
delaying the receipt of work by the stage by a time delay Ds, the time delay Ds being calculated in accordance with the following formula:
Ds
≥
[
(
(
Ni
+
Ns
)
·
Do
)
(
No
·
Of
)
]
-
Di
where Ni is the first number of items of work received by the stage;
Di is a duration over which Ni items of work were received by the stage;
No is the second number of items of work processed by the stage;
Do is a duration over which No items were processed by the stage;
Of is the overdrive factor;
and Ns is a number of items of work about to be received into the stage,
wherein each of the stages of the system may perform throttling actions independently to improve the overall throughput of the system.

34 more elements

A method for implementing workflow in a distributed computing environment, the method comprising:

performing workflow in a distributed computing environment comprising a plurality of workflow stages operating in sequence to perform work associated with a given task, wherein each stage of the distributed computing environment performs a portion of the work associated with the given task and consumes one or more resources in performing such work;
performing a workflow control process to control workflow in the distributed computing environment, wherein performing a workflow control process comprises:
each stage monitoring its own capacity to perform work by using a sliding window to monitor a first number of items of work transmitted to the each stage during the sliding window and a second number of items of work processed by the each stage during the sliding window and to predict a rate of new work received by the each stage and a rate at which work is being completed by the each stage;
each stage monitoring information from a succeeding stage indicating a capacity of the succeeding stage to perform work;
and
each stage performing a throttling action based on both a comparison between the information obtained from the succeeding stage and a quantitative threshold value maintained by the each stage and said monitoring of its own capacity to perform work,
wherein each of the stages of the distributed computing environment may perform throttling actions independently to improve the overall throughput of the system, and
wherein performing the throttling action by the stage comprises delaying the receipt of work by the stage by a time delay Ds determined as the function:
Ds
≥
[
(
(
Ni
+
Ns
)
·
Do
)
(
No
·
Of
)
]
-
Di
where Ni is the first number of items of work received by the stage, Di is a first duration over which the first number of items of work were received by the stage, No is the second number of items of work processed by the stage, Do is a duration over which the second number of items of work were processed by the stage, Of is an overdrive factor configured to increase the monitored capacity to perform work of the each stage, and Ns is a third number of items of work about to be received into the stage.

26 more elements

A computer readable device, disk, or memory storing program code which is executable by a computer to implement method steps for controlling workflow by a stage in a system comprising a plurality of workflow stages that operate in sequence to perform work associated with a given task, wherein each stage of the system performs a portion of the work associated with the given task, and wherein a given stage receives work from a previous stage and transmits work to a subsequent stage, wherein the method steps for controlling workflow by a given stage in the system comprise:

the stage monitoring its own capacity to perform work by using a sliding window to monitor a first number of items of work transmitted to the each stage during the sliding window and a second number of items of work processed by the each stage during the sliding window and to predict a rate of new work received by the each stage and a rate at which work is being completed by the each stage, the monitored capacity to perform work is based on the rate at which work is being completed by the each stage and an overdrive factor such that the monitored capacity to perform work is greater than the rate at which work is being completed, the monitoring performed by the stage comprising:
comparing a state of a resource of the stage to a threshold value;
the stage obtaining information from a succeeding stage indicating a capacity of the succeeding stage to perform work;
and
the stage performing a throttling action based on both a comparison between the information obtained from the succeeding stage and a quantitative threshold value maintained by the stage and said monitoring of its own capacity to perform work, the performing a throttling action by the stage comprising:
performing a throttling action if the rate of new work received by the stage is greater than the rate at which work is being completed by the stage, and
delaying the receipt of work by the stage by a time delay Ds, the time delay Ds being calculated in accordance with the following formula:
Ds
≥
[
(
(
Ni
+
Ns
)
·
Do
)
(
No
·
Of
)
]
-
Di
where Ni is the first number of items of work received by the stage;
Di is a duration over which Ni items of work were received by the stage;
No is the second number of items of work processed by the stage;
Do is a duration over which No items were processed by the stage;
Of is the overdrive factor;
and Ns is a number of items of work about to be received into the stage,
wherein the stage performs throttling actions independently of throttling actions of other stages of the system to improve the overall throughput of the system.

31 more elements

Dependencies are inferred from the claim text.

Facts

Application: 11/144,412Filed 3 Jun 2005
Published: US 2006/0277317 A17 Dec 2006
Granted: 3 Apr 2012
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

H04L 47/22
Flow control; Congestion control: traffic shaping
G06Q 10/06
Administration; Management: resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation…
H04L 47/25
Flow control; Congestion control: with rate being modified by the source upon detecting a change of network conditions
H04L
Digital communication

Family

US 2006/0277317 A1Pre-grant publication · published 7 Dec 2006
US 8,150,994 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key