System and method for clock synchronization in a wireless backhaul network using IEEE 1588 precision time protocol
A method and system is disclosed for clock synchronization in a wireless backhaul network, based on the IEEE1588 Precision Time Protocol (PTP). The network comprises a plurality of hubs, each hub serving one or more remote backhaul modules. Each hub comprises a slave clock, which communicates with a master clock through forward and reverse links. The method comprises, for each hub, estimating the frequency drift {circumflex over (α)} and offset {circumflex over (β)} from the forward and reverse links between the master and slave clock, estimating the accuracy of {circumflex over (α)} and {circumflex over (β)}, determining the least congested link, and adjusting the frequency of the slave clock based on {circumflex over (α)} and {circumflex over (β)} from the least congested link. A fixed or variable time window size is selected to achieve a desired accuracy of {circumflex over (α)} and {circumflex over (β)}. The method may comprise estimating a maximum holdover time for maintaining synchronization with a desired confidence level.
1. A method for clock synchronization in a fixed wireless backhaul network using IEEE1588 Precision Time Protocol (PTP), the wireless backhaul network comprising a plurality of fixed nodes, each node comprising a hub or a Remote Backhaul Module (RBM), wherein each hub serves one or more Remote Backhaul Modules (RBMs), and wherein each hub comprises a slave clock, and each slave clock communicates with a master clock through a forward link (master-to-slave) and a reverse link (slave-to-master), the method comprising, for each slave clock, the steps of:
for a frame rate of F t and a time window size W, during each time window W, obtaining a plurality of time-stamps, comprising t 1 and t 2 , for the forward link and t 3 and t 4 , for the reverse link, and storing said plurality of time stamps;
determining from said stored time stamps, for said time window W, an estimated frequency drift {circumflex over (α)} and estimated offset {circumflex over (β)} for each of the forward and reverse links;
determining an estimation error Δ{circumflex over (α)} of the estimated drift frequency drift {circumflex over (α)} and an estimation error Δ{circumflex over (β)} of the estimated offset {circumflex over (β)} for each of the forward and reverse links;
determining which of the forward and reverse links is a least congested link; and
if the estimation errors Δ{circumflex over (α)} and Δ{circumflex over (β)} of the least congested link are less than or equal to a predefined maximum estimation error, adjusting the slave clock based on said estimated frequency drift {circumflex over (α)} and estimated offset {circumflex over (β)} of the least congested link;
otherwise, changing the window size and repeating the preceding steps until the estimation errors Δ{circumflex over (α)} and Δ{circumflex over (β)} of the least congested link are less than or equal to a predefined maximum estimation error, or, declaring loss of synchronization.
2. The method of claim 1 , wherein, if the estimation error errors Δ{circumflex over (α)} and Δ{circumflex over (β)} of the least congested link are greater than the maximum estimation error, incrementally increasing the time window size by a factor c, where c is greater than one, and repeating said steps until the estimation errors Δ{circumflex over (α)} and Δ{circumflex over (β)} of the least congested link are less than or equal to the predefined maximum estimation error.
3. The method of claim 1 , wherein, if the estimation error errors Δ{circumflex over (α)} and Δ{circumflex over (β)} of the least congested link are less than or equal to the maximum estimation error, successively decreasing the time window size by ΔW and repeating the preceding steps to obtain a minimum window size that provides estimation errors Δ{circumflex over (α)} and Δ{circumflex over (β)} of the least congested link that are less than or equal to the predefined maximum estimation error.
4. The method of claim 1 , wherein the least congested link of the forward and reverse links is determined as the link that results in the least estimation error.
5. The method of claim 1 further comprising, for each of the forward and reverse links, applying packet delay filtering to identify a plurality of lucky packets in said time window W, and applying linear regression on the plurality of lucky packets to obtain the estimated frequency drift {circumflex over (α)} and estimated offset {circumflex over (β)}.
6. The method of claim 1 , wherein determining estimated frequency drift frequency drift {circumflex over (α)} and estimated offset {circumflex over (β)} for the forward and reverse links comprises:
for the forward link, determining intermediate drifts and offset values {tilde over (α)}, {tilde over (β)}, by solving the following optimization:
min
α
~
,
β
~
∑
i
=
1
WF
t
t
2
(
i
)
-
t
1
(
i
)
-
α
~
(
t
1
(
i
)
-
t
1
(
1
)
)
-
β
~
subject
to
t
2
(
i
)
-
t
1
(
i
)
≥
α
~
(
t
1
(
i
)
-
t
1
(
1
)
)
+
β
~
,
∀
i
∈
{
1
,
…
,
WF
t
}
performing packet delay filtering (PDV) comprising applying packet filtering using the said intermediate values {tilde over (α)}, {tilde over (β)}, to identify lucky packets that satisfy the following condition:
LP={i:t 2 (i) −t 1 (i) ≦{tilde over (α)}( t 1 (i) −t 1 (1) )+{tilde over (β)}+6σ J }
n LP =|LP|, number of lucky packets
applying linear regression on the lucky packets to find the said estimated frequency drift frequency drift {circumflex over (α)} and estimated offset {circumflex over (β)}, and
correspondingly, for the reverse link, determining intermediate drifts and offset values {tilde over (α)}, {tilde over (β)}, by replacing t 1 with t 4 and t 2 −t 1 with t 4 −t 3 in the above optimization; and
defining the offset in forward link as O={circumflex over (β)}−tmpd and the offset in the reverse link as O=−({circumflex over (β)}−tmpd).
7. The method of claim 6 , further comprising performing jitter filtering using linear regression comprising:
for the forward link,
let x, y, be two n LP ×1 vectors, given by
x={t 1 (i) −t 1 (i) :iεLP}, y={t 2 (i) −t 1 (i) :iεLP}
wherein the estimated frequency drift and offset are given by
α
~
=
(
x
-
x
_
)
T
(
y
-
y
_
)
(
x
-
x
_
)
T
(
x
-
x
_
)
,
{tilde over (β)}= y −{tilde over (α)} x
and, correspondingly, for the reverse link, replacing t 1 with t 4 and t 2 −t 1 with t 4 −t 3 .
8. The method of claim 6 , wherein,
for a given Confidence level, CL %, estimating the estimation errors on {circumflex over (α)} and {circumflex over (β)}, denoted by Δ{circumflex over (α)} and Δ{circumflex over (β)}, respectively, such that αε[α−Δ{circumflex over (α)}, α+Δ{circumflex over (α)}] and βε[{circumflex over (β)}−Δ{circumflex over (β)}, {circumflex over (β)}+Δ{circumflex over (β)} ];
let t n LP -2 * denote the (1−(1−CL/100)/2) quantile of student t n LP -2 distribution (Student's t-distribution with n LP −2 degrees of freedom);
let
S
α
=
1
n
LP
-
2
(
y
-
(
α
^
x
+
β
^
)
)
T
(
y
-
(
α
^
x
+
β
^
)
)
(
x
-
x
_
)
T
(
x
-
x
_
)
,
S
β
=
S
α
x
T
x
n
LP
;
then, the estimation errors are given by
Δ {circumflex over (α)}=S α t n LP -2 *
Δ{circumflex over (β)}= S β t n LP -2 *.
9. The method of claim 8 wherein, for CL=99%, the following approximation is used t n LP -2 *≈2.578+26660e −2.0265n LP .
10. The method of claim 6 , wherein determining the least congestion link of the forward and reverse links comprises selecting the link that results in the largest number of lucky packets.
11. The method of claim 6 , wherein:
If n LP in the forward link >= min − n LP AND n LP in the
reverse link >= min − n LP
AND
Δα 12 ≦ max − freq − error AND Δα 34 ≦ max − freq − error
If Δα 12 ≦ Δα 34 :
f = f − (K p {circumflex over (α)} 12 + K I ({circumflex over (β)} 12 − tmpd))
W := W − ΔW
Else
f = f + (K p {circumflex over (α)} 34 + K I ( {circumflex over (β)} 34 − tmpd))
W := W − ΔW
EndIf
Elseif n LP in the forward link >= min − n LP AND Δα 12 ≦ max −
freq − error
f = f − (K p {circumflex over (α)} 12 + K I ({circumflex over (β)} 12 − tmpd))
W := W − ΔW
Elseif n LP in the reverse link >= min − n LP AND Δα 34 ≦ max −
freq − error
f = f + (K p {circumflex over (α)} 34 + K I ( {circumflex over (β)} 34 − tmpd))
W := W − ΔW
Else
W := cW
EndIf.
12. The method of claim 6 , wherein:
If n LP in the forward link >= min − n LP AND n LP in the
reverse link >= min − n LP
If n LP in the forward link≧ n LP in the reverse link:
f = f − (K p {circumflex over (α)} 12 + K I ({circumflex over (β)} 12 − tmpd))
W := W − ΔW
Else
f = f + (K p {circumflex over (α)} 34 + K I ( {circumflex over (β)} 34 − tmpd))
W := W − ΔW
EndIf
Elseif n LP in the forward link >= min − n LP
f = f − (K p {circumflex over (α)} 12 + K I ({circumflex over (β)} 12 − tmpd))
W := W − ΔW
Elseif n LP in the reverse link >= min − n LP
f = f + (K p {circumflex over (α)} 34 + K I ( {circumflex over (β)} 34 − tmpd))
W := W − ΔW
Else
W := cW
EndIf.
13. The method of claim 6 , wherein:
If n LP in the forward link >= min − n LP AND n LP in the
reverse link >= min − n LP
If n LP in the forward link≧ n LP in the reverse link:
f = f − (K p {circumflex over (α)} 12 + K I ({circumflex over (β)} 12 − tmpd))
Else
f = f + (K p {circumflex over (α)} 34 + K I ( {circumflex over (β)} 34 − tmpd))
EndIf
Elseif n LP in the forward link >= min − n LP
f = f − (K p {circumflex over (α)} 12 + K I ({circumflex over (β)} 12 − tmpd))
Elseif n LP in the reverse link >= min − n LP
f = f + (K p {circumflex over (α)} 34 + K I ( {circumflex over (β)} 34 − tmpd))
Else
Do not adjust the frequency
EndIf.
14. The method of claim 6 , wherein to reduce the memory storage required to estimate the frequency drift {circumflex over (α)} and offset {circumflex over (β)}, from complexity O(W)) to complexity O(√{square root over (W)}), the steps of obtaining a plurality of time-stamps, comprising t 1 and t 2 , for the forward link and t 3 and t 4 , for the reverse link, and storing said plurality of time stamps comprises:
obtaining timestamps for every √{square root over (N p2keep WF t )} packets, where N p2keep is a number of packets to keep, and storing only N p2keep lucky packets, and
estimating the frequency drift {circumflex over (α)}ε{{circumflex over (α)} 12 , {circumflex over (α)} 34 } and offset {circumflex over (β)}ε{{circumflex over (β)} 12 , {circumflex over (β)} 34 } for the stored √{square root over (N p2keep W F t )} lucky packets.
15. The method of claim 14 , further comprising selecting a small window having a short window size sufficient to obtain a desired minimum number of lucky packets, and performing said procedure recursively for a plurality of said small windows, thereby reducing the storage to O( n+1 √{square root over (W)}), where n is the number of times the above procedure is run.
16. The method of claim 1 further comprising:
determining a maximum tolerable synchronization error, MaxSynchError, between the master clock and slave clock;
determining a target confidence level for synchronization; and
declaring loss of synchronization if
|{circumflex over (β)}− tmpd |+Δ{circumflex over (β)}≧MaxSynchError
where tmpd is the mean propagation delay.
17. The method of claim 1 , further comprising
determining a target confidence level for synchronization, MaxSynchError; and
computing a maximum holdover time as:
Maximum
hold
over
time
=
max
(
MaxSynchError
-
(
β
^
-
tmpd
)
+
Δ
β
^
min
(
α
^
+
Δ
α
^
,
α
^
-
Δ
α
^
)
,
0
)
where {circumflex over (β)} is the estimated offset, Δ{circumflex over (β)} is the estimation error on {circumflex over (β)}, {circumflex over (α)} is the estimated drift, Δ{circumflex over (α)} is the estimation error on {circumflex over (α)}, and tmpd is the mean propagation delay.
18. A system for clock synchronization using IEEE1588 precision time protocol (PTP) in a fixed wireless backhaul network comprising a plurality of nodes, said nodes comprising hubs and Remote Backhaul Modules (RBMs), wherein each hub serves one or more Remote Backhaul Modules (RBMs), each hub comprising a slave clock, and wherein each slave clock communicates with a master clock through a forward link (master-to-slave) and a reverse link (slave-to-master), and processor means comprising at least one processor and a computer readable storage medium, storing programming instructions for execution by said at least one processor, for implementing the method of claim 1 .
19. A non-transitory computer readable storage medium in a fixed wireless backhaul network comprising a plurality of nodes, said nodes comprising hubs and Remote Backhaul Modules (RBMs), wherein each hub serves one or more Remote Backhaul Modules (RBMs), each hub comprising a slave clock, and wherein each slave clock communicates with a master clock through a forward link (master-to-slave) and a reverse link (slave-to-master), the non-transitory computer readable storage medium storing programming instructions for execution by at least one processor, for implementing a method for clock synchronization using IEEE1588 Precision Time Protocol (PTP), comprising, for each slave clock, the steps of:
for a frame rate of F t and a time window size W, during each time window W, obtaining a plurality of time-stamps, comprising t 1 and t 2 , for the forward link and t 3 and t 4 , for the reverse link, and storing said plurality of time stamps;
determining from said stored time stamps, for said time window W, an estimated frequency drift {circumflex over (α)} and estimated offset {circumflex over (β)} for each of the forward and reverse links;
determining an estimation error Δ{circumflex over (α)} of the estimated drift frequency drift {circumflex over (α)} and an estimation error Δ{circumflex over (β)} of the estimated offset {circumflex over (β)} for each of the forward and reverse links;
determining which of the forward and reverse links is a least congested link; and
if the estimation errors Δ{circumflex over (α)} and Δ{circumflex over (β)} of the least congested link are less than or equal to a predefined maximum estimation error, adjusting the slave clock based on said estimated frequency drift {circumflex over (α)} and estimated offset {circumflex over (β)} of the least congested link;
otherwise, changing the window size and repeating the preceding steps until the estimation errors Δ{circumflex over (α)} and Δ{circumflex over (β)} of the least congested link are less than or equal to a predefined maximum estimation error, or, declaring loss of synchronization.