System and method for implementing PNRP locality

• US 10,142,409 B2
• Filed: 10/01/2012
• Issued: 11/27/2018
• Est. Priority Date: 03/07/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Miller, John L., Costa, Manuel, Horton, Noah, Huitema, Christian, Singhal, Sandeep K.
• Primary Examiner(s): Mesfin, Yemane
• Assistant Examiner(s): Banthrongsack, Jeff
• Application Number:
  US13/632,664
• Publication Number:
  US 20130031404A1
• Time in Patent Office: 2,248 Days
• Field of Search: None
• 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, comprising:

determining, by one or more processors of a computing system, one or more network latencies between a host node and one or more peer nodes, wherein determining the one or more network latencies comprises probing at least one publisher of an address of a peer node and storing probe results in a cache; and

determining, by the one or more processors, a set of network coordinates of the host node in a coordinate space at least partly based on the one or more network latencies, the determining including;

determining whether the cache comprises probe results indicating one or more network latencies for at least d+1 peer nodes of the one or more peer nodes, d being an integer representing a dimensionality of the coordinate space; and

based at least partly on a first determination that the cache does not comprise the probe results indicating the one or more network latencies for the at least d+1 peer nodes, estimating the set of network coordinates of the host node;

or

based at least partly on a second determination that the cache does comprise the probe results indicating the one or more network latencies for the at least d+1 peer nodes, calculating the set of network coordinates of the host node using d+1 network latencies.

2. The method of claim 1, the method further comprising:

receiving a trigger for coordinate reset.

3. The method of claim 1, the method further comprising determining a subset of known locality-aware peer nodes based upon the host node.

4. The method of claim 1, wherein the host node is associated with a peer-to-peer network.

5. The method of claim 1, the method further comprising:

resetting the set of network coordinates of the host node upon expiration of a timer.

6. The method of claim 1, wherein the host node is configured to use Peer Name Resolution Protocol (PNRP).

7. A system, comprising:

one or more processing units; and

memory comprising instructions that, responsive to being executed by at least one of the one or more processing units, perform operations comprising;

determining one or more network latencies between a host node and one or more peer nodes, wherein determining the one or more network latencies comprises probing at least one publisher of an address of a peer node and storing probe results in a cache; and

determining a set of network coordinates of the host node in a coordinate space at least partly based on the one or more network latencies, the determining including;

determining whether the cache comprises probe results indicating one or more network latencies for at least d+1 peer nodes of the one or more peer nodes, d being an integer representing a dimensionality of the coordinate space; and

in response to determining that the cache does not comprise the probe results indicating the one or more network latencies for the at least d+1 peer nodes, estimating the set of network coordinates of the host node.

8. The system of claim 7, wherein the operations further comprise receiving a trigger for coordinate reset.

9. The system of claim 7, wherein the operations further comprise determining a subset of known locality-aware peer nodes based upon the host node.

10. The system of claim 7, wherein the host node is associated with a peer-to-peer network.

11. The system of claim 7, wherein the operations further comprise:

resetting the set of network coordinates of the host node.

12. The system of claim 7, wherein the host node is configured to use Peer Name Resolution Protocol (PNRP).

20. The system of claim 7, wherein the operations further comprise discovering a Peer Name Resolution Protocol (PNRP) certified peer address of a peer node.

13. A computer-readable storage device comprising instructions that are executable by one or more processors of a computing system to perform operations comprising:

determining one or more network latencies between a host node and one or more peer nodes, wherein determining the one or more network latencies comprises probing at least one publisher of an address of a peer node and storing probe results in a cache; and

determining a set of network coordinates of the host node in a coordinate space at least partly based on the one or more network latencies, the determining including;

determining whether the cache comprises probe results indicating one or more network latencies for at least d+1 peer nodes of the one or more peer nodes, d being an integer representing a dimensionality of the coordinate space; and

in response to determining that the cache does not comprise the probe results indicating the one or more network latencies for the at least d+1 peer nodes, estimating the set of network coordinates of the host node.

14. The computer-readable storage device of claim 13, the operations further comprising:

receiving a trigger for coordinate reset.

15. The computer-readable storage device of claim 13, the operations further comprising determining a subset of known locality-aware peer nodes based upon the host node.

16. The computer-readable storage device of claim 13, wherein the host node is associated with a peer-to-peer network.

17. The computer-readable storage device of claim 13, the operations further comprising resetting one or more network coordinates in the set of network coordinates of the host node.

18. The computer-readable storage device of claim 13, wherein the host node is configured to use Peer Name Resolution Protocol (PNRP).

19. The method of claim 17, further comprising discovering a Peer Name Resolution Protocol (PNRP) certified peer address of a peer node.