Fault-tolerant clock synchronization for embedded distributed multi-cluster systems

Abstract

Embedded computer control systems become more and more common for different functional tasks in cars, airplanes, and factory automation systems. In addition, systems for different functional tasks become interconnected and system functions more integrated. As a consequence, these systems become larger and more complex. Multi-cluster systems are a way to structure large distributed systems to manage complexity and overcome communication bandwidth limitations. A cluster is a system where nodes are tightly coupled and are connected via direct communication links. Nodes of different clusters are loosely coupled and are connected via special nodes that connect two clusters, so-called gateway nodes. In distributed control systems, a common notion of time of all nodes is fundamental for control, because it allows a consistent system view of dynamic environments and supports meaningful exchange of time-related data between clusters. This thesis presents a clock synchronization algorithm for multi-cluster systems that is especially suited for embedded control systems. The requirements of embedded systems are addressed by supporting increased dependability necessities and decreased computing resources of embedded systems compared to desktop computer systems. Furthermore, the algorithm assures the composability of the cluster time bases, that is the precision of clusters is not worsened when several clusters are connected and synchronized. By addressing systematic and stochastic errors of cluster times differently, the influence of systematic errors is eliminated and the quality of synchronization only depends on stochastic errors. Since systematic errors of cluster times are usually an order of magnitude larger than stochastic errors for typical real-time embedded control systems, the presented algorithm achieves a significant improvement to known synchronization algorithms. An implementation of the proposed clock synchronization algorithm on top of the Time-Triggered Architecture and experiments show that clock synchronization of nodes of multi-cluster systems can be achieved with an accuracy of less than one microsecond.

Steuerungssysteme werden immer verbreiteter fuer verschiedene Aufgaben in Autos, Flugzeugen oder Automatisierungssystemen eingesetzt. Der Trend geht dahin, die unterschiedlichen Systeme zu vernetzen und mehr Funktionen zu integrieren. Als Konsequenz werden solche Systeme aufwendiger und komplizierter. Multi-Cluster-Systeme sind ein Ansatz zur Strukturierung von grossen verteilten Systemen, um die Komplexitaet beherrschen und die Bandbreitenlimitierung bewaeltigen zu koennen. Ein Cluster ist ein System, dessen Rechenknoten eng gekoppelt und direkt kommunizieren koennen. Rechenknoten von verschiedenen Clustern sind lose gekoppelt und koennen nur ueber sogenannte Gateways miteinander kommunizieren. Gateways sind spezielle Rechenknoten, die zwei Kommunikationssysteme miteinander verbinden. Ein gemeinsamer Zeitbegriff ist fuer die koordinierte Steuerung in verteilten Steuerungssystemen notwendig, weil ein gemeinsamer Zeitbegriff eine konsistente Systemsicht erlaubt und den sinnvollen Datenaustausch von zeitabhaengigen Variablen ermoeglicht. Diese Arbeit praesentiert einen Uhrensynchronisationsalgorithmus fuer Multi-Cluster-Systeme, der fuer den Einsatz in eingebetteten Systemen geeignet ist. Die Anforderungen an eingebettete Systeme sind vor allem hohe Zuverlaessigkeit und geringer Ressourcen-Gebrauch im Vergleich zu Desktop-Computersystemen. Der vorgestellte Algorithmus erreicht die Integration von Zeitbasen von Clustern, wobei die Praezision von Zeitbasen der Cluster durch die Integration von mehreren Clustern nicht verschlechtert wird. Systematische Uhrenfehler beeinflussen die Synchronisationsqualitaet nicht, weil systematische und stochastische Uhrenfehler unterschiedlich behandelt werden. Da systematische Uhrenfehler meist eine Zehnerpotenz groesser als stochastische sind, erreicht der Algorithmus eine signifikante Verbesserung in der Synchronisationsqualitaet verglichen mit bekannten Uhrensynchronisationsalgorithmen. Eine Implementierung des Uhrensynchronisationsalgorithmus unter Verwendung der Time-Triggered Architecture sowie Experimente zeigen, dass Uhren von Rechenknoten verschiedener Cluster mit einer Praezisionsgenauigkeit, die kleiner als eine Mikrosekunde ist, erreicht werden kann.