Method for establishing and maintaining a shared view of time in a peer-to-peer network

• US 20050108373A1
• Filed: 11/05/2003
• Published: 05/19/2005
• Est. Priority Date: 11/05/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Huitema, Christian, Dewey, Jeremy L., Zhang, Xiaohai
• Granted Patent: US 7,689,720 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols

Abstract

A shared concept of time, called “graph time,” is agreed upon by all nodes within a graph. Each node maintains its own local delta representative of a difference in the node'"'"'s system clock and graph time. Upon connecting to a neighbor node in a graph, a node is sent graph time as perceived by the neighbor node. In accordance with an embodiment, the node assumes that the lag time in receiving the graph time from the neighbor node is one-half of the lag time between the request for the connection and the receipt of the graph time. Graph time as sent by the neighbor node is added to one-half of the total delay and the sum is subtracted from the node'"'"'s system time to calculate the delta for the node requesting connection.

Claims

1. A computer-implemented method for maintaining a shared concept of time between nodes in a graph, the method comprising:

at a first node in a graph, maintaining a perceived graph time representing a perception of a shared concept of time for the graph; and

at a second node in the graph, receiving information about the perceived graph time, and calculating a neighbor delta representative of a difference between the perceived graph time and a system time for the second node.

2. The method of claim 1, wherein receiving information occurs responsive to a connection request by the second node.

3. The method of claim 2, wherein the connection request is made to the first node.

4. The method of claim 2, wherein the information comprises the perceived graph time.

5. The method of claim 2, wherein calculating the local delta by the second node comprises assuming that a lag time in receiving the perceived graph time from the first node is one-half of a lag time between a time of the request for the connection by the second node and a time of a receipt of the perceived graph time by the second node.

6. The method of claim 5, wherein the calculation for the neighbor delta comprises adding the perceived graph time to one-half of the lag time to arrive at a sum, and subtracting the sum from a system time of the second node at the time of the receipt.

7. The method of claim 1, further comprising calculating a local delta for the second node utilizing the neighbor delta, the local delta representing a difference between system time for the second node and graph time.

8. The method of claim 7, wherein the local delta is equal to the neighbor delta if a previous local delta has not been calculated for the second node.

9. The method of claim 7, wherein, if a previous local delta has been calculated for the second node, the local delta is calculated as a weighted average of the neighbor delta and the previous local delta.

10. The method of claim 9, wherein the weighted average is calculated using the following formula:

local delta=previous local delta*((x−

1)/x)+(neighbor delta)*(1/x));

wherein x is a positive whole number.

11. The method of claim 10, wherein x is a positive integer between 4 and 16, inclusive.

12. The method of claim 1, further comprising minimizing the local delta by applying a shift factor.

13. The method of claim 12, wherein applying a shift factor comprises:

decreasing the local delta by a fraction of the time between a present calculation of local delta connection and a previous calculation of a previous local delta, divided by the shifting period.

14. The method of claim 13, wherein the present calculation comprises a request for connection to the graph, and the previous calculation comprises a most recent request for connection to the graph.

15. A computer-readable medium having computer-executable instructions for performing a method, the method comprising:

at a first node in a graph, maintaining a perceived graph time representing a perception of a shared concept of time for the graph; and

at a second node in the graph, receiving information about the perceived graph time, and calculating a neighbor delta representative of a difference between the perceived graph time and a system time for the second node.

16. The computer-readable medium of claim 15, wherein receiving information occurs responsive to a connection request by the second node.

17. The computer-readable medium of claim 16, wherein the connection request is made to the first node.

18. The computer-readable medium of claim 16, wherein the information comprises the perceived graph time.

19. The computer-readable medium of claim 16, wherein calculating the local delta by the second node comprises assuming that a lag time in receiving the perceived graph time from the first node is one-half of a lag time between a time of the request for the connection by the second node and a time of a receipt of the perceived graph time by the second node.

20. The computer-readable medium of claim 19, wherein the calculation for the neighbor delta comprises adding the perceived graph time to one-half of the lag time to arrive at a sum, and subtracting the sum from a system time of the second node at the time of the receipt.

21. The computer-readable medium of claim 15, further comprising calculating a local delta for the second node utilizing the neighbor delta, the local delta representing a difference between system time for the second node and graph time.

22. The computer-readable medium of claim 21, wherein the local delta is equal to the neighbor delta if a previous local delta has not been calculated for the second node.

23. The computer-readable medium of claim 21, wherein, if a previous local delta has been calculated for the second node, the local delta is calculated as a weighted average of the neighbor delta and the previous local delta.

24. The computer-readable medium of claim 23, wherein the weighted average is calculated using the following formula:

local delta=previous local delta*((x−

1)/x)+(neighbor delta)*(1/x));

wherein x is a positive whole number.

25. The computer-readable medium of claim 24, wherein x is a positive integer between 4 and 16, inclusive.

26. The computer-readable medium of claim 15, further comprising minimizing the local delta by applying a shift factor.

27. The computer-readable medium of claim 26, wherein applying a shift factor comprises:

decreasing the local delta by a fraction of the time between a present calculation of local delta connection and a previous calculation of a previous local delta, divided by the shifting period.

28. The computer-readable medium of claim 27, wherein the present calculation comprises a request for connection to the graph, and the previous calculation comprises a most recent request for connection to the graph.