System virtualization techniques are gradually applied to embedded systems with the performance improvement of embedded devices; however, there is a large time offset (i.e., deviation) of hundreds of ms between virtual machines (VMs) due to the drift of the virtualization abstraction layer and the jitter phenomenon. It is urgent to significantly reduce this offset by time synchronization techniques. Unfortunately, the current mainstream time synchronization software (e.g., Chrony and LinuxPTP) cannot be used in the embedded virtualized system connected by the fieldbus, such as controller area network (CAN); meanwhile, drift correction-based time synchronization techniques dedicated to CAN bus cannot be utilized for virtualized systems. In this study, we design a general vmPTP, which is a precise time protocol (PTP) for inter-VM communication in embedded virtualized systems based on Linux kernel-based VM (KVM). This is the first time synchronization work focused on embedded virtualized systems. We implement two vmPTP versions based on VirtIO and inter-VM shared memory (IVSHMEM) according to the four message (i.e., packet) exchanges of PTP. We propose an asymmetry compensation strategy to solve the problem of asymmetric rate of I/O operations in the message exchange process, which optimizes the offset computation. We further produce a convergence stopping approach which can continuously converge the offset until the offset is within the given bound and stop. We conduct experimental evaluations on both X86-64 and ARM64 architectures. For two versions of vmPTP, the experimental results show that: 1) the offsets are always within$1~{\mu }$s on two architectures; 2) the offsets are less than that of LinuxPTP and Chrony; and 3) the vmPTP’s CPU and memory utilization on the X86-64 architecture are merely 0.3% and 0.1%, respectively, whereas those on the ARM64 architecture are 3.8% and 0.1%, respectively. We experiment with vmPTP in real-time application and the result demonstrates that vmPTP is feasible and reliable in the real platform.

With the development of the automotive industry toward intelligence and automation, there is a trend of controller area network (CAN) migrating to CAN with flexible data-rate (CAN-FD), where frame packing (i.e., packing signals of various periods, deadlines, and payloads into frames following the standard CAN-FD format) is critical to address the high bandwidth demand with limited resources. Existing works have applied integer linear programming (ILP), which easily gets intractable as the number of signals to be packed increases, or proposed heuristics, which are not able to obtain the optimal solution. In addition, the security model employed does not meet the AUTOSAR SecOC specification. This article reports a novel frame-packing approach for CAN-FD with an AUTOSAR-compliant security model. We establish the theory that extending the existing frame to pack signals with the same period leads to shorter worst-case transmission time (WCTT) and thus lower bus utilization compared to creating a new frame. Following this principle, the design space is tremendously pruned, where the optimal solution is guaranteed to remain. With pruning, we are able to increase the optimally solvable size of the problem from 150 signals to 300 signals, which is sufficient for practical usage. When there are 300 signals, only 10−142 of the original design space needs to be explored. To further improve efficiency, we apply pruning to heuristics. When the signal size is 500, for simulated annealing (SA), the computation time can be reduced by 54.1% and the bus utilization can be saved by 10.5% with pruning being deployed. In addition, we propose the max–min ant system as an alternative, which achieves better bus utilization than SA in shorter computation. Our reported method is generally applicable to other CAN-based distributed networks demanding higher bandwidth as well, such as in industry automation.

As an Ethernet-based communication protocol with timing determinism, TSN (time-sensitive networking) has become a well-recognized promising in-vehicle network solution for increasingly automated automobiles. To satisfy the reliability requirement of safety-critical applications, existing works towards fault-tolerant TSN trade too much bandwidth for redundancy, limiting their scope of applicability. Targeting mixed-critical traffic, which is widely found in practice, we define a shared fault-tolerant segment that is compatible with the TSN standard. It serves the critical flows when faults occur, to improve their reliability and serves the non-critical flows when otherwise, to improve their quality of service (QoS). On top of this, we propose a space-time redundancy scheduling algorithm, aiming to make the most efficient use of bandwidth, i.e., to fulfill both the reliability as well as hard real-time requirements, and maximize the QoS with the least bandwidth. In essence, we formulate a bi-objective design space exploration problem with hundreds of thousands of decision variables and solve it with customized heuristics. Experimental results show that compared to the state-of-the-art methods, our reported work increases the number of critical flows that can be accommodated on a resource-constrained network by 3 to 4 times, and achieve the highest QoS with an average reduction of 60.3% in bandwidth. As the first work along sharing of bandwidth between mixed-critical traffic in fault-tolerant TSN, this idea can be further pursued towards higher efficiency and may be applied in general autonomous systems.

Virtual machines (VMs) have been increasingly deployed in real-time systems to enhance heterogeneous resource sharing. Despite being isolated for security and prevention of failure propagation, VMs need to communicate with each other to complete certain tasks jointly. A real-time inter-VM communication framework has been proposed based on VirtIO, which is in essence a mechanism of message passing with high latency and low scalability on data amount. In contrary, IVSHMEM implements inter-VM communication with shared memory, which is generally fast and large in throughput. Unfortunately, IVSHMEM does not resolve resource contention between flows and hence cannot be applied in real-time scenarios. In this work, we propose a real-time inter-VM communication framework RTISM built upon shared memory and IVSHMEM. RTISM provides priority-based scheduling and supports mixed-criticality flows. Worst-Case Response Time (WCRT) analysis is reported to bound the end-to-end communication delay and a Limited Priority Assignment (LPA) algorithm is developed to enhance schedulability. Experimental evaluation shows that (i) RTISM has about 4 times higher throughput than the VirtIO-based inter-VM communication framework; (ii) LPA improves schedulability by over 25% compared to the state-of-the-art; (iii) WCRT produces a tight bound.

