Method for estimating offset for clocks at network elements
AssigneeLucent Technologies Inc.
InventorsDaniel R. Jeske, Ashwin Sampath
Life of this patent
Estimating the term…
Abstract
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.
Claims13
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 {Xi}ni=1 and {Yi}ni=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 {Xi}ni=1 and {Yi}ni=1, and
- determining said estimate of offset as a function of said statistic.
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 {Xi}i=1n and {Yi}1=1n 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.
Dependencies are inferred from the claim text.