Method for predicting performance of distributed stream processing systems

• US 7,818,417 B2
• Filed: 01/10/2006
• Issued: 10/19/2010
• Est. Priority Date: 01/10/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ginis, Roman, Strom, Robert E.
• Primary Examiner(s): Lee; Philip C
• Assistant Examiner(s): Benoit; Esther
• Application Number:
  US11/328,588
• Publication Number:
  US 20070174233A1
• Time in Patent Office: 1,743 Days
• Field of Search: 703/13, 703/22, 709/200, 709/224, 709/246
• US Class Current: 709/224
• CPC Class Codes: H04L 41/0853 by actively collecting configuration information or by backing up configuration information
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 41/50 Network service management, e.g. ensuring proper service fulfilment according to agreements

Abstract

A method comprises estimating a performance of a processing system using queuing theory wherein the processing system comprises a network that accepts at least one input message stream from a plurality of publishing clients, transforms the at least one input message stream into at least one output message stream utilizing the plurality of transforms distributed in a first assignment among the plurality of brokers, and delivers the at least one output message stream to at least one of the plurality of subscribing clients, performing optimization upon the assignment of the plurality of transforms using the estimated performance to produce a second assignment, and reassigning the plurality of transforms in accordance with the second assignment.

Claims

1. A method, comprising:

estimating a performance of a processing system using queuing theory, said processing system comprising a network that receives at least one input message stream from at least one publishing client, transforms said at least one input message stream into at least one output message stream utilizing a plurality of transforms distributed in a first assignment among a plurality of brokers, and outputs said at least one output message stream to at least one subscribing client, where a movement of one of said input message streams to one of said output message stream comprises a data flow passing through at least one of said plurality of brokers, where each transform performs a logical operation upon at least one corresponding input message stream to produce at least one corresponding output message stream, and where in the first assignment each transform is assigned to a broker;

performing optimization upon said first assignment of said plurality of transforms using said estimated performance to produce a second assignment; and

reassigning said plurality of transforms among said plurality of brokers connected to the network in accordance with said second assignment, and where the reassigning results in at least one transform being reassigned from an initial broker to a different broker;

where estimating comprises;

computing a flow service time Wf for each of a plurality of data flow in the network and a utilization for each of said plurality of brokers connected to the network;

computing a current solution value comprising a sum of a plurality of products of each of a plurality of flow service times in the network and a corresponding weight indicative of an importance of a single one of said plurality of flow service times in the network with respect to other ones of said plurality of flow service times in the network.

3. The method of claim 1 wherein a weight is indicative of an importance of a single one of said flow service time with respect to other ones of said flow service time.

4. The method of claim 1 wherein performing optimization comprises the steps of:

a. identifying a highest utilized broker having a highest one of said plurality of utilizations;

b. identifying at least one other one of said plurality of brokers forming a neighbor of said highest utilized broker identified;

c. reassigning in sequential fashion said plurality of transforms assigned to said highest utilized broker to one of a plurality of neighboring brokers;

d. estimating a performance of said system and repeating step c wherein said reassigned one of said plurality of transforms is reassigned to a different one of said plurality of neighboring brokers;

e. repeating steps c-d until all of said plurality of neighboring brokers have been utilized; and

f. selecting a reassignment from step c having a best estimated performance in step d to be said second assignment.

5. The method of claim 4 wherein said steps c-d are repeated at least approximately 5,000 times.

6. The method of claim 4 wherein said steps c-d are repeated at least approximately 10,000 times.

7. The method of claim 1 wherein performing optimization comprises changing at least one link between at least two of said plurality of brokers.

15. The method of claim 1, wherein at least two of the plurality of transforms are assigned to one of the brokers in the first assignment and wherein at least one of the at least two transforms assigned to the one broker is assigned to another broker in the second assignment.

2. A memory embodying a program of machine-readable instructions executable by a digital processing apparatus to perform operations to optimize an assignment of transforms, the operations comprising:

estimating a performance of a processing system using queuing theory, said processing system comprising a network that receives at least one input message stream from at least one publishing client, transforms said at least one input message stream into at least one output message stream utilizing a plurality of transforms distributed in a first assignment among a plurality of brokers, and outputs said at least one output message stream to at least one subscribing client, where a movement of one of said input message streams to one of said output message streams comprises a data flow passing through at least one of said plurality of brokers, where each transform performs a logical operation upon at least one corresponding input message stream to produce at least one corresponding output message stream, and where in the first assignment each transform is assigned to a broker;

