Towards Virtual Networking for a Time-Triggered Hypervisor

T OWARDS V IRTUAL N ETWORKING FOR A T IME -T RIGGERED H YPERVISOR

arXiv:2610.17899v1 [cs.NI] 13 Oct 2026

AUTHORS ’ V ERSION Jan Ruh NXP Semiconductors, Vienna, Austria jan.ruh@nxp.com

Silviu S. Craciunas NXP Semiconductors, Vienna, Austria silviu.craciunas@nxp.com

Jan Korecky TTControl, Vienna, Austria

October 14, 2026

A BSTRACT Virtualization enables mixed-criticality applications to run on shared hardware by isolating them within separate virtual machines (VMs). However, achieving end-to-end timing guarantees for critical tasks hosted on virtual CPUs (VCPUs) without relying on static partitioning is hard. A possible solution is a time-triggered hypervisor that dispatches VMs’ VCPUs to processor cores according to a predetermined global schedule. A global schedule includes the computation, the network, and the virtualization layer to provide end-to-end timing guarantees across hosts and VMs during design time. In this work, we propose a VirtIO-based virtual network that realizes IEEE 802.1Qbv quasi-compliant inter-VM communication, providing predictable timing for critical messages exchanged between time-triggered VMs. We present our VirtIO-based virtual network architecture and derive networklevel scheduling constraints that emerge from the properties of the proposed solution. We implement the proposed design in the ACRN hypervisor and evaluate the end-to-end latency of critical traffic in a loaded network, demonstrating that our time-triggered VirtIO-net prototype provides predictable end-to-end latency under load. Keywords Virtual Networking · Hypervisor · Real-time · Time-Triggered

1

Introduction

Modern cyber-physical systems (CPS) are becoming increasingly powerful, featuring enhanced processing capabilities, a greater number of CPU cores, and expanded memory. This evolution allows for a broader range of functionalities to execute on a single device by running multiple virtual machines (VMs). Typically, we require CPS to deliver both realtime functionalities and high-level user-facing applications [1]. Virtualization thrives in edge computing for industrial automation, where data processing takes place at the network’s edge in proximity to machinery rather than in the cloud. Here, edge computing devices run hard real-time control systems alongside soft real-time or best-effort data-driven applications [2]. Moreover, the automotive industry shifts away from using dedicated electronic control units (ECU) per function to utilizing computationally more powerful multicore multi-SoC systems that support both infotainment applications and conventional automotive control functions [3], [4]. Additionally, high-level functionalities in CPS often require feature-rich general-purpose operating systems, such as GNU/Linux derivatives, while safety-critical and real-time functionalities rely real-time operating systems [1]. In full system virtualization, a hypervisor creates a hardware-software duplicate of a real machine allocating resources to the resulting VMs [5]. There are two main approaches to tackle real-time requirements in VMs: consolidating VMs’ resource requirements or statically partitioning hardware resources. The former allocates virtual CPUs (vCPUs) RTNS 2025, November 5–7, 2025, Pisa, Italy. © 2025 Copyright held by the owner/author(s). Publication rights licensed to Springer. This is the author’s version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in The 33rd International Conference on Real-Time Networks and Systems (RTNS 2025), November 5–7, 2025, Pisa, Italy.

Towards Virtual Networking for a Time-Triggered Hypervisor

AUTHORS ’ V ERSION

to VMs and the hypervisor dispatches VCPUs on processor cores according to a runtime scheduling policy. For example, RT-XEN [6], [7], implements a real-time deferrable server and uses compositional schedulability analysis [8] to dimension VCPU budgets and periods for hosted (soft) real-time tasks. Conversely, resource partitioning [9, 10, 11] statically assigns hardware (HW) resources, such as processor cores, memory, and I/O devices, to VMs to achieve strict spatial isolation, temporal isolation, and freedom from interference. Static partitioning trades timing predictability for scalability and efficiency since the available HW resources, such as cores or network interface cards (NICs) limits the number of VMs [1]. A time-triggered hypervisor [12, 13, 14] is a compromise that dispatches VCPUs on processor cores according to a precomputed static schedule table to enable strict temporal isolation with design-time end-to-end timing guarantees [14] while static memory partitions enforce spatial isolation. Event-driven VCPUs can utilize idle slots within the time-triggered schedule [15] offering resource efficiency. In many applications, VMs need to communicate with each other, on the same or different hosts, and with additional requirements on the maximum end-to-end latency of critical data transmission. For inter-VM communication on the same host, shared memory offers the least computational overhead, and the inter-VM shared memory (IVSHMEM) device [16] supported in open-source hypervisors such as QEMU/KVM, ACRN [10], and Jailhouse [9], can achieve high data throughput and reduced latency depending on the communication partners’ timing characteristics. However, the peer-topeer nature hinders applying standard protocols and inter-VM communication across hosts. In comparison, sharing NICs via virtual networks enables seamless inter-VM communication utilizing existing protocols and communication middleware across both VM and bare-metal deployments. Yet multiple VMs transmitting data on a virtual network entails unpredictable delays, which are unacceptable in real-time systems since they result in deadline misses and system failures. Unpredictable delays, trace back to runtime scheduling decisions in the virtual network backend that governs packet transmissions between VMs virtual NICs and external physical NICs so that it is hard to meet timing requirements in virtual networks. In this paper we propose a time-triggered inter-VM communication architecture for a time-triggered hypervisor (such as the one proposed in [12, 13, 14]) to enable predictable communication latencies between VMs on the same and different hosts. We derive network-level scheduling constraints that arise from the properties of the proposed design. We further describe the implementation of our proposed solution in the open-source hypervisor ACRN [10, 17] using a virtual network based on the VirtIO framework [18]. Lastly, we evaluate the design on real industrial edge devices by testing end-to-end latencies of transferred packets under load. We survey related work in Sec. 2. Next, we present the system model (Sec. 3), the correctness constraints for timetriggered schedules (Sec. 4), and the implementation for the ACRN hypervisor (Sec. 5). In Sec. 6, we outline the test setup and cases for evaluation, discuss results, and conclude in Sec. 7.

2

Related work

This work examines time-triggered inter-VM communication based on the IEEE 802.1Qbv TSN amendment [19], aiming to extend time-triggered operations of a hypervisor to inter-VM communication, as suggested by [12, 13, 14]. We review related work on time-triggered scheduling implementations at the user, operating system, and hypervisor levels, along with TSN features in Linux and inter-process and inter-VM communication methods. MotionWise [20] implements a user-space TT scheduler that provides deterministic execution of automotive applications [21]. Gala et al. [22] successfully applied time-triggered VCPU scheduling to Linux Kernel Virtual Machine (KVM) in a cloud-computing environment to enforce temporal isolation and memory bandwidth limits. Karachatzis et al. [23] present a kernel-level TT scheduler for Linux and compare it to user space scheduling in MotionWise. Furthermore, Gala et al. [24] present time-triggered Linux kernel-level scheduling with an acceptance test for event-triggered tasks. GNU/Linux implements several TSN features [25]. For example, the traffic control utility (tc) [26] interfaces with the kernel’s queueing disciplines (qdiscs) including the TAPRIO qdisc [27], providing scheduled traffic according to IEEE 802.1Qbv. A common approach to inter-process and inter-VM communication is shared memory. The inter-VM shared memory (IVSHMEM) device [16], supported in open-source hypervisors such as QEMU/KVM, ACRN [10], and Jailhouse [9] allows sharing share memory with co-hosted VMs through a virtual PCI device. In recent versions, Jailhouse implements an extended IVSHMEM specification v2.0, enabling connections between up to 65536 peers, interrupt-based event signaling, and the option to use an IVSHMEM network driver that exposes a virtual Ethernet device [28]. Similar virtual PCI shared memory devices can be found in commercial offerings such as QNX [29]. Alternatively, hypervisors that feature a Linux host, such as the KVM, or a Linux-based privileged VM, such as Xen [30] or ACRN [10], often realize inter-VM communication as a virtual network with TAP devices attached to a Linux bridge appearing to the VMs as regular network interfaces. A memory region backs up each TAP device shared between the VM and the system hosting the Linux bridge. The de facto standard for virtual network devices in Linux-based virtual networks is 2

Towards Virtual Networking for a Time-Triggered Hypervisor

AUTHORS ’ V ERSION

VirtIO [18], which specifies how virtual device backends in the privileged system communicate data via virtqueues with virtual device frontends in the VMs. In [31], three alternative placements of a transmission (TX) scheduler for TSN in virtualized platforms, i.e., one per application, one per VM, or one in the hypervisor/a privileged context, are evaluated using simulation. However, they fail to acknowledge that relying on a TX scheduler in either the user space or the kernel space of VMs requires VMs to trust each other to adhere to the schedule. We argue that the TX scheduler must reside in a trusted component hindering the practicality of their solution. Schwäricke et al. [32] propose a framework enabling predictable inter-VM communication in static partitioning hypervisors. They implemented a prototype in Jailhouse, delegating stream scheduling to a dedicated bare-metal broker cell that exploits the hardware platform’s DMA engine for data transfer and utilizes established mechanisms, including cache-coloring [33] and memory bandwidth regulation [34] to isolate EDFscheduled streams between VMs. VMs interface with the predictable inter-VM communication engine using standard VirtIO socket virtual devices. Li et al. [35] propose a real-time communication framework utilizing an IVSHMEM memory region shared between multiple VMs. The shared memory region for each VM contains distinct TX and reception (RX) queues per priority, as well as a priority-based TX engine. We note that fixed priority-based stream scheduling is prone to starvation in the case of a faulty high-priority sender. Furthermore, the TX engines’ execution context, i.e., whether it executes as a separate process within the VMs or the context of the transmitting application as part of the IVSHMEM device driver, or is it a host OS component, remains unclear despite its implications on expected throughput, temporal isolation, and security. Ferraro et al. [28] introduce a similar solution as part of their automotive time-sensitive architecture. Their prototypical implementation of an IVSHMEM-based virtual TSN switch (VTSN) executes as a bare-metal application in a dedicated Jailhouse cell. It exhibits reduced round-trip time for varying packet sizes compared to a partitioned Xen virtual networking configuration. However, the current VTSN prototype does not actually support any TSN traffic shaping mechanisms. BiRtIO [36] is a VirtIO network implementation for the Bao static partitioning hypervisor. The authors report an average latency jitter of 243.96 µs using multi-queue priority (MQPRIO) and credit-based shaper (CBS) qdiscs.

3

System Model

We consider a distributed virtualized real-time system and illustrate an example with two nodes in Fig. 1. We model S  n it as a directed graph G(V, L) where the vertices V = V S ∪ V are switches V S and VMs V n hosted on ∀n∈V N

