Method for estimating offset for clocks at network elements
View Patent ↗A new algorithm for clock offset estimation for resources distributed across a network (such as the Internet). By exchanging a sequence of time-stamped messages between pairs of network nodes and separately estimating variable delays for each message direction, present inventive embodiments provide more accurate estimates for clock offset between node pairs. Present inventive algorithms operate in a variety of peer and server network configurations while providing significant improvement in convergence speed and accuracy.
1. In a network having a plurality of network nodes, each node having a clock, a method for estimating offset of the clock at a first node, A, relative to the clock at a second node, B, the method comprising
exchanging n rounds of ordered time-stamped messages between said nodes A and B, n being an integer,
determining values for a pair of sequences of random variables {X i } n i=1 and {Y i } n i=1 related, respectively, to the sojourn times for ith of said A→B and B→A messages, i=1, 2, . . . , n, wherein transit of messages from node A to node B are represented as A→B and transit of messages from node B to node A are represented as B→A,
determining a statistic as a function of said {X i } n i=1 and {Y i } n i=1 , and
determining said estimate of offset as a function of said statistic.
2. The method of claim 1 wherein said statistic is given by
(
T
1
,
T
2
,
S
1
,
S
2
)
=
(
min
X
i
1
≤
i
≤
n
,
∑
i
=
1
n
X
i
,
min
Y
i
1
≤
i
≤
n
,
∑
i
=
1
n
Y
i
)
.
3. The method of claim 2 wherein said determining of said estimate of offset as a function of said statistic comprises determining
θ
~
=
1
2
[
n
T
1
-
T
2
/
n
n
-
1
-
n
S
1
-
S
2
/
n
n
-
1
]
.
4. The method of claim 1 wherein said random variables are X i =T i 1 −T i 0 and Y i =T i 3 −T i 2 , respectively, where are T i 1 −T i 0 is the sojourn time for the ith A→B message and T i 3 −T i 2 is the sojourn time for the ith B→A message.
5. The method of claim 1 wherein at the ith of said rounds, i=1, . . . , n, where n is an integer, said messages comprise
from said node A, a first message to said node B comprising a time stamp T i 0 indicating the current time at said node A when said first message is sent,
from said node B, a second message to said node A comprising a time stamp T i 1 indicating the current time at said node B when said first message was received, and a time stamp T i 2 indicating the time at said node B at which said second message is sent, and wherein the method further comprises
determining T i 3 , the time at which said second message is received at said node B.
6. The method of claim 5 further comprising determining at said first node for each i,i=1,2, . . . ,n
X i =T i 1 −T i 0 and Y i =T i 3 −T i 2 ,
where
T i 3 −T i 2 =d−θ+e i BA
T i 1 −T i 0 =d+θ+e i AB , and
wherein θ is the offset of the clock at said second node from the clock at said first node, d is the fixed delay experienced by a message from one of said nodes to the other of said nodes, e i AB is the variable delay at said ith round for a message from said node A to said node B, e i BA is the variable delay at said ith round for a message from said node B to said node A.
7. The method of claim 6 wherein the probability distribution for e i AB and e i BA need not be of the same family of distributions.
8. The method of claim 6 wherein the probability distribution for each of e i AB and e i BA is chosen from the set of probability distributions comprising exponential, lognormal, gamma and Weibull distributions.
9. In a network having a plurality of network nodes, each node having a clock, a method for estimating a bootstrapped bias-corrected offset, {tilde over (θ)} BC , of the clock at a first node, A, relative to the clock at a second node, B, the method comprising
exchanging n rounds of ordered time-stamped messages between said nodes A and B, n being an integer,
determining values for a pair of sequences of random variables {X i } i=1 n and {Y i } 1=1 n relating, respectively, to the sojourn times for ith of said A→B and B→A messages, i=1, 2, . . . , n, wherein transit of messages from node A to node B are represented as A→B and transit of messages from node B to node A are represented as B→A, and
determining said bootstrapped bias-corrected estimate of offset in accordance with
θ
~
B
C
=
∑
i
=
1
n
v
i
(
X
(
i
)
-
Y
(
i
)
)
,
where
v
1
=
n
n
-
1
{
1
2
-
1
2
n
2
+
1
2
(
n
-
1
n
)
n
}
,
and
v
i
=
n
n
-
1
{
-
1
2
n
2
-
1
2
(
n
-
i
+
1
n
)
n
+
1
2
(
n
-
i
n
)
n
}
,
i
≥
2.
10. The method of claim 9 wherein at the ith of said rounds, i=1, . . . , n, where n is an integer, said messages comprise
from said node A, a first message to said node B comprising a time stamp T i 0 indicating the current time at said node A when said first message is sent,
from said node B, a second message to said node A comprising a time stamp T i 1 indicating the current time at said node B when said first message was received, and a time stamp T i 2 indicating the time at said node B at which said second message is sent, and wherein the method further comprises
determining T i 3 , the time at which said second message is received at said node B.
11. The method of claim 10 further comprising determining at said first node for each i, i=1, 2, . . . , n
X i =T i 1 −T i 0 and Y i =T i 3 −T i 2 ,
where
T i 3 −T i 2 =d−θ+e i BA
T i 1 −T i 0 =d+θ+e i AB , and
wherein θ is the offset of the clock at said second node from the clock at said first node, d is the fixed delay experienced by a message from one of said nodes to the other of said nodes, e i AB is the variable delay at said ith round for a message from said node A to said node B, e i BA is the variable delay at said ith round for a message from said node B to said node A.
12. The method of claim 11 wherein the probability distribution for e i AB and e i BA need not be of the same family of distributions.
13. The method of claim 11 wherein the probability distribution for each of e i AB and e i BA is chosen from the set of probability distributions comprising exponential, lognormal, gamma and Weibull distributions.