Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 25
Текст из файла (страница 25)
In the first phase, every node acquires knowledge about the state of theglobal time counters in all the other nodes by the exchange of messages among thenodes. In the second phase, every node analyzes the collected information to detecterrors, and executes the convergence function to calculate a correction value for thelocal global time counter.
A node must deactivate itself if the correction termcalculated by the convergence function is larger than the specified precision ofthe ensemble. Finally, in the third phase, the local time counter of the node isadjusted by the calculated correction value.
Existing algorithms differ in the way inwhich the time values are collected from the other nodes, in the type of convergencefunction used, and in the way in which the correction value is applied to the localtime counter.Reading the Global Time. In a local-area network, the most important term affecting the precision of the synchronization is the jitter of the time messages that carrythe current time values from one node to all the other nodes.
The known minimaldelay for the transport of a time message between two nodes can be compensatedby an a priori known delay-compensation term [Kop87] that compensates for thedelay of the message in the transmission channel and in the interface circuitry.The delay jitter depends more than anything else on the system level, at which thesynchronization message is assembled and interpreted. If this is done at a high levelof the architecture, e.g., in the application software, all random delays caused by thescheduler, the operating system, the queues in the protocol software, the message703 Global TimeTable 3.1 Approximate jitter of the synchronization messageSynchronization message assembled and interpretedAt the application software levelIn the kernel of the operating systemIn the hardware of the communication controllerApproximate range of jitter500 ms–5 ms10–100 msLess than 1 msretransmission strategy, the media-access delay, the interrupt delay at the receiver,and the scheduling delay at the receiver, accumulate and degrade the quality of thetime values, thus deteriorating the precision of the clock synchronization.
Table 3.1gives approximate value ranges for the jitter that can be expected at the differentlevels [Kop87]:Since a small jitter is important to achieve high precision in the global time, anumber of special methods for jitter reduction have been proposed. Christian[Cri89] proposed the reduction of the jitter at the application software level usinga probabilistic technique: a node queries the state of the clock at another node by aquery-reply transaction, the duration of which is measured by the sender. Thereceived time value is corrected by the synchronization message delay that isassumed to be half the round-trip delay of the query-reply transaction (assumingthat the delay distribution is the same in both directions).
A different approach istaken in the Time-Triggered Architecture. A special clock synchronization unit hasbeen implemented to support the segmentation and assembly of synchronizationmessages at the hardware level, thereby reducing the jitter to a few microseconds.The new IEEE 1588 standard for clock synchronization limits the jitter by hardwareassisted time stamping [Eid06].Impossibility Result. The important role of the latency jitter e for internal synchronization is emphasized by an impossibility result by Lundelius and Lynch [Lun84].According to this result, it is not possible to internally synchronize the clocks of anensemble consisting of N nodes to a better precision than1P¼e 1N(measured in the same units as e) even if it is assumed that all clocks have perfectoscillators, i.e., the drift rates of all the local clocks are zero.The Convergence Function.
The construction of a convergence function is demonstrated by the example of the distributed Fault-Tolerant-Average (FTA) algorithmin a system with N nodes where k Byzantine faults should be tolerated. The FTAalgorithm is a one-round algorithm that works with inconsistent information andbounds the error introduced by the inconsistency.
At every node, the N measuredtime differences between the node’s clock and the clocks of all other nodes arecollected (the node considers itself a member of the ensemble with time differencezero). These time differences are sorted by size. Then the k largest and the ksmallest time differences are removed (assuming that an erroneous time value is3.4 Internal Clock Synchronization71either larger or smaller than the rest). The remaining N 2k time differences are,by definition within the precision window definition (since only k values areassumed to be erroneous and an erroneous value is larger or smaller than a goodvalue). The average of these remaining N 2k time differences is the correctionterm for the node’s clock.Example: Figure 3.12 shows an ensemble of seven nodes and one tolerated Byzantinefault.
The FTA takes the average of the five accepted time values shown.The worst-case scenario occurs if all good clocks are at opposite ends of theprecision window P, and the Byzantine clock is seen at different corners by twonodes. In the example of Fig. 3.13, node j will calculate an average value of 4P/5and node k will calculate an average value of 3P/5; the difference between thesetwo terms, caused by the Byzantine fault, is thus P/5.Precision of the FTA. Assume a distributed system with N nodes, each one with itsown clock (all time values are measured in seconds).
At most k out of the N clocksbehave in a Byzantine manner.A single Byzantine clock will cause the following difference in the calculatedaverages at two different nodes in an ensemble of N clocks:Ebyz ¼ P=ðN 2kÞ:In the worst case a total of k Byzantine errors will thus cause an error term ofEkbyz ¼ kP=ðN 2kÞ:Considering the jitter of the synchronization messages, the convergence function ofthe FTA algorithm is given byFðN; k; eÞ ¼ ðkP=ðN 2kÞÞ þ e:Fig. 3.12 Accepted andrejected time valuesprecision window Paccepted time valuesrejected time valuesjkFig. 3.13 Worst possiblebehavior of a malicious(Byzantine) clocktime differenceview of node jview of node kprecision window Πtime differencegood time valuesj average calculated by node jk average calculated by node kmaliciously faulty values723 Global TimeTable 3.2 Byzantine error term m(N, k)Number of nodes in the ensembleFaults4567121.51.331.25233101.141.54151.081.221.5201.061.141.27301.031.081.22Combining the above equation with the synchronization condition (Sect.
3.4.1)and performing a simple algebraic transformation, we get the precision of the FTAalgorithm:PðN; k; e; GÞ ¼ ðe þ GÞN 2k¼ ðe þ GÞmðN; kÞ:N 3kwhere m(N, k) is called the Byzantine error term and is tabulated in Table 3.2.The Byzantine error term m(N, k) indicates the loss of quality in the precision dueto the inconsistency arising from the Byzantine errors. In a real environment, atmost one Byzantine error is expected to occur in a synchronization round (and eventhis will happen very, very infrequently), and thus, the consequence of a Byzantineerror in a properly designed synchronization system is not serious.The drift-offset Gis determined by the quality of the selected oscillator and thelength of the resynchronization interval. If a standard quartz oscillator with anominal drift rate of 104 s/s is used, and the clocks are resynchronized everysecond, then G is about 100 ms. Because the stochastic drift rate of a crystalis normally two orders of magnitude smaller than the nominal drift rate that isdetermined by the systematic error of the quartz oscillator, it is possible to reducethe drift offset G by up to two orders of magnitude by performing systematic errorcompensation.Many other convergence functions for the internal synchronization of the clockshave been proposed and analyzed in the literature [Sch88].3.4.4State Correction Versus Rate CorrectionThe correction term calculated by the convergence function can be applied to thelocal-time value immediately (state correction), or the rate of the clock can bemodified so that the clock speeds up or slows down during the next resynchronization interval to bring the clock into better agreement with the rest of the ensemble(rate correction).State correction is simple to apply, but it has the disadvantage of generating adiscontinuity in the time base.
If clocks are set backwards and the same nominaltime value is reached twice, then, pernicious failures can occur within the real-timesoftware (see the example in Sect. 3.1.4). It is therefore advisable to implement rate3.5 External Clock Synchronization73correction with a bound on the maximum value of the clock drift so that the error ininterval measurements is limited. The resulting global time base then maintains thechronoscopy property despite the resynchronization.
Rate correction can be implemented either in the digital domain by changing the number of microticks in some of the(macro)ticks, or in the analog domain by adjusting the voltage of the crystal oscillator. Toavoid a common-mode drift of the complete ensemble of clocks, the average of the ratecorrection terms among all clocks in the ensemble should be close to zero.3.5External Clock SynchronizationExternal synchronization links the global time of a cluster to an external standard oftime. For this purpose it is necessary to access a timeserver, i.e., an external timesource that periodically broadcasts the current reference time in the form of a timemessage.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
