DISTRIBUTED AGGREGATION ON AN OVERLAY NETWORK

• US 20100268808A1
• Filed: 04/21/2009
• Published: 10/21/2010
• Est. Priority Date: 10/24/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mohsin, Mansoor, Hill, Richard D., Chkodrov, Gueorgui, Marucheck, Michael J., Dopson, Dave
• Granted Patent: US 8,176,200 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: G06F 11/2028 eliminating a faulty processor or activating a spare
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 11/3495 for systems
• CPC Class Codes: G06F 2201/86 Event-based monitoring
• CPC Class Codes: G06F 2201/875 Monitoring of systems including the internet
• CPC Class Codes: G06F 2201/885 Monitoring specific for caches

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.

Claims

1. 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 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 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 different messages corresponding to the same key ID for each corresponding different key ID within a local dictionary, including 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; and

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 for the one or more of the plurality of different key IDs.

2. The method as recited in claim 1, wherein the overlay network is a ring overlay.

3. The method as recited in claim 2, wherein the an act of the first tier node pre-aggregating event related data from different messages corresponding to the same key ID comprises an act of the first node using a hash algorithm to convert the key ID into a key ID hash representative of an ID in the ID space of the ring overlay.

4. The method as recited in claim 3, wherein an act of the first tier node routing a message to the at least one other node comprises an act of sending the message to the ID in the ID space of the ring overly.

5. The method as recited in claim 1, wherein the act of the first tier node pre-aggregating event related data from different messages corresponding to the same key ID for each corresponding different key ID within a local dictionary comprises an act of creating a dictionary entry for a key ID.

6. The method as recited in claim 1, wherein the act of the first tier node pre-aggregating event related data from different messages corresponding to the same key ID for each corresponding different key ID within a local dictionary comprises an act of merging received data for a key ID with existing data in the data dictionary for the key ID.

7. The method as recited in claim 1, wherein the act of the first tier node routing a message to the at least one other node comprises an act of the first tier node routing a message to one or more second tier nodes.

8. The method as recited in claim 1, wherein the act first tier node routing a message to one or more second tier nodes comprises an act of the first tier node routing 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 in response to detecting the that the output timing interval has occurred, the message containing pre-aggregated data for the at least one key ID that the second tier node has been partitioned to be responsible for.

9. The method as recited in claim 1, wherein the act of the first tier node routing a message to the at least one other node comprises an act of the first tier node routing a message to a central node.

10. 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 from a plurality of first tier nodes for one or more key IDs that the second tier node has been has been partitioned to be responsible for within the overlay network;

an act of the second tier node aggregating 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.

11. The method as recited in claim 10, wherein the overlay network is a ring overlay.

12. The method as recited in claim 11, wherein the act of a second tier node receiving pre-aggregated event related from a plurality of first tier nodes for one or more key IDs that the second tier node has been has been partitioned to be responsible for comprises an act of receiving pre-aggregated event related data that was routed to an ID that the second tier node is responsible for within the ring ID space.

13. The method as recited in claim 10, wherein the second tier node aggregating received pre-aggregated data comprises an act of creating a dictionary entry for a key ID.

14. The method as recited in claim 10, wherein the second tier node aggregating received pre-aggregated data comprises an act of merging received data for a key ID with existing data in the data dictionary for the key ID.

15. The method as recited in claim 10, wherein the recurring aggregation period and the second recurring aggregation period have the same value.

16. The method as recited in claim 10, wherein the 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 comprises an act of the second tier node sending the aggregate total for each of the one or more key IDs to a central node

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 corresponding to one of a plurality of different key IDs, b) pre-aggregate event related data from different messages corresponding to the same key ID within a local dictionary for each different key ID, c) determine when the output timing interval has occurred, and 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,

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 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.

18. The method as recited in claim 17, wherein 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 comprises an act of one or more other second tier nodes assuming responsibility for a range of the ring ID space that the failed node was responsible for.

19. The method as recited in claim 18, wherein the 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 comprises:

an act of the one or more nodes updating routing tables to indicate the changes in responsibility; and

an act of propagating updated routing table information to other nodes on the ring overlay.

20. The method as recited in claim 19, wherein the 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 comprises an act of the other nodes using the updated routing table information to update their routing tables.