A Transactional TCP/IP Stack Suitable for WCEC Analysis

• Introduction
  • Platform is a highly resource-constrained embedded system with a persistent memory device and hardware that implements a power-failure interrupt (PFI). The system is intermittently powered by some form of locally generated renewable energy, no battery is present because of the environmental hazards. Capacitors are used instead.
  • On these devices, the system must still achieve guaranteed forward-progress. It must never waste any energy by starting some operation which can then not be completed because power runs out before a new stable state is reached.
  • To achieve this, we use worst-case energy-consumption (WCEC) analysis of the software on the device. It is your goal to develop a transactional networking stack (TCP/IP) to which WCEC analysis can be applied.
    • The device must only turn itself off (persisting the applicaton, OS, and network stack state to non-volatile memory) when it has reached a stable state in which it can remain indefinately.
    • The stack has a set of operations (e.g., advance_tcp_window()) that bring the device from one stable state to another. All these operations must have a WCEC that can be statically analyzed in future work.
  • Future work will attempt to prove properties like liveness and forward progress based on your implementation (envisioned using Petri nets). Your stack should be developed with this in mind.
• Background
  • You should already be familiar with low-level programming (e.g., from https://sys.cs.fau.de/lehre/ws23/bs)
  • “Whole-System Worst-Case Energy-Consumption Analysis for Energy-Constrained Real-Time Systems” https://drops.dagstuhl.de/storage/00lipics/lipics-vol106-ecrts2018/LIPIcs.ECRTS.2018.24/LIPIcs.ECRTS.2018.24.pdf
    • https://en.wikipedia.org/wiki/Worst-case_execution_time (WCEC is has similar restrictions.)
  • https://sys.cs.fau.de/research/respect
  • https://www.nt.uni-saarland.de/publications/vogelgesang2024towards/
  • We assume our system has a PFI (interrupt) to inform us about an imminent power failure: https://www4.cs.fau.de/Publications/2021/eichler_21_hicss.pdf
  • Wikipedia > A Simplified TCP State Diagram
  • Applications
    • BATS: https://sys.cs.fau.de/research/bats
    • https://www.usenix.org/system/files/nsdi22-paper-geissdoerfer.pdf
• Related Work
  • tpIP: A Time-Predictable TCP/IP Stack for Cyber-Physical Systems (https://ieeexplore.ieee.org/document/8421149)
    • Has a great overview of related work and design considerations.
    • We focus on WCEC analysis, not WCET analysis.
      • When does WCEC differ from WCET for a network stack?
    • They make sure every function by itself has a WCEC, but our goal is more ambitious. We want a guarantee for forward-progress iff there is limited packet loss.
      • Or are these two requirements equivalent?
    • Is polling really necessary or can we use blocking sockets?
      • Blocking allows the CPU to sleep, thus we can save energy even thought we may not be able to save time.
    • They implement it for SLIP plus a serial device. We want to impl. it for Ethernet and WiFi.
  • ejIP: a TCP/IP stack for embedded Java (https://dl.acm.org/doi/10.1145/2093157.2093167)
  • https://sys.cs.fau.de/extern/person/gerhorst/23-10_respect-vnv-heap/
  • “The Internet of Batteryless Things” https://dl.acm.org/doi/pdf/10.1145/3624718
  • “Intermittently-powered bluetooth that works” (Winkel et al. 2022)
  • NvMR: non-volatile memory renaming for intermittent computing (https://dl.acm.org/doi/10.1145/3470496.3527413)
  • “Whole Process Persistence with coreboot” Max Streicher (2023, BA Thesis)
  • “Microbial fuel cells in coral reef sediments as indicator tools for organic carbon eutrophication” https://www.sciencedirect.com/science/article/pii/S1470160X23005277
  • Similar, but not what we want:
    • https://ieeexplore.ieee.org/abstract/document/4404726?casa_token=SkFW9rUJYrEAAAAA:F29GS1lDyWQvMApxEvNHkgrM4R5kpbyAH4vz9b_bqz0duWCdDPgy5ToEKq0UyPwjlgqDkPDu4Ks
    • https://tldp.org/LDP/LG/issue47/stacey.html
• Design
  • To simplify your stack, you must not have a clear separation of the OSI layers in your implementation (e.g., transport, packet, and link layer).
  • To implement your transaction, here’s an example of a few primitives that will be needed. These will be the building blocks for going from one stable state to another. To implement those, there are numerous resources online (linked under implementation).
    • MAC address lockup
      • Prepare ARP request
        • Could also be part of send_arp_request() but putting all the stuff without side effects into a separate primitive will improve the WCEC of the actual send/await-reply transaction.
      • Send ARP request
      • Await ARP reply
      • Process ARP reply
    • Send IP packet, has O(maxPacketSize)
      • Can be split up similarily to the MAC address lookup.
  • Example of stable states and associated transitions for your network stack (per connection). It is part of your work to analyze whether these can be split up further (goal is to reduce the maximum WCEC of the transitions):
    1. closed: Connection closed, initial state
       • To get to ip_ready, three transactions can be used:
         1. Prepare ARP request
         2. Send ARP request and await ARP reply (see below for details)
         3. Process ARP reply
    2. ip_ready: Ready for sending IP packets (MAC address available)
    3. tcp_transfer(TCP window state):
       • Reached after TCP connection setup (handshake done)
         • Challenge: Can the handshake be split up further to improve the WCEC?
       • It is likely best to parameterize this state with the state of the TCP window (send and ACKed bytes, not-yet sendable bytes). Will later be transformed into one/many Petri net places.
       • Repeated TCP send/ack pairs advance the window
         • Use the “Send IP packet” primitive.
       • close() brings us back to the initial state.
  • Waiting for the response must (unfortunately) be included in the transactions to make sure we reach a new stable state in which the device can remain indefinately without secrificing guaranteed forward-progress.
    • Otherwise, we open the door for infinite loops such as
      1. “I have a little energy”
      2. “I send ARP Request”
      3. “I turn myself off, missing the ARP response”
      4. “I have a little energy again, relize I missed the response and resend the ARP Request”
    • For WCEC we assume some maximum network latency (e.g., one second).
    • Forward progress can of course only be guaranteed if we do not have packet loss.
      • Can be done with TTEthernet or Time-Sensitive Networking, which is part of the IEEE 802.1 (as mentioned in the tpIP paper).
• Implementation
  • Hardware
    • SoC: ESP32-C3 (https://www.espressif.com/en/products/socs/esp32-c3)
    • NVRAM: Adafruit SPI FRAM (https://learn.adafruit.com/adafruit-spi-fram-breakout)
  • Both Zephyr and ESP-IDF use primitives from Espressif’s binary blobs to interface with the network hardware. Thus, the most portable route is to write a network stack that is OS-independent and only uses these interfaces.
    • This should make your network stack (implemented as a library) portable to both Zephyr RTOS and ESP-IDF (based on FreeRTOS).
    • https://infosec.exchange/@0xor0ne/112195267522564616
  • If possible, use the hardware directly instead of the binary blobs, see https://esp32-open-mac.be/ (ESP32, ESP32-C3 is WIP)
  • Existing network stacks from which code can be reused:
    • https://git.nt.uni-saarland.de/respect/esp32-wifi-stack
      • This is a prototype the supports UDP.
    • Zephyr Wifi driver that also uses the Espressif binary blobs: https://github.com/zephyrproject-rtos/zephyr/blob/main/drivers/wifi/esp32/src/esp_wifi_drv.c
      • Zephyr RTOS Supported Boards » RISC-V Boards » ESP32-C3: https://docs.zephyrproject.org/latest/boards/riscv/esp32c3_devkitm/doc/index.html
      • This driver can be used as a reference, but we can not reuse the full Zephyr networking stack because it was not developed with WCEC analysis in mind.
    • https://github.com/espressif/esp-lwip
      • https://en.wikipedia.org/wiki/LwIP
    • https://github.com/cozis/microtcp
    • ESP-NOW (suggested by Peter Wägemann)
    • “The main difference between lwIP and uIP is the handling of TCP retransmissions. While lwIP keeps the packet buffers allocated for retransmission, applications using uIP have to reproduce the data on a retransmission. The later approach further saves memory.” (https://ieeexplore.ieee.org/document/8421149)
      • Should we attempt to impl. this optimization too?
      • tpIP statically preallocates all buffers with a configurable size. You should likely do the same.
• Scientific Writing
  • “Vale: enforcing style guidelines for text”: https://lwn.net/Articles/964075/