Load balancing distribution of data to multiple recipients on a peer-to-peer network

• US 8,913,492 B2
• Filed: 07/27/2012
• Issued: 12/16/2014
• Est. Priority Date: 06/18/2007
• Status: Active Grant

• Current Assignee: Sony Interactive Entertainment Inc. (Sony Group Corp.)
• Original Assignee: Sony Computer Entertainment Incorporated (Sony Group Corp.)
• Inventors: Detwiler, Stephen C., Marr, James E., Vass, Attila
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Kaur, Pamit
• Application Number:
  US13/560,191
• Publication Number:
  US 20120294148A1
• Time in Patent Office: 872 Days
• Field of Search: 370/230, 370/400
• US Class Current: 370/230
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1019 Random or heuristic server selection
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053
• CPC Class Codes: H04L 67/1074 for supporting data block transmission mechanisms file transfer H04L67/06

Abstract

Each peer node in a plurality has a different corresponding key value. Each of the nodes can broadcast one or more items to a plurality of recipient nodes. The recipient nodes are arranged into a list according to a key value order. The list is divided into two or more parts of approximately equal size, and each part of the list and the one or more items is forwarded to a recipient peer node corresponding to a first key value in that part of the list. It is emphasized that this abstract is provided to comply with the rules requiring an abstract that will allow a searcher or other reader to quickly ascertain the subject matter of the technical disclosure. This abstract is submitted with the understanding that it will not be used to interpret or limit the scope or meaning of the claims.

Claims

1. A peer-to-peer network, comprising:

a plurality of peer nodes, wherein each peer node is configured to communicate with one or more other ones of said peer nodes over the peer-to-peer network, wherein the peer-to-peer network is an overlay network, wherein each peer node in the plurality has a different corresponding key value, wherein each of the one or more peer nodes is operable to broadcast one or more items to a plurality of recipient nodes of the plurality of peer nodes by

arranging the plurality of recipient nodes into a list according to a key value order,

dividing the list into two or more parts of approximately equal size, and forwarding each part of the list and the one or more items to a recipient peer node corresponding to a first key value in that part of the list, wherein dividing the list into two or more parts of approximately equal size, and forwarding each part of the list and the one or more items to a peer node corresponding to a first key value in that part of the list avoids overloading intermediate nodes in routing messages in the peer-to-peer network.

2. The peer-to-peer network of claim 1 wherein each peer node is configured to communicate directly with a select subset of other peer nodes in the plurality, wherein each node in the select subset for a given node is associated with a key value stored in a finger table on the given node.

3. The peer-to-peer network of claim 1 wherein the peer nodes are organized according to a distributed hash table.

4. The peer-to-peer network of claim 3 wherein the distributed hash table is characterized by an even random distribution.

5. The peer-to-peer network of claim 1 wherein the plurality of peer nodes includes one or more devices selected from the group of laptop or portable computers;

server computers;

desktop computers and workstations;

mobile computing devices, mobile phones, personal digital assistants, portable digital media players, and portable or handheld game consoles;

home entertainment devices, video game consoles, digital media players, set-top boxes, media center computers and storage devices.

6. A peer node, comprising:

a processor;

a network interface operable to couple the peer node to a network; and

a memory operable to store program instructions and a finger table, wherein the program instructions are executable by the processor to;

communicate with one or more peer nodes on a peer-to-peer network, wherein the peer-to-peer network is an overlay network, wherein each peer node in the plurality has a different corresponding key value;

wherein the peer node is operable to broadcast one or more items to a plurality of recipient nodes of the plurality of peer nodes by;

arranging the plurality of peer nodes into a list according to a key value order

dividing the list into two or more parts of approximately equal size, and

forwarding each part of the list and the one or more items to a peer node corresponding to a first key in that part of the list, wherein dividing the list into two or more parts of approximately equal size, and forwarding each part of the list and the one or more items to a peer node corresponding to a first key value in that part of the list avoids overloading intermediate nodes in routing messages in the peer-to-peer network.

7. The peer node of claim 6 wherein the processor is a multi-core processor.

8. The peer node of claim 6 wherein the processor is a cell processor.

9. The peer node of claim 6 wherein the processor, memory and network interface are components of a laptop or portable computer;

server computer;

desktop computer or workstations;

mobile computing device, mobile phone, personal digital assistant, portable digital media player, and portable or handheld game console;

home entertainment device, video game console, digital media players, set-top boxes, media center computers or storage device.

10. The peer node of claim 6, wherein the finger table includes a plurality of node keys associated with a subset of nodes in a peer-to-peer overlay network.

11. The peer node of claim 10, wherein the finger table includes a plurality of data keys, divided into a plurality of data key groups wherein each key group is associated with a corresponding node key.

12. In a peer-to-peer overlay network a method for broadcasting one or more items of data to a plurality of recipient peer nodes selected from a plurality of peer nodes organized in a peer-to-peer overlay network wherein each peer node is associated with a different corresponding key value, the method comprising:

arranging the plurality of recipient peer nodes into a list according to a key value order;

dividing the list into two or more parts of approximately equal size; and

forwarding each part of the list and the one or more items to a recipient peer node corresponding to a first key in that part of the list, wherein dividing the list into two or more parts of approximately equal size, and forwarding each part of the list and the one or more items to a peer node corresponding to a first key value in that part of the list avoids overloading intermediate nodes in routine messages in the peer-to-peer network.

13. The method of claim 12, further comprising determining an amount of bandwidth available for one or more nodes in the plurality of nodes.

14. The method of claim 13, wherein forwarding each part of the list includes preferentially selecting the first key in at least one of the two or more parts according to an amount of bandwidth available for the node corresponding to the first key.

15. The method of claim 14 wherein the first key is a member of a finger table that corresponds to a node that is responsible for an address space containing most of the peers in the plurality.

16. The method of claim 15 wherein the peer node corresponding to the first key for one part of the list corresponds to a predecessor of the peer node corresponding to the first key for another part of the list.

17. A non-transitory computer-accessible storage medium comprising program instructions, wherein the program instructions are computer-executable on a peer node to implement a method for broadcasting one or more items of data to a plurality of recipient peer nodes selected from a plurality of peer nodes organized in a peer-to-peer overlay network wherein each peer node is associated with a different corresponding key value, the method comprising:

arranging a plurality of recipient peer nodes into a list according to a key value order;

dividing the list into two or more parts of approximately equal size; and

forwarding each part of the list and the one or more items to a recipient peer node corresponding to a first key in that part of the list, wherein dividing the list into two or more parts of approximately equal size, and forwarding each part of the list and the one or more items to a peer node corresponding to a first key value in that part of the list avoids overloading intermediate nodes in routine messages in the peer-to-peer network.