virtualized end-systems n ∈ V N . The edges L ⊂ V × V are either bi-directional, full-duplex physical links between vertices (VMs or switches) or bi-directional virtual links between VMs hosted on the same end-system. A virtualized end-system is an SMP platform with a table-driven dispatcher in the hypervisor, the privileged VM, and user VMs. The hypervisor allocates VCPUs on physical cores (c.f. Fig. 1, VCPUs), while the privileged VM (c.f. Fig. 1, VMs 4 and 8) manages virtual links for its user VMs. User VMs (c.f. Fig. 1, VMs 1–3 and 5–7) run periodic TT tasks based on a coordinated schedule. These VMs execute a set of dependent and independent TT tasks, with dependent tasks communicating through streams on the physical/virtual TSN backbone. Each switch and end system’s privileged VM executes the IEEE 802.1AS clock synchronization protocol [37] to establish a global time base [38] with an upper bounded precision Π, i.e., the maximum time difference between any two non-faulty clocks. Privileged VMs share the derived synchronized time with co-located user VMs and the hypervisor via a shared memory-based dependent clock [12]. The macrotick (slot length) divides the global time in the guest OS and hypervisor of a virtualized end system into equal slices, representing the smallest granularity for scheduling decisions [39], [40]. To simplify the already complex correctness constraints, we will assume a timeline represented by the natural numbers, i.e., a macrotick of 1 on all nodes. Generalizing the correctness constraints to different macroticks is trivial (e.g., [14]). A static schedule of a node’s core or a link’s egress queue is a set of slots that repeats with a period called the hyperperiod THP . For completeness, we recapitulate the physical network and communication model, the task model, and the system virtualization model from [14] in Sec. 3.1. We introduce our virtual network model in Sec. 3.2. 3.1

Communication, Task, and Virtualization Model

The physical network is a time-sensitive network (TSN) [41] featuring IEEE 802.1As-2020 [37], gPTP clock synchronization and IEEE 802.1Qbv [42] scheduled traffic. IEEE 802.1Qbv [42] introduces a time-aware gate mechanism that manages the opening and closing of egress ports, thereby controlling the forwarding of frames based on a cyclic schedule table, referred to as a Gate Control List (GCL) [43]. A NIC’s local clock governs its operation [44]. A stream si := {(a, ν1 ), (ν1 , ν2 ), ..., (νm−1 , νm ), (νm , b)} between a sender a ∈ V and a receiver b ∈ V on a predefined route via intermediate nodes ν1 , ..., νm ∈ N is a communication requirement with period Ti . Each stream si ∈ S periodically releases stream jobs that must be transmitted within their respective period instances. The communication model is not strictly periodic, i.e., each stream job can be transmitted at a different time in each period instance. Let Jixy be 3

AUTHORS ’ V ERSION

Node 2

Node 1

VCPUs

Towards Virtual Networking for a Time-Triggered Hypervisor

Time Sensitive Network

Figure 1: System model with a virtual network

the finite ordered set of jobs that stream si ∈ S releases on a link (x, y) ∈ si until the hyperperiod. Each stream si ∈ S communicates a payload of size Si . When communicating via physical links, the maximum transmission xy unit (M T U ) limits the number of bytes in a frame so that each stream job Jij ∈ Jixy consists of a list of frames xy xy xy xy Fij with |Fij | = ⌈ MSTi U ⌉ since a stream’s total payload can exceed the M T U . Each frame fijk ∈ Fij has a xy x,y transmission duration fijk .L. When transmitted over a physical link (x, y) ∈ si with a given speed s in bits/second, S

·109 ·8

xy xy the transmission duration is fijk .L = ijksxy , where Sijk is the size of the frame fijk in bytes. The transmission xy xy xy time of a frame fijk ∈ Fij on link (x, y) ∈ si relative to the period is fijk .ϕ. The absolute scheduling offset of a xy xy frame fijk in period instance j is fijk .ϕ + j · Ti .

A TT task τi is a tuple (Ri , Di , Ci , Ti , Ai ) where Ri is the release time, Di is the relative deadline, Ci is the WCET, Ti is the period, and Ai is its resource affinity. The set of all periodic RT tasks is T . A context switch between tasks on a core c induces an overhead δτ (c). As for the streams, we assume a non-strictly periodic model, i.e., each task job can execute at a different time in each period instance. A task τi releases a finite ordered set of jobs Ji until the hyperperiod. Jobs are preemptible, so each job Jij ∈ Ji comprises a finite list of job segments Xij . A period-relative offset xijk .ϕ and length xijk .L define a job segment xijk ∈ Xij . A segment’s absolute scheduling offset in period sk instance j is xijk .ϕ + jTi . A pair of TT tasks communicate with each other via a TSN stream. Let τi −→ τj indicate a sk data dependency between two tasks τi , τj ∈ T , i.e., τj receives input data from τi via stream sk ∈ S. It is E(τi −→ τj ) the maximum end-to-end latency of a data dependency. A virtualized end system n ∈ V N is an SMP system, and C n denotes its set of cores that share a main memory. Each virtualized end system hosts multiple TT VMs that share the physical compute and memory resources. TT VMs can have access to a dedicated network interface card (NIC) connected to the TSN backbone or to a virtual NIC connected to a software bridge in a privileged VM as illustrated in Fig., 1. A TT VM j ∈ V n dispatches TT tasks on a set of VCPUs. Each VCPU is assigned to run on exactly one physical core, with no migration allowed at runtime. Let P(c) be the set of all VCPUs running on a core c ∈ C n . TT VCPUs are preemptible; thus, a TT VCPU ρi ∈ P(c) comprises a set of segments Zi . An offset zij .ϕ and a length zij .L define a VCPU segment zij ∈ Zi . VCPU segments do not have a period, and their offset is relative to the hyperperiod. Switching between VCPUs on a core c introduces a context switch overhead δρ (c). Let T (ρ) be the set of TT tasks allocated to a VM’s VCPU ρ. 3.2

Virtual Network Model

In this paper, we propose a time-triggered IEEE 802.1Qbv quasi-compliant inter-VM communication based on the VirtIO specification [45]. On each virtualized end system n ∈ V N , we assume the existence of a privileged VM p ∈ V n , hosting a software bridge. The software bridge forwards Ethernet frames between co-located user VMs and to the TSN backbone connected to the privileged VM through a passthrough NIC. There exists a shared memory region between each user and privileged VM, which in turn, contains q egress and ingress queues. Towards a user VM v ∈ V n , its egress and ingress queues appear as a regular NIC, whereas the privileged VM’s OS kernel abstracts each shared memory region as a kernel virtual network interface (in UNIX-like OS commonly known as a TAP interface). The privileged VM serves a VM v’s egress and ingress queues with dedicated transmission (TX) and reception (RX) tasks tx tx rx rx T X v (ρp ) := {τv,1 , ..., τv,q } and RX v (ρp ) := {τv,1 , ..., τv,q } on a virtual CPU ρp . We refer to the shared memory 4

Towards Virtual Networking for a Time-Triggered Hypervisor

AUTHORS ’ V ERSION

region between a user VM u ∈ V n \ {p} and the privileged VM p, the egress and ingress queues it contains, and the TX and RX tasks serving them as a virtual link (v, p) ∈ L.

Notably, we consider bidirectional links, i.e., (v, p) = (p, v) ∈ L, however, if we write a virtual link as (v, p), it tx implies that the privileged VM must dispatch v’s TX task τv,i ∈ T X v (ρp ) to read sent Ethernet frames from its corresponding egress queue i and let the software bridge determine their destination. Accordingly, if we write a virtual rx link as (p, v), it implies that v’s RX task τv,i ∈ RX v (ρp ) writes the Ethernet frames forwarded by the software bridge to the corresponding ingress queue i. In contrast to physical networks, where a frame’s transmission duration f.L depends on the link speed, in a virtual network, the worst-case memory read and write rates rdwc and wrwc of the virtualized end system hosting a virtual link capture the transmission duration depending on whether the virtual link tx is sending or receiving. If a virtual link (v, p) is sending, i.e. its TX task τv,i reads data from the egress queue i, the vp vp Slkm rd rx transmission duration is flkm .L = rdwc = flkm .L . If a virtual link (p, v) is receiving, i.e., its RX task τv,i writes pv pv Slkm wr data to the ingress queue i, the transmission duration is flkm .L = wrwc = flkm .L .

We set of all TX and RX S tasks assigned to a VCPU ρp ∈ P(c) of a privileged VM p with T X n (ρp ) := S denote the v n v tx rx tx rx ∀v∈V n T X (ρp ) and RX (ρp ) := ∀v∈V n RX (ρp ). Furthermore, we write Sv,i , Sv,i , Jv,i , and Jv,i for the sets of all streams and stream jobs send and received by a VM v ∈ V n that map to egress or ingress queue 1 ≤ i ≤ q, respectively. We make no assumptions on the number of VCPUs available to a privileged VM to host virtual links’ TX and RX tasks, nor its VCPUs’ execution mode, i.e., VCPUs hosting virtual links may be pinned to a processor core or time-triggered. tx rx While a TX task τv,i or RX task τv,i is active on its VCPU ρp , it forwards or receives queued frames to or from the tx respective egress or ingress queues of its virtual links. Accordingly, dispatching an egress queue i’s TX task τv,i corresponds to setting the state of a 802.1Qbv time-aware gate on VM v’s virtual NIC’s i-th egress queue to open. It becomes apparent that the timing, i.e., latency and jitter, of data transmission via virtual links depends on scheduling TX and RX tasks’ jobs on the VCPU ρp . We assume that TX and RX tasks only release new jobs if packets are waiting in their respective egress and ingress queues so that the task model for scheduling TX and RX tasks follows the characteristics of the TSN streams generating data. Consequently, a VM v ∈ V n communicating Qbv streams over a virtual link will periodically place packets in a tx TT egress queue i or retrieve packets from a TT ingress queue i. Therefore, TX and RX task τv,i ∈ T X v (ρp ) and v rx tx τv,i ∈ T X (ρp ) are TT tasks (Riv , Div , Civ , Tiv , Avi ) with release time Riv = 0, a period Tiv = lcm{Tx |∀sx ∈ Sv,i }, a deadline Div = Tiv , and an affinity Avi := ρp . The WCET Civ of a TX task is the sum of its frames’ worst-case read tx durations and TX delay δ tx times the number of processed stream jobs Jv,i :   X X tx v Civ = δ tx · |Jvi |+ fijk .Lrd tx ∈J tx ∀Jvij vi

v ∈F tx fijk vij

A RX task’s WCET Civ is the sum of its frames’ worst-case write durations and a reception delay δ rx times the number rx of processed stream jobs Jv,i :  X  X rx v Civ = δ rx · |Jvi |+ fijk .Lwr rx ∈J rx ∀Jvij vi

v ∈F rx fijk vij

If we are not explicitly referencing a specific VM’s TX or RX task, we drop the VM superscripts for readability. A stream sx ∈ S features at most two virtual links, one between the sender and the privileged VM and one between the privileged VM and the receiver. Given the sets of periodic TX and RX tasks T X (ρp ) and RX (ρp ) we can apply the TT task model. Up to the hyperperiod THP , for all TT queues i ∈ {1, ..., m}, TX and RX tasks τitx ∈ T X (ρp ) and τirx ∈ RX (ρp ) release a finite number of jobs denoted by Jitx and Jirx . We assume that TX and RX tasks’ jobs are preemptable, i.e., each tx rx job Jij ∈ Jitx and Jij ∈ Jirx gives rise to finite lists of job segments Xijtx and Xijrx . We define a TX or RX task job segment xijk by its period-relative offset xijk .ϕ and its length xijk .L.

4

Correctness Constraints

