Method for synchronizing the time clocks of computing devices connected to a communication medium, and the computing devices concerned.

0001Distributed computer systems consist of a number of autonomous computers (node ​​computers) that are loosely connected to one another via a local network (communication medium). The communication medium can have a bus / tree or ring topology, various methods of accessing the node computers to the network having become known. Protocols define the communication between the individual node computers over the network. A detailed description of this problem area can be found in Stallings W., "Local Networks", Computing Surveys, Vol. 16, No.1, March 1984, p.3-41.

0002It corresponds to the state of the art that each node computer has its own real-time whore. The accuracy of these watches is in the range of the accuracy of quartz watches, ie the relative error is 10 ** - 6.

0003If a real-time application, for example a technical process, is now controlled by a distributed real-time system, it is necessary to synchronize the real-time clocks within the individual node computers. The accuracy of the synchronization defines the time intervals that can still be resolved by the system. Inaccuracies in synchronization can lead to loss of information and often to a breakdown of the entire system. In some cases, e.g. With the nationwide load distribution of electrical energy, such inaccuracies can actually have catastrophic consequences.

0004The clocks are synchronized in a distributed real-time system by exchanging messages, which saves channels and lines for synchronization. If possible, the synchronization process should be fault-tolerant, ie a faulty clock should be recognized as such and should not be further considered in the synchronization process. The loss of individual messages should also be tolerated. That part of the broadcast or The received message, which contains the information about the status of the local real-time clock, is called a time stamp and typically has a length of 2 to 4 bytes.

0005In recent years, some algorithms for the fault-tolerant synchronization of real-time clocks in distributed computer systems coupled via messages have been published. As part of the SIFT research project (JH Wensley et al. "SIFT: The Design and Analysis of a Fault Tolerant System for Aircraft Control", Proceedings of the IEEE Vol 66, No. 10, p. 1240-1255, October 1978) a prototype of a message-synchronized, distributed, highly reliable computer system was built. Mini computers available on the market were used as node computers. The synchronization algorithm was executed in the (only) CPU of these node computers in parallel with the application software.

0006From the above work it is apparent that the computing effort increases significantly with the number of node computers in a network and the number of tolerated errors and the central processing unit of the node computers then becomes unbearably stressed. A major improvement in this regard is the computing system according to AT-PS 382.253 (A 2030/84), which creates an autonomous synchronization unit and leads to the unbundling of tasks in the node computer and thus to a reduction in software complexity.

0007So that the time determination of a global system event can be determined precisely on a clock tick, the following must apply: g> Δ wherein: g ... granularity, resolution, that is the distance between two ticks, and Δ ... maximum deviation between two clocks in the system.

0008In order to obtain a sufficiently small granularity, Δ must be kept as small as possible.

0009The deviation Δ can be calculated, for example for the so-called "fault-tolerant average algorithm", as:<maths id="math0001" num=""><img file="EP0247026A2_D0001.tif" /></maths> wherein: ε ... reading blur ξ ... maximum deviation of two clocks during the synchronization interval N ... number of clocks in the system k ... number of "wrong" clocks

0010For synchronization intervals with a length of 1s, for example, typisch ∼ 5µs is typical, whereas ε is between 1ms and 10ms depending on the type of system or protocol.

0011The reading blur ε is determined by three factors, namely:<ul id="ul0001" list-style="none"><li>a) the variability of the time from reading the clock (creation of the time stamp) to sending the message</li><li>b) the variability of the time of the message transport</li><li>c) The variability of the time from the arrival of the message at the recipient to the reading of the clock.</li></ul>

0012The variability mentioned under a) is caused by the fact that, on the one hand, the node computer must not send at any time, but must wait until access to the communication medium is available and, on the other hand, because of the complex structure of the communication unit, a considerable amount of time may pass before being requested is actually sent by the central unit of the node computer.

0013The invention has set itself the task of significantly reducing the reading blur by reducing the variability mentioned under a) above.

0014This goal can be achieved with a method of the type mentioned in the introduction, in which, according to the invention, the time stamp is only created and embedded in the message when the node computer has started to send the message.

0015Thanks to the method according to the invention, it is ensured that the time stamp read out of the message is always "current". Depending on the type of network and the protocol used, the granularity can be reduced by one to two orders of magnitude. In contrast, the time stamp according to the prior art was already set at a time when the actual time of transmission was still uncertain.