With the advancement of intelligence and networked automotive, the domain-centralized architecture, which employs time sensitive networking (TSN) as the inter-domain backbone network and control area network with flexible data rate (CAN-FD) as the intra-domain network, has garnered significant attention. However, cross-domain end-to-end communication involves multiple components, and significant disparities between TSN and CAN-FD render response time analysis within domain-centralized architecture for mixed-critical traffic exceptionally complex. In this paper, we develop a cross-domain with TSN and CAN-FD end-to-end response time evaluation tool, which analyzes the response time of mixed-critical traffic under different design options segment by segment. We specifically analyze the waiting times of different messages in the domain control unit when faced with the design options of one-to-one and multi-to-one conversion of CAN-FD and TSN frames. The proposed evaluation tool can be easily extended to different design options to support more application scenarios. Theoretical computational analysis and real hardware measurements show the effectiveness of our tool.

Retention, with its powerful energy-saving effect and negligible switching delay, offers the advantages of Power Gating (PG) and Clock Gating (CG), and has gradually been adopted into the processor power management systems by both AMD and Intel. However, there has been no research on how to integrate retention to achieve energy-efficient task scheduling. Furthermore, although most commercial chips support per-cluster configurations to achieve energy saving, existing energy-efficient works often underutilize all cores in the cluster, resulting in numerous static power from unused cores. In this paper, we propose a task partitioning algorithm to optimize energy consumption among clusters. We further study energy-efficient scheduling of directed acyclic graph (DAG) tasks with arbitrary deadlines on multicore platforms, which is the first work to integrate the per-cluster retention to reduce power consumption by fully utilizing the used clusters. The experimental results verify that our approach can increase the retention time by 21.24% and reduce the static energy consumption in the idle state by 45.81% compared to retention-based work-conserving scheduling.

Controller area network with flexible data-rate (CAN-FD) has received great attention in automotive cyber–physical systems (ACPSs) due to its high bandwidth and long payload. However, CAN-FD adopts a broadcast message transmission mechanism and lacks security protection, making it extremely vulnerable to cyberattacks. CAN-FD message packing (packing signals into messages) with low bandwidth occupancy (utilization) under security constraints is the prerequisite for running intelligent applications in ACPS. In this work, we implement a two-stage CAN-FD message packing solution to reduce bandwidth utilization and improve signal acceptance rate under security constraints. The first stage solves the message packing problem of minimizing bus bandwidth utilization under security constraints. The second stage aims at improving the signal acceptance rate by repacking signals. Experimental results show that the first stage reduces average bus bandwidth utilization by 135% compared with the unpacking solution, and the second stage improves the average signal acceptance rate by 5% than existing advanced methods.

With the trend towards automated driving, Controller Area Network (CAN) is migrating to CAN with Flexible Data-Rate (CAN-FD), where frame packing (i.e., packing signals of various periods, deadlines, and payloads into frames following the standard CAN- FD format) is critical to address the high bandwidth demand with limited resources. Existing works have applied Integer Linear Programming (ILP), which easily gets intractable as the number of signals to be packed increases, or proposed heuristics, which are not able to obtain the optimal solution. In addition, the security model employed does not meet the AUTOSAR SecOC specification. This paper reports a novel frame packing approach for CAN-FD with an AUTOSAR-compliant security model. We establish the theory that extending the existing frame to pack signals with the same period leads to shorter WCTT (worst-case transmission time) and thus lower bus utilization compared to creating a new frame. Following this principle, the design space is tremendously pruned. As shown in the comprehensive experiments, only 10−9 of the original size or even a smaller portion needs to be explored, while the optimality is kept. The computational time is correspondingly reduced, generating solutions within 15 minutes to large-scale problems that are otherwise intractable with ILP.

Graph clustering aims to identify clusters that feature tighter connections between internal nodes than external nodes. We noted that conventional clustering approaches based on a single vertex or edge cannot meet the requirements of clustering in a higher-order mixed structure formed by multiple nodes in a complex network. Considering the above limitation, we are aware of the fact that a clustering coefficient can measure the degree to which nodes in a graph tend to cluster, even if only a small area of the graph is given. In this paper, we introduce a new cluster quality score, i.e., the local motif rate, which can effectively respond to the density of clusters in a higher-order graph. We also propose a motif-based local expansion and optimization algorithm (MLEO) to improve local higher-order graph clustering. This algorithm is a purely local algorithm and can be applied directly to higher-order graphs without conversion to a weighted graph, thus avoiding distortion of the transform. In addition, we propose a new seed-processing strategy in a higher-order graph. The experimental results show that our proposed strategy can achieve better performance than the existing approaches when using a quadrangle as the motif in the LFR network and the value of the mixing parameter $\mu $ exceeds 0.6.

As the Internet grows in scale and complexity, the benefits of network performance measurements and monitoring are significantly increasing. Sampling-based measurement methods provide adequate techniques for reducing the quantity of control data and attract growing interests. The research reported in this paper, addresses the issue of how to carry out the sampling in an adaptive fashion, so that the accuracy for measuring the quality of service parameters (delay, loss, jitter, throughput) is better if we know something about the traffic type and traffic parameters. Our study proposes and investigates a mechanism that can be set up to adaptively adjust the parameters of the sampling technique. Two realistic network topologies based on MPLS networks are setup to evaluate the proposed adaptive sampling scheme for monitoring and measuring network performance metrics. Compared with conventional sampling techniques (systematic and stratified sampling), simulation results are presented to illustrate that adaptive sampling provides the potential for better monitoring, control, and management of high-performance networks with higher accuracy.