Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 26
Текст из файла (страница 26)
This time message must raise a synchronization event (such as the beep ofa wrist watch) in a designated node of the cluster and must identify this synchronization event on the agreed time scale. Such a time scale must be based on a widelyaccepted measure of time, e.g., the physical second, and must relate the synchronization event to a defined origin of time, the epoch. The interface node to atimeserver is called a time gateway.
In a fault-tolerant system, the time-gatewayshould be a fault-tolerant unit (FTU – see Sect. 6.4.2).3.5.1External Time SourcesAssume that the time gateway is connected to a GPS (Global Positioning System).The accuracy of a GPS receiver is better than 100 ns and it has an authoritativelong-term stability – in some sense, GPS is the worldwide measurement standardfor measuring the progression of time.
Alternatively, the external time source canbe a temperature compensated crystal oscillator (TCXO) with a drift rate of betterthan 1 ppm, causing a drift offset of better 1 ms/s or an atomic clock, e.g., a Rubidumclock with a drift rate in the order of 1012 , causing a drift offset of about 1 ms in 10days (more expensive atomic clocks are even better). The time gateway periodically broadcasts time messages containing a synchronization event, as well as theinformation to place this synchronization event on the TAI scale.
The time gatewaymust synchronize the global time of its cluster with the time received from theexternal time source. This synchronization is unidirectional, and therefore asymmetric, as shown in Fig. 3.14. It can be used to adjust the rate of the clocks withoutany concern for the occurrence of emergent instability effects.If another cluster is connected to this primary cluster by a secondary timegateway, then, the unidirectional synchronization functions in the same manner.The secondary time gateway considers the synchronized time of the primary clusteras its time reference, and synchronizes the global time of the secondary cluster.743 Global TimeGPS receivertime servertimegatewayclustertimegatewayflow of externalsynchronizationclusterFig.
3.14 Flow of externalsynchronizationFTUtimegatewayWhile internal synchronization is a cooperative activity among all the membersof a cluster, external synchronization is an authoritarian process: the time gatewayforces its view of external time on all its subordinates. From the point of view offault tolerance, such an authoritarian regime introduces a problem: if the authoritysends an incorrect message, then all its obedient subordinates will behave incorrectly. However, for external clock synchronization, the situation is under controlbecause of the inertia of time. Once a cluster has been synchronized, the faulttolerant global time base within a cluster acts as a monitor of the time gateway.An external synchronization message will only be accepted if its content is sufficiently close to the cluster’s view of the external time. The time gateway has only alimited authority to correct the drift rate of a cluster. The enforcement of amaximum common-mode correction rate is required to keep the error in relativetime-measurements small.
The software in each node of the cluster checks themaximum correction rate.The implementation must guarantee that it is impossible for a faulty externalsynchronization to interfere with the proper operation of the internal synchronization,i.e., with the generation of global time within a cluster. The worst possible failurescenario occurs if the external timeserver fails maliciously – a very low probabilityfailure mode if the external timeserver is GPS.
This leads to a common-modedeviation of the global time from the external time base with the maximum permitteddeviation rate. In a properly designed synchronization system, this drift from theexternal time base will not affect the internal synchronization within a cluster.3.5.2Time GatewayThe time gateway must control the timing system of its cluster in the followingways:1. It must initialize the cluster with the current external time.2.
It must periodically adjust the rate of the global time in the cluster to bring it intoagreement with the external time and the standard of time measurement, thesecond.3.5 External Clock Synchronization753. It must periodically send the current external time in a time message to the nodesin the cluster so that a reintegrating node can reinitialize its external time value.The time gateway achieves this task by periodically sending a time message witha rate-correction byte. This rate-correction byte is calculated in the time gateway’ssoftware.
First, the difference between the occurrence of a significant event, e.g.,the exact start of the full second in the timeserver, and the occurrence of the relatedsignificant event in the global time of the cluster, is measured by using the localtime base (microticks) of the gateway node. Then, the necessary rate adjustment iscalculated, bearing in mind the fact that the rate adjustment is bounded by theagreed maximum rate correction. This bound on the rate correction is necessary tokeep the maximum deviation of relative time measurements in the cluster below anagreed threshold, and to protect the cluster from faults of the server.3.5.3Time FormatsOver the last few years, a number of external-time formats have been proposedfor external clock synchronization.
The most important one is the standard for thetime format proposed in the Network Time Protocol (NTP) of the Internet [Mil91].This time format (Fig. 3.15) with a length of 8 B contains two fields: a 4 B fullseconds field, where the seconds are represented according to UTC, and a fractionof a second field, where the fraction of a second is represented as a binary fractionwith a resolution of about 232 ps. On January 1, 1972, at midnight the NTP clockwas set to 2,272,060,800.0 s, i.e., the number of seconds since January 1, 1900 at00:00 h.The NTP time is not chronoscopic because it is based on UTC which has toaccommodate for the switching second. The occasional insertion of a leap secondinto UTC can disrupt the continuous operation of a time-triggered real-time system.Another time format is the IEEE 1588 standard time format [Eid06].
In this timeformat the epoch starts on January 1, 1970 at 00:00 h or is user defined. The fullseconds are counted according to TAI, while the unit of the fraction of a second isthe nanosecond. This leads to abrupt change in the representation whenever a fullsecond is reached.The Time-Triggered Architecture (TTA) uses a time format that is a combination of IEEE 1588 and NTP. The full seconds are counted as in TAI (such as IEEE1588), but parts of a second are represented in a binary fraction of the full second(such as NTP). It is thus chronoscopic and conforms fully to the dual system.Fig. 3.15 Time format in theNetwork Time Protocol(NTP)full seconds UTC, 4 bytesbinary fraction of second, 4 bytesrange up to the year 2036.
i.e., 136 years wrap-around cycle763 Global TimePoints to RememberlllllllllllllllllAn event happens at an instant, i.e., at a point of the timeline. A duration is asection of the timeline delimited by two instants.A consistent delivery order of a set of events in a distributed system does notnecessarily reflect the temporal or causal order of the events.A physical clock is a device for time measurement that contains a counter and aphysical oscillation mechanism that periodically generates an event to increasethe counter.Typical maximum drift rates r of physical clocks are in the range from 102to 107 s/s, or lower, depending on the quality (and price) of the resonator.The precision denotes the maximum offset of respective ticks of any two clocksof an ensemble during the time interval of interest.The accuracy of a clock denotes the maximum offset of a given clock from theexternal time reference during the time interval of interest.TAI is a chronoscopic timescale, i.e., a timescale without any discontinuities,that is derived from the frequency of the radiation of a specified transition of thecesium atom 133.UTC is a non-chronoscopic timescale that is derived from astronomical observations of the rotation of the earth in relation to the sun.A global time is an abstract notion that is approximated by properly selectedmicroticks from the synchronized local physical clocks of an ensemble.The reasonableness condition ensures that the synchronization error is alwaysless than one granule of the global time.If the difference between the time-stamps of two events is equal to or larger than2 ticks, then that temporal order of events can be recovered, provided the globaltime is reasonable.The temporal order of events can always be recovered from their time-stampsif the event set is at least 0/3g precedent.If events happen only at properly selected points of a sparse time base, then it ispossible to recover the temporal order of the events without the execution of anagreement protocol.The convergence function F denotes the offset of the time values immediatelyafter the resynchronization.The drift offset Gindicates the maximum divergence of any two good clocksfrom each other during the resynchronization interval Rint, in which the clocksare free running.The synchronization condition states that the synchronization algorithm mustbring the clocks so close together that the amount of divergence during the nextfree-running resynchronization interval will not cause a clock to leave theprecision interval.Clock synchronization is only possible if the total number of clocks N islarger or equal to (3k + 1), if k is the number of clocks behaving maliciouslyfaulty.Review Questions and Problemsllllll77The most important term affecting the precision of the synchronization is thelatency jitter of the synchronization messages that carry the current time valuesfrom one node to all other nodes of an ensemble.When applying the fault-tolerant average algorithm, the Byzantine error factorm(N, k) denotes the loss of quality in the precision caused by the Byzantine errors.State correction of a clock has the disadvantage of generating a discontinuity inthe time base.While internal synchronization is a cooperative activity among all members of acluster, external synchronization is an authoritarian process: the timeserverforces its view of external time on all its subordinates.The NTP time, based on UTC, is not chronoscopic.
The occasional insertion of aleap second can disrupt the continuous operation of a time-triggered real-timesystem.The time gateway maintains the external synchronization by periodically sending a time message with a rate correction byte to all the nodes of a cluster.Bibliographic NotesThe problem of generating a global time base in a distributed system has first beenanalyzed in the context of the SIFT [Wen78] and FTMP [Hop78] projects. A VLSIchipfor clock synchronization in distributed systems was developed by Kopetz andOchsenreiter [Kop87].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
