System and method for implementing PNRP locality

• US 7,826,396 B2
• Filed: 03/07/2005
• Issued: 11/02/2010
• Est. Priority Date: 03/07/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Miller, John L., Costa, Manuel, Horton, Noah, Huitema, Christian, Singhal, Sandeep K.
• Primary Examiner(s): Yao; Kwang B
• Assistant Examiner(s): Kao; Jutai
• Application Number:
  US11/072,525
• Publication Number:
  US 20060209704A1
• Time in Patent Office: 2,066 Days
• Field of Search: 370/252, 370/255, 370/238, 370/352, 709/243, 709/217, 709/223, 709/249, 375/261, 382/209, 700/90, 713/156
• US Class Current: 370/255
• CPC Class Codes: H04L 43/0858 One way delays
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/12 Network monitoring probes
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1068 Discovery involving direct consultation or announcement among potential requesting and potential source peers

Abstract

A method is provided for a host node in a computer network to determine its coordinates in a d-dimensional network space, comprising discovering an address of a peer node in the network, measuring network latency between the host node and the peer node, determining whether network latency has been measured for at least d+1 peer nodes, where, if network latency has not been measured for at least d+1 peer nodes, estimating the network coordinates of the host node, and where, if network latency has been measured for at least d+1 peer nodes, calculating the network coordinates of the host node using d+1 measured latencies.

Claims

1. A method for a host node in a peer to peer computer network to determine its coordinates in a d-dimensional network space that uses Peer Name Resolution Protocol (PNRP), comprising, at the host node:

determining, by the host node, whether the host node is a first locality-aware node in the peer to peer computer network;

if the host node determines the host node is the first locality-aware node in the peer to peer computer network, setting a fist set of network coordinates of the host node to be an origin of the d-dimensional network space; and

if the host node determines the host node is not the first locality-aware node in the peer-to-peer computer network;

discovering an address of a peer node in the PNRP network;

measuring network latency between the host node and the peer node based on results of a probe of a publisher of the address of the peer node;

storing, in an entry of a global cloud cache at the host node, locality data for the peer node and a state indicating whether or not a valid locality estimation has been obtained for the peer node;

determining a number of locality-aware peer nodes for which network latency has been measured, the number of locality-aware peer nodes for which network latency has been measured corresponding to a number of probe results stored in the global cloud cache;

if the number of locality-aware peer nodes for which network latency has been measured is less than d+1, estimating the first set of network coordinates of the host node;

if the number of locality-aware peer nodes for which network latency has been measured is greater than or equal to d+1, calculating the first set of network coordinates of the host node in the peer to peer network using d+1 measured latencies wherein closer locality-aware peer nodes to the host node will have a smaller network latency and closer network coordinates and locality-aware peer nodes that are further away from the host node will have a higher network latency and further network coordinates from the host node;

receiving a trigger for a coordinate reset;

selecting a subset of known locality-aware peer nodes based at least in part on levels in the global cloud cache;

re-measuring the network latency between the host node and each of the subset of known locality-aware peer nodes;

calculating a second set of network coordinates of the host node using re-measured network latency; and

using the second set of network coordinates of the host node when a first calculated error corresponding to the first set of network coordinates is greater than or equal to a second calculated error corresponding to the second set of network coordinates.

2. The method of claim 1, wherein the address is a PNRP certified peer address.

3. The method of claim 2, wherein the certified peer address includes network coordinates for the peer node.

4. The method of claim 1, wherein the d-dimensional network space is a seven dimensional network space.

5. The method of claim 1, wherein estimating the first set of network coordinates is performed using the Downhill Simplex method.

6. The method of claim 1, wherein measuring network latency is performed by measuring the time between sending a PNRP inquire message and receiving a PNRP authority message.

7. The method of claim 1, wherein measuring network latency is performed by measuring the time between a sent ping and a received ping.

15. The method of claim 1, wherein the trigger for coordinate reset comprises at least one of:

a local address change of the host node;

a determined disparity between an actual round-trip time and an estimated round-trip time for a number of nearby peer nodes;

an Ipv6 migration of the host node;

or

a repair of a cloud merge assisted, at least in part, by the host node.

16. The method of claim 1, further comprising when the second calculated error is greater than the first calculated error:

initiating a timer for a random time interval;

prior to an expiration of the timer, receiving an updated address from each of at least a portion of the subset of peer nodes and update the global cloud cache with information from the updated address; and

upon expiration of the timer, initiating the trigger for coordinate reset.

8. A non-transitory computer-storage medium having computer executable instructions for performing steps for a host node in a peer to peer computer network to determine its coordinates in a d-dimensional Peer Name Resolution Protocol (PNRP) network space, the steps comprising:

determining, by the host node, whether the host node is a first locality-aware node in the peer to peer computer network;

if the host node determines the host node is the first locality-aware node in the peer to peer computer network, setting a first set of network coordinates of the host node to be an origin of the d-dimensional network space; and

if the host node determines the host node is not the first locality-aware node in the peer-to-peer computer network;

discovering an address of a peer node in the PNRP network;

measuring network latency between the host node and the peer node based on results of a probe of a publisher of the address of the peer node;

storing, in an entry of a global cloud cache at the host node, locality data for the peer node and a state indicating whether or not a valid locality estimation has been obtained for the peer node;

determining a number of locality-aware peer nodes for which network latency has been measured, the number of locality-aware peer nodes for which network latency has been measured corresponding to a number of probe results stored in the global cloud cache;

if the number of locality-aware peer nodes for which network latency has been measured is less than d+1, estimating the first set of network coordinates of the host node;

if the number of locality-aware peer nodes for which network latency has been measured is greater than or equal to d+1, calculating the first set of network coordinates of the host node in the peer to peer network using d+1 measured latencies wherein closer locality-aware peer nodes to the host node will have a smaller network latency and closer network coordinates and locality-aware peer nodes that are further away from the host node will have a higher network latency and further network coordinates from the host node;

receiving a trigger for a coordinate reset;

selecting a subset of known locality-aware peer nodes based at least in part on levels in the global cloud cache;

re-measuring the network latency between the host node and each of the subset of known locality-aware peer nodes;

calculating a second set of network coordinates of the host node using re-measured network latency; and

using the second set of network coordinates of the host node when a first calculated error corresponding to the first set of network coordinates is greater than or equal to a second calculated error corresponding to the second set of network coordinates.

9. The non-transitory computer-storage medium of claim 8, wherein the address is a PNRP certified peer address.

10. The non-transitory computer-storage medium of claim 9, wherein the certified peer address includes network coordinates for the peer node.

11. The non-transitory computer-storage medium of claim 8, wherein the d-dimensional network space is a seven dimensional network space.

12. The non-transitory computer-storage medium of claim 8, wherein estimating the first set of network coordinates is performed using the Downhill Simplex method.

13. The non-transitory computer-storage medium of claim 8, wherein measuring network latency is performed by measuring the time between sending a PNRP inquire message and receiving a PNRP authority message.

14. The non-transitory computer-storage medium of claim 8, wherein measuring network latency is performed by measuring the time between a sent ping and a received ping.

17. The non-transitory computer-storage medium of claim 8, wherein the trigger for the coordinate reset comprises at least one of:

a local address change of the host node;

a determined disparity between an actual round-trip time and an estimated round-trip time for a number of nearby peer nodes;

an Ipv6 migration of the host node;

or

a repair of a cloud merge assisted, at least in part, by the host node.

18. The non-transitory computer-storage medium of claim 8, wherein when the second calculated error corresponding to the second set of network coordinates is greater than the first calculated error corresponding to the first set of network coordinates, the steps further comprise:

initiating a timer for a random time interval;

prior to an expiration of the timer, receiving an updated address from each of at least a portion of the subset of peer nodes and update the global cloud cache with information from the updated address; and

upon expiration of the timer, initiating the trigger for coordinate reset.