Previous work [14] proposed correctness constraints for TT tasks with end-to-end latency on TT VCPUs in SMP platforms using a TSN backbone. However, it assumed each TT VM had a passthrough NIC, which isn’t usually the case. We address this by introducing new correctness constraints that enable IEEE 802.1Qbv inter-VM and external communication through virtual NICs, as detailed in Sec. 3.2. The scheduling problem, i.e., if for a given set of TT tasks 5

Towards Virtual Networking for a Time-Triggered Hypervisor

AUTHORS ’ V ERSION

hosted on a set of TT VCPUs executing on cores across several virtualized end systems communicating via Qbv streams over a mixed physical/virtual TSN backbone there exist(s) correct solution(s) that fulfill(s) the correctness constraints, is NP-complete. A solution of the scheduling problem is a set of static schedule tables specifying task and VCPU segment offsets, lengths, and frame offsets fulfilling all correctness constraints. We differentiate between checking a given solution’s correctness, which can be done in polynomial time, and finding a solution for which (if P ̸= N P ) no polynomial time algorithm exists. For now, we are only interested in the correctness of an existing solution. Akin to the introduced system model, in Sec. 4.1–4.3 we briefly recapitulate the most important correctness constraints presented in [14], and introduce new constraints (Strict Source and Destination Task Alignment Constraints) required by our generalization of the model in [14]. Then, in Sec. 4.4, we introduce the correctness constraints for the proposed virtual network model that extend the existing network constraints [14] enabling strict, predictable end-to-end latency when communicating in a mixed physical/virtual Qbv network. 4.1

Task Correctness Constraints

Job segments must be limited by release, deadline, and WCET of their tasks. Constraint 1 (Release Time and Deadline). Given the virtualized distributed real-time system defined by the graph G(V, L), we have: ∀n ∈ V, ∀c ∈ C n , ∀ρ ∈ P(c), ∀τi ∈ T (ρ), ∀Jij ∈ Ji , ∀xijk ∈ Xij : (xijk .ϕ ≥ Ri ) ∧ (xijk .ϕ + xijk .L ≤ Di )

The length of each task segment should be no shorter than the overhead of context switching to ensure job progression. Additionally, the total size of a job’s segments must equal or exceed the task’s Worst Case Execution Time (WCET) plus the context-switching overhead for those segments. Constraint 2 (Job Segment Size Constraint). Given the virtualized distributed real-time system defined by the graph G(V, L), we have: ∀n ∈ V, ∀c ∈ C n , ∀ρ ∈ P(c), ∀τi ∈ T (ρ), ∀Ji,j ∈ Ji :   X (∀xi,j,k ∈ Xij : xi,j,k .L ≥ δτ (c)) ∧  xi,j,k .L ≥ Ci + |Xi,j | · δτ (c) ∀xi,j,k ∈Xij

For any pair of tasks assigned to the same resource, their job segments’ execution intervals cannot overlap. Constraint 3 (Task Overlapping Constraint). Given the virtualized distributed real-time system defined by the graph G(V, L), we have: ∀n ∈ V, ∀c ∈ C n , ∀ρ1 , ρ2 ∈ P(c), ∀τi ∈ T (ρ1 ), ∀τl ∈ T (ρ2 ), ∀Jij ∈ Ji , ∀Jlm ∈ Jl , ∀xijk ∈ Xij , ∀xlmn ∈ Xlm , xijk ̸= xlmn : (xijk .ϕ + j · Ti ≥ xlmn .ϕ + m · Tl + xlmn .L) ∨ (xlmn .ϕ + m · Tl ≥ xijk .ϕ + j · Ti + xijk .L)

4.2

End-to-End Correctness Constraints

The end-to-end latency constraint imposes a maximum delay between the start of a sender task and the completion time of a receiver task in a user VM. Virtualized end systems and switches within a TSN network G(V, L) share a common global time established by the IEEE 802.1AS clock synchronization protocol and characterized by its precision Π. The time difference between a receiving task job completing its execution and a sending task job starting execution is less than or equal to their streams’ end-to-end latency minus the precision Π. Constraint 4 (End-to-End Constraint). Given the virtualized distributed real-time system defined by the graph G(V, L), we have: ∀a, b ∈ V, ∀ca ∈ C a , ∀cb ∈ C b , ∀ρa ∈ P(ca ), ∀ρb ∈ P(cb ), s

h ∀τi ∈ T (ρa ), τl ∈ T (ρb ) s.t. τi −→ τl , ∀Jij ∈ Ji , ∀Jlm ∈ Jl :

max

∀xlmn ∈Xlm

{xlmn .ϕ + xlmn .L} −

min

∀xijk ∈Xij

s

h {xijk .ϕ} ≤ E(τi −→ τj ) − Π

Furthermore, he transmission schedule of the stream sk aligns along its route to the sender and receiver task schedule. The propagation delay δ xy is the time it takes a frame to travel on a physical link from the source to the destination. 6

Towards Virtual Networking for a Time-Triggered Hypervisor

AUTHORS ’ V ERSION

Constraint 5 (Task Alignment Constraint). Given the set of streams S and the virtualized distributed real-time system defined by the graph G(V, L), we have: ∀a, b ∈ V, ∀ca ∈ C a , ∀cb ∈ C b , ∀ρa ∈ P(ca ), ∀ρb ∈ P(cb ), s

h ∀τi ∈ T (ρa ), τj ∈ T (ρb ) s.t. τi −→ τj , ∀Jik ∈ Ji , ∀Jjk ∈ Jj :   ax max {xikl .ϕ + xikl .L} ≤ ax min ax {fhkl .ϕ} ∧

∀xikl ∈Xik

∀fhkl ∈Fhk

yb yb min {xjkl .ϕ} ≥ max {fhkl .ϕ + fhkl .L} + δ yb + Π yb yb ∀xjkl ∈Xjk ∀fhkl ∈Fhk

!

When a stream’s source node is a VM, the VM’s network stack buffers frames but its VCPU may not be running when the frames’ TX or RX times arrive. Hence, in addition to the constraints from [14], we introduce strict source and destination task alignment constraints. The strict source task alignment constraint ensures that the source task job’s last segment and the transmission of the stream job’s last frame complete simultaneously. The destination task alignment constraint ensures that a destination task job’s first segment is dispatched when the TX of a stream job’s first frame completes. Together with Constraint 9, these new alignment constraints implicitly ensure that the source/destination task job’s VCPU is running when the NIC transmits/receives a stream job’s frames. We presume that the source/destination task’s WCET includes the worst-case transmission/reception overhead induced by the network stack. Constraint 6 (Strict Source Task Alignment Constraint). Given the set of streams S and the virtualized distributed real-time system G(V, L), we have: ∀a ∈ V, ∀b ∈ V, ∀ca ∈ C a , ∀cb ∈ C b , ∀ρa ∈ P(ca ), ∀ρb ∈ P(cb ), s

h ∀τi ∈ T (ρa ), τj ∈ T (ρb ) s.t. τi −→ τj , ∀Jik ∈ Ji , ∀Jjk ∈ Jj : % $

max {xikl .ϕ + xikl .L} =

∀xikl ∈Xik

max

ax ∈F ax ∀fhkl hk

ax ax {fhkl .ϕ + fhkl .L}

For the destination task alignment constraint, if the last hop is a virtual link, we additionally need to account for the worst-case RX delay δ rx , the TX delay δ tx , and the context switch time δτ (ρp ) to the virtual link’s RX task job segment.  rx δ + δ tx + δτ (ρp ), if (v, u) is a virtual link rx δ (v, u) = 0, otherwise Constraint 7 (Strict Destination Task Alignment Constraint). Given the set of streams S and the virtualized distributed real-time system, we have: ∀a ∈ V, ∀b ∈ V, ∀ca ∈ C a , ∀cb ∈ C b , ∀ρa ∈ P(ca ), ∀ρb ∈ P(cb ), s

h ∀τi ∈ T (ρa ), τj ∈ T (ρb ) s.t. τi −→ τj , ∀Jik ∈ Ji , ∀Jjk ∈ Jj : $

min

∀xjkl ∈Xjk

4.3

{xjkl .ϕ} + δ rx (y, b) =

