Method for predicting performance of distributed stream processing systems

• US 8,499,069 B2
• Filed: 04/02/2008
• Issued: 07/30/2013
• 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): Nguyen, Thuong
• Assistant Examiner(s): HENDERSON, ESTHER BENOIT
• Application Number:
  US12/061,343
• Publication Number:
  US 20080184262A1
• Time in Patent Office: 1,945 Days
• Field of Search: 709/224
• 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 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, 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 in the first assignment each transform is assigned to a broker, and where the network comprises both links providing logical connections for data flows between entities in the network and channels providing physical media over which the data flows corresponding to the logical connections travel, the channels physically connecting the brokers, where one or more links are assigned to each channel in the first assignment;

performing optimization upon said first assignment of said plurality of transforms using said estimated performance to produce a second assignment, wherein performing optimization further comprises;

re-estimating the performance of said system based at least on computation of a flow service time Wf for each of said plurality of data flows and computation of a utilization for each of said plurality of brokers, each of said plurality of links, and each of said pluralities of channels;

identifying a most loaded channel having a highest one of said utilizations of said plurality of channels;

reassigning at least one transform from a highest utilized broker to brokers within a predetermined number of channels away from the highest utilized broker;

performing re-estimating and reassigning at least one transform for each of the brokers within the predetermined number of channels away from the highest utilized broker;

selecting a best reassignment from the reassigning at least one transform and as judged by the re-estimating as the second assignment; and

reassigning said plurality of transforms in accordance with said second assignment; and

where the reassigning said plurality of transforms results in at least one transform being reassigned from an initial broker to a different broker.

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

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

4. The method of claim 1, wherein said estimating and re-estimating comprises:

computing the flow service time W_f for each of said plurality of data flows, wherein computing a service flow service time W_f further comprises determining a queueing delay and an expected service time for each broker in each data flow and summing the queueing delay and the expected service time for each of the brokers in the data flow to determine the flow service time W_f for a corresponding flow; 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.

5. The method of claim 4 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.

6. The method of claim 1, wherein performing re-estimating and reassigning is repeated at least approximately 5,000 times.

7. The method of claim 6 wherein said performing re-estimating and reassigning is repeated at least approximately 10,000 times.

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

9. A memory 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, 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 in the first assignment each transform is assigned to a broker, and where the network comprises both links providing logical connections for data flows between entities in the network and channels providing physical media over which the data flows corresponding to the logical connections travel, the channels physically connecting the brokers, where one or more links are assigned to each channel in the first assignment;

performing optimization upon said assignment of said plurality of transforms using said estimated performance to produce a second assignment, wherein performing optimization further comprises;

re-estimating the performance of said system based at least on computation of a flow service time Wf for each of said plurality of data flows and computation of a utilization for each of said plurality of brokers, each of said plurality of links, and each of said pluralities of channels;

identifying a most loaded channel having a highest one of said utilizations of said plurality of channels;

reassigning at least one transform from a highest utilized broker to brokers within a predetermined number of channels away from the highest utilized broker;

performing re-estimating and reassigning at least one transform for each of the brokers within the predetermined number of channels away from the highest utilized broker;

selecting a best reassignment from the reassigning at least one transform and as judged by the re-estimating as the second assignment; and

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

10. The memory of claim 9, wherein said estimating and re-estimating comprises:

computing a flow service time W_f for each of said plurality of data flows, wherein computing a service flow service time W_f further comprises determining a queueing delay and an expected service time for each broker in each data flow and summing the queueing delay and the expected service time for each of the brokers in the data flow to determine the flow service time W_f for a corresponding flow;

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.

11. The memory of claim 10 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.

12. The memory of claim 9 wherein said performing optimization comprises changing at least one link between at least two of said plurality of brokers.

13. The memory of claim 9, wherein said performing re-estimating and reassigning is repeated at least approximately 5,000 times.

14. The memory of claim 13 wherein said performing re-estimating and reassigning is repeated at least approximately 10,000 times.

15. An apparatus comprising:

at least one memory comprising computer-readable code;

at least one processor configured, in response to executing the computer-readable code, to cause the apparatus to perform the following;

estimating a performance of a processing system using queueing theory, 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 in the first assignment each transform is assigned to a broker, and where the network comprises both links providing logical connections for data flows between entities in the network and channels providing physical media over which the data flows corresponding to the logical connections travel, the channels physically connecting the brokers, where one or more links are assigned to each channel in the first assignment; and

performing optimization upon said first assignment of said plurality of transforms using said estimated performance to produce a second assignment, wherein performing optimization further comprises;

re-estimating the performance of said system based at least on computation of a flow service time Wf for each of said plurality of data flows and computation of a utilization for each of said plurality of brokers, each of said plurality of links, and each of said pluralities of channels;

identifying a most loaded channel having a highest one of said utilizations of said plurality of channels;

reassigning at least one transform from a highest utilized broker to brokers within a predetermined number of channels away from the highest utilized broker;

performing re-estimating and reassigning at least one transform for each of the brokers within the predetermined number of channels away from the highest utilized broker;

selecting a best reassignment from the reassigning at least one transform and as judged by the re-estimating as the second assignment; and

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

16. The apparatus of claim 15 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.

17. The apparatus of claim 16 wherein said estimating and re-estimating comprises:

computing a flow service time W_f for each of said plurality of data flows, wherein computing a service flow service time W_f further comprises determining a queueing delay and an expected service time for each broker in each data flow and summing the queueing delay and the expected service time for each of the brokers in the data flow to determine the flow service time W_f for a corresponding flow; 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.

18. The apparatus of claim 17 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.

19. The apparatus of claim 15 wherein said performing optimization comprises performing broker bottleneck elimination.

20. 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 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, 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 in the first assignment each transform is assigned to a broker, and where the network comprises both links providing logical connections for data flows between entities in the network and channels providing physical media over which the data flows corresponding to the logical connections travel, the channels physically connecting the brokers, where one or more links are assigned to each channel in the first assignment;

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, wherein the computer usable program code for performing optimization further comprises;

computer usable program code for re-estimating the performance of said system based at least on computation of a flow service time Wf for each of said plurality of data flows and computation of a utilization for each of said plurality of brokers, each of said plurality of links, and each of said pluralities of channels;

computer usable program code for identifying a most loaded channel having a highest one of said utilizations of said plurality of channels;

computer usable program code for reassigning at least one transform from a highest utilized broker to brokers within a predetermined number of channels away from the highest utilized broker;

computer usable program code for performing re-estimating and reassigning at least one transform for each of the brokers within the predetermined number of channels away from the highest utilized broker;

computer usable program code for selecting a best reassignment from the reassigning at least one transform and as judged by the re-estimating as the second assignment; and

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

21. The computer program product of claim 20 wherein said computer usable program code for estimating and for re-estimating comprises:

computer code for computing a flow service time W_f for each of at least one data flow, wherein computing a service flow service time W_f further comprises determining a queueing delay and an expected service time for each broker in each data flow and summing the queueing delay and the expected service time for each of the brokers in the data flow to determine the flow service time W_f for a corresponding flow; 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.

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