Distributed aggregation on an overlay network
First Claim
1. In an overlay network including a plurality of first tier nodes, a plurality of second tier nodes, and at least one other node, each of the plurality of first tier nodes configured to send pre-aggregated event related data to second tier nodes in accordance with a corresponding recurring aggregation period, each of the second tier nodes configured to send aggregate total data to the at least one other node, in accordance with a second corresponding recurring aggregation period, a method for aggregating event related data, the method comprising:
- an act of a second tier node receiving pre-aggregated event related data and key values corresponding to one or more key IDs from a plurality of first tier nodes, wherein the second tier node has been has been partitioned to be responsible for the one or more key IDs within the overlay network;
an act of the second tier node aggregating the received pre-aggregated data for each of the one or more key IDs that the second tier node has been has been partitioned to be responsible for into an aggregate total for each of the one or more key IDs;
an act of the second tier node detecting that its corresponding recurring aggregation period has occurred; and
an act of the second tier node sending the aggregate total for each of the one or more key IDs to at least one other node.
2 Assignments
0 Petitions
Accused Products
Abstract
The present invention extends to methods, systems, and computer program products for distributed aggregation on an overlay network. Embodiments of the invention utilize tiers of nodes that are cascaded in a layered system. Each tier reduces the size of data by orders of magnitude through pre-aggregation. Thus, high volume streams of messages can be reduced to lower volume streams at large scales, such as, for example, the Internet. No central coordination is used; thus there is no central point of failure or bottleneck. When a node fails, other nodes in the same tier as the failing node automatically take over the responsibilities of the failed node.
-
Citations
20 Claims
-
1. In an overlay network including a plurality of first tier nodes, a plurality of second tier nodes, and at least one other node, each of the plurality of first tier nodes configured to send pre-aggregated event related data to second tier nodes in accordance with a corresponding recurring aggregation period, each of the second tier nodes configured to send aggregate total data to the at least one other node, in accordance with a second corresponding recurring aggregation period, a method for aggregating event related data, the method comprising:
-
an act of a second tier node receiving pre-aggregated event related data and key values corresponding to one or more key IDs from a plurality of first tier nodes, wherein the second tier node has been has been partitioned to be responsible for the one or more key IDs within the overlay network; an act of the second tier node aggregating the received pre-aggregated data for each of the one or more key IDs that the second tier node has been has been partitioned to be responsible for into an aggregate total for each of the one or more key IDs; an act of the second tier node detecting that its corresponding recurring aggregation period has occurred; and an act of the second tier node sending the aggregate total for each of the one or more key IDs to at least one other node. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. In an overlay network including a plurality of first tier nodes and at least one other node, each of the plurality of first tier nodes configured to periodically send pre-aggregated event related data to the at least one other node in accordance with a corresponding recurring aggregation period, a method for aggregating event related data, the method comprising:
-
an act of a first tier node receiving a plurality of event related messages, each event related message containing event related data and a key value corresponding to one or more of a plurality of different key IDs; an act of the first tier node pre-aggregating event related data from each received message within a local dictionary, wherein event related data corresponding to each particular key ID is aggregated within the local dictionary with the event related data for each other message corresponding to the same particular key ID, including at least aggregating event related data in a first message corresponding to a specified key ID with event related data in a second different message also corresponding to the specified key ID; an act of the first tier node detecting that its corresponding recurring aggregation period has occurred; an act of the first tier node routing a message to the at least one other node, the message containing pre-aggregated event related data and key values corresponding to the one or more of the plurality of different key IDs; and the first tier node removing from the local dictionary each entry corresponding to the pre-aggregated event related data and key values corresponding to the one or more of the plurality of different key IDs contained in the routed message. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. In a ring overlay network including a plurality of first tier nodes and a plurality of second tier nodes, and at least one other node, each first tier node having an recurring aggregation period, the recurring aggregation period indicating the frequency with which first tier nodes are to send pre-aggregated event related data to second tier nodes,
each of the plurality of first tier nodes configured to: -
a) receive a plurality of event related messages, each event related message containing event related data and a key value corresponding to one of a plurality of different key IDs, b) pre-aggregate event related data within a local dictionary such that, for each different key ID, event related data from different messages corresponding to the same key ID are aggregated within the local dictionary with event related data of the different messages corresponding to the same key ID, c) determine when the output timing interval has occurred, d) send a message to each second tier node for which the local dictionary contains data for at least one key ID that the second tier node has been partitioned to be responsible for within the overlay network in response to detecting the that the recurring aggregation period has occurred, and e) remove from the local dictionary each entry corresponding to the pre-aggregated event related data corresponding to the at least one key ID contained in the routed message, each second tier node having a second recurring aggregation period, the second recurring aggregation period indicating the frequency with which second tier nodes are to send pre-aggregated event related data to the at least one other node, each of plurality of second tier nodes configured to; a) receive pre-aggregated event related data from a plurality of first tier nodes for each key ID that the second tier node has been has been partitioned to be responsible for, b) aggregate received pre-aggregated data for each key ID that the second tier node has been has been partitioned to be responsible for into an aggregate total for each key ID, c) determine when the second recurring aggregation period has occurred, and d) send the aggregate total for each key ID to the at least one other node, a method for recovering from a node failure in the ring overlay network, the method comprising; an act of detecting that a node that is participating in aggregation of data within the ring overlay network has failed; an act of other nodes on the ring overlay network continuing to participate in aggregation in their configured capacity notwithstanding that the node has failed; an act of one or more of the other non-failing nodes in the same tier as the failing node each automatically assuming responsibility for aggregating at least a portion of the data that the failed node was responsible for prior to failure such that the one or more other non-failing nodes collectively assume responsibility for aggregating data in the capacity of the failed node; an act of making other nodes in the ring overlay network aware that the one or more other nodes have collective assumed responsibility for aggregating data in the capacity of the failed node; and an act of the other nodes reconfiguring themselves to interact with the one or more of other non-failing nodes to aggregate data in the ring overlay network. - View Dependent Claims (18, 19, 20)
-
Specification