 |
Claims  |
|
|
What is claimed is:
1. In a distributed processing system containing a plurality of
interconnected nodes including a clerk node and a plurality of server
nodes providing time to the system, wherein the clerk node includes a
local clock having a predetermined resolution value, keeping a local time,
and having an inaccuracy associated therewith representing an amount by
which that local time deviates from a correct time value, a method for
maintaining a correct time in the clerk node comprising the steps,
performed by the clerk node, of:
requesting an updated time interval from at least one of the server nodes
when the local inaccuracy of the local clock of the clerk node exceeds a
predetermined maximum inaccuracy value;
noting a request time according to the local clock of the clerk node when
the clerk node requests said updated time interval
receiving from the server nodes respective updated time interval
representations and corresponding delay values;
noting, for each receipt of said updated time interval representations and
corresponding delay values, a different response time according to the
local clock of the clerk node;
calculating a correct time interval from said received updated time
interval representations, said received delay values, said noted request
time, said noted response times, and the resolution value of the local
clock of the clerk node, wherein the correct time is contained within said
calculated correct time interval; and
adjusting the local time kept by the local clock of the clerk node
according to said calculated correct time interval.
2. The method of claim 1, further including the step of:
incrementing the local time of the local clock of the clerk node by
periodically adding an incrementation value equal to the predetermined
resolution value to the local time kept by the local clock, and
wherein said adjusting step further includes the step of:
changing said incrementation value according to said calculated correct
time interval.
3. The method of claim 2, wherein said adjusting step further includes the
steps of:
calculating a duration value to determine a length of time during which
said changing step is performed: and
restoring said incrementation value to the predetermined resolution value
when said incrementation value changing step has been performed for a
length of time equal to said calculated duration value.
4. The method of claim 1, further including the step of:
calculating a resynchronization time at which the inaccuracy of the local
clock of the clerk node exceeds said predetermined maximum inaccuracy
value, and
wherein said requesting step is performed when the local clock of the clerk
node has a time substantially equal to said calculated resynchronization
time.
5. The method of claim 4, further including the step of requesting an
updated time interval from the server nodes when the local clock has a
time substantially equal to a predetermined maximum resynchronization
time.
6. The method of claim 1, wherein each server node includes a local clock
keeping a local time and having an inaccuracy value associated therewith,
and wherein the server nodes include time maintainer node which updates
its local clock by said requesting, request time noting, receiving,
response time noting, calculating, and adjusting steps used by the clerk
node and a time provider node which updates its local clock by accessing
an external time source, wherein said requesting step further includes the
steps, performed by the clerk node, of:
requesting an updated time interval from the time maintainer node using a
predetermined protocol; and
requesting an updated time interval from a time provider node using said
predetermined protocol.
7. The method of claim 1, wherein each server node includes a local clock
keeping a local time and having an inaccuracy value associated therewith,
and wherein the server nodes include a time maintainer node which updates
its local clock by said requesting, request time noting, receiving,
response time noting, calculating, and adjusting steps used by the clerk
node and a time provider node which updates its local clock by accessing
an external time source, wherein said receiving step further includes the
steps, performed by said clerk node, of:
receiving an updated time interval representation and a corresponding delay
value from the time maintainer node using a predetermined protocol; and
receiving an updated time interval representation and corresponding delay
values from the time provider node using said predetermined protocol.
8. In a distributed processing system containing a plurality of
interconnected server nodes, one of which is called a time maintainer
node, wherein the server nodes provide time to the system and wherein the
time maintainer node includes a local clock having a predetermined
resolution value, keeping a local time, and having an inaccuracy
associated therewith representing an amount by which that local time
deviates from a correct time value, a method for maintaining a correct
time in the time maintainer node comprising the steps, performed by the
time maintainer node, of:
requesting an updated time interval from at least one of the server nodes
when the local inaccuracy of the local clock of the time maintainer node
exceeds a predetermined maximum inaccuracy value:
noting a request time according to the local clock of the time maintainer
node when the time maintainer node requests said updated time interval;
receiving from the server nodes respective updated time interval
representations and corresponding delay values;
noting, for each receipt of said updated time interval representations and
corresponding delay values, a different response time according to the
local clock of the time maintainer node;
calculating a correct time interval from said received updated time
interval representations, said received delay values, said noted request
time, said noted response times, and the resolution value of the local
clock of the time maintainer node, wherein the correct time is contained
within said calculated correct time interval; and
adjusting the local time kept by the local clock of the time maintainer
node according to said calculated correct time interval.
9. The method of claim 8, further including the step of:
incrementing the local time of the local clock of the time maintainer node
by periodically adding an incrementation value equal to the predetermined
resolution value to the local time kept by the local clock, and
wherein said adjusting step further includes the step of:
changing said incrementation value according to said calculated correct
time interval.
10. The method of claim 9, wherein said adjusting step further includes the
steps of:
calculating a duration value to determine a length of time during which
said changing step is performed; and
restoring said incrementation value to the predetermined resolution value
when said incrementation value changing step has been performed for a
length of time equal to the calculated duration value.
11. The method of claim 8, further including the step of:
calculating a resynchronization time at which the inaccuracy of the local
clock of the time maintainer node exceeds said predetermined maximum
inaccuracy value, and
wherein said requesting step is performed when the local clock of the time
maintainer node has a time substantially equal to said calculated
resynchronization time.
12. The method of claim 8, further including the step of requesting an
updated time interval from the server nodes when the local clock has a
time substantially equal to a predetermined maximum resynchronization
time.
13. The method of claim 8, further including the step of detecting as
faulty server nodes those server nodes from which updated time interval
representations outside of said calculated correct time interval are
received.
14. The method of claim 8, wherein each server node includes a local clock
keeping a local time and having an inaccuracy value associated therewith,
and wherein the server nodes include a second time maintainer node and a
time provider node which updates its local clock by accessing an external
time source, wherein said requesting step further includes the steps,
performed by the time maintainer node, of:
requesting an updated time interval from the second time maintainer node
using a predetermined protocol; and
requesting an updated time interval from the time provider node using said
predetermined protocol.
15. The method of claim 8, wherein each server node includes a local clock
keeping a local time and having an inaccuracy value associated therewith,
and wherein the server nodes include a second time maintainer node and a
time provider node which updates its local clock by accessing an external
time source, wherein said receiving step further includes the steps,
performed by the time maintainer node of, of:
receiving an updated time interval representation and a corresponding delay
value from the second time maintainer node using a predetermined protocol;
and
receiving an updated time interval representation and corresponding delay
values from the time provider node using said predetermined protocol.
16. The method of claim 8, wherein each of the server nodes possesses one
of a plurality of epoch numbers identifying a group of nodes,
wherein said time interval representation and delay value receiving step
further includes the step of receiving from the server nodes the epoch
numbers of the server nodes, and
further including the step of ignoring said updated time interval
representations and corresponding delay values received from a server node
when said received epoch number received from the server node differs from
said epoch number of the time maintainer node.
17. In a distributed processing system containing interconnected nodes
including a server node and one other node, wherein the nodes include a
local clock having a predetermined resolution value, keeping a local time,
and having an inaccuracy associated therewith representing an amount by
which that local time deviates from a correct time value, a method for
maintaining a correct time in the other node comprising the steps,
performed by the server node, of:
receiving a request for an updated time interval from the other node when
the local inaccuracy of the local clock of the other node exceeds a
predetermined maximum inaccuracy value;
noting a receipt time according to the local clock of the server node when
the server node receives said request from the other node:
calculating a delay value from said noted receipt time;
calculating an updated time interval representation from the local time of
the local clock of the server node and the inaccuracy of the local clock
of the server node; and
sending said updated time interval representation and said corresponding
delay value to the other node.
18. The method of claim 17, wherein the server node possesses one of a
plurality of epoch numbers identifying a group of nodes, and
wherein said sending step further includes the step of sending the epoch
number of the server node to the other node.
19. In a distributed processing system containing a plurality of
interconnected nodes including a clerk node and a server node providing
time to the system, wherein each of the nodes includes a local clock
having a predetermined resolution value, keeping a local time, and having
an inaccuracy associated therewith representing an amount by which that
local time deviates from a correct time value, a method for maintaining a
correct time in the clerk node comprising the steps of:
requesting, by the clerk node, an updated time interval from the server
node when the local inaccuracy of the local clock of the clerk node
exceeds a predetermined maximum inaccuracy value;
noting, by the clerk node, a request time according to the local clock of
the clerk node when the clerk node requests said updated time interval;
receiving, by the clerk node, from the server node an updated time interval
representation and corresponding delay value;
noting, by the clerk node, for said receipt of said updated time interval
representation and corresponding delay value, a response time according to
the local clock of the clerk node;
calculating, by the clerk node, a correct time interval from said received
updated time interval representation, said received delay value, said
noted request time, said noted response time, and the resolution value of
the local clock of the clerk node, wherein the correct time is contained
within said calculated correct time interval;
adjusting, by the clerk node, the local time kept by the local clock of the
clerk node according to said calculated correct time interval;
receiving, by the server node, said request for an updated time interval
from the clerk node;
noting, by the server node, a receipt time according to the local clock of
the server node when the server node receives said request from the clerk
node;
calculating, by the server node, a delay value from said noted receipt
time;
calculating, by the server node, an updated time interval representation
from the local time of the local clock of the server node and the
inaccuracy of the local clock of the server node; and
sending, by the server node, said updated time interval representation and
said corresponding delay value to the clerk node.
20. The method of claim 19, wherein the server node possesses one of a
plurality of epoch numbers identifying a group of nodes, and
wherein said sending step further includes the step, performed by the
server node, of sending the epoch number of the server node to the clerk
node.
21. The method of claim 19, further including the step, performed by the
clerk node, of: incrementing the local time of the local clock of the
clerk node by periodically adding an incrementation value equal to the
predetermined resolution value to the local time kept by the local clock
of the clerk node, and
wherein said adjusting step further includes the step, performed by the
clerk node, of changing said incrementation value according to said
calculated correct time interval.
22. The method of claim 21, wherein said adjusting step further includes
the steps, performed by the clerk node, of:
calculating a duration value to determine a length of time during which
said changing step is performed; and
restoring said incrementation value to the predetermined resolution value
when said changing step has been performed for a length of time equal to
said calculated duration value.
23. The method of claim 19, further including the step, performed by the
clerk node, of calculating a resynchronization time at which the
inaccuracy of the local clock of the clerk node exceeds said predetermined
maximum inaccuracy value, and
wherein said requesting step is performed by the clerk node when the local
clock of the clerk node has a time substantially equal to said calculated
resynchronization time.
24. The method of claim 23, further including the step, performed by the
clerk node, of requesting an updated time interval from the server node
when the local clock of the clerk node has a time substantially equal to a
predetermined maximum resynchronization time.
25. The method of claim 19, wherein the distributed processing further
contains a plurality of interconnected server nodes including a time
maintainer node which updates its local clock by said requesting, request
time noting, receiving, response time noting, calculating, and adjusting
steps used by the clerk node and a time provider node which updates its
local clock by accessing an external time source, wherein said requesting
step performed by the clerk node further includes the steps of:
requesting an updated time interval from the time maintainer node using a
predetermined protocol; and
requesting an updated time interval from the time provider node using said
predetermined protocol.
26. The method of claim 19, wherein the distributed data processing system
further contains a plurality of interconnected server nodes including a
time maintainer node which updates its local clock by said requesting,
request time noting, receiving, response time noting, calculating, and
adjusting steps used by the clerk node and a time provider node which
updates its local clock by accessing an external time source, wherein said
receiving step performed by the clerk node further includes the steps of:
receiving an updated time interval representation and a corresponding delay
value from the time maintainer node using a predetermined protocol; and
receiving an updated time interval representation and a corresponding delay
value from the time provider node using said predetermined protocol.
27. The method of claim 19, wherein the server node is a time maintainer
node, wherein the distributed processing system further contains a second
server node providing time to the system, and further comprising the
steps, performed by the time maintainer node, of:
requesting an updated time interval from the other server node when the
local inaccuracy of the local clock of the time maintainer node exceeds a
predetermined maximum inaccuracy value;
noting a request time according to the local clock of the time maintainer
node when the time maintainer node requests said updated time interval;
receiving from the other server node an updated time interval
representation and a corresponding delay value;
noting, for said receipt of said updated time interval representation and
corresponding delay value, a response time according to the local clock of
the time maintainer node;
calculating a correct time interval from said received updated time
interval representation, said received delay value, said noted request
time, said noted response time, and the resolution value of the local
clock of the time maintainer node, wherein the correct time is contained
within said calculated correct time interval: and
adjusting the local time kept by the local clock of the time maintainer
node according to said calculated correct time interval
28. The method of claim 27, further including the step, performed by the
time maintainer node, of:
incrementing the local time of the local clock of the time maintainer node
by periodically adding an incrementation value equal to the predetermined
resolution value to the local time kept by the local clock, and
wherein said adjusting step performed by the time maintainer node further
includes the step of changing said incrementation value according to said
calculated correct time interval.
29. The method of claim 28, wherein said adjusting step performed by the
time maintainer node further includes the steps of:
calculating a duration value to determine a length of time during which
said changing step is performed; and
restoring said incrementation value to the predetermined resolution value
when said incrementation value changing step has been performed for a
length of time equal to the calculated duration value.
30. The method of claim 27, further including the step, performed by the
time maintainer node, of:
calculating a resynchronization time at which the inaccuracy of the local
clock of the time maintainer node exceeds said predetermined maximum
inaccuracy value, and
wherein said requesting step is performed by the time maintainer node when
the local clock of the time maintainer node has a time substantially equal
to said calculated resynchronization time.
31. The method of claim 27, further including the step, performed by the
time maintainer node, of requesting an updated time interval from the
other server node when the local clock has a time substantially equal to a
predetermined maximum resynchronization time.
32. The method of claim 27, further including the step, performed by the
time maintainer node, of detecting as faulty server nodes those server
nodes from which updated time interval representations outside of said
calculated correct time interval are received.
33. The method of claim 27, wherein the other server node is a time
provider node which updates its local clock by accessing an external time
source, wherein the distributed processing system further contains a
second time maintainer node providing time to the system, and wherein said
requesting step performed by the time maintainer node further includes the
steps of:
requesting an updated time interval from the second time maintainer node
using a predetermined protocol; and
requesting an updated time interval from the time provider node using said
predetermined protocol.
34. The method of claim 27, wherein the other server node is a time
provider node which updates its local clock by accessing an external time
source, wherein the distributed processing system further contains a
second time maintainer node providing time to the system, and wherein said
requesting step performed by the time maintainer node further includes the
steps of:
receiving an updated time interval representation and a corresponding delay
value from the second time maintainer node using a predetermined protocol:
and
receiving an updated time interval representation and corresponding delay
values from the time provider node using said predetermined protocol.
35. The method of claim 27, wherein each of the server nodes possesses one
of a plurality of epoch numbers identifying a group of nodes,
wherein said time interval representation and delay receiving step
performed by the time maintainer node further includes the step of
receiving from the other server nodes the epoch numbers of the server
nodes, and
further including the step of ignoring said updated time interval
representations and corresponding delay values received from a server node
when said received epoch number received from said server node differs
from said epoch number of the time maintainer node.
36. The method of claim 19, wherein the server node is a time provider node
which updates its local clock by accessing an external time source,
wherein the distributed processing system further contains an other server
node providing time to the system, an further including the steps,
performed by the time provider node, of: requesting an updated time
interval from the other server node periodically: noting a request time
according to the local clock of the time provider node when the time
provider node requests said updated time interval:
receiving from the other server node an updated time interval
representation and corresponding delay value:
noting, for said receipt of said updated time interval representation and
corresponding delay value, a response time according to the local clock of
the time provider node;
calculating a correct time interval from said received updated time
interval representation, said received delay value, said noted request
time, said noted response time, and the resolution value of the local
clock of the time provider node, wherein the correct time is contained
within said calculated correct time interval; and
detecting as faulty server nodes those server nodes from which updated time
interval representations outside of said calculated correct time interval
are received.
37. A clerk node in a distributed processing system containing a plurality
of interconnected server nodes, the clerk node providing a correct time to
an application program in the system and comprising:
a memory having a location accessible by the application program;
a local clock keeping a local time having an associated inaccuracy;
incrementing means connected to said local clock for causing said local
time to increase periodically:
first processing means connected to at least one server node and responsive
to a first series of instructions stored in said memory, for ensuring that
said local time of said local clock is within a predetermined inaccuracy
of the correct time, said processing means including:
means for requesting an updated time interval from at least one of the
server nodes when the inaccuracy of said local clock exceeds a
predetermined maximum inaccuracy value,
means for noting a request time according to said local clock when the
clerk node requests said updated time interval,
means for receiving from the server nodes respective update time interval
representations and corresponding delay values,
means for noting, for each receipt of said updated time interval
representations and corresponding delay values, a different response time
according to said local clock,
means for calculating a correct time interval from said received updated
time interval representations, said received delay values, said noted
request time, said noted response times, and said resolution value of said
local clock, wherein the correct time is contained within said calculated
correct time interval, and
means for adjusting said local time kept by said local clock according to
said calculated correct time interval; and
second processing means, connected to said memory and to said local clock
and responsive to a second series of instructions stored in said memory,
for storing said local time kept by said local clock into the memory
location accessible by the application program.
38. A time maintainer node in a distributed processing system containing a
plurality of interconnected server nodes providing time information to the
system, the time maintainer node maintaining a correct time and
comprising:
a memory;
a local clock keeping a local time having an associated inaccuracy:
incrementing circuit means connected to said local clock for periodically;
and
processing means connected to at least one server node and responsive to a
series of instructions stored in said memory, for ensuring that said local
time of said local clock is within a predetermined inaccuracy of the
correct time, said processing means including:
means for requesting an updated time interval from at least one of the
server nodes when the inaccuracy of said local clock exceeds said
predetermined maximum inaccuracy value,
means for noting a request time according to said local clock when the time
maintainer node requests said updated time interval,
means for receiving from the server nodes respective updated time interval
representations and corresponding delay values,
means for noting, for each receipt of said updated time interval
representations and corresponding delay values, a different response time
according to said local clock,
means for calculating a correct time interval from said received updated
time interval representations, said received delay values, said noted
request time, said noted response times, and said resolution value of said
local clock, wherein the correct time is contained within said calculated
correct time interval, and
means for adjusting the local time kept by said local clock according to
said calculated correct time interval.
39. The time maintainer node of claim 38, wherein the distributed
processing system further includes a requesting node that requests an
updated time interval,
and wherein the time maintainer node further includes:
second processing means, connected to the requesting node and to said local
clock, responsive to a second series of instructions stored in said
memory, for responding to a request from the requesting node, said second
processing means including:
means for receiving the request for an updated time interval from the
requesting node,
means for noting a receipt time according to said local clock when the time
maintainer node receives the request from the requesting node,
means for calculating a delay value from said noted receipt time,
means for calculating an updated time interval representation from the
local time of said local clock and the inaccuracy of said local clock, and
means for sending said updated time interval representation and said
corresponding delay value to the requesting node.
40. The time maintainer node of claim 39, wherein said time maintainer node
possesses one of a plurality of epoch numbers identifying a group of
nodes, and
wherein said second processing means further includes means for sending the
epoch number of the time maintainer node to the requesting node.
41. A time provider node in a distributed processing system containing a
plurality of interconnected server nodes, the time provider node
maintaining a correct time and comprising:
a memory;
a local clock keeping a local time having an associated inaccuracy;
increment circuit means connected to said local clock for causing said
local time to increase periodically;
external time source interface means for receiving an external time value
from an external time source;
means, connected to the external time source interface means and executing
instructions stored in the memory, for ascertaining an inaccuracy of the
external time source;
means, connected to the ascertaining means and executing instructions
stored in the memory, for calculating a correct time, including the
external time value and an interval reflecting the inaccuracy of the
external time source, from said external time value and said inaccuracy of
said external time source; and
means connected to said calculating means and executing instructions stored
in the memory for adjusting the local time kept by said local clock
according to said calculated correct time.
42. The time provider node of claim 41, wherein the distributed processing
system further includes a requesting node that requests an updated time
interval, wherein the time provider node further includes:
second processing means connected to said local clock and to the requesting
node, responsive to instructions stored in said memory, for responding to
the request for an updated time interval, said second processing means
including:
means for receiving the request for an updated time interval from the
requesting node,
means for noting a receipt time according to said local clock when the time
provider node receives said request from the requesting node,
means for calculating a delay value from said noted receipt time,
means for calculating an updated time interval representation from the
local time of said local clock and the inaccuracy of the local clock, and
means for sending said calculated updated time interval representation and
said corresponding delay value to the requesting node.
43. The time provider node of claim 42, wherein the time provider node
possesses one of a plurality of epoch numbers identifying a group of
nodes, and
wherein said second processing means further includes means for sending the
epoch number of the time provider node to the requesting node. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
The present invention relates to distributed processing systems, and
specifically to a method of maintaining a correct time in a plurality of
nodes of a distributed processing system.
(A) GENERAL NETWORK OVERVIEW
Some distributed data processing systems are configured as Local Area
Networks (LAN's) having multiple nodes connected together for passing
information back and forth. One such distributed data processing system
network 29 is shown in FIG. 1. The network consists of multiple nodes 30
which pass information along connecting lines 32. The connecting lines 32
may be twisted-pair wires, coaxial cables, or the like. The nodes 30 may
be any of various types of devices hooked to the network, such as
VAXclusters provided by Digital Equipment Corporation, microcomputers,
intelligent workstations, mainframe computers or the like.
All nodes in the network 29 contain software responsible for organizing and
coordinating the flow of information between the nodes. One type of such
software is dedicated to the mechanics of establishing a signal connection
between nodes, of transmitting information between nodes, and of ending
the connection when the information transmittal is complete. Such software
operates according to one of a variety of communication protocols, such as
Digital Network Architecture (DNA) or Open System Interconnection (OSI),
which are well known in the art and will not be
A second type of software in the nodes is dedicated, not to the mechanics
of information transmittal, but to generating the information being
transmitted, i.e., to application programs. Examples of application
programs include word processors, mail programs, data base managers, etc.
A third type of software in the nodes provides an easy-to-use interface
between the application programs and various other hardware or software.
Software programs of this third type are called "clerks," "clerk
software," or "clerk programs" because they handle the details of
information transfer for the application programs. Application programs
interfacing with clerks are called "clients," "client software," or
"client programs" because the application programs are being served by the
clerks. Nodes containing clerk software are called clerk nodes.
FIG. 2 shows a clerk program 40 in a memory 44 of a node 41. Clerk program
40 provides an interface between the network via lines 32 and an
application program 42, which is also in memory 44 of node 41. Clerk
program 40, which is executed by a processor 46 in the node 41, transmits
and receives information to and from network 29 via lines 32. Clerk
program 40 communicates with application program 42 via locations (not
shown) in memory 44 under control of application program 42. Many types of
clerk programs similar to clerk program 40 may exist to handle the various
needs of application programs.
FIG. 2 also shows a local clock 48 of node 41. Local clock 48 is
incremented regularly (if it is digital) or increased at a regular rate
(if it is analog) to keep what is called "local time" for node 41. This
incrementing is accomplished by an increment circuit 49. Local clock 48 is
accessed, i.e., set and read, by clerk program 40 in node 41. Clerk
program 40 also serves as an interface to local clock 48 for application
program 42. Thus, clerk program 40 of FIG. 2 is called a "time service"
clerk because it services requests for the local time from application
program 42.
As shown in FIG. 2, not all application programs interface to the network
via clerks. Some application programs, such as an application program 50
of FIG. 2, handle their own network communications yet still access clerk
program 40 to obtain the local time.
Several methods exist for controlling the communication of information
between the nodes 30. For example, the network of FIG. 1 uses a method
called "carrier-sensing multiple access with collision detection"
(CSMA/CD) as defined in IEEE Standard 802.3. Under CSMA/CD, all nodes on
the network are of equal importance. A node 30 can "send" information on
the network only when no other node is trying to send information. If a
node tries to send information at the same time that another node is also
trying to send information, each node will wait a randomly-determined
period of time and then attempt to resend its information. Since the
period of time each node waits before attempting a resend is randomly
determined, it is probable that both resends will be successful. Every
node On the CSMA/CD network "listens" to all information sent over the
network. If any node "sees" information intended for that node, the node
will receive the information and take appropriate action. Information
passing between the nodes of the network is organized into packets. Each
packet contains data or control information surrounded by control and
routing information.
Network 29 of FIG. 1 operates using the Ethernet standard for data
transmission. This standard governs the protocol used in transmitting data
at a low conceptual level. It is compatible with the OSI and DNA
communications protocols.
Packets on an Ethernet network may be sent using one of two basic methods:
unicasting and multicasting. In unicasting, a packet is sent from a first
node to a second node. The destination address field of the packet
indicates that the packet is destined for a single node. In multicasting,
a single node broadcasts information to multiple nodes and the destination
address field of the packet indicates that the packet is destined for a
group of nodes.
(B) REPRESENTATION OF TIME IN A DISTRIBUTED PROCESSING SYSTEM
(i) Notation
An abstract notion of time is defined by some standard which provides a
frame of reference by which all values of time are related. One such
standard is Universal Coordinated Time (UTC), an international standard
maintained by the International Time Bureau (BIH) and the one in general
use throughout the world. Political representations of UTC (such as
Eastern Standard Time (EST) or Pacific Daylight Time (PDT)) are
functionally equivalent to UTC. A clock is simply a device that provides a
measure of UTC. The UTC time standard runs at a rate that is almost
constant since it is based on ultra-stable atomic clocks. However, some
users of time signals need time that is referenced to the rotation of the
earth. This time standard is known as UT1 and is inferred from
astronomical observations. To keep UTC and UT1 approximately equal,
occasional corrections of exactly one second--called "leap" seconds--are
inserted into the UTC time scale when necessary.
In order to quantify how well a clock is measuring UTC, it is important to
define the concept of "correct" time. Let C.sub.i denote a local clock in
an ith node of network 29 and let C(i,t) represent the value of C.sub.i at
the time t. (Throughout this specification, times denoted by t refer to
UTC). In order to quantify how well a clock is measuring UTC, we introduce
several properties of Clocks. Most important of these is the property of
correctness. The following definitions will be used throughout the
remainder of the specification:
Inaccuracy: A perfect clock is one where C(i,t)=t, t. However, a real clock
always introduces some error. The inaccuracy of C.sub.i at time t, denoted
by .alpha.(i,t), is defined as the deviation of C.sub.i from UTC. Hence,
.alpha.(i,t)=C(i,t)-t.
Drift: The rate of change of inaccuracy is called the drift and for C.sub.i
of an analog clock is given by:
.delta.(i,t)=dC(i,t)/dt-1.
C.sub.i of a digital clock is given by:
.vertline.C(i,t+.DELTA.t)-C(i,t)-.DELTA.t.vertline.<.delta..DELTA.t.delta.i
.delta.t
for some interval .DELTA.t.
Monotonicity: A clock is said to be monotonic if its measure of time is
never decreasing, i.e., if
C(i,t.sub.2)>C(i,t.sub.1) for t.sub.2 >t.sub.1.
Resolution: The resolution of a clock is the maximum time interval that can
elapse without there being any change in the value of the clock. The
resolution is denoted by p.
Skew: For two clocks i and j, the skew at time t is given by
.sigma.ij(t)=.vertline.C(i,t)-C(j,t).vertline..
Correctness: For complete time information, it is not sufficient to supply
only the time C(i,t). The inaccuracy must be represented as well. Suppose
that a clock reports a positive inaccuracy I(i,t) with the value of time
C(i,t). For this combination of time and inaccuracy to be correct, we
require that I(i,t).gtoreq..vertline..alpha.(i,t).vertline. meaning that
C(i,t)-I(i,t).ltoreq.t.ltoreq.C(i,t)+I(i,t).
Time at clock i can be represented as an interval W(i,t)=[C(i,t)-I(i,t),
C(i,t)+I(i,t)]. As shown in FIG. 3, for an arbitrary interval V=[x,y], we
define V =x; V =y, .parallel.V.parallel.=(x+y)/2 (the midpoint of the
interval); and .vertline.V.vertline.=y-x (the width of the interval).
Using interval notation, the inaccuracy is given by
I(i,t)=.vertline.W(i,t).vertline./2. A time interval is said to be correct
if W(i,t) .ltoreq.t.ltoreq. W(i,t) , i.e., the interval contains UTC. A
set of M local clocks is said to be synchronized if the clocks intervals
overlap, i.e., W(1,t).andgate.W(2,t), . . . , W(M,t).noteq.0. If the
clocks are correct, they must be synchronized.
Next, some notation for interval arithmetic is defined. The sum of two
intervals is defined as [x,y]+[u,v]=[x,u, y+v]. The sum of an interval and
a scalar is identical to the sum of two intervals, one of which has width
zero. Thus [x, y]+z=[x,y]+[z,z]=[x+z, y+z]. This sum is equivalent to
translating the interval along the real line. The notation [x, y].+-.z
denotes a "stretching" of the interval, i.e., [x, y].+-.z=[x-z, y+z].
(ii) Clocks
Two basic types of clocks exist: clocks that obtain time from an external
source, such as radio signals, and clocks that are self-contained, such as
crystal clocks. Clocks of the first type measure UTC with a known bound on
the inaccuracy which depends on the propagation delay of the radio signal
and implementation specific details. If operating correctly, the time and
inaccuracy reported by clocks of the first type define an interval that
contains the instantaneous value of UTC. Clocks of the second type supply
the time in the form of a scalar and there is no inherent notion of
inaccuracy. However, clocks of the second type do have bounds on their
drifts, which is denoted by .delta. max. So, giv | | |
