×

Method for decentralized load distribution in an event-driven system using localized migration between physically connected nodes and load exchange protocol preventing simultaneous migration of plurality of tasks to or from a same node

  • US 8,479,216 B2
  • Filed: 08/18/2009
  • Issued: 07/02/2013
  • Est. Priority Date: 08/18/2009
  • Status: Active Grant
First Claim
Patent Images

1. A method of decentralized load distribution in an event-driven system, the method comprising the steps of:

  • receiving a data flow to be processed by a plurality of tasks at a plurality of nodes in the event- driven system having stateful and stateless event processing components wherein the plurality of tasks are selected from the group consisting of hierarchical tasks, wherein a hierarchical task is a task that is dependent on the output of another task, nonhierarchical tasks, wherein a nonhierarchical task is a task that is not dependent on the output of another task, and mixtures thereof;

    collecting statistics about the execution of each task hosted at each node;

    creating a list of neighbor nodes, using the collected statistics, to which a task can be partially or wholly transferred;

    selecting at least one target task at a source node for consideration to migrate, to a target node, the target node selected from the list of neighbor nodes, to distribute the system load of processing the at least one target task;

    choosing the target node to which the at least one target task can be migrated wherein the target node meets predetermined criteria in terms of load distribution quality such that the target node must be physically connected to;

    (a) the source node hosting the target task, (b) a parent node hosting a parent task of the target task, and (c) a child node hosting a child task of the target task; and

    establishing a load exchange protocol at each node for governing the number of migrations of target tasks,wherein local decentralized load migrations lead to overall system load distribution in the event-driven system; and

    wherein the load exchange protocol comprises all of the following;

    (i) a decision to migrate the target task should not lead to oscillation such that a target task is migrated more than once to the target node and back to a node first hosting the target task;

    (ii) no simultaneous migration of 2 or more tasks to a single target node in a single machine cycle shall occur;

    (iii) no simultaneous migrations of 2 or more tasks from a node in a single machine cycle shall occur; and

    (iv) an end result of target task migration should improve load distribution in some manner.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×