Browse Prior Art Database

Clock Synchronization Algorithm for Broadcast Networks

IP.com Disclosure Number: IPCOM000037053D
Original Publication Date: 1989-Nov-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 4 page(s) / 46K

Publishing Venue

IBM

Related People

Franaszek, PA: AUTHOR [+2]

Abstract

Disclosed is a method to allow a network of computers to synchronize their clocks by receiving and sharing U.S. National Bureau of Standards time broadcast signals. The network is assumed to possess the following properties. 1. The network is a broadcast network. 2. One or more nodes are able to receive and decode WWV time signals transmitted by the National Bureau of Standards. 3. Nodes lacking WWV receivers have some other local clock which maintains the time in between updates from the WWV-driven clocks. 4. WWV-driven clocks have a drift rate of 0. 5. Clocks that are not driven by WWV run at a rate that is bounded between (1 - p) and (1 + p) of absolute time. 6. The drift rate of a clock is fixed. 7.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 58% of the total text.

Page 1 of 4

Clock Synchronization Algorithm for Broadcast Networks

Disclosed is a method to allow a network of computers to synchronize their clocks by receiving and sharing U.S. National Bureau of Standards time broadcast signals. The network is assumed to possess the following properties.
1. The network is a broadcast network.
2. One or more nodes are able to receive and decode WWV

time signals transmitted by the National Bureau of

Standards.
3. Nodes lacking WWV receivers have some other local clock

which maintains the time in between updates from the

WWV-driven clocks.
4. WWV-driven clocks have a drift rate of 0.
5. Clocks that are not driven by WWV run at a rate that is

bounded between (1 - p) and (1 + p) of absolute time.
6. The drift rate of a clock is fixed.
7. A synchronization message sent from one processor to

another is delivered and processed in at least delay1

and at most delay2 seconds after the sending processor

read its clock.
8. Messages are never lost.
9. A request for medium access must be granted in at most

access delay seconds.

Due to production tolerances, clocks that are not driven by WWV may run faster or slower than those that are. If we disallow abrupt changes in the clock time, it is clear that clocks must be adjusted by adjusting their drift rate. Two approaches suggest themselves.
1. A hardware-based approach-possibly implemented by

adding a varicap diode in parallel with the crystal so

as to vary its resonant frequency,
2. A software-based approach in which the time read on the

hardware clock HC is translated to a logical clock

value of C via the linear transformation C = Offset +

(1 + µ x HC. p determines the rate of the clock, while

Offset is chosen so as to ensure that the logical clock

is continuous at the time of modification.

This algorithm is based on the second approach. In addition, the algorithm is designed so that in the event of a message being lost, a WWV-driven node will with very high probability retransmit its time with an overhead of only 2 messages. The algorithm run by WWV-driven nodes differs somewhat from that run by the other nodes. The Algorithm Run by WWV-Driven Nodes:
1. (Initialization) Timer E W1

Cycle

Receive Synch_Message on incoming edge, forward it

on corresponding outgoing edges.

If (Synch_Message = Set_Me or

Please_Retransmit) Then

1

Page 2 of 4

If we have a token transmit (C, WWV) .

If not, request permission to transmit and

transmit (C,WWV) when permission is granted.

Timer E W1

Else If (Synch_Message = (T,WWV)) Then

Timer E W2

Delete any requests for medium access for

the purpose of transmitting a synch message.

End If

End Cycle
2. Timeout(Timer)

If we have a toke...