Broadcast messaging in peer to peer overlay network
View Patent ↗Broadcast messages are efficiently directed to nodes of an overlay network. Broadcast messages include an End ID parameter specifying the range of key values for nodes that should receive the broadcast message. Each node of an overlay network maintains a list of finger nodes and their respective key values. Upon receiving a broadcast message, a node assigns a finger node a new End ID value based upon the End ID value of the broadcast message or the key value of an adjacent finger node. The node compares a finger node's new End ID value with the finger node's key value to determine whether to forward the broadcast message to that finger node. A broadcast message forwarded to a finger node includes an End ID parameter equal to the new End ID value determined for the finger node. Nodes can aggregate response messages from its finger nodes.
1. A method of processing a broadcast message in an overlay network, the method comprising:
receiving a broadcast message including an End ID from a sending node, wherein the End ID specifies a range of key values for finger nodes that should receive copies of the broadcast message;
selecting an entry of a finger table, wherein the each entry of the finger table includes a reference to a finger node and a key value associated with the finger node;
determining if there is a following entry of the finger table, wherein the following entry includes a key value adjacent to the key value of the selected finger table entry according to a node order;
setting a new End ID to the key value associated with the following entry in response to the determination that there is a following entry of the finger table;
setting a new End ID to the End ID of the received broadcast message in response to the determination that there is not a following entry of the finger table;
comparing the key value of the selected finger table entry with the new End ID; and
forwarding a copy of the broadcast message with the new End ID to the finger node of the selected entry in response to a determination that the key value of the selected finger table entry is within the range of key values specified by the new End ID.
2. The method of claim 1 , wherein the finger table includes two or more entries arranged according to their respective key values.
3. The method of claim 1 , wherein the node order is ascending according to key values.
4. The method of claim 1 , wherein the node order is descending according to key values.
5. The method of claim 1 , further comprising:
storing a reference to a sending node communicating the broadcast message;
receiving a response message from at least one finger node in response to the forwarded copy of broadcast message;
aggregating the received response messages into a combined response message; and
forwarding the combined response message to the sending node.
6. The method of claim 5 , further comprising:
receiving a response to the broadcast message; and
including the response in the combined response message.
7. The method of claim 5 , wherein aggregating the received response messages further comprises using a frequency domain transformation to create a compact representation of the received response messages.
8. A method of processing a broadcast message in an overlay network, the method comprising:
receiving a broadcast message by a current node with a current key value, wherein the broadcast message includes a Start ID and an End ID from a sending node, wherein the Start ID and End ID specify a range of key values for finger nodes that should receive copies of the broadcast message;
selecting an entry of a finger table, wherein the each entry of the finger table includes a reference to a finger node and a key value associated with the finger node;
determining if there is a following entry of the finger table, wherein the following entry includes a key value adjacent to the key value of the selected finger table entry according to a node order;
setting a new End ID to the key value associated with the following entry in response to the determination that there is a following entry of the finger table;
setting a new End ID to the End ID of the received broadcast message in response to the determination that there is not a following entry of the finger table;
comparing the key value of the selected finger table entry with the new End ID and the Start ID with the new End ID; and
in response to a determination that the key value of the selected finger table entry is within a range of key values specified by the new End ID and that the Start ID is within a range of key values specified by the new End ID:
setting a new Start ID to the key value of the selected entry of the finger table or the Start ID, whichever is furthest from the current key value; and
forwarding a copy of the broadcast message with the new End ID and the new Start ID to the finger node of the selected entry.
9. The method of claim 8 , wherein the finger table includes two or more entries arranged according to their respective key values.
10. The method of claim 8 , wherein the node order is ascending according to key values.
11. The method of claim 8 , wherein the node order is descending according to key values.
12. The method of claim 8 , further comprising:
storing a reference to a sending node communicating the broadcast message;
receiving a response message from at least one finger node in response to the forwarded copy of broadcast message;
aggregating the received response messages into a combined response message; and
forwarding the combined response message to the sending node.
13. The method of claim 12 , further comprising:
receiving a response to the broadcast message; and
including the response in the combined response message.
14. The method of claim 12 , wherein aggregating the received response messages further comprises using a frequency domain transformation to create a compact representation of the received response messages.
15. An information storage medium encoded with instructions adapted to direct an information processing device to perform an operation, the operation comprising:
receiving a broadcast message including an End ID from a sending node, wherein the End ID specifies a range of key values for finger nodes that should receive copies of the broadcast message;
selecting an entry of a finger table, wherein the each entry of the finger table includes a reference to a finger node and a key value associated with the finger node;
determining if there is a following entry of the finger table, wherein the following entry includes a key value adjacent to the key value of the selected finger table entry according to a node order;
setting a new End ID value to the key value associated with the following entry in response to the determination that there is a following entry of the finger table;
setting a new End ID value to the End ID of the received broadcast message in response to the determination that there is not a following entry of the finger table;
comparing the key value of the selected finger table entry with the new End ID value; and
forwarding a copy of the broadcast message with the new End ID value to the finger node of the selected entry in response to a determination that the key value of the selected finger table entry is within the range of key values specified by the new End ID value.
16. The information storage medium of claim 15 , wherein the finger table includes two or more entries arranged according to their respective key values.
17. The information storage medium of claim 15 , wherein the node order is ascending according to key values.
18. The information storage medium of claim 15 , wherein, the node order is descending according to key values.
19. The information storage medium of claim 15 , further comprising:
storing a reference to a sending node communicating the broadcast message;
receiving a response message from at least one finger node in response to the forwarded copy of broadcast message;
aggregating the received response messages into a combined response message; and
forwarding the combined response message to the sending node.
20. The information storage medium of claim 19 , further comprising:
receiving a response to the broadcast message; and
including the response in the combined response message.
21. The information storage medium of claim 19 , wherein aggregating the received response messages further comprises using a frequency domain transformation to create a compact representation of the received response messages.
22. An information storage medium encoded with instructions adapted to direct an information processing device to perform an operation, the operation comprising:
receiving a broadcast message by a current node with a current key value, wherein the broadcast message includes a Start ID and an End ID from a sending node, wherein the Start ID and End ID specify a range of key values for finger nodes that should receive copies of the broadcast message;
selecting an entry of a finger table, wherein the each entry of the finger table includes a reference to a finger node and a key value associated with the finger node;
determining if there is a following entry of the finger table, wherein the following entry includes a key value adjacent to the key value of the selected finger table entry according to a node order;
setting a new End ID to the key value associated with the following entry in response to the determination that there is a following entry of the finger table;
setting a new End ID to the End ID of the received broadcast message in response to the determination that there is not a following entry of the finger table;
comparing the key value of the selected finger table entry with the new End ID and the Start ID with the new End ID; and
in response to a determination that the key value of the selected finger table entry is within a range of key values specified by the new End ID and that the StartID is within a range of key values specified by the new End ID:
setting a new Start ID to the key value of the selected entry of the finger table or the Start ID, whichever is furthest from the current key value; and
forwarding a copy of the broadcast message with the new End ID and the new Start ID to the finger node of the selected entry.