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

• US 7,689,720 B2
• Filed: 11/05/2003
• Issued: 03/30/2010
• Est. Priority Date: 11/05/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Xiaohai, Huitema, Christian, Dewey, Jeremy L.
• Primary Examiner(s): Jaroenchonwanit; Bunjob
• Assistant Examiner(s): Keehn; Richard G
• Application Number:
  US10/702,405
• Publication Number:
  US 20050108373A1
• Time in Patent Office: 2,337 Days
• Field of Search: 709/248
• US Class Current: 709/248
• 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 that comprises a peer to peer, serverless network wherein the nodes are peers on the network, the method comprising:

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

at a second node in the graph in the peer to peer network,

receiving information about the perceived graph time wherein receiving information occurs responsive to a connection request to join the peer to peer network by the second node and wherein the connection request is made to the first node, and

calculating a local delta representative of a difference between the perceived graph time and a system time for the second node 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;

if a previous local delta has been calculated for the second node, the local delta is calculated as a weighted average of a neighbor delta wherein the neighbor delta is representative of a difference between the perceived graph time and a system time for the second node and 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 and the previous local delta 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 integer between 4 and 16, inclusive; and

wherein previous local delta equals a previously calculated local delta and

wherein the neighbor delta equals system time less graph time plus half delay

wherein the delay equals system welcome time less system connect time;

if a previous local delta has not been calculated for the second node, the local delta is equal to the neighbor delta.

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

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

4. The method of claim 3, 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.

5. The method of claim 4, 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.

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

at a first node in a graph that comprises a peer to peer, serverless network wherein the nodes are peers on the network, maintaining a perceived graph time representing a perception of a shared concept of time for the graph;

at a second node in the graph in the peer to peer network, receiving information about the perceived graph time, wherein receiving information occurs responsive to a connection request to join the peer to peer network by the second node and wherein the connection request is made to the first node, and

calculating a local delta representative of a difference between the perceived graph time and a system time for the second node 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;

if a previous local delta has been calculated for the second node, the local delta is calculated as a weighted average of a neighbor delta 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 and the previous local delta 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 integer between 4 and 16, inclusive; and

wherein previous local delta equals a previously calculated local delta and

wherein the neighbor delta equals system time less graph time plus half delay

wherein the delay equals system welcome time less system connect time;

if a previous local delta has not been calculated for the second node, the local delta is equal to the neighbor delta;

minimizing the local delta by applying a shift factor 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 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.