yb yb .ϕ + fhkl .L} + δ yb + Π min {fhkl yb yb ∀fhkl ∈Fhk

%

System Virtualization Constraints

Similar to Constraint 3, VCPU segments cannot overlap if on the same resource. Constraint 8 (Virtual CPU Overlapping). Given the virtualized distributed real-time system defined by the graph G(V, L), we have: ∀n ∈ V, ∀c ∈ C n , ∀ρi , ρm ∈ P(c), ∀zij ∈ Zi , ∀zmn ∈ Zm , zij ̸= zmn : (zij .ϕ ≥ zmn .ϕ + zmn .L) ∨ (zmn .ϕ ≥ zij .ϕ + zij .L)

The VCPU segment size must be at least equal to the sum of all task job segments allocated to it, plus the overhead of VCPU context switching. This requirement involves a helper set Oij , which identifies the task job segments that completely overlap with the specific VCPU segment zij . For a VCPU segment zij of ρi assigned to core c, it can be expressed as: Oij = {xlmn |∀τl ∈ T (ρi ), ∀Jlm ∈ Jl , ∀xlmn ∈ Xlm : (xlmn .ϕ + m · Tl ≥ zij .ϕ) ∧ (xlmn .ϕ + m · Tl + xlmn .L ≤ zij .ϕ + zij .L)} 7

Towards Virtual Networking for a Time-Triggered Hypervisor

AUTHORS ’ V ERSION

Constraint 9 (Virtual CPU Size Constraint). Given the virtualized distributed real-time system defined by the graph G(V, L), we have: X ∀n ∈ V, ∀c ∈ C n , ∀ρi ∈ P(c), ∀zij ∈ Zi : zij .L ≥ δρ (c) + xlmn .L xlmn ∈Oij

All task segments that overlap with a given VCPU segment, i.e., are elements of the set Oij , must be assigned to the corresponding VCPU ρi . Constraint 10 (Virtual CPU Assignment). Given the virtualized distributed real-time system defined by the graph G(V, L), we have: ∀n ∈ V, ∀c ∈ C n , ∀ρi ∈ P(c), ∀zij ∈ Zi , ∀xlmn ∈ Oij : τl ∈ T (ρi )

4.4

Virtual Network Constraints

The correctness constraints for IEEE 802.1Qbv from [14] also apply in this work. The following constraints specify correctness if a shared memory-based virtual network served by per-queue TX and RX tasks is present in the privileged VM of a virtualized end system. An 802.1Qbv stream’s transmission on a virtual link differs from a deterministic Ethernet link in that a virtual link requires a TX or a RX task executing on a computational resource to forward data in an egress queue or to receive data on an ingress queue, respectively. A VM v ∈ V n sending a stream sk ∈ S via a virtual link (v, p) ∈ Ln , where p ∈ V n is n’s privileged VM, amounts tx to writing the stream data to an egress queue i and dispatching the corresponding TX task τv,i ∈ T X v (ρp ). For tx tx tx released stream jobs Jv,i , the TX task τv,i releases jobs Ji to read the stream jobs’ frames from v’s egress queue i and determine their destination. Instead, if VM v is receiving a stream sk on a virtual link (p, v) ∈ Ln , it requires a RX rx task τv,i ∈ RX v (ρp ) to write stream data to the associated ingress queue before its guest OS can read the frames. Thus, rx rx similar to outgoing streams, for incoming stream jobs Jv,i , the RX task τv,i releases jobs Jiv to write the stream jobs’ v frames to v’s ingress queue i. As a result, a TX or RX task job Jij requires segments Xijv depending on the released tx tx rx tx stream job instances Jkl ∈ Jv,i or Jkl ∈ Jv,i , i.e., for any stream job sent or received via a virtual link there must exist a TX or RX task job segment encapsulating and processing its frames. Accordingly, a TX/RX task job segment constraint must ensure that a TX or RX task job’s segment size xvijk .L is greater or equal to the sum of all stream jobs’ TX or RX delays, frames’ transmission durations, and the task context switch time overhead δτ (ρp ) on a VCPU ρp . We express the constraint similar to the Virtual CPU Size Constraint 9 using a helper set. We define the helper set Rvijk containing all stream jobs a TX or RX task segment xvijk ∈ Xijv serves: tx tx Rvijk := {Jftxg |∀sf ∈ Sv,i , ∀Jftxg ∈ Jv,i , ∀ff gh ∈ Fftxg : jg · T k f j= ∧ (ff gh .ϕ + g · Tf ≥ xijk .ϕ + j · Ti ) Tiv ∧ (ff gh .ϕ + ff gh .L + g · Tf ≤ xijk .ϕ + xijk .L − δ(xvijk ) + j · Ti )}

The term δ(xvijk ) captures the TX delay δ tx , if xvijk is a TX task job segment and the RX delay δ rx , if xvijk is a RX task job segment: ( δ tx , if xvijk is TX task job segment v δ(xijk ) = rx −δ , if xvijk is RX task job segment Constraint 11 (TX Task Job Segment Size Constraint). Given the virtualized distributed real-time system defined by the graph G(V, L), we have: tx v ∀n ∈ V, ∀v ∈ V n , ∀c ∈ C n , ∀ρp ∈ P(c), ∀τv,i ∈ T X v (ρp ), ∀Jij ∈ Jiv , ∀xvijk ∈ Xijv  X  X tx tx tx ∀sl ∈ Sv,i , ∀Jlm ∈ Jlm : xvijk .L ≥ δτ (ρp ) + δ tx + fklm .L tx ∈Rv ∀Jlm ijk

tx ∀fklm ∈Jlm

Constraint 12 (RX Task Job Segment Size Constraint). Given the virtualized distributed real-time system defined by the graph G(V, L), we have: tx v ∀n ∈ V, ∀v ∈ V n , ∀c ∈ C n , ∀ρp ∈ P(c), ∀τv,i ∈ T X v (ρp ), ∀Jij ∈ Jiv , ∀xvijk ∈ Xijv  X  X rx rx tx ∀sl ∈ Sv,i , ∀Jlm ∈ Jlm : xvijk .L ≥ δτ (ρp ) + δ rx + fklm .L rx ∈Rv ∀Jlm ijk

8

rx ∀fklm ∈Jlm

Towards Virtual Networking for a Time-Triggered Hypervisor

5

Implementation

5.1

SMT-EDF Schedule Co-Synthesis

AUTHORS ’ V ERSION

Encoding correctness constraints as linear integer arithmetic expressions (Z, +, ≥) and using Satisfiability Modulo Theories (SMT) to find valid variable assignments or a model is an established method to schedule time-triggered systems [46, 47, 48, 43, 14]. Incrementally adding assertions to, checking the SMT context, and backtracking if a SMT context is unsatisfiable has proven efficient for scheduling communication in TTEthernet [46]. However, when co-scheduling computational and communication resources of large systems, SMT-based scheduling with incremental backtracking exhibits long runtimes since the high utilization of computational compared to communication resources results in repeated backtracking [47]. The introduction of a system virtualization layer and VCPU constraints further multiplies interdependency, impeding the performance benefits gained by incremental backtracking. In [14], the authors proposed identifying and jointly adding dependent VCPU, task, and stream constraints to the solver context to prevent conflicting segment offsets, segment sizes, and frame offsets of interdependent schedulable entities that otherwise would result in backtracking. Their SMT-based dependency-aware scheduler minimizes the number of required VCPU segments, hence virtualization overhead, with a reasonable runtime for small systems, yet it scales poorly with increasing system size. Therefore, they further implement a runtime-optimized scheduler similar to demand-based scheduling [47, 48] that utilizes the SMT scheduler to synthesize schedule tables for dependent tasks and their streams. Then, it simulates earliest deadline first (EDF) to schedule TT tasks without dependencies, so-called free tasks, and VCPUs via a heuristic. Their SMT-EDF scheduler effectively trades a decreased runtime for higher virtualization overhead [14]. Here, we also implemented an SMT-EDF scheduler utilizing the Python API of Z3 [49] to schedule dependent TT task jobs, their VCPUs, stream jobs, and TX and RX task jobs. We facilitate the resulting partial schedule tables to enforce busy intervals I c on a processor core c for the EDF simulation. Our SMT-EDF scheduler takes sets of TT tasks T , TT TX and RX tasks T X and RX , TT VCPUs P, and Qbv streams S. It derives a subset of dependent s s tasks T ′ := {τ |∀τ, τ ′ ∈ T , ∀s ∈ S : τ − → τ′ ∨ τ′ − → τ } and VCPUs P ′ := {ρ|∀τ ∈ T ′ : τ ∈ T (ρ)} to pass to the SMT-based dependency-aware network scheduler together with the sets T X and RX . Our implementation of the SMT-based dependency-aware scheduler identifies groups of dependent schedulable entities (TT tasks, VCPUs, streams, TX and RX tasks) as in [14], performs a necessary polynomial schedulability test [50], and, if successful, jointly adds their resulting Constraints 1–10 (and the 802.1Qbv Constraints [14]) to the SMT context. If the Z3 SMT solver returns true, the scheduler freezes the resulting segment offsets, segment sizes, and frame offsets and proceeds to the next group. Otherwise, the scheduler backtracks, combining groups to check a larger SMT context. If the SMT-based dependency-aware scheduler finds schedule tables for T ′ , S, T X , RX , and P ′ , it uses the resulting busy intervals I c := {[zij .ϕ, zij .ϕ + zij .L]|∀ρi ∈ P ′ (c), ∀zij ∈ Zi } and the remaining free TT tasks T \ T ′ and VCPUs P \ P ′ as an input to an EDF simulation of core c. The simulation of a core c maintains a ready list dispatching TT tasks’ jobs according to an EDF policy. If the simulation dispatches a job Jmn ∈ Jm of a free TT task τm ∈ T \ T ′ on a VCPU ρk , it differentiates two cases. In the case ρk is already running, the simulation accounts for the task context switch time δτ (ρk ). If ρk is not running, the simulation additionally accounts for the VCPU context switch time δρ (c). Once context switch times have been accounted for, the simulation tracks a jobs runtime until the next preemption. When the simulation preempts a task job and/or VCPU, it creates segments xmno and zkl . Before each busy interval [zij .ϕ, zij .ϕ + zij .L] ∈ I c at simulation time zij .ϕ − δρ (c), the simulation checks if the VCPU ρk ∈ P \ P ′ currently active within the simulation matches the busy interval’s VCPU ρi ∈ P ′ . If the VCPUs differ, the simulation preempts the currently active VCPU ρk accounting for the VCPU preemption overhead δρ (c) and resumes the simulation after the busy interval at time zij .ϕ + zij .L. Otherwise, the simulation continues until time zij .ϕ to then preempt the currently active task job for the duration zij .L of the busy interval. If the EDF simulation detects a deadline miss, it adds the corresponding free task and its VCPU to a set of incomplete tasks T ∗ and VCPUs P ∗ and continues the simulation. When the EDF simulation on all cores returns and there are incomplete free TT tasks T ∗ and VCPUs P ∗ , our scheduler adds them to the sets of dependent tasks T ′ = T ′ ∪ T ∗ and VCPUs P ′ = P ′ ∪ P ∗ and invokes the SMT-based dependency-aware scheduler again. The SMT-EDF scheduler alternates between the SMT-based dependency-aware scheduler and the EDF simulation until either there are no more incomplete free tasks, or, in the worst-case, it is T ′ = T and P ′ = P and the SMT-based dependency-aware scheduler solves the entire original problem. However, in the average case EDF-SMT scheduler exhibits greatly reduced runtime compared to the SMT-based dependency-aware scheduler. Fig. 2 shows a correct schedule according to our Constraints 1–12 (and the network Constraints in [14]) synthesized by our SMT-EDF scheduler for a system with 2 virtualized end systems, each hosting four VMs. One privileged VM per node runs the TX and RX tasks of a virtual TT network on a pinned single VCPU (core 0). These VMs access a passthrough NIC linking them. Three user VMs, each with one VCPU, share core 1. In total, the setup has 6 user VMs 9

Towards Virtual Networking for a Time-Triggered Hypervisor

Node 2 core 1

τ4

τ2

ρ 10

ρ 20 1 τ tx

core 0

τ8

ρ 30

τ8

ρ 20 ρ 30

2 τ2 τ tx rx

τ9

ρ 20 ρ 30

ρ 30

τ4

τ2

ρ 10

2 τ3 τ3 τ rx rx rx

ρ 20 1 τ tx

AUTHORS ’ V ERSION

τ8

ρ 30

τ9

ρ 20 ρ 30

2 τ2 τ tx rx

τ8

ρ 30

3 τ rx

ρ 20

3 τ2 τ rx rx

VM 2 eth0 VM 1 eth0

Node 1 core 1

τ0

τ1

ρ 10

ρ 20

τ 10

ρ 10 ρ 30

1 τ1 τ2 τ3 τ tx tx tx rx

core 0

τ1

ρ 20 ρ 30

τ5

ρ 20

1 τ2 τ2 τ3 τ tx tx rx rx

τ1

ρ 30 ρ 20 ρ 30 ρ 10 ρ 30 2 τ3 τ tx rx

τ0

ρ 10

τ1

ρ 20 ρ 30

1 τ1 τ1 τ2 τ2 τ tx tx tx tx rx

τ5

ρ 20

ρ 30

3 τ rx

VM 2 eth0 VM 1 eth0

linux-br2 tap3 tap2

linux-br1 tap3 tap2 eth0 0.00

2.00

4.00

6.00

8.00 10.00 12.00 14.00 16.00 18.00 20.00

Global time in ms spanning first hyperperiod Figure 2: Example of a correct schedule

hosting 15 tasks, with 10 communicating via 5 Qbv streams. The data flow for one internal and one external stream is indicated by black arrows. 5.2

A Time-Triggered Hypervisor

We implemented a TT hypervisor with TT VCPU scheduling and TT VirtIO virtual networking based on the ACRN hypervisor [10] for x86-64 architectures. We chose ACRN over other open-source type-1 hypervisors, such as Xen [30], or a type-2 hypervisor such as the Linux KVM, due to an existing clock synchronization infrastructure [12, 51] for the ACRN hypervisor that grants the hypervisor access to a global time base to align TT VCPU with task and network scheduling, a facility missing in Xen. In Linux KVM, a global time is available to the host through CLOCK_REALTIME and the host and guests can use the same user space clock synchronization stack as in [12, 51]. Furthermore, several implementations of TT scheduling for the Linux kernel [22, 23, 24] already exist. However, Linux KVM relies on QEMU [52] to configure VirtIO networking via vhost in-kernel or run it directly in user space. Note that we did not consider purely static partitioning hypervisors, such as Jailhouse [9] or Bao [11], since they do not support VCPU scheduling by design. 5.2.1

TT VCPU Scheduling

Officially, the ACRN hypervisor supports fixed priority (FP) scheduling, a borrowed virtual time (BVT) [53] scheduler, and static partitioning of cores via a no-operation (NOOP) scheduler similar to Xen’s NULL scheduler. Configuring schedule tables for TT VCPUs at compile time is relevant when considering safety and security. However, for this proof-of-concept (PoC), we preferred setting VCPU schedule tables during runtime via a hypercall, easing development and testing. During startup until the privileged VM sets a schedule table for TT VCPUs and enables TT operation, our implementation utilizes a configurable secondary scheduler (BVT or FP) to dispatch VCPUs. Once the privileged VM 10

Towards Virtual Networking for a Time-Triggered Hypervisor

AUTHORS ’ V ERSION

switches the hypervisor to TT operation via a hypercall, the hypervisor dispatches TT VCPUs according to the intervals configured in the per-core schedule tables. Let n denote the number of entries in a core’s schedule table. A hypervisor schedule table entry at an index 0 ≤ i ≤ n contains its offset ϕi , its size (or relative deadline) Li , a pointer to its associated VCPU ρi (or NULL for idle slots), and a pointer to the next schedule table entry i + 1. We utilize the x86-64 hardware platform’s timestamp counter (TSC) deadline timer to prevent VCPUs from overrunning and to execute the schedule table. For a timer invocation j during hyperperiod hp, the hypervisor checks if the schedule table entry is a VCPU entry, an idle entry, or an alignment entry and proceeds accordingly: VCPU Entry The TT scheduler sets the current schedule table entry to i = (j + 1) mod n, updates the active VCPU pointer, and arms the TSC deadline timer to preempt VCPU execution next at TSC tscj+1 = tscj + Li . •

Idle Entry The TT scheduler invokes the secondary scheduler to dispatch regular VCPUs until the end of the idle slot at tscj+1 = tscj + Li . •

Alignment Entry Let the function g : N → N return the global time at local time tscj ∈ N. The TT scheduler reads the global time g(tscj ) provided by the dependent clock [12, 51] to calculate the runtime deviation ∆ = g(tscj ) − (hp · THP + ϕi ) from the schedule table. If it is ∆ < 0, it means the TT execution is early compared to the intended execution. Thus, the hypervisor must realign by delaying the next TSC deadline timer for ∆ cycles tscj+1 = tscj + Li + ∆. If instead it is ∆ > 0, the TT execution is late, so the hypervisor must shorten the next TSC deadline timer by ∆ cycles tscj+1 = tscj + Li − ∆. •

Lastly, when (j + 1) mod n = 0, the TT scheduler completes a hyperperiod incrementing hp and wrapping back to entry 0. Note that if the misalignment exceeds the table entry size |∆| > Li , the hypervisor must handle the resulting exception, and the TT scheduler must enter a predefined safe state. We can model alignment intervals on the hypervisor and guest OS levels as special TT tasks or VCPUs. Here, we pessimistically dimension alignment intervals and let the SMT-EDF scheduler place them periodically per core and VM. For example, in Fig. 2, we can identify alignment intervals on the hypervisor-level of node 2 at time 0.0 ms and at the guest-OS level at times 3.6 ms, 3.8 ms and 4.0 ms.

5.2.2

IEEE 802.1Qbv VirtIO Network

We extended the ACRN DM’s VirtIO network implementation to support up to eight transmit-receive virtqueue pairs through multi-queue TAP devices. A virtqueue is a shared memory region with a ring buffer between the privileged and a user VM. We map each TX and RX virtqueue to a distinct pthread that implements the TX and RX threads described in Sec. 3.2. We acknowledge that the Linux kernel’s vhost virtual networking backend, also available in ACRN’s privileged VM, already supports multi-queue operation serving TX and RX virtqueues by distinct kernel threads. However, we found an implementation via pthreads in the ACRN DM more straightforward for a PoC. The privileged VM in our setup runs a time-triggered Linux kernel [23], enabling it to dispatch TX and RX pthreads of IEEE 802.1Qbv egress and ingress queues according to schedule tables generated by our EDF-SMT scheduler as described in Sec. 5.2, enforcing the virtual network’s IEEE 802.1Qbv quasi-compliant operation. We say quasi-compliant, since to a user VM, the virtual multi-queue NIC is transparent and, presuming a GNU/Linux guest, the OS can configure a TAPRIO qdisc as it would for a passthrough physical NIC. Nevertheless, the TT privileged VM only provides timing guarantees on the corresponding virtual link if, in addition, a correctly aligned (c.f. Sec. 4.4) schedule table entry for the virtqueue’s TX task exists. Furthermore, contrary to the IEEE 802.1Qbv standard that enforces strict timing on the egress queue only, for strict timing guarantees in our TT virtual network, we also require a schedule table entry for the virtqueue’s RX task; however, its configuration and existence remain transparent to a receiving VM. The TT operation of TX and RX virtqueues removes notification overheads compared to the regular, non-TT operation. In regular operation, a sending user VM’s VirtIO frontend driver notifies the target virtqueue of the new data, resulting in a VM exit and the hypervisor injecting a virtual interrupt into the privileged VM. In the privileged VM, the interrupt invokes the DM to signal the corresponding TX pthread to read and forward data from the virtqueue. Similarly, on the receive path in regular operation, the Linux bridge queues frames in the target VM’s TAP device, resulting in a callback that notifies the corresponding virtqueue’s RX pthread. The RX pthread writes frames from the TAP device to its RX virtqueue and notifies the target VM via a virtual interrupt once completed. In contrast, in TT operation, we disable virtqueue notifications on the send and receive paths since we know a priori by the schedule tables when user VMs send and receive frames, rendering notifications moot. 11

Towards Virtual Networking for a Time-Triggered Hypervisor

6

AUTHORS ’ V ERSION

Experimental Evaluation

Our experimental evaluation of the proposed time-triggered virtual networking is two-part. First, we evaluate the schedulability and runtime of the SMT-EDF offline scheduler for an increasing number of VMs with time-triggered VCPUs, considering inter-VM communication and external communication between VMs of two virtualized end systems. By increasing the number of VMs connected to the software bridge in a privileged VM, we automatically also increase the number of virtual links. Secondly, we present our testbed consisting of an industrial edge computing device running TT ACRN and time-triggered GNU/Linux in the privileged and user VMs executing generated task, stream, virtual network, and VCPU schedule tables. We report our findings, executing TT tasks with non-trivial dependencies in GNU/Linux VMs on the virtualized end system. 6.1 6.1.1

Schedulability and Runtime System Parameters

Before we could generate schedules, we needed to to instantiate the system parameters introduced as part of the model and the correctness constraints (c.f. Sec. 3 and 4), namely, the task context switch overhead δτ (ρ), the VCPU context switch overhead δρ (c), the TT TX and RX tasks’ TX and RX delays δ tx and δ rx , the guest OS network stack’s TX and RX overheads otx and orx , and the clock synchronization precision Π. The target hardware platform is a commercial edge computing device featuring an Intel Atom E3950 multicore processor with four cores at 1.6 GHz each and 8 GiB main memory. We measured the task context switch time δτ (ρ) forcing two high priority processes to repeatedly preempt each other by alternately reading from blocking pipes [54]. In between preemptions, each process performed strided memory reads/and writes to incur worst-case cache interference [55]. The measurement tasks took timestamps before each pipe read to calculate the task context switch time. We could not apply the same methodology to measure the VCPU context switch time δρ (c) since there exists no standard mechanism to force alternating preemptions between the VCPUs of a hypervisor. Therefore, we instrumented a x86-64 model specific register (MSR) to cause a VM exit upon read access. A simple dispatch logic in the MSR access VM exit handler forced a VCPU context switch. To measure the VCPU context switch time, two VMs with one VCPU each shared a processor core. Each VCPU executed a simple measurement task, that, again, performed strided memory reads/and writes to incur worst-case cache interference and then read the instrumented MSR to force a VCPU preemption and context switch to the partner measurement VM’s VCPU. The measurement task took timestamps before each MSR read to calculate the VCPU context switch time. For task and VCPU context switch times we collected 2 · 105 data points each. To determine δ tx , δ rx , otx , and orx , we generated tables for two TT tasks executing on distinct VCPUs sharing cores and communicating via a Qbv stream. This presented a mutual dependency, since schedule generation required us to already know said parameters. Therefore, we presumed overly pessimistic values of δ tx∗ = 1 ms, δ rx∗ = 1 ms, otx∗ = 1 ms, and orx∗ = 1 ms. We further instantiated the task and VCPU context switch times δτ (c) = 115 µs and δρ (c) = 165 µs to the max. measured value by the method described before and the precision to Π = 0 since for this measurement VMs shared a host. We executed the resulting set of schedule tables for 30 minutes and measured the actual values of δ tx , δ rx , otx and orx instrumenting the ACRN DM. We synchronized the dependent clock [12] of the privileged VMs on the two industrial edge computing devices using LinuxPTP. We derived the upper bound on the precision Π = 43 ns as in [12]. Furthermore, we report the measured synchronization precision Π∗ with Π∗ ≤ Π. Fig. 3 summarizes the measurement results. The box plots’ whiskers capture the Q 0.05 and Q 0.95 quantiles, the red line the median, and the red × marks the max measured value. Our PoC based on GNU/Linux VMs and an uncertified open-source hypervisor has only limited applicability for hard real-time systems [56]. However, using GNU/Linux may be viable in safety-critical systems considering certain tradeoffs [57, 58]. For instance, one such trade-off arises from our choice of the system parameters to generate schedules. Using the median or Q, 0.95 measured values leads to higher system utilization but may result in occasional deadline misses, whereas using the maximum measured value (or an analytical worst-case) ensures no deadline misses at the expense of schedulability. Note that in practice, there are varying system requirements concerning the rate of deadline misses we deem tolerable. In industrial systems [59, 60], periodic critical events map to either isochronous TSN streams, which cannot miss any deadlines, or to cyclic TSN streams, which can tolerate 1 − 4 consecutive frame drops. Typically, we design industrial and automotive systems to tolerate some degree of deadline misses. 6.1.2

Experimental Results

Our schedulability experiments for synthetic task sets and streams use parameters from two real-world automotive benchmarks, referred to as TTTech [15] (c.f. Sec. IV.B) and WATERS [61]. For each benchmark, we evaluate the 12

Towards Virtual Networking for a Time-Triggered Hypervisor

runtime 2h

75%

90s

50%

1s

25%

10ms

Runtime

100%

timeout

10 /1 10 4 /2 10 6 /5 20 0 /1 20 4 /2 20 6 /5 30 0 /1 30 4 /2 30 6 /5 0

0% 10 /1 10 4 /2 10 6 /5 20 0 /1 20 4 /2 20 6 /5 30 0 /1 30 4 /2 30 6 /5 0

Schedulability

schedulability

AUTHORS ’ V ERSION

max

q0.95

#streams/#VMs

Figure 4: Schedulability and runtime using max. and q0.95 system parameters

schedulability and runtime when using the Q 0.95 system parameters compared to the max measured system parameters (c.f. Fig. 3) for an increasing number of VMs and streams on two virtualized end systems whose privileged VMs have access to passthrough NICs with a direct physical link.

o tx

) o rx

(ρ

δτ

)

(c

δρ

δ tx

δ rx

Π∗

Time [µs]

For both benchmarks, we randomly generated 10, 20, and 300 30 IEEE 802.1Qbv streams selecting stream sizes from the set {1, 2, 4, 8, 16, 32, 64, 3000} byte with distribution 250 {0.35, 0.49, 0.13, 0.008, 0.013, 0.005, 0.002, 0.002} re200 sulting in 20, 40, 60, and 80 communicating TT tasks. For the TTTech benchmark [15], we generated a to150 tal 120 TT tasks with periods randomly selected from 100 the set {5, 10, 20, 40, 80} ms with a distribution of {0.09166, 0.2666, 0.125, 0.19166, 0.325}, i.e., if there 50 are n ∈ {20, 40, 60} communicating tasks we addi0 tionally generate (120 − n) free TT tasks. We randomly picked the WCETs utilizing the Randfixedsum algorithm [62, 63] to approximate the per-core utilization of approximately 50% including context switch Figure 3: System overheads overheads. For the WATERS benchmark [61], we randomly selected TT tasks’ periods from the set T := {1, 2, 5, 10, 20, 50, 100, 200, 1000} ms with distribution {0.03, 0.02, 0.02, 0.25, 0.25, 0.03, 0.2, 0.01, 0.04}. Given a task’s random period Ti ∈ T at index i, we select its corresponding average-case execution time at index i from the set ACET s = {5, 4.2, 11.04, 10.09, 8.74, 17.56, 10.53, 2.56, 0.43}µs and its minimum and maximum WCET factors fmin and fmax from the sets Fmin = {1.3, 1.54, 1.13, 1.06, 1.06, 1.13, 1.02, 1.03, 1.84} and Fmax = {29.11, 19.04, 18.44, 30.03, 15.61, 7.76, 8.88, 4.9, 4.75}, respectively. Then, we pick a random WCET factor f ∈ [fmin , fmax ] and calculate the task’s WCET Ci = f · ACET s[i]. We assigned each generated task to a VCPU of a core with spare capacity, and repeated the procedure until it reaches the per-core target utilization of approximately 50% including context switch overheads. For a given pair τi , τj TT tasks communicating via a stream sk , we assume that they share a period, i.e., we do not consider multi-rate dependencies, and set their end-to-end requirement equals sk their period E(τi −→ τj ) = Ti = Tj .

For each schedulability experiment’s configuration, we generated and scheduled 10 random task sets. We assumed a realistic configuration of the GNU/Linux privileged and user VMs. Therefore, for each target device, we statically allocated core 0 to host its privileged VM’s VCPU with the TT TX and RX tasks. We configured each user VM i with 2 VCPUs so that VCPU ρi0 acted as a bookkeeping core isolating the TT VCPU ρi1 1 . Bookkeeping VCPUs {ρi0 } shared core 1 scheduled with BVT whereas TT VCPUs {ρi1 } were equally distributed to the remaining cores 2 and 3. To counter a high schedule generation runtime, 14 EDF-SMT scheduler instances solved experiment configurations in parallel on an AMD Ryzen 7 57003D with 8 physical cores (16 logical cores) at 2.64 GHz each running Kubuntu 25.04 with Linux kernel v6.14.0 accessing 128 GiB of RAM. We set an EDF-SMT scheduler timeout of 2 h. Fig. 4 illustrates the schedulability and runtime results for the TTTech benchmark [15]. The left y-axis we shows the schedulability, i.e., how many instances were schedulable until the time-out, and the right, logarithmic y-axis shows the 1

kernel cmd. line parameters: rcu_nocb=1 rcu_nocb_poll nohz_full=1 isolcpus=1

13

Towards Virtual Networking for a Time-Triggered Hypervisor

AUTHORS ’ V ERSION

synthesis runtime. The x-axis displays the system size in terms of number of streams and number of VMs. We can see that when comparing max. and mean used delays during schedule synthesis, for max. parameters the schedulability starts declining already for smaller system sizes due to the high delay values, whereas with the q95 parameters, the schedulability remains high for larger system sizes. Both the number of streams and number of VMs influence the schedulability and runtime. The WATERS benchmark timed out for all instances mainly due to the big difference between the lowest and the highest periods and is not shown here. For such systems, either a separation on different physical cores based on period values [64], period transformation [65], or a pure heuristic-based solution are preferable (e.g. [66]).

Frequency

Our TT testbed consists of single edge computing deavg = −2.22 µs, std = 32.71 µs vice (c.f. Sec. 6.1.1) running ACRN v2.4 with TT VCPU min = −1467.29 µs, max = 996.28 µs scheduling, the privileged VM hosting the TT virtual net1200 works’ TX and RX tasks, and TT user VMs. The number of user VMs hosted on the edge computing device is 1000 limited by the available persistent memory to store VM images. Currently, we are hosting 6 user VMs (as de800 scribed in Sec. 6.1.2) with 1 bookkeeping VCPU and 1 TT VCPU each. We assigned the bookkeeping VCPUs 600 to core 1 and the TT VCPUs to cores 2 or 3, respectively, 400 resulting in a total of 6 bookkeeping VCPUs on core 1 and 3 TT VCPUs each per cores 2 and 3. Exploring 200 the schedule tables, we found that the GNU/Linux-based implementation requires additional system-specific con0 straints to correctly handle overheads resulting from the -25 -50 0 25 50 Linux kernel’s software-interrupt handling and the readcopy-update (RCU) subsystem. For now these unpreEnd-to-End Latency Deviation [µs] dictable overheads in the GNU/Linux prototype resulted in an increasing number of failed streams. For up to 5 Figure 5: End-to-end latency deviation from schedule tables TT streams, 60 free TT tasks resulting in a total target for 5 streams. utilization of 50% per TT core, and interfering iperf network traffic between VMs, we found 95% of stream jobs successfully completing. Fig. 5 shows the deviation of the measured end-to-end latency from the end-to-end latency dictated by the schedule tables. Despite outliers expected in a GNU/Linux-based implementation, we can see that the measured end-to-end latency of the 5 TSN streams follows the expected end-to-end latency tightly only deviating by ±12 µs.

7

Conclusion

We have proposed a VirtIO-based virtual network that realizes IEEE 802.1Qbv quasi-compliant inter-VM communication for time-triggered hypervisors, providing predictable timing for critical messages. We presented our VirtIO-based virtual network architecture and derived network-level scheduling constraints that emerge from the proposed solution’s properties. Schedulability and schedule synthesize runtime experiments for two benchmark task sets have highlighted the difficulty of generating global schedule tables considering realistic systems parameters. To the authors knowledge, our PoC utilizing the ACRN hypervisor is the first demonstrating tight end-to-end latency guarantees of TT tasks hosted on TT VCPUs communicating via a TT virtual network. Addressing present drawbacks of our PoC requires a close interplay of (operating) system engineering and modeling resulting system-specific constraints.

Acknowledgements The work is co-funded by the Chips Joint Undertaking (Chips JU) and National Authorities (FFG Grant Agreement No. 50307277) under grant agreement No. 101139789 (HAL4SDV project).

14

Towards Virtual Networking for a Time-Triggered Hypervisor

AUTHORS ’ V ERSION

References [1] Gernot Heiser. Virtualizing embedded systems - why bother? In Proc. DAC, 2011. [2] Hongyu Pei Breivold and Kristian Sandström. Internet of things for industrial automation – challenges and technical solutions. In Proc. DSDIS, 2015. doi:10.1109/DSDIS.2015.11. Johannes Deichmann, Martin Kellner, Patrick Keuntje, and Julia [3] Ondrej Burkacky, Werra. Rewiring car electronics and software architecture for the ‘roaring 2020s’. https://www.mckinsey.com/industries/automotive-and-assembly/our-insights/ rewiring-car-electronics-and-software-architecture-for-the-roaring-2020s, 2021. [4] Georg Niedrist. Deterministic architecture and middleware for domain control units and simplified integration process applied to ADAS. In Fahrerassistenzsysteme 2016. Springer Fachmedien Wiesbaden, 2018. doi:https://doi.org/10.1007/978-3-658-21444-9. [5] Gerald J. Popek and Robert P. Goldberg. Formal requirements for virtualizable third generation architectures. Commun. ACM, 17(7):412–421, jul 1974. ISSN 0001-0782. doi:10.1145/361011.361073. URL https://doi. org/10.1145/361011.361073. [6] Sisu Xi, Justin Wilson, Chenyang Lu, and Christopher Gill. RT-Xen: Towards real-time hypervisor scheduling in xen. In Proc. EMSOFT, 2011. [7] Sisu Xi, Meng Xu, Chenyang Lu, Linh T. X. Phan, Christopher Gill, Oleg Sokolsky, and Insup Lee. Real-time multi-core virtual machine scheduling in Xen. In Proc. EMSOFT, 2014. doi:10.1145/2656045.2656061. [8] Arvind Easwaran, Insik Shin, and Insup Lee. Optimal virtual cluster-based multiprocessor scheduling. Real Time Syst., 43(1):25–59, 2009. doi:10.1007/S11241-009-9073-X. URL https://doi.org/10.1007/ s11241-009-9073-x. [9] Ralf Ramsauer, Jan Kiszka, Daniel Lohmann, and Wolfgang Mauerer. Look mum, no VM exits! (almost). CoRR, abs/1705.06932, 2017. URL http://arxiv.org/abs/1705.06932. [10] Hao Li, Xuefei Xu, Jinkui Ren, and Yaozu Dong. ACRN: a big little hypervisor for iot development. In Jennifer B. Sartor, Mayur Naik, and Chris Rossbach, editors, Proceedings of the 15th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, VEE 2019, Providence, RI, USA, April 14, 2019, pages 31–44. ACM, 2019. doi:10.1145/3313808.3313816. URL https://doi.org/10.1145/3313808.3313816. [11] José Martins, Adriano Tavares, Marco Solieri, Marko Bertogna, and Sandro Pinto. Bao: A lightweight static partitioning hypervisor for modern multi-core embedded systems. In Marko Bertogna and Federico Terraneo, editors, Workshop on Next Generation Real-Time Embedded Systems, NG-RES@HiPEAC 2020, January 21, 2020, Bologna, Italy, volume 77 of OASIcs, pages 3:1–3:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. doi:10.4230/OASICS.NG-RES.2020.3. URL https://doi.org/10.4230/OASIcs.NG-RES.2020.3. [12] Jan Ruh, Wilfried Steiner, and Gerhard Fohler. Clock synchronization in virtualized distributed real-time systems using ieee 802.1as and acrn. IEEE Access, 9:126075–126094, 2021. doi:10.1109/ACCESS.2021.3111045. [13] Jan Ruh. Towards a robust mmio-based synchronized clock for virtualized edge computing devices. In Proc. ETFA, pages 01–08, 2021. doi:10.1109/ETFA45728.2021.9613473. [14] Jan Ruh and Silviu S. Craciunas. End-to-end schedulability of virtualized distributed time-triggered systems. In Proceedings of the 32nd International Conference on Real-Time Networks and Systems, RTNS 2024, Porto, Portugal, November 6-8, 2024, pages 242–254. ACM, 2024. doi:10.1145/3696355.3696364. URL https: //doi.org/10.1145/3696355.3696364. [15] Anaïs Finzi, Silviu S. Craciunas, and Marc Boyer. Integrating sporadic events in time-triggered systems via affine envelope approximations. In 2024 IEEE 30th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 15–28, 2024. doi:10.1109/RTAS61025.2024.00010. [16] A. Cameron Macdonell. AAINR89468.

Shared-memory optimizations for virtual machines.

PhD thesis, CAN, 2011.

[17] The Linux Foundation. A Big Little Hypervisor for IoT Development. https://projectacrn.org/, 2021. [Online; accessed 16-January-2025]. [18] Rusty Russell. Virtio: Towards a de-facto standard for virtual i/o devices. SIGOPS Oper. Syst. Rev., 42(5), 2008. ISSN 0163-5980. doi:10.1145/1400097.1400108. [19] IEEE. Ieee standard for local and metropolitan area networks – bridges and bridged networks - amendment 25: Enhancements for scheduled traffic. IEEE Std 802.1Qbv-2015, 2016. doi:10.1109/IEEESTD.2016.8613095. 15

Towards Virtual Networking for a Time-Triggered Hypervisor

AUTHORS ’ V ERSION

[20] MotionWise: Safe Vehicle Software Platform, 2018. software-products/motionwise.

URL https://www.tttech-auto.com/

[21] Marija Sokcevic. Partitioned Complexity, 2020. knowledge-platform/partitioned-complexity.

URL https://www.tttech-auto.com/

[22] Gautam Gala, Javier Castillo Rivera, and Gerhard Fohler. Work-in-progress: Cloud computing for time-triggered safety-critical systems. In Proc. RTSS, pages 516–519, 2021. doi:10.1109/RTSS52674.2021.00054. [23] Paraskevas Karachatzis, Jan Ruh, and Silviu S. Craciunas. An evaluation of time-triggered scheduling in the linux kernel. In Proc. RTNS. ACM, 2023. [24] Gautam Gala, Isser Kadusale, and Gerhard Fohler. Joint time-and event-triggered scheduling in the linux kernel. CoRR, abs/2306.16271, 2023. doi:10.48550/ARXIV.2306.16271. URL https://doi.org/10.48550/arXiv. 2306.16271. [25] Intel Corporation. TSN Documentation Project for Linux. https://tsn.readthedocs.io/index.html, 2019. [Online; accessed 14-January-2025]. [26] Bert Hubert. tc(8) — Linux manual page. https://man7.org/linux/man-pages/man8/tc.8.html, 2001. [Online; accessed 16-November-2022]. [27] Intel. Configuring TSN Qdiscs. https://tsn.readthedocs.io/qdiscs.html, 2019. [Online; accessed 14-January-2025]. [28] Donato Ferraro, Luca Palazzi, Federico Gavioli, Michele Guzzinati, Andrea Bernardi, Benjamin Rouxel, Paolo Burgio, and Marco Solieri. Time-sensitive autonomous architectures. Real Time Syst., 59(4):568–608, 2023. doi:10.1007/S11241-023-09404-2. URL https://doi.org/10.1007/s11241-023-09404-2. [29] Virtual Device Reference: vdev shmem. URL https://www.qnx.com/developers/docs/7.0.0/#com.qnx. doc.hypervisor.user/topic/vdev_ref/vdev_shmem.html. [30] Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex Ho, Rolf Neugebauer, Ian Pratt, and Andrew Warfield. Xen and the art of virtualization. In Michael L. Scott and Larry L. Peterson, editors, Proceedings of the 19th ACM Symposium on Operating Systems Principles 2003, SOSP 2003, Bolton Landing, NY, USA, October 19-22, 2003, pages 164–177. ACM, 2003. doi:10.1145/945445.945462. URL https: //doi.org/10.1145/945445.945462. [31] Luca Leonardi, Lucia Lo Bello, and Gaetano Patti. Towards time-sensitive networking in heterogeneous platforms with virtualization. In 25th IEEE International Conference on Emerging Technologies and Factory Automation, ETFA 2020, Vienna, Austria, September 8-11, 2020, pages 1155–1158. IEEE, 2020. doi:10.1109/ETFA46521.2020.9212116. URL https://doi.org/10.1109/ETFA46521.2020.9212116. [32] Gero Schwäricke, Rohan Tabish, Rodolfo Pellizzoni, Renato Mancuso, Andrea Bastoni, Alexander Zuepke, and Marco Caccamo. A real-time virtio-based framework for predictable Inter-VM communication. In Proc. RTSS, 2021. doi:10.1109/RTSS52674.2021.00015. [33] Renato Mancuso, Roman Dudko, Emiliano Betti, Marco Cesati, Marco Caccamo, and Rodolfo Pellizzoni. Real-time cache management framework for multi-core architectures. In 19th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2013, Philadelphia, PA, USA, April 9-11, 2013, pages 45–54. IEEE Computer Society, 2013. doi:10.1109/RTAS.2013.6531078. URL https://doi.org/10.1109/RTAS. 2013.6531078. [34] Heechul Yun, Gang Yao, Rodolfo Pellizzoni, Marco Caccamo, and Lui Sha. Memory bandwidth management for efficient performance isolation in multi-core platforms. IEEE Trans. Computers, 65(2):562–576, 2016. doi:10.1109/TC.2015.2425889. URL https://doi.org/10.1109/TC.2015.2425889. [35] Zonghong Li, Guoqi Xie, Wenhong Ma, Xiongren Xiao, Yong Xie, Wei Ren, and Wanli Chang. RTISM: Real-time inter-vm communication based on shared memory for mixed-criticality flows. In Proc. RTSS, 2023. doi:10.1109/RTSS59052.2023.00032. [36] João Peixoto, José Martins, David Cerdeira, and Sandro Pinto. Birtio: Virtio for real-time network interface sharing on the bao hypervisor. IEEE Access, 12:185434–185447, 2024. doi:10.1109/ACCESS.2024.3512777. URL https://doi.org/10.1109/ACCESS.2024.3512777. [37] Institute of Electrical and Electronics Engineers. Ieee standard for local and metropolitan area networks– timing and synchronization for time-sensitive applications - corrigendum 1: Technical and editorial corrections. IEEE Std 802.1AS-2020/Cor 1-2021 (Corrigendum to IEEE Std 802.1AS-2020), pages 1–33, 2022. doi:10.1109/IEEESTD.2022.9765410. 16

Towards Virtual Networking for a Time-Triggered Hypervisor

AUTHORS ’ V ERSION

[38] Hermann Kopetz and Wilfried Steiner. Real-Time Systems - Design Principles for Distributed Embedded Applications, Third Edition. Springer, 2022. ISBN 978-3-031-11991-0. doi:10.1007/978-3-031-11992-7. URL https://doi.org/10.1007/978-3-031-11992-7. [39] Hermann Kopetz. Sparse time versus dense time in distributed real-time systems. In Proceedings of the 12th International Conference on Distributed Computing Systems, Yokohama, Japan, June 9-12, 1992, pages 460–467. IEEE Computer Society, 1992. doi:10.1109/ICDCS.1992.235008. URL https://doi.org/10.1109/ICDCS. 1992.235008. [40] Damir Isovic and Gerhard Fohler. Handling mixed sets of tasks in combined offline and online scheduled real-time systems. Real Time Syst., 43(3):296–325, 2009. doi:10.1007/S11241-009-9088-3. URL https: //doi.org/10.1007/s11241-009-9088-3. [41] Institute of Electrical and Electronics Engineers. Time-Sensitive Networking Task Group. https://www. ieee802.org/1/pages/tsn.html, 2017. [Online; accessed 09-November-2022]. [42] IEEE. 802.1Qbv - Enhancements for Scheduled Traffic, 2016. URL https://standards.ieee.org/ standard/802_1Qbv-2015.html. [43] Silviu S. Craciunas, Ramon Serna Oliver, Martin Chmelík, and Wilfried Steiner. Scheduling real-time communication in IEEE 802.1qbv time sensitive networks. In Alain Plantec, Frank Singhoff, Sébastien Faucou, and Luís Miguel Pinho, editors, Proceedings of the 24th International Conference on Real-Time Networks and Systems, RTNS 2016, Brest, France, October 19-21, 2016, pages 183–192. ACM, 2016. doi:10.1145/2997465.2997470. URL https://doi.org/10.1145/2997465.2997470. [44] Silviu S. Craciunas and Ramon Serna Oliver. Out-of-sync schedule robustness for time-sensitive networks. In 17th IEEE International Conference on Factory Communication Systems, WFCS 2021, Linz, Austria, June 9-11, 2021, pages 75–82. IEEE, 2021. doi:10.1109/WFCS46889.2021.9483602. URL https://doi.org/10.1109/ WFCS46889.2021.9483602. [45] Virtual I/O Device (VIRTIO) Version 1.2. Committee Specification 01, OASIS, July 2022. URL https: //docs.oasis-open.org/virtio/virtio/v1.2/cs01/virtio-v1.2-cs01.html. Edited by Michael S. Tsirkin and Cornelia Huck. [46] Wilfried Steiner. An evaluation of smt-based schedule synthesis for time-triggered multi-hop networks. In Proceedings of the 31st IEEE Real-Time Systems Symposium, RTSS 2010, San Diego, California, USA, November 30 - December 3, 2010, pages 375–384. IEEE Computer Society, 2010. doi:10.1109/RTSS.2010.25. URL https://doi.org/10.1109/RTSS.2010.25. [47] Silviu S. Craciunas and Ramon Serna Oliver. Smt-based task- and network-level static schedule generation for timetriggered networked systems. In Mathieu Jan, Belgacem Ben Hedia, Joël Goossens, and Claire Maiza, editors, 22nd International Conference on Real-Time Networks and Systems, RTNS ’14, Versaille, France, October 8-10, 2014, page 45. ACM, 2014. doi:10.1145/2659787.2659812. URL https://doi.org/10.1145/2659787.2659812. [48] Silviu S. Craciunas and Ramon Serna Oliver. Combined task- and network-level scheduling for distributed time-triggered systems. Real-Time Systems, 52, 03 2016. doi:10.1007/s11241-015-9244-x. [49] Leonardo Mendonça de Moura and Nikolaj S. Bjørner. Z3: an efficient SMT solver. In C. R. Ramakrishnan and Jakob Rehof, editors, Tools and Algorithms for the Construction and Analysis of Systems, 14th International Conference, TACAS 2008, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2008, Budapest, Hungary, March 29-April 6, 2008. Proceedings, volume 4963 of Lecture Notes in Computer Science, pages 337–340. Springer, 2008. doi:10.1007/978-3-540-78800-3_24. URL https://doi. org/10.1007/978-3-540-78800-3_24. [50] C. L. Liu and James W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM, 20(1):46–61, 1973. doi:10.1145/321738.321743. URL https://doi.org/10.1145/321738.321743. [51] Jan Ruh, Wilfried Steiner, and Gerhard Fohler. IEEE 802.1as multi-domain aggregation for virtualized distributed real-time systems. In 53rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2023 - Supplemental Volume, Porto, Portugal, June 27-30, 2023, pages 70–76. IEEE, 2023. doi:10.1109/DSNS58398.2023.00027. URL https://doi.org/10.1109/DSN-S58398.2023.00027. [52] Fabrice Bellard. Qemu, a fast and portable dynamic translator. In Proceedings of the FREENIX Track: 2005 USENIX Annual Technical Conference, April 10-15, 2005, Anaheim, CA, USA, pages 41–46. USENIX, 2005. URL http://www.usenix.org/events/usenix05/tech/freenix/bellard.html. [53] Kenneth J. Duda and David R. Cheriton. Borrowed-virtual-time (bvt) scheduling: supporting latency-sensitive threads in a general-purpose scheduler. SIGOPS Oper. Syst. Rev., 33(5):261–276, December 1999. ISSN 0163-5980. doi:10.1145/319344.319169. URL https://doi.org/10.1145/319344.319169. 17

Towards Virtual Networking for a Time-Triggered Hypervisor

AUTHORS ’ V ERSION

[54] John K. Ousterhout. Why aren’t operating systems getting faster as fast as hardware? In Proceedings of the Usenix Summer 1990 Technical Conference, Anaheim, California, USA, June 1990, pages 247–256. USENIX Association, 1990. [55] Chuanpeng Li, Chen Ding, and Kai Shen. Quantifying the cost of context switch. In Proceedings of the Workshop on Experimental Computer Science, Part of ACM FCRC, San Diego, CA, USA, 13-14 June 2007, page 2. ACM, 2007. doi:10.1145/1281700.1281702. URL https://doi.org/10.1145/1281700.1281702. [56] Federico Reghenzani, Giuseppe Massari, and William Fornaciari. The real-time linux kernel: A survey on preempt_rt. ACM Comput. Surv., 52(1), feb 2019. ISSN 0360-0300. doi:10.1145/3297714. URL https: //doi.org/10.1145/3297714. [57] L. Abeni, A. Goel, C. Krasic, J. Snow, and J. Walpole. A measurement-based analysis of the real-time performance of linux. In Proceedings. Eighth IEEE Real-Time and Embedded Technology and Applications Symposium, pages 133–142, 2002. doi:10.1109/RTTAS.2002.1137388. [58] Daniel Bristot de Oliveira, Daniel Casini, Rômulo Silva de Oliveira, and Tommaso Cucinotta. Demystifying the Real-Time Linux Scheduling Latency. In Marcus Völp, editor, 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020), volume 165 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1– 9:23, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-152-8. doi:10.4230/LIPIcs.ECRTS.2020.9. URL https://drops.dagstuhl.de/entities/document/10.4230/ LIPIcs.ECRTS.2020.9. [59] A Ademaj, D Puffer, D Bruckner, G Ditzel, L Leurs, MP Stanica, P Didier, R Hummen, R Blair, and T Enzinger. Industrial automation traffic types and their mapping to qos/tsn mechanisms. TSN mechanisms, 3, 2019. [60] Astrit Ademaj, David Puffer, Dietmar Bruckner, George Ditzel, Ludwig Leurs, Marius-Petru Stanica, Paul Didier, René Hummen, Richard Blair, and Thomas Enzinger. Time sensitive networks for flexible manufacturing testbed description of converged traffic types. White Paper IIC:WHT:IS3:V1.0:PB, Industrial Internet Consortium, April 2018. URL https://www.iiconsortium.org/pdf/IIC_TSN_Testbed_Traffic_Whitepaper_20180418. pdf. [61] Simon Kramer, Dirk Ziegenbein, and Arne Hamann. Real world automotive benchmarks for free. In 6th International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS), volume 130, 2015. [62] Paul Emberson. Taskgen v1.0. https://github.com/jlelli/taskgen. [63] Paul Emberson, Roger Stafford, and Robert I Davis. Techniques for the synthesis of multiprocessor tasksets. In Proceedings of the 1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS 2010), pages 6–11, 2010. [64] Hamid Reza Faragardi, Björn Lisper, Kristian Sandström, and Thomas Nolte. An efficient scheduling of autosar runnables to minimize communication cost in multi-core systems. In 7’th International Symposium on Telecommunications (IST’2014), pages 41–48, 2014. doi:10.1109/ISTEL.2014.7000667. [65] Mitra Nasri and Gerhard Fohler. An efficient method for assigning harmonic periods to hard real-time tasks with period ranges. In 2015 27th Euromicro Conference on Real-Time Systems, pages 149–159, 2015. doi:10.1109/ECRTS.2015.21. [66] Ali Syed and Gerhard Fohler. Efficient offline scheduling of task-sets with complex constraints on large distributed time-triggered systems. Real Time Syst., 55(2):209–247, 2019. doi:10.1007/S11241-018-9320-0. URL https: //doi.org/10.1007/s11241-018-9320-0.

18

Errata for “Towards Virtual Networking for a Time-Triggered Hypervisor” (RTNS 2025) Jan Ruh

Silviu S. Craciunas

Jan Korecky

October 13, 2026

This document corrects errors in the formal system model and correctness constraints of the paper “Towards Virtual Networking for a Time-Triggered Hypervisor,” published in the Proceedings of the 33rd International Conference on Real-Time Networks and Systems (RTNS 2025). The errors concern the formal statement of the model and constraints. The schedule synthesis implementation used in the experimental evaluation enforced the intended semantics, so the experimental results and the conclusions of the paper are unaffected. Constraints 1–5 and 8–10 of the paper recapitulate constraints of the RTNS 2024 paper “End-to-End Schedulability of Virtualized Distributed Time-Triggered Systems” (DOI: 10.1145/3696355.3696364) and inherit some of the errors corrected in the errata of that paper.

Erratum 1 — Typographical correction, TX/RX task definitions, Section 3.2 Two corrections apply to the definition of the virtual-network backend tasks. rx ∈ RX v (ρ ), not of T X v (ρ ) as (a) The RX task must be a member of the RX task set, τv,i p p published (likewise in the quantifier prefix of Constraint 12, cf. Erratum 4).

(b) The period of an RX task must be derived from the received streams, Tiv = lcm{Tx | ∀sx ∈ rx }, not from S tx as published. Sv,i v,i

Erratum 2 — Joint unsatisfiability of Constraints 5, 6, and 7, Section 4.2 The first conjunct of Constraint 5 is an alternative to Constraint 6, while its second conjunct is an alternative to Constraint 7. These alternatives must not be applied jointly, but this clarification is missing in the paper. As published, all three constraints are stated over the same universally quantified domain and when applied jointly, they are unsatisfiable. In the implementation, Constraint 6 is only applied if a stream’s first link is a virtual link, and Constraint 7 is only applied if a stream’s last link is a virtual link. Accordingly, the first or second conjunct of Constraint 5 does not apply in the respective case. The paper therefore needs to include the following clarification after Constraint 7: Constraints 5–7 apply mutually exclusively, depending on the type of a stream’s first and last link. If the first link (a, x) of a stream sh is a virtual link, Constraint 6 applies and the first conjunct of Constraint 5 is omitted. Otherwise, the first conjunct of Constraint 5 applies and Constraint 6 is omitted. Analogously, if the last link (y, b) of sh is a virtual link, Constraint 7 applies and the second conjunct of Constraint 5 is omitted. Otherwise, the second conjunct of Constraint 5 applies and Constraint 7 is omitted. Hence, for every stream, exactly one of Constraint 5’s first conjunct and Constraint 6 holds, and exactly one of Constraint 5’s second conjunct and Constraint 7 holds.

1

Erratum 3 — Helper set Rvijk , Section 4.4 Three corrections apply to the helper set for the TX/RX task job segment size constraints. (a) The job-instance mapping is computed as j = ⌊(g · Tf )/Tiv ⌋ using the TX/RX task period Tiv , but the two containment inequalities add the instance offset as j ·Ti , where i is a queue index and Ti is undefined. Both occurrences must read j · Tiv . (b) The published segment-internal reservation {︄ δ tx , if xvijk is a TX task job segment v δ(xijk ) = −δ rx , if xvijk is a RX task job segment carries a sign error: with −δ rx , the upper containment bound ff gh .ϕ + ff gh .L + g · Tf ≤ xijk .ϕ + xijk .L − δ(xvijk ) + j · Tiv permits frames of an RX segment to complete δ rx after the segment ends, contradicting Constraint 12, which reserves δ rx per stream job inside the segment. The definition must read δ(xvijk ) = δ rx for RX task job segments. (c) The helper set is defined only for TT TX tasks. The definition for TT RX tasks is analogous. We can write: x x x x x Rv,x ijk := {Jf g |∀sf ∈ Sv,i , ∀Jf g ∈ Jv,i , ∀ff gh ∈ Ff g : ⌊︂ g · T ⌋︂ f j= ∧ (ff gh .ϕ + g · Tf ≥ xijk .ϕ + j · Tiv ) Tiv

∧ (ff gh .ϕ + ff gh .L + g · Tf ≤ xijk .ϕ + xijk .L − δ(xvijk ) + j · Tiv )}

with x ∈ {tx, rx}.

Erratum 4 — Constraints 11 and 12 (TX/RX Task Job Segment Size), Section 4.4 There are some typos and spurious variables that can be removed, hence the corrected constraints read: Constraint 11 (TX Task Job Segment Size Constraint). tx ∀n ∈ V, ∀v ∈ V n , ∀c ∈ C n , ∀ρp ∈ P(c), ∀τv,i ∈ T X v (ρp ), ∀Jijtx ∈ Jitx , ∀xvijk ∈ Xijtx : )︂ ∑︂ (︂ ∑︂ xvijk .L ≥ δτ (ρp ) + δ tx + ff gh .L ∀Jftxg ∈Rv,tx ijk

∀ff gh ∈Fftxg

Constraint 12 (RX Task Job Segment Size Constraint). rx ∀n ∈ V, ∀v ∈ V n , ∀c ∈ C n , ∀ρp ∈ P(c), ∀τv,i ∈ RX v (ρp ), ∀Jijrx ∈ Jirx , ∀xvijk ∈ Xijrx : (︂ )︂ ∑︂ ∑︂ xvijk .L ≥ δτ (ρp ) + δ rx + ff gh .L v,rx ∀Jfrx g ∈Rijk

∀ff gh ∈Ffrx g

Erratum 5 — Typographical correction, Section 4.2 In the paragraph preceding Constraint 5, “Furthermore, he transmission schedule of the stream sk aligns along its route” must read “Furthermore, the transmission schedule of the stream sh aligns along its route” (the constraint binds sh ).

2

Related documents

• Towards Virtual Networking for a Time-Triggered Hypervisor#1343098
• Docker Containers vs. Virtual Machines: A Comparative Study of Architecture, Performance, Configuration, and Security#1110528
• Docker Containers vs. Virtual Machines: A Comparative Study of Architecture, Performance, Configuration, and Security#919477
• Kirin: Cloud-native WebAssembly Service Orchestration#1160993
• Kirin: Cloud-native WebAssembly Service Orchestration#1144598