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

• US 8,238,237 B2
• Filed: 06/18/2007
• Issued: 08/07/2012
• 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:
  US11/764,680
• Publication Number:
  US 20080310302A1
• Time in Patent Office: 1,877 Days
• Field of Search: 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

A method and system for load balancing the distribution of a file or block of data to multiple recipients on a peer to peer network is disclosed.

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 each peer node is operable to;

A) receive or initiate a request to search for a plurality of items, wherein each item is represented by a key value, arrange the plurality of items into a list according to a key value order, divide the list into two or more parts of approximately equal size, look up in a finger table a finger node to closest to a first key value in each part, and, for each part, forward a request for the items in the part to the corresponding finger node,

wherein dividing the list into two or more parts of approximately equal size, looking up the finger node closest to the first key value in each part, and, for each part, forwarding the request to the corresponding finger node avoids overloading intermediate nodes in routing requests in the peer-to-peer network; and

/or

B) broadcast one or more items to a 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 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 peer nodes include 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 node is operable to

A) receive or initiate a request to search for a plurality of items, wherein each item is represented by a key value, arrange the plurality of items into a list according to a key value order, divide the list into two or more parts of approximately equal size, look up in a finger table a finger node closest to a first key value in each part, and, for each part, forward a request for the items in the part to the corresponding finger node,

wherein dividing the list into two or more parts of approximately equal size, looking up the finger node closest to the first key value in each part, and, for each part, forwarding the request to the corresponding finger node avoids overloading intermediate nodes in routing requests in the peer-to-peer network; and

/or

B) broadcast one or more items to a 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 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 search method, comprising:

receiving or initiating at a peer node a request to search for a plurality of items, wherein each item is represented by a key value;

a) arranging the plurality of items into a list according to a key value order;

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

c) looking up in a finger table a finger node for each part based on a first key value in that part; and

d) forwarding a request for the items corresponding to each part to the corresponding finger node,

wherein dividing the list into two or more parts of approximately equal size, looking up the finger node closest to the first key value in each part, and, for each part, forwarding the request to the corresponding finger node avoids overloading intermediate nodes in routing requests in the peer-to-peer network.

13. The method of claim 12 wherein the finger node for each part corresponds to a key value that is closest to the first key value in that part.

14. The method of claim 12, further comprising performing a) through d) on the request for the items corresponding to at least one of the two or more parts at the corresponding finger node for that part.

15. The method of claim 12, wherein d) includes forwarding with the request a network address associated with a peer node originating the request.

16. The method of claim 12, further comprising determining an amount of bandwidth available for one or more nodes corresponding to key values in the finger table.

17. The method of claim 16 wherein c) comprises preferentially selecting the key value for at least one of the two or more parts based on an availability of bandwidth for the one or more nodes corresponding to key values in the finger table.

18. The method of claim 12 wherein c) comprises preferentially selecting the key value for each of the two or more parts based on an availability of bandwidth for the one or more nodes corresponding to key values in the finger table.

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

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 in that part of the list avoids overloading intermediate nodes in routing messages in the peer-to-peer network.

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

21. The method of claim 20, 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.

22. The method of claim 21 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.

23. The method of claim 22 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.

24. A non transitory computer-accessible storage medium comprising program instructions, wherein the program instructions are computer-executable on a peer node to implement:

a) receiving or initiating at the peer node a request to search for a plurality of items, wherein each item is represented by a key value;

b) arranging the plurality of items into a list according to a key value order;

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

d) looking up in a finger table a finger node for each part based on a first key value in that part; and

e) forwarding a request for the items corresponding to each part to the corresponding finger node,

wherein dividing the list into two or more parts of approximately equal size, looking up the finger node closest to the first key value in each part, and, for each part, forwarding the request to the corresponding finger node avoids overloading intermediate nodes in routing requests in the peer-to-peer network.

25. A non transitory computer-accessible storage medium comprising program instructions, wherein the program instructions are computer-executable on a peer node to implement:

arranging a plurality of peer nodes to which one or more items are to be broadcast 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 in that part of the list avoids overloading intermediate nodes in routing messages in the peer-to-peer network.