Transcription
Ensuring Reliable NetworksAn Introduction toTTEthernetTU Vienna, Apr/26, 2013Guest Lecture in Deterministic Networking (DetNet)Wilfried Steiner, Corporate Copyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 1
What They Have in Common Boeing 787NASA OrionEnsuring Reliable NetworksReliable Networks from TTTechAudi A8www.tttech.comAirbus A380Copyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 2
Future Markets for Real-TimeFault-Tolerant CommunicationRequirements on a communicationinfrastructure for future markets Real-time requirements Fault tolerance requirements Low cost Low power Low weight Low size Consumer acceptancewww.tttech.comEnsuring Reliable NetworksA system failure potentially leads to Loss of life Loss of economic assets Loss of research results Loss of power Loss of quality of service (QoS) Any bad thing we can think of Copyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 3
Closed and Open WorldCommunicationClosed World CommunicationPerformance guarantees:real-time, dependability, safetyStandards:ARINC 664, ARINC 429, TTP,MOST, FlexRay, CAN, LIN, Applications:Flight control, powertrain, chassis,passive and active safety, .Validation & verification:Certification, formal analysis, .High costEnsuring Reliable NetworksOpen World CommunicationNo performance guarantees:best effortsStandards:Ethernet, TCP/IP, UDP, FTP,Telnet, SSH, .Applications:Multi-media, audio, video, phones,PDAs, internet, web, Validation & verification:No certification, test, simulation, .Low costWe see a market requirement to use the same physicalnetwork for data flows from both worlds.www.tttech.comCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 4
Mixed-Criticality SystemsOpen NetworksWindowsPCWindowsPCEnsuring Reliable NetworksHow to share systemresourcesand partition critical andnon-critical tandard IEEE802.3Ethernet LANF2 F4F1 F2 F4Time and spacepartitioned OSwww.tttech.comF1 F2 F3 F4F1 F2 F3 F4Time and spacepartitioned OSTime and spacepartitioned OSTime and spacepartitioned OSSafety-, Time- or Mission-Critical SystemCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 5
Traffic ClassesEnsuring Reliable NetworksApplicationTTEthernet provides several traffic classes inparallel: time-triggered, rate-constrained, andbest-effortLayer3-7Time-Triggered: dispatch messages according apredefined communication scheduleRate-Constrained: enforce minimum durationbetween two frames of the same streamBest-Effort: standard Ethernet communicationparadigm – no temporal guarantees are givenTime-Triggered ExtensionEthernet IEEE 802.3TTEthernet40 msecTT1TT2RCRC30 msecBE40 msecTT1BERCTT230 msecBETT1RC40 msecBERCTT2TT1BE30 msecBERC30 msecRCTT1TIMELongest Communication Cycle in this Example: LCM(30,40) 120msecwww.tttech.comCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 6
TTEthernet, a CommunicationInfrastructureTTEEnsuring Reliable NetworksHighlight: Flexible Integrationand COTS Backward CompatibleTTEFXETHTTETTECANFXCANFXCANFXCAN 1 Mbit/secFX 10 Mbit/secTTPFXTTETTPTTPTTPTTE1 Gbit/sec100 Mbit/secTTETTEwww.tttech.comTTETTECopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 7
The Motivation for EthernetEnsuring Reliable Networks Ethernet hardware is low cost. Ethernet is a well-established open-world standard and veryscaleable. The OSI reference model gives a well-structured classification ofconcepts that can be built on top of Ethernet. Existing tools can be leveraged as cost-efficient diagnosis tools. As all messages in TTEthernet are standard Ethernet compliant,existing tools can be leveraged for time-triggered messages as well. Standard web servers can be leveraged for maintenance andconfiguration. Engineers learn about Ethernet at school.Ethernet compatibility enables the usage of technologythat is established, tested, and verified.www.tttech.comCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 8
OutlineEnsuring Reliable NetworksPrerequisites for Safe and Deterministic Communication Asynchronous vs. Synchronous Communication Clock Synchronization and Fault-Tolerant Clock Synchronization Formal Verification ActivitiesUtilization of Safe and Deterministic Communication Time-Triggered Communication Constraints in Multi-Hop Networks Integrated communication for mixed-criticality systems Combined Time-Triggered / Rate-Constrained / Best-Effort Communication Tooling OverviewSummarywww.tttech.comCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 9
OutlineEnsuring Reliable NetworksPrerequisites for Safe and Deterministic Communication Asynchronous vs. Synchronous Communication Clock Synchronization and Fault-Tolerant Clock Synchronization Formal Verification ActivitiesUtilization of Safe and Deterministic Communication Time-Triggered Communication Constraints in Multi-Hop Networks Integrated communication for mixed-criticality systems Combined Time-Triggered / Rate-Constrained / Best-Effort Communication Tooling OverviewSummarywww.tttech.comCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 10
Ethernet AsynchronousCommunicationNICEnsuring Reliable ronous Communication Transmission Points in Time are not predictableSWITCHNIC Transmission Latency and Jitter accumulate Number of Hops has a significant impact Usually solved by High Wire-Speeds & Low Utilizationand/or Priorities Problem of Indeterminism’’ remainswww.tttech.comCopyright TTTech Computertechnik AG. All rights reserved.NICNIC5/18/2013 / Page 11
Adding Clock Synchronizationto EthernetETTEnsuring Reliable NetworksETTETTEthETTTTETTEETTETTETTIN 1Time MasterEth1588Enabler for Synchronous Operation: 15Synchronized Global TimeCommunication Schedulewww.tttech.com88EthCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 12
Quality of Clock Synchronization: PrecisionEnsuring Reliable NetworksIn an ensemble of clocks, the precision is defined as themaximum distance between any two synchronized nonfaulty clocks at any point in real time.Late Clockwww.tttech.comPerfect ClockPage 13Early Clock
Time-Triggered OperationEnsuring Reliable Networks Time-Division Multiple-Access Communication Composable network Complexity reduction and faster integration Fault tolerant communication systemNode Asendt1Node Bt2receivet1Node receivet3receivet2sendt3Copyright TTTech Computertechnik AG. All rights reserved.time5/18/2013 / Page 14
Synchronous Communication (TT)NICEnsuring Reliable ous CommunicationSWITCHNICXExactly one order of messages Mi(in contrast to PERM(Mi) in async. comm)www.tttech.comCopyright TTTech Computertechnik AG. All rights reserved.NICNIC5/18/2013 / Page 15
Example: 1,000 Frames(Industrial-Sized)2Dataflow Links are enumeratedon the x-axis12Ensuring Reliable Networks15346 XTime-Triggered Onlywww.tttech.comCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 16
Single-MasterSynchronizationEnsuring Reliable NetworksEthIN 1IN 1IN 1IN 1IN 1IN 1IN 1IN 1EthTime MasterIN1 1588constant and/or dynamic1588Ethwww.tttech.comCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 17
Transparent Clock and Permanence302Ensuring Reliable NetworksdispatchSM 10SM 2SM 3302ES 102send5SC 1306dispatch0SM 4306ES 106send5SC 2302sendSwitch 201receiveSM 5455302sendSwitch 202receiveSwitch 203302CM 170SM 645302receive1030230680max transmission delay ( 120)permanence delay (120 – 10 110)max transmission delay ( 120)permanence delay (120 – 80 40)302Switch 203 permanence0510 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 yright TTTech Computertechnik AG. All rights reserved.3065/18/2013 / Page 18
Synchronization ServicesEnsuring Reliable NetworksMessage ExchangeMessage ExchangerfectClockFast ClockPeComputer TimeClock Synchronization ServiceClock Synchronization Service isexecuted during normal operation modeto keep the local clocks synchronized toeach other.Startup/Restart Service is executed toreach an initial synchronization of thelocal clocks in the system.Integration/Reintegration Service isused for components to join an alreadysynchronized system.Clique Detection Services are used todetect loss of synchronization andestablishment of disjoint sets ofsynchronized components.Slow ClockR.intR.intReal TimeStartup/Restart Servicewww.tttech.comCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 19
Single-Master ClockSynchronizationETTEnsuring Reliable NetworksETTETTEthETTTTETTEETTETTETTIN 1Time MasterEth1588Enabler for Synchronous Comm.: 15Synchronized Global TimeCommunication Schedulewww.tttech.com88EthCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 20
Fault-Tolerant ClockSynchronizationEnsuring Reliable NetworksETTTime MasterETTETTTTETTEIN 1EthIN 1INE 1TTIN 1TTETime MasterTTEETTIN 1ETT IN 1Time MasterETTEth15Fault-tolerant synchronization servicesare needed for establishing a safeglobal time basewww.tttech.com881588EthCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 21
Step 1: ALL Synchronization Master DispatchIN Frames at the SAME Scheduled Point in TimeCompressionMasterEnsuring Reliable NetworksIN 5SynchronizationMaster 5IN 1SynchronizationMaster 1IN 2IN 3SynchronizationMaster 2SynchronizationMaster 3PrecisionSM1t 0www.tttech.com.SM4SM5SM1SynchronizationMaster 4Acceptance Window(of SM 2/5)SM2DispatchPermanenceIN 4SM3CMSM2SM4SM5SM3t 1,t 2t 4,t 5CMReference PointCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 22
Step 2: Compression Master Dispatch CompressedIN Frame back to Synchronization Masters/ClientsCompressionMasterEnsuring Reliable NetworksIN CSynchronizationMaster 5SynchronizationMaster 1SynchronizationMaster 2SynchronizationMaster 3PrecisionAcceptance Window(of SM 2/5)SM2DispatchPermanenceSM1t 0www.tttech.com.SM4SM5SM1SynchronizationMaster 4SM3CMSM2SM4SM5SM3t 1,t 2t 4,t 5CMReference PointCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 23
TTEthernet ClockSynchronization iEnsuring Reliable NetworksAlgorithm Specificationwww.tttech.comCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 24
TTEthernetClock Synchronization iiwww.tttech.comEnsuring Reliable NetworksCopyright TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 25
Other Synchronization SafetyMechanismsEnsuring Reliable NetworksControlled and autonomous late integration Synchronous operation will be reached when a sufficient number of ECUsis powered-up. Remaining ECUs may power up at arbitrary times and will join synchronousoperation.Controlled and autonomous re-integration ECUs that drop out of the synchronous operation will autonomously reintegrateafter recovery.Controlled and autonomous system-wide reset In the extremely unlikely event that the synchronous time-base is lost, thesystem is configurable to automatically execute a controlled system-widerestart.Synchronization robustness against EMI Synchronization is configurable to continue operation without receivingsynchronization messages for a parameterized number of t TTTech Computertechnik AG. All rights reserved.5/18/2013 / Page 26
Formal Verification ActivitiesEnsuring Reliable NetworksTTEthernet Executable Formal Specification Using symbolic and bounded model checkers sal-smc and sal-bmcFocus on Interoperation of Synchronization Services (Startup, Restart, CliqueDetection, Clique Resolution, abstract Clock Synchronization)Verification of Lower-Level Synchronization Functions Permanence Function (sal-inf-bmc k-induction)Compression Function (sal-inf-bmc k-induction)Formal Verification of Clock Synchronization Algorithm First time by means of Model Checking (sal-inf-bmc k-induction)Re-use of the Formal Models to prove: Layered clock-rate correction algorithm (sal-inf-bmc k-induction)Layered clock-diagnosis algorithm (sal-inf-bmc k-induction)Verification and minor corrections of the “Sparse Timebase” Concept Distributed computations withoutexplicit coordination (PVS)Work has mostly been done in the contextof the Marie Curie CoMMiCS projectFP7 (FP7/2007-2013) project no. 236701www.tttech.comCopyright TTTech Computertechnik AG. All rights reserved.CoMMiCS5/18/2013 / Page 27
ReferencesEnsuring Reliable NetworksB. Dutertre, A. Easwaran, B. Hall, W. Steiner, “Model-based analysis of Timed-Triggered Ethernet,”Proceedings of the 31st IEEE/AIAA Digital Avionics Systems Conference (DASC 2012), IEEE 2012,Recipient of “Best in Session” and “Best in Track” awardsW. Steiner, G. Bauer, B. Hall and M. Paulitsch, “Time-Triggered Ethernet: TTEthernet,”In Time-Triggered Communication, R. Obermaisser, editor, CRC Press, 2011W. Steiner and J. Rushby, “TTA and PALS: Formally Verified Design Patterns for Distributed CyberPhysical Systems,” Proceedings of the 30th IEEE/AIAA Digital Avionics Systems Conference (DASC2011), IEEE 2011, Recipient of “Best in Session” and “Best in Track” awardsW. Steiner and B. Dutertre, “Layered Diagnosis and Clock-Rate Correction for the TTEthernet ClockSynchronization Protocol, ” Proceedings of the 17th IEEE Pacific Rim International Symposium onDependable Computing (PRDC 2011), IEEE Computer Society, 2011W. Steiner and B. Dutertre, “Automated Formal Verification of the TTEthernet Synchronization Quality,”Proceedings of the 3rd NASA Formal Methods Symposium (NFM 2011), Springer Lect
www.tttech.com Ensuring Reliable Networks Page 13 Quality of Clock Synchronization: Precision In an ensemble of clocks, the precision is defined as the
