Patent Document ID: 20090235251
Application ID: 12046262
Patent Flag: 0

Claim One:
1. In a computer system, an approach for placing a message transformation graph onto an overlay network of broker machines, to optimize a given objective function, consisting of: receiving an initial message transformation graph, a network topology, and expected performance properties of the initial message transformation graph and of network nodes and links, and a designation of particular stateless transformations in the transformation graph as being replicable; running a placement algorithm without replicating any transformations to determine a set of top N best task-to-broker assignments with respect to the given objective function, such as end-to-end latency; until the objective function improvement drops below a designated threshold, repeat an improvement step consisting of the following sub-steps: identifying a replicable transformation which forms the performance bottleneck, and designating it as the R-task for this step; augmenting the transformation graph by replicating the R-task; finding a best load distribution among the R-task's replicas such that the load distributions from the previous run of the placement algorithm are feasible solutions for the next run; deriving a set of starting points from the top N best task-to-broker assignments achieved from the previous run of the placement algorithm; re-executing the placement algorithm on the augmented graph, starting the search from the above derived starting points to determine a new set of top N placement best task-to-broker assignments; and determining a final optimal task-to-broker assignment from the best of the top N task-to-broker assignments.