performing optimization upon said first assignment of said plurality of transforms using said estimated performance to produce a second assignment; and

reassigning said plurality of transforms among said plurality of brokers connected to the network in accordance with said second assignment, and where the reassigning results in at least one transform being reassigned from an initial broker to a different broker;

where estimating comprises;

computing a flow service time Wf for each of a plurality of data flows in the network and a utilization for each of said plurality of brokers connected to the network; and

computing a current solution value comprising a sum of a plurality of products of each of a said plurality of flow service times in the network and a corresponding weight indicative of an importance of a single one of said plurality of flow service times in the network with respect to other ones of said plurality of flow service times in the network.

8. A system comprising:

a network comprising a plurality of brokers that accepts at least one input message stream, transforms said at least one input message stream into at least one output message stream utilizing a plurality of transforms distributed in a first assignment among said plurality of brokers, and outputs said at least one output message stream, where each transform performs a logical operation upon at least one corresponding input message stream to produce at least one corresponding output message stream, and where in the first assignment each transform is assigned to a broker;

means for estimating a performance of said system using queuing theory; and

means for performing optimization upon said first assignment of said plurality of transforms using said estimated performance to produce a second assignment; and

means for reassigning said plurality of transforms in accordance with said second assignment, and where the reassigning results in at least one transform being reassigned from an initial broker to a different broker;

means for computing a flow service time Wf for each of a plurality of data flows and a utilization for each of said plurality of brokers; and

means for computing a current solution value comprising a sum of a plurality of products of each of a plurality of flow service times and a corresponding weight.

9. The system of claim 8 wherein a movement of one of said input message streams to one of said output message streams comprises a data flow passing through at least one of said plurality of brokers.

10. The system of claim 9 wherein each of a plurality of weights is indicative of an importance of a single one of said plurality of flow service times with respect to other ones of said plurality of flow service times.

11. The system of claim 8 wherein said means for performing optimization comprises a means for performing broker bottleneck elimination.

12. A computer program product comprising a memory having computer usable program code for optimizing an assignment of a plurality of transforms amongst a plurality of brokers, said computer program product including:

computer usable program code for estimating a performance of a processing system using queuing theory wherein a processing system comprises a network that receives at least one input message stream, transforms said at least one input message stream into at least one output message stream utilizing a plurality of transforms distributed in a first assignment among a plurality of brokers, and outputs said at least one output message stream, where each transform performs a logical operation upon at least one corresponding input message stream to produce at least one corresponding output message stream, and where in the first assignment each transform is assigned to a broker;

computer usable program code for performing optimization upon said first assignment of said plurality of transforms using said estimated performance to produce a second assignment; and

computer usable program code for reassigning said plurality of transforms in accordance with said second assignment, and where the reassigning results in at least one transform being reassigned from an initial broker to a different broker;

computer code for computing a flow service time Wf for each of at least one data flow and a utilization for each of a plurality of broker machines; and

computer code for computing a current solution value comprising a sum of a plurality of products of each of an at least one flow service times and a corresponding weight.

13. The computer program product of claim 12 wherein said computer usable program code for estimating comprises:

computer code for identifying a highest utilized broker having a highest one of a plurality of utilizations;

computer code for identifying at least one other one of said plurality of brokers forming a neighbor of said highest utilized broker identified;

computer code for reassigning in sequential fashion said plurality of transforms assigned to said highest utilized broker to one of a plurality of neighboring brokers;

computer code for estimating a performance of said processing system and repeating said reassigning wherein said reassigning one of said plurality of transforms is reassigned to a different one of said plurality of neighboring brokers;

computer code for repeating said reassigning until all of said plurality of neighboring brokers have been utilized; and

computer code for selecting a reassignment from having a best estimated performance in to be said second assignment.

14. The computer program product of claim 12 wherein said computer code for performing said optimization comprises changing a link between at least two of said plurality of brokers.

16. The computer program product of claim 12, wherein at least two of the plurality of transforms are assigned to one of the brokers in the first assignment and wherein at least one of the at least two transforms assigned to the one broker is assigned to another broker in the second assignment.