Topology management in peer-to-peer content distribution clouds

• US 8,364,758 B2
• Filed: 01/26/2007
• Issued: 01/29/2013
• Est. Priority Date: 02/21/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hydrie, Aamer, Klemets, Anders E., Gkantsidis, Christos, Miller, John, Rodriguez, Pablo Rodriguez, Weiss, Rebecca C.
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): SHIU, HO T
• Application Number:
  US12/279,823
• Publication Number:
  US 20090265473A1
• Time in Patent Office: 2,195 Days
• Field of Search: None
• US Class Current: 709/204
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• 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/1012 based on compliance of requirements or conditions with available server resources
• CPC Class Codes: H04L 67/1014 based on the content of a request
• CPC Class Codes: H04L 67/1021 based on client or server locations
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1042 using topology management mechanisms
• CPC Class Codes: H04L 67/1044 Group management mechanisms management of multicast group membership H04L12/185; reconfiguring of node membership in a computing system to eliminate errors G06F11/1425
• CPC Class Codes: H04L 67/1061 using node-based peer discovery mechanisms static access to replicated servers H04L67/1006; service discovery H04L67/51
• CPC Class Codes: H04L 67/1063 Discovery through centralising entities
• CPC Class Codes: H04L 67/107 with limitation or expansion of the discovery scope
• CPC Class Codes: H04L 67/1072 Discovery involving ranked list compilation of candidate peers

Abstract

A topology management process is implemented in peer-to-peer content distribution clouds using tracker nodes. Tracker nodes have information about available peers and assist peers in finding other peers to connect to. Various algorithms for use at the tracker nodes are described for selecting which peers to return as potentials for forming connections to. In addition, architectures and algorithms to allow efficient scaling of tracker nodes in peer-to-peer clouds are described.

Claims

1. A method of controlling the shape of a peer-to-peer content distribution cloud, the method comprising:

under control of at least one tracker node in communication with a plurality of peer nodes, the method comprising the acts of, at the tracker node;

(i) receiving a request from one of the peer nodes requesting information about one or more other peer nodes to connect to, the request comprising;

details of peer nodes that the requesting peer node does not want to connect to; and

opaque metadata that is semantically unknown to the tracker node and including items of information about a behaviour at the requesting peer node;

(ii) accessing information about a plurality of available peer nodes associated with the tracker node, the accessed information comprising;

details of the peer nodes that the requesting peer node does not want to connect to; and

one or more of;

quality of service information, upload speed information, download speed information, number of existing peer connections, and opaque metadata that is semantically unknown to the tracker node, and including items of information about a behaviour at at least one of the plurality of available peer nodes,

(iii) selecting one or more of the available peer nodes on the basis of one or more criteria, the criteria including quality of service levels, relative upload ability, relative download ability, and/or relative number of existing peer connections; and

on the basis of the accessed information;

wherein the selecting comprises determining, at the tracker node, how many of the opaque metadata items at the requesting peer node match opaque metadata items provided by peer nodes during registration; and

(iv) sending information about the selected available peer nodes to the requesting peer node.

2. A method as claimed in claim 1 wherein the accessed information comprises information provided by peer nodes during registration with the tracker and/or information provided by the requesting peer node.

3. A method as claimed in claim 1 wherein the one or more criteria further include locality, subscription levels, pseudo random selection, historical peer behaviour information, forecast peer behaviour information, relative local resources, relative node accessibility, and predicted pairwise connectivity.

4. A method as claimed in claim 1 wherein the accessed information further comprises one or more of:

locality information, subscription information, historical peer behaviour information, and forecast peer behaviour information, local resource information, type of internet address, node accessibility information, and predicted pairwise connectivity information.

5. A method as claimed in claim 4 wherein the locality information is selected from one or more of internet protocol addresses, network co-ordinate system information, internet protocol address to geolocation database results, information about whether peers are in a public or a private network region, postal address information, global positioning system information.

6. A method as claimed in claim 5 wherein the locality information comprises comparison of internet protocol address prefixes.

7. A computer program comprising computer-executable instructions embodied on a computer readable storage device, when executed by one or more processors, perform the method of claim 1.

8. A method as claimed in claim 1 further comprising:

(v) sending, to the requesting peer node, information about a frequency with which the requesting peer node should repeatedly inform the at least one tracker node of a presence of the requesting peer node.

9. A tracker node for controlling the shape of a peer-to-peer content distribution cloud comprising a plurality of peer nodes, the tracker node comprising:

(i) an input arranged to receive a request from one of the peer nodes requesting information about one or more other peer nodes to connect to, the request comprising;

details of peer nodes that the requesting peer node does not want to connect to; and

opaque metadata that is semantically unknown to the tracker node and including items of information about a behaviour at the requesting peer node;

(ii) a peer node information interface for accessing information about a plurality of available peer nodes associated with the tracker node, the accessed information comprising;

details of the peer nodes that the requesting peer node does not want to connect to; and

one or more of;

quality of service information, upload speed information, download speed information, number of existing peer connections, and opaque metadata that is semantically unknown to the tracker node, and including items of information about a behaviour at at least one of the plurality of available peer nodes,

(iii) a processor arranged to select one or more of the available peer nodes on the basis of one or more criteria including quality of service levels, relative upload ability, relative download ability, and/or relative number of existing peer connections; and

on the basis of the accessed information;

the processor arranged such that the selecting comprises determining, at the tracker node, how many of the opaque metadata items at the requesting peer node match opaque metadata items provided by peer nodes during registration; and

(iv) an output arranged to send information about the selected available peer nodes to the requesting peer node.

10. A tracker node as claimed in claim 9 wherein the accessed information comprises information provided by peer nodes during registration with the tracker and/or information provided by the requesting peer node.

11. A tracker node as claimed in claim 9 wherein the one or more criteria further include locality, subscription levels, pseudo random selection, historical peer behaviour information, forecast peer behaviour information, relative local resources, relative node accessibility, and predicted pairwise connectivity.

12. A tracker node as claimed in claim 9, wherein the accessed information comprises one or more of:

locality information, subscription information, historical peer behaviour information, forecast peer behaviour information, local resource information, type of internet address, node accessibility information, and predicted pairwise connectivity information.

13. A tracker node as claimed in claim 12 wherein the locality information is selected from one or more of internet protocol addresses, network co-ordinate system information, internet protocol address to geolocation database results, information about whether peers are in a public or a private network region, postal address information, global positioning system information.

14. A peer to peer content distribution cloud comprising a plurality of tracker nodes, at least one tracker node of the plurality of tracker nodes comprising:

(i) an input arranged to receive a request from one of the peer nodes requesting information about one or more other peer nodes to connect to, the request comprising;

details of peer nodes that the requesting peer node does not want to connect to; and

opaque metadata that is semantically unknown to the tracker node and including items of information about a behaviour at the requesting peer node;

(ii) a peer node information interface for accessing information about a plurality of available peer nodes associated with the tracker node, the accessed information comprising;

details of the peer nodes that the requesting peer node does not want to connect to; and

one or more of;

quality of service information, upload speed information, download speed information, number of existing peer connections, and opaque metadata that is semantically unknown to the tracker node, and including items of information about a behaviour at at least one of the plurality of available peer nodes;

(iii) a processor arranged to select one or more of the available peer nodes on the basis of one or more criteria including quality of service levels, relative upload ability, relative download ability, and/or relative number of existing peer connections; and

on the basis of the accessed information,

the processor arranged such that the selecting comprises determining, at the tracker node, how many of the opaque metadata items at the requesting peer node match opaque metadata items provided by peer nodes during registration; and

(iv) an output arranged to send information about the selected available peer nodes to the requesting peer node.

15. A peer to peer content distribution cloud as claimed in claim 14 wherein the peer nodes associated with each tracker node are different and each tracker node is able to access information only about its associated peer nodes.

16. A peer to peer content distribution cloud as claimed in claim 14 wherein each peer node is associated with more than one of the tracker nodes.

17. A peer to peer content distribution cloud as claimed in claim 14 wherein peer nodes are arranged to make requests for other peer nodes to connect to from different ones of the tracker nodes.

18. A peer to peer content distribution cloud as claimed in claim 17 wherein the peer nodes are arranged to select which tracker node to request other peer details from on any of the following criteria:

random selection, select each tracker in turn, select any tracker other than the one previously used, select only from trackers the peer is associated with.