Method for predicting performance of distributed stream processing systems

• US 20070174233A1
• Filed: 01/10/2006
• Published: 07/26/2007
• Est. Priority Date: 01/10/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ginis, Roman, Strom, Robert
• Granted Patent: US 7,818,417 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 queueing 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 queueing theory wherein said 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;

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 in accordance with said second assignment.

2. The method of claim 1 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.

3. The method of claim 1 wherein said network receives said at least one input message stream from at least one publishing client.

4. The method of claim 1 wherein said network outputs said at least one output message stream to at least one subscribing client.

5. The method of claim 2 wherein said estimating comprises:

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

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

6. The method of claim 5 wherein a weight 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.

7. The method of claim 5 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 identified utilized broker;

c. reassigning in sequential fashion said plurality of transforms assigned to said highest utilized broker to one of said 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.

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

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

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

11. A signal bearing medium tangibly 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 queueing theory, said processing system comprising;

a network comprising a plurality of brokers 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 said plurality of brokers, and outputs said at least one output message stream;

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

reassigning said plurality of transforms in accordance with said second assignment.

12. The signal bearing medium of claim 11 wherein each 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.

13. The signal bearing medium of claim 12 wherein said estimating comprises:

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

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

14. The signal bearing medium of claim 13 wherein a weight 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.

15. The signal bearing medium of claim 13 wherein said 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 identified utilized broker;

c. reassigning in sequential fashion said plurality of transforms assigned to said highest utilized broker to one of said 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 improved assignment.

16. The signal bearing medium of claim 11 wherein said performing optimization comprises changing at least one link between at least two of said plurality of brokers.

17. The signal bearing medium of claim 15 wherein steps c-d are repeated at least approximately 5,000 times.

18. The signal bearing medium of claim 17 wherein steps c-d are repeated at least approximately 10,000 times.

19. 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;

means for estimating a performance of said processing system using queueing 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.

20. The system of claim 19 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.

21. The system of claim 20 wherein said estimating means comprises:

means for computing a flow service time W_f for each of said 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 said plurality of flow service times and a corresponding weight.

22. The system of claim 21 wherein each of said 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.

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

24. A broker machine comprising:

at least one transform through which passes at least one data flow wherein said broker machine is coupled to at least one other broker machine comprising at least one transform, said transforms forming a first assignment of a plurality of transforms;

means for estimating a performance of said broker machine using queuing theory;

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

means for modifying an assignment of at least one of said plurality of transforms in accordance with said second assignment.

25. The broker machine of claim 24 wherein said estimating means comprises:

means for computing a flow service time W_f for said at least one data flow and a utilization for each of said plurality of broker machines; and

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

26. A computer program product comprising a computer usable medium 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 queueing theory wherein said 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;

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.

27. The computer code of claim 26 wherein said computer usable program code for estimating comprises:

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

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

28. The computer code of claim 27 wherein said computer usable program code for estimating comprises:

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

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

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

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

computer code for repeating said reassigment 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.

29. The computer code of claim 27 wherein said computer code for performing said optimization comprises changing a link between at least two of said plurality of brokers.