Presentation 11/20: Fine-Grained Network Time Synchronization using Reference Broadcasts
22 views
Skip to first unread message
Su Kim
Nov 20, 2007, 1:32:40 PM11/20/07
to ASU:CSE535 FALL 07 Mobile Computing
Authors: Jeremy Elson, Lewis Girod and Deborah Estrin,
Title: "Fine-Grained Network Time Synchronization using Reference
Broadcasts,"
Published: In Proceedings of the Fifth Symposium on Operating Systems
Design and Implementation (OSDI 2002), Boston, MA, December 2002
Title: "Fine-Grained Network Time Synchronization using Reference
Broadcasts,"
Published: In Proceedings of the Fifth Symposium on Operating Systems
Design and Implementation (OSDI 2002), Boston, MA, December 2002
Shiraz Saleem
Nov 20, 2007, 5:52:08 PM11/20/07
to asu_cse...@googlegroups.com
Some questions which were raised in my presentation and for which the answers were not convincing enough were,
Why does the precision decay slowly in Multi-hop networks? (Aarti)
The synchronization error appeared Gaussian in the set of receivers and the mean error converges to zero with large number of pulses broadcasted. If the average one hop error is
σ , then the average path error is σ*sqrt(n).(I proved to you in class how they came at this solution). The reason for a slow decay is due to O(sqrt(n)). They proved this experimentally also.
Why do you quantify bandwidth used by beacon nodes v/s precision? (Ayan)
The precision of the synchronization seem improves as the number of pulses broadcasted are higher. So it would be useful to know that for a given bandwidth utilization by the beacon node, what would the level of precision acheived.
Best Wishes,
Shiraz
jun.s...@asu.edu
Nov 20, 2007, 7:08:01 PM11/20/07
to ASU:CSE535 FALL 07 Mobile Computing
critique by Jun Shen
Overview:
This paper presents a Reference-Broadcast Synchronization
(RBS), a time synchronization scheme works without explicit timestamp.
The paper validates RBS from two wireless implementations. One
implementation is on Berkeley Motes and the other is on Compaq IPAQ.
Strength:
1. RBS does not require an explicit timestamp beacon signals, not even
a dedicated synchronization signal. Because it does not synchronize
time clock between the sender and the receiver, it synchronizes the
clock between receivers.
2. RBS removes the non-determinism from the critical path, in other
words, it removes the error generated from "Send Time" and "Access
Time" so that it obtains a high synchronization precision.
3. Clock skew has been addressed using "least-squares linear
regression".
4. The paper shows the relationship between the number of nodes and
the accuracy of synchronization, between the number of reference
broadcasts and the accuracy. Besides, the paper gives a comparison
between RBS and NTP, showing the superior of RBS over NTP
Weakness:
1. If network contains few nodes, then the accuracy of the RBS is
dubious.
2. If a broadcast is not well dispersed, then the RBS is not
applicable.
3. Some details are omitted such as how can two nodes make sure that
they are comparing the arrival time of a same broadcast message.
Overview:
This paper presents a Reference-Broadcast Synchronization
(RBS), a time synchronization scheme works without explicit timestamp.
The paper validates RBS from two wireless implementations. One
implementation is on Berkeley Motes and the other is on Compaq IPAQ.
Strength:
1. RBS does not require an explicit timestamp beacon signals, not even
a dedicated synchronization signal. Because it does not synchronize
time clock between the sender and the receiver, it synchronizes the
clock between receivers.
2. RBS removes the non-determinism from the critical path, in other
words, it removes the error generated from "Send Time" and "Access
Time" so that it obtains a high synchronization precision.
3. Clock skew has been addressed using "least-squares linear
regression".
4. The paper shows the relationship between the number of nodes and
the accuracy of synchronization, between the number of reference
broadcasts and the accuracy. Besides, the paper gives a comparison
between RBS and NTP, showing the superior of RBS over NTP
Weakness:
1. If network contains few nodes, then the accuracy of the RBS is
dubious.
2. If a broadcast is not well dispersed, then the RBS is not
applicable.
3. Some details are omitted such as how can two nodes make sure that
they are comparing the arrival time of a same broadcast message.
Su Kim
Nov 27, 2007, 2:08:28 PM11/27/07
to ASU:CSE535 FALL 07 Mobile Computing
From Aarti,
Please find my critique for the paper below:
Paper: Fine Grained Network Time Synchronization uing Reference
Broadcasts
Critique: Aarti Munjal
Overview:
The paper presents a scheme for time-synchronization in a network
which is different from other algorithms and novel in that it proposes
a synchronization between set of receivers instead of between senders
and receivers. Periodically, nodes send beacon messages to neighbors
which are treated as point of reference(of comparing clock-times) by
the neighbors and hence the name 'Reference Broadcasts Scheme' (RBS).
Its performance is compared with NTP and the synchronization errors in
both schemes are compared. RBS outperforms NTP in lightly loaded
network and has little effect on its sync error when the load in
network increases while NTP-performance is badly affested by the
increased load in the network.
So, here are few strong points and weaker side of the paper:
Strength ----
1. The scheme has been compared with widely used NTP, so the novel
idea involved has been proved to be fruitful when it outperforms
NTP.
2. The sync error involved is in microseconds, when it has been
tested on various hardware platforms which proves its feasibility in
real time aplications also.
3. With multi-hops the precision decays slowly, which I guess answers
the question as to how scalable the scheme is.
Weaker Side ----
1. Good that the scheme has been comapred with widely use protocol
NTP, but how justifiable is replacing NTP with this scheme. Even if
the scheme outperforms NTP, will it be a good idea to replace NTP with
this, thats a big question in itself.
2. The one point that they have pointed out tehmselves is the
'Convergence Time'. So, it would have been good to provide with some
thoughts about how long the scheme takes to converge. Even if it has
not been done experimentally, but I guess the question can be answered
analytically.
Please find my critique for the paper below:
Paper: Fine Grained Network Time Synchronization uing Reference
Broadcasts
Critique: Aarti Munjal
Overview:
The paper presents a scheme for time-synchronization in a network
which is different from other algorithms and novel in that it proposes
a synchronization between set of receivers instead of between senders
and receivers. Periodically, nodes send beacon messages to neighbors
which are treated as point of reference(of comparing clock-times) by
the neighbors and hence the name 'Reference Broadcasts Scheme' (RBS).
Its performance is compared with NTP and the synchronization errors in
both schemes are compared. RBS outperforms NTP in lightly loaded
network and has little effect on its sync error when the load in
network increases while NTP-performance is badly affested by the
increased load in the network.
So, here are few strong points and weaker side of the paper:
Strength ----
1. The scheme has been compared with widely used NTP, so the novel
idea involved has been proved to be fruitful when it outperforms
NTP.
2. The sync error involved is in microseconds, when it has been
tested on various hardware platforms which proves its feasibility in
real time aplications also.
3. With multi-hops the precision decays slowly, which I guess answers
the question as to how scalable the scheme is.
Weaker Side ----
1. Good that the scheme has been comapred with widely use protocol
NTP, but how justifiable is replacing NTP with this scheme. Even if
the scheme outperforms NTP, will it be a good idea to replace NTP with
this, thats a big question in itself.
2. The one point that they have pointed out tehmselves is the
'Convergence Time'. So, it would have been good to provide with some
thoughts about how long the scheme takes to converge. Even if it has
not been done experimentally, but I guess the question can be answered
analytically.
0 new messages