Introduction toEmbedded SystemsLecture X: Networking in Embedded Systems: Control Area Network, FlexRay, IEEE 1588Edward A. Lee & Sanjit A. SeshiaUC Berkeley2011Adapted from original slides by Marco Di Natale, Wenchao Li, and John EidsonEECS 149, UC Berkeley: 2Today’s Cars• X-by-wire vs. conventional mechanical and hydraulic systems• Basics: power locks/door/window/engine start• Sensors/Actuators: tire, airbags, powertrain, video, radar, and photoelectrics, etc.• Control/Safety: ABS, EBD/CBC, EBA/BAS/BA, ASR/TCS/TRC, ESP/DSC/VSC, etc.• Entertainment System• Auto-Park• DARPA’s Urban ChallengeImage: General MotorsEECS 149, UC Berkeley: 3Today’s Cars• Number of Electronic Control Units (ECUs) in a car: – Low end: 30 ~ 50 (doors, roof, etc)– High end: 70~100 • Lines of code: ~100 million (Future: 200~300 million)• The radio and navigation system in the current S-class Mercedes-Benz requires over 20 million lines of code alone and that the car contains nearly as many ECUs as the new Airbus A380 (excluding the plane’s in-flight entertainment system). • Cost of electronics/software: 35% ~ 40% in premium cars (for hybrid it is even higher!)• How can we ensure timely and reliable communication via the “wires”?[http://www.spectrum.ieee.org/feb09/7649]EECS 149, UC Berkeley: 4CAN busCAN = Controller Area Network– Publicly available communications standard [1] http://www.semiconductors.bosch.de/pdf/can2spec.pdfSerial data bus developed by Bosch in the 80s– Support for broadcast and multicast comm– Low cost– Deterministic resolution of the contention– Priority-based arbitration– Timing analysis for real-time messages– Automotive standard but used also in automation, factory control, avionics and medical equipment– Simple, 2 differential (copper) wire connection– Speed of up to 1Mb/s– Error detection and signallingEECS 149, UC Berkeley: 5CAN-based systemPeripheral HWSystem SWAppl.SWDevice driversRTOSMiddlewareApplicationFirmware(MAC layer implementation)TX buffers(TXobjects)typically 1 to 32RX buffers(RXobjects)typically 1 to 32EECS 149, UC Berkeley: 6CAN bus: Data FrameEECS 149, UC Berkeley: 7Priority-Based ArbitrationMain points:All nodes are synchronized on the SOF bitThe bus behaves as a wired-ANDAn example …00101011010 01111010010 00111110110Id = 0x15a Id = 0x3d2 Id = 0x1f60000sof0010011011 010110101 0EECS 149, UC Berkeley: 8Priority-Based ArbitrationA sender must wait longer than that maximum propagation latency before sending the next bit.Why?EECS 149, UC Berkeley: 9The type of arbitration implies that the bit time is at least twice the propagation latency on the busThis defines a relation between the maximum bus length and the transmission speed. The available values are Bit rate Bus length1 Mbit/s 25 m800 kbit/s 50 m500 kbit/s 100 m250 kbit/s 250 m125 kbit/s 500 m50 kbit/s 1000 m20 kbit/s 2500 m10 kbit/s 5000 mnode Anode Bnode A starts transmitting a bitnode B overwritesnode A reads the effect of changes by BMinimum bit timetimePriority-Based ArbitrationEECS 149, UC Berkeley: 10Assumptions that Impact TimingTiming Analysis (and inversions) – Ideal behaviorAssumption 1: nodes are not synchronized, but clocks evolve at the same rateAssumption 2: messages are always transmitted by nodes based on their priority (ID) – ideal priority queue of messagesAssumption 3: periodic messages, but no assumption on the message phasesEECS 149, UC Berkeley: 11Timing based on Priorities – Ideal Behaviorid = 0x103id = 0x261id = 0x304id = 0x122id = 0x141id = 0x111id = 0x202id = 0x103id = 0x111id = 0x141id = 0x202id = 0x122id = 0x261id = 0x304EECS 149, UC Berkeley: 12Timing Analysis --- Worst-Case Reponse Timeid = 0x103id = 0x261id = 0x304id = 0x122id = 0x141id = 0x111id = 0x202Critical instant theorem: for a preemptive priority based scheduled resource, the worst case response time of an object occurs when it is released together with all other higher priority objects and they are released with their highest rateEECS 149, UC Berkeley: 13id = 0x103id = 0x261id = 0x304id = 0x122id = 0x141id = 0x111id = 0x202id = 0x261spend time in local queue (higher priority messages are transmitted with max rate)Iiid = 0x103id = 0x111Message transmission timeCiMiMessage Mi starts its transmissionid = 0x122id = 0x141id = 0x202Timing Analysis --- Worst-Case Reponse TimeEECS 149, UC Berkeley: 14Timing Analysis under Ideal ConditionsTiming Analysis – worst case latency – Ideal behavior [2]The transmission of a message cannot be preemptedid = 0x261qi = time spent in local queue Iiid = 0x103id = 0x111Message transmission timeCiMiMessage Mi starts its transmissionid = 0x304Biinterference from higher priority messagesblocking from lower priority messagesiiiIBq iiiCqw )(,ihpjjiiIIjjijiCTqI,jihpjjiiiCTqBq)(Fixed point formula: solved iteratively by setting qi(0)=0 until the minimum solution is foundEECS 149, UC Berkeley: 15CAN busIn reality, this analysis can give optimistic results!A number of issues need to be considered …–…– Availability of TxObjects at the adapter– Finite copy time between the queue and the TxObjectsAdapters typically only have a limited number of TXObjects or RxObjects availableEECS 149, UC Berkeley: 16CAN busA number of issues need to be considered …–…– Availability of TxObjects at the adapter• Let’s check the controller specifications!EECS 149, UC Berkeley: 17CAN busWhat happens if only one TxObject is available?– Assuming preempatbility of TxObjectid = 0x103id = 0x261id = 0x304id = 0x122 id = 0x2a1id = 0x2d2id = 0x261id = 0x341id = 0x122id = 0x103preemptionid = 0x261Priority inversion for 0x261 AFTER its queuing timeEECS 149, UC Berkeley: 18Violation of Priority-based Queuing1.857316 1 110 Rx d 8 00 09 BF 00 00 06 00 001.857548 1 120 Rx d 8 03 85 23 83 06 EA 03 851.857696 1 170 Rx d 3 01 00 861.858256 1 124 Rx d 5 00 03 83 03 85……3.877361 1 110 Rx d 8 00 09 C4 00 00 06 00 003.877597 1 120 Rx d 8 03 83 23 81 06 EA 03 823.877819 1 308 Rx d 7 00 80 2A 00 00 00 AD3.878309 1 124 Rx d 5 00 03 81 03 83......4.017366 1 110 Rx d 8 00 09 C4 00 00 06 00 004.017600 1 120 Rx d 8 03 85 23 80 06 EA 03 814.017768 1 348 Rx d 4 08 48 43 FF4.018312 1 124 Rx d 5 00 03