Adding fault tolerance to a flexible real-time Ethernet network for embedded systems

Abstract

[cat]Un sistema encastat distribuït consisteix en un conjunt de nodes computacionals que cooperen per aconseguir un objectiu comú dins d’un sistema físic més gran. En les societats modernes podem trobar aquests sistemes per tots costats: en avions, cotxes i trens; en fàbriques, plantes químiques i centrals elèctriques; en satèl·lits artificials i sondes espacials; en aparells domèstics i en equips mèdics; i en molts altres sistemes. Sigui on sigui que els trobem, i independentment del que facin, els nodes d’un sistema encastat distribuït han de col·laborar per aconseguir un objectiu comú. Així per exemple els nodes d’un cotxe col·laboren per assegurar un viatge segur i agradable i els nodes en una fàbrica col·laboren per fabricar un producte. Com la col·laboració requereix de comunicació, els sistemes encastats distribuïts necessiten un subsistema de comunicació o xarxa que permeti l’intercanvi de missatges entre nodes. Aquests missatges han de ser intercanviats a temps ja que els sistemes encastats distribuïts interactuen amb entorns físics que avancen de forma inexorable i no esperen. Això significa que la xarxa ha de donar suport a la comunicació en temps real; és a dir, els missatges han de ser intercanviats abans d’instants de temps preestablerts, anomenats terminis temporals. Per a aquest tipus de comunicació, Ethernet ha estat tradicionalment inadequat ja que no podia proporcionar garanties de temps real. Però això ha canviat gràcies a nous protocols basats en Ethernet. Entre ells destaquen per la seva flexibilitat els que es basen en el paradigma de comunicació FTT (flexible time-triggered). La propietat clau de FTT és que pot garantir el lliurament a temps de missatges fins i tot si els paràmetres de temps real canvien durant l’execució del sistema. Mentre s’executa el sistema, tant els terminis temporals com els temps de transmissió, els períodes i els temps mínims entre arribades dels missatges poden canviar. Malgrat els seus avantatges, les versions de FTT actuals per Ethernet només satisfan els requisits de temps real si no hi ha fallades ni avaries de components. Desafortunadament això fa que siguin inadequades per a moltes aplicacions en les quals s’usen sistemes encastats distribuïts, com per exemple els subsistemes crítics d’avions i automòbils. Al cap i a la fi, en la realitat, fallades sí que ocorren i cal tractar-los perquè el sistema sigui fiable. En aquesta tesi anem a veure que FTT basat en Ethernet pot ser modificat per ser tolerant a fallades i que això es pot fer sense sacrificar les garanties de temps real o la flexibilitat que el paradigma FTT proporciona. Això obre la possibilitat d’usar Ethernet, amb el seu baix cost i alt ample de banda, en futurs sistemes encastats distribuïts que han de ser tolerants a fallades, flexibles i alhora de temps real. Establim la veracitat de que FTT sobre Ethernet pot fer-se tolerant a fallades (preservant la seva flexibilitat i garanties de temps real) mitjançant un nou subsistema de comunicació que ho demostra. En particular, en aquesta tesi dissenyam tal subsistema de comunicació i demostram la seva factibilitat mitjançant una sèrie de prototips de prova de concepte. El nou subsistema de comunicació, denominat Flexible Time-Triggered Repli-cated Star for Ethernet (FTTRS), es basa en Hard Real-Time Ethernet Switching (HaRTES), que és una implementació en Ethernet commutat del paradigma FTT. En concret, FTTRS tracta les vulnerabilitats d’HaRTES: elimina els punts únics d’avaria d’HaRTES mitjançant la replicació de components crítics, garanteix el determinisme de rèplica d’aquests components replicats, restringeix la semàntica d’avaries dels components segons sigui necessari, i fa que els intercanvis de missatge siguin capaços de tolerar fallades transitòries de canal, mantenint la flexibilitat i les garanties en temps real del paradigma FTT.

