System and method for implementing PNRP locality

• US 8,310,956 B2
• Filed: 09/16/2010
• Issued: 11/13/2012
• 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:
  US12/883,346
• Publication Number:
  US 20110004677A1
• Time in Patent Office: 789 Days
• Field of Search: None
• 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 reset its coordinates in a d-dimensional network space that uses Peer Name Resolution Protocol (PNRP), comprising, at the host node:

determining a first set of network coordinates for the host node;

receiving a trigger for coordinate reset; and

based on the reception of the trigger;

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

determining a current network latency between the host node and each of the subset of known locality-aware peer nodes;

determining a second set of network coordinates of the host node based on the current 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, at least one peer node of the subset of known locality-aware peer nodes having a PNRP certified peer address.

3. The method of claim 1, an address of at least one peer node of the subset of known locality-aware peer nodes including network coordinates for the at least one peer node.

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

5. The method of claim 1, determining the first set of network coordinates for the host node comprising determining the first set of network coordinates based on at least one of:

an estimated network latency between the host node and at least one other peer node, or a measured network latency between the host node and the at least one other peer node.

6. The method of claim 5, determining the first set of network coordinates based on the estimated network latency comprising determining the first set of network coordinates based on the Downhill Simplex method.

7. The method of claim 1, determining the current network latency comprising at least one of:

measuring the current network latency or estimating the current network latency.

8. The method of claim 7, measuring the current network latency comprising at least one of:

measuring an amount of time between sending a PNRP inquire message and receiving a PNRP authority message, or measuring an amount of time between a sent ping and a received ping.

9. The method of claim 1, comprising determining at least one of the first calculated error or the second calculated error based on a corresponding measured network latency and a corresponding estimated network latency.

10. The method of claim 9, determining the at least one of the first calculated error or the second calculated error based on the corresponding measured network latency and the corresponding estimated network latency comprising determining the at least one of the first calculated error or the second calculated error based on a sum of squares error between the corresponding measured network latency and the corresponding estimated network latency.

11. The method of claim 1, receiving the trigger for coordinate reset comprising receiving at least one of:

a local address change of the host node;

a determined disparity between an actual round-trip time measurement and an estimated round-trip time measurement 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.

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

initiating a timer for a time interval;

prior to an expiration of the timer, receiving an updated address from each of a plurality of other peer nodes and updating the global cloud data store with information from the updated addresses; and

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

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

determining a first set of network coordinates for the host node;

receiving a trigger for coordinate reset; and

based on the reception of the trigger;

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

determining a current network latency between the host node and each of the subset of known locality-aware peer nodes;

determining a second set of network coordinates of the host node based on the current 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.

14. The non-transitory computer-storage medium of claim 13, an address of at least one peer node in the subset of known locality-aware peer nodes including at least one of:

a PNRP certified peer address or network coordinates for the at least one peer node.

15. The non-transitory computer-storage medium of claim 13, the d-dimensional PNRP network space a seven dimensional network space.

16. The non-transitory computer-storage medium of claim 13, determining the first set of network coordinates for the host node comprising determining the first set of network coordinates for the host node based on at least one of:

an estimated network latency between the host node and at least one other peer node, or a measured network latency between the host node and the at least one other peer node.

17. The non-transitory computer-storage medium of claim 13, determining the current network latency comprising at least one of:

measuring the current network latency or estimating the current network latency.

18. The non-transitory computer-storage medium of claim 13, the method comprising determining at least one of the first calculated error or the second calculated error based on a corresponding measured network latency and a corresponding estimated network latency.

19. The non-transitory computer-storage medium of claim 13, the trigger for the coordinate reset comprising at least one of:

a local address change of the host node;

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

a migration of the host node;

or

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

20. The non-transitory computer-storage medium of claim 13, 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 method comprises:

initiating a timer for a time interval;

prior to an expiration of the timer, receiving an updated address from each of a plurality of other peer nodes, and updating the global cloud data store with information from the updated addresses; and

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