0016An advantageous development of this method is characterized in that after a command from the central unit of the node computer, its communication unit reads the beginning of the message from the memory of the node computer via direct memory access and stores it in an internal FIFO memory, thereupon the access authorization to the communication medium is checked and, if the same is present, the transmission of the message from the FIFO memory is started and the time stamp is then created and embedded in the message via the FIFO memory.

0017It is expedient if the message length is chosen to be greater than the storage capacity of the FIFO memory, since the premature filing and "aging" of the time stamp can be avoided without special measures.

0018The inaccuracies of the internal clock are least effective if the time stamp in the area of ​​the message end is embedded in the message.

0019A node computer for carrying out the method according to the invention, which contains a central processing unit, a local real-time clock, a synchronization unit, a communication unit and a memory, is characterized in that the communication unit which has direct access to the memory via a DMA unit contains a FIFO memory, the Storage capacity is less than the message length, the communication unit having received a send command from the central unit for reading a first message part into the FIFO memory, for subsequently checking the access authorization to the communication medium, after the presence of the same for reading out the FIFO memory to the communication medium and for further transferring the message from the memory into the FIFO memory and at a predetermined position of the message for reading a time stamp created in the synchronization unit into the FIFO memory.

0020The invention together with its further advantages and features is explained in more detail below using an exemplary embodiment which is illustrated in the drawing. This shows the diagram of a node computer that is loosely coupled to a communication medium.

0021A number of node computers 2, 2ʹ, 2ʺ are connected to a communication medium 1, only one computer being shown in more detail. For example, the bus line can connect several computers within a building. In general, local networks are systems with high data transmission speeds (0.1 to 100 Mbps, short distances (100m to 50km) and low error rates (10⁻⁹ to 10⁻¹¹). The individual node computers can be accessed, for example, in time division multiple access (TDMA), in the token process or in a CSMA (carrier sense multiple access) process.

0022A node computer 2 consists, for example, of a central unit 3, which is connected via an internal bus 4 to a memory 5, input / output subsystems 6, a communication unit 7 and a synchronization unit 8. The output of a local clock 9 is connected via a line 10 directly to the interrupt input of the synchronization unit, the synchronized local time pulses being forwarded via a signal line 11 for the global time to the subsystems 6 and, for example, the interrupt input of the central unit 3. A further signal line 12 is provided for the direct notification of the time of reception of a message from the communication unit 7 to the synchronization unit 8.

0023However, it should be noted at this point that the synchronization unit 8 does not necessarily have to represent its own physical structure, but can be contained in the central unit or in the communication unit.

0024The communication unit 7 contains a FIFO memory 13. Such a "first-in, first-out" memory has the property that the data are read out in the same order in which they were written. Furthermore, a DMA unit 14 is included in the communication unit, which enables direct memory access.

0025If the node computer 2 is to send a message to a further node computer which is also loosely connected to the communication medium 1, a command is transmitted from the central unit 3 to the communication unit 7 via the internal bus 4, which command contains the actual send command and information about information contained in the memory. includes information to be sent.

0026The communication unit then uses direct memory access 13 to take the beginning of the message to be sent from memory 5 and stores this part of the message in FIFO memory 13. The communication unit 7 now checks its access authorization to the medium 1. As soon as this is available, the message, that is to say the beginning thereof, is sent out of the FIFO memory 13. The communication unit 7 is set up in such a way that, at a certain degree of emptying of the FIFO memory 13, it initiates the transfer of further message parts from the memory 5 into the FIFO memory 13.

0027After the start of the transmission of the message, a time stamp is created by the synchronization unit 8 via a corresponding command and embedded in the message as the FIFO memory 13 is filled up. In order to keep additional inaccuracies from internal clocks low, the time stamp should be as close to the end of the message as possible.

0028It is furthermore expedient that the time stamp may only be at a point in the message which is further away from the beginning of the message than the storage capacity of the FIFO memory 13. Otherwise, the time stamp would be stored with the first message part in the FIFO memory 13 before the start of transmission and would lie there indefinitely before being sent. If, for example, the FIFO memory 13 has a capacity of 128 bytes, care must be taken by appropriate programming to ensure that the time stamp is displayed in the message at the earliest from the 129 bytes of the message length.