Patent Document ID: 7840677
Application ID: 12046262
Patent Flag: 1

Claim One:
1. In a computer system having a processor, a method for placing a message transformation graph onto an overlay network of broker machines, to optimize a given objective function, the method consisting of: receiving in the processor 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 in the processor a placement algorithm without replicating any transformations to determine a set of task-to-broker assignments with respect to the given objective function, including end-to-end latency; setting a hash map value to empty; until the objective function improvement drops below a designated threshold, repeat an improvement step in the processor consisting of the following sub-steps: identifying a replicable transformation which forms the performance bottleneck, and designating the replicable transformation as a sensitive transformation for this step; augmenting the transformation graph by replicating the sensitive transformation; finding a best load distribution among the sensitive transformation's replicas such that the load distributions from the previous run of the placement algorithm are feasible solutions for a next run; deriving a set of starting points from the task-to-broker assignments achieved from a 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 task-to-broker assignments; and determining a final optimal task-to-broker assignment from the task-to-broker assignments storing a number of replicas and load distribution information for the replica transformation in the hash map.