[spa]Un sistema empotrado distribuido consiste en un conjunto de nodos computacionales que cooperan para alcanzar un objetivo común dentro de un sistema físico más grande. En las sociedades modernas podemos encontrar estos sistemas por todos lados: en aviones, coches y trenes; en fábricas, plantas químicas y centrales eléctricas; en satélites artificiales y sondas espaciales; en aparatos domésticos y en equipos médicos; y en muchos otros sistemas. Sea donde sea que los encontremos, e independientemente de lo que hagan, los nodos de un sistema empotrado distribuido deben colaborar para alcanzar un objetivo común. Así por ejemplo los nodos de un coche colaboran para asegurar un viaje seguro y agradable y los nodos en una fábrica colaboran para fabricar un producto. Como la colaboración requiere de comunicación, los sistemas empotrados distribuidos necesitan un subsistema de comunicación o red que permita el intercambio de mensajes entre nodos. Estos mensajes deben ser intercambiados a tiempo ya que los sistemas empotrados distribuidos interactúan con entornos físicos que avanzan de forma inexorable y no esperan. Eso significa que la red debe dar soporte a la comunicación en tiempo real; es decir, los mensajes deben ser intercambiados antes de instantes de tiempo preestablecidos, llamados plazos temporales. Para este tipo de comunicación, Ethernet ha sido tradicionalmente inadecuado ya que no podía proporcionar garantías de tiempo real. Pero esto ha cambiado gracias a nuevos protocols basados en Ethernet. Entre ellos destacan por su flexibilidad los que se basan en el paradigma de comunicación FTT (flexible time-triggered). La propiedad clave de FTT es que puede garantizar la entrega a tiempo de mensajes incluso si los parámetros de tiempo real cambian durante la ejecución del sistema. Mientras se ejecuta el sistema, tanto los plazos temporales como los tiempos de transmisión, los periodos y los tiempos mínimos entre llegadas de los mensajes pueden cambiar. A pesar de sus ventajas, las versiones de FTT actuales para Ethernet sólo satisfacen los requisitos de tiempo real si no hay fallos ni averías de componentes. Desafortunadamente esto hace que sean inadecuadas para muchas aplicaciones en las cuales se usan sistemas empotrados distribuidos, como por ejemplo los subsistemas críticos de aviones y automóviles. Al fin y al cabo, en la realidad, fallos sí que ocurren y hay que tratarlos para que el sistema sea fiable. En esta tesis demostramos que FTT basado en Ethernet puede ser modificado para ser tolerante a fallos y que esto se puede hacer sin sacrificar las garantías de tiempo real o la flexibilidad que el paradigma FTT proporciona. Esto abre la posibilidad de usar Ethernet, con su bajo coste y alto ancho de banda, en futuros sistemas empotrados distribuidos que deben ser tolerantes a fallos, flexibles y a la vez de tiempo real. Establecemos la veracidad de que FTT sobre Ethernet puede hacerse tolerante a fallos (preservando su flexibilidad y garantías de tiempo real) mediante un novedoso subsistema de comunicación que lo demuestra. En particular, diseñamos tal subsistema de comunicación y demostramos su factibilidad mediante una serie de prototipos de prueba de concepto. El nuevo subsistema de comunicación, denominado Flexible Time-Triggered Replicated Star for Ethernet (FTTRS), se basa en Hard Real-Time Ethernet Switching (HaRTES), que es una implementación en Ethernet conmutado del paradigma FTT. En concreto, FTTRS trata las vulnerabilidades de HaRTES: elimina los puntos únicos de avería de HaRTES mediante la replicación de componentes críticos, garantiza el determinismo de réplica de estos componentes replicados, restringe la semántica de averías de los componentes según sea necesario, y hace que los intercambios de mensaje sean capaces de tolerar fallos transitorios de canal, todo ello manteniendo la flexibilidad y las garantías de tiempo real del paradigma FTT.

[eng]Distributed embedded systems consist of a set of computing nodes that cooperate to achieve a common goal within a larger physical system. In modern societies they are ubiquitous. Among other places we find them in aircraft, cars, trains, factories, chemical plants, power plants, human-made satellites, space probes, household appliances, and medical equipment. Wherever we find a distributed embedded system, and whatever it does, its nodes must collaborate to achieve a common goal. For example, the nodes in a car collaborate to ensure a safe and comfortable journey and the nodes in a factory collaborate to manufacture a given product. Collaboration calls for a means of communication: a communication subsystem or network that allows nodes to exchange messages among themselves. These messages must be exchanged on time. Distributed embedded systems interact with physical environments that progress inexorably and do not wait. This means that the network must support \emph{real-time} communication; that is, messages must be exchanged before specified instants of time, called deadlines. For this task, Ethernet has traditionally been unsuitable. It could not provide real-time guarantees. But this has changed thanks to the development of new Ethernet-based protocols. Among them, the ones based on the Flexible Time-Triggered (FTT) communication paradigm stand out because of their flexibility: they can guarantee the timely delivery of messages even if the real-time parameters of messages change at runtime. For instance, deadlines, transmission times, periods, and minimum interarrival times of messages are all allowed to change at runtime. Despite their advantages, current Ethernet versions of FTT can only meet real-time requirements in the absence of faults. But this is unacceptable in many of the domains where distributed embedded systems are deployed, such as critical subsystems in avionics or cars. Faults do occur and they have to be dealt with for the system to be reliable. In this dissertation we deal with such faults. We show that FTT, using Ethernet as the underlying technology, can be made fault tolerant, and that this can be done without sacrificing the real-time guarantees or flexibility that the FTT paradigm provides. Why is this important? Because it opens up the possibility of using high-bandwidth and inexpensive Ethernet in future distributed embedded systems that must simultaneously be fault-tolerant, flexible, and realtime. As to how we show that FTT over Ethernet can be made fault tolerant while preserving its flexibility and hard real-time guarantees, we present a novel communication subsystem that proves the point. In particular, we design such a communication subsystem and show its feasibility by means of a series of proof-of-concept prototypes. The novel communication subsystem, called \emph{Flexible Time-Triggered Replicated Star for Ethernet} (FTTRS), is based on \emph{Hard Real-Time Ethernet Switching} (HaRTES), which is a switched Ethernet implementation of the FTT paradigm. Specifically, FTTRS addresses the vulnerabilities of HaRTES: it eliminates the single points of failure of HaRTES by replicating critical components, it ensures the replica determinism of these replicated components, it restricts the failure semantics of the components as necessary, and it makes message exchanges capable of tolerating transient channel faults, all the while maintaining the flexibility and real-time guarantees of the FTT paradigm.