Tight end-to-end worst-case delay bounds for periodic traffic streams are essential for time sensitive networks. In this paper, we provide an algorithm to compute a tight (and accurate) end-to-end worst-case bound by considering distinct topological patterns and the manner in which streams enter and leave switches. This refined analysis uses non-preemptive, strict-priority arbitration mechanism commonly deployed in Ethernet switches. Compared to the state-of-the-art that considers all higher and equal priority interference as contributing to the worst-case bound, we present an analytical approach for computing a tighter worst-case delay bound and prove through discrete event simulations that only a certain number of equal-priority interference streams can actually affect the worst-case case. Our results enable efficient resource allocation and have implications for online re-configuration mechanisms for time-sensitive factory communication systems.

Time Sensitive Networking (TSN) is a set of standards aimed at providing real-time guarantees over existing Ethernet standards. Worst-case traversal time (WCTT) analyses of network traffic are traditionally used in schedulability and routing analyses to determine feasible routes for traffic streams. However, worst-case conditions happen quite rarely from a probabilistic perspective. The typical or average-case traversal times are easier to compute and can be used as an effective design tool for routing and scheduling. In this paper, we present "MaLoC" or Maximally Loaded Common links for routing and scheduling of rate-constrained (RC) traffic in time-sensitive networks (TSN). The proposed framework employs a fully decentralized approach to route and schedule generation with only switch-local information. We further provide a preliminary evaluation of the proposed approach using a simple network topology.

Schedulability analyses for preemptive real-time systems need to take into account cache-related preemption delays (CRPD) caused by preemptions between the tasks. The estimation of the CRPD values must be sound, i.e. it must not be lower than the worst-case CRPD that may occur at runtime, but also should minimise the pessimism of estimation. The existing methods over-approximate the computed CRPD upper bounds by accounting for multiple preemption combinations which cannot occur simultaneously during runtime. This over-approximation may further lead to the over-approximation of the worst-case response times of the tasks, and therefore a false-negative estimation of the system’s schedulability. In this paper, we propose a more precise cache-aware response time analysis for sporadic real-time systems under fully-preemptive fixed priority scheduling. The evaluation shows a significant improvement over the existing state of the art approaches.

In real-time systems that employ preemptive scheduling and cache architecture, it is essential to account as precisely as possible for cache-related preemption delays in the schedulability analysis, as an imprecise estimation may falsely deem the system unschedulable. In the current state of the art for preemptive scheduling of tasks with fixed preemption points, the existing schedulability analysis considers overly pessimistic estimation of cache-related preemption delay, which eventually leads to overly pessimistic schedulability results. In this paper, we propose a novel response time analysis for real-time tasks with fixed preemption points, accounting for a more precise estimation of cache-related preemption delays. The evaluation shows that the proposed analysis significantly dominates the existing approach by being able to always identify more schedulable tasksets.

The increasing industrial demand for handling complex functionalities has influenced the design of hardware architectures for time critical embedded systems, during the past decade. Multicore systems facilitate the inclusion of many complex functionalities, while, at the same time, inducing cache related overheads, as well as adding partitioning complexity to the overall system schedulability. One of the efficient paradigms for controlling and reducing the cache related costs in real-time systems is limited preemptive scheduling (LPS), with its particular instance fixed preemption points scheduling (LP-FPPS), which has been shown to outperform other alternatives as well as has been supported by and investigated in the automotive domain. With respect to the partitioning constraints, partitioned scheduling has been widely used to preruntime allocate tasks to specific cores, resulting in predictable cache-related preemption delays estimations. In this paper, we propose to integrate the LP-FPPS and partitioned scheduling on fixed-priority multicore real-time systems in order to increase the overall system schedulability. We define a new joint approach for task partitioning and preemption point selection, which is based on the computation of the maximum blocking tolerance upon each allocation, thus being able to quantify the schedulability of the taskset on each processor. Furthermore, we investigate the partitioning strategies based on different heuristics, i.e., first fit decreasing and worst fit decreasing, and priority and density taskset orderings. The evaluation performed on randomly generated tasksets shows that in the general case, no single partitioning strategy fully dominates the others. However, the evaluation results reveal that the certain partitioning strategies perform significantly better with respect to the overall schedulability for specific taskset characteristics. The results also reveal that the proposed partitioning strategies outperform fully preemptive and nonpreemptive partitioned scheduling in terms of successful partitioning.

Fixed priority scheduling is used in many real-time systems; however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive earliest deadline first (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP). As this lower bound matches a recently published upper bound for the same quantity, it closes the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, in other words, there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive the exact speed-up factor required to guarantee FP-P feasibility of any constrained-deadline FP-NP feasible task set.

Configuration processes of real-time networks are costly both in terms of time and engineering effort and require the system to be shutdown during the reconfiguration phase thus resulting in significant down time as well. The convergence of IT/OT technologies is bringing a whole world of possibilities for the configuration and management of real-time networks for the automation industry. With software defined networking (SDN) features like the separation of the data and control plane and standards like IEEE 802.1 developed with the goal of adding deterministic capabilities to traditionally dynamic switched Ethernet networks, the plug and play paradigm is almost around the corner. In this paper, we go one step further and start looking into the self-configuration of real-time networks. To achieve that we propose to introduce a Configuration Agent in the network, an entity that continuously monitors the network to detect changes and automatically update the configuration to adapt to such changes while maintaining desired quality of service. We present here the complete framework for the Configuration Agent that will provide self-configuration capabilities to real-time networks. The proposed framework has IEEE 802.1 as its core, but also shows how the set of standards need to be extended in order to achieve the self-configuration requirements. Concretely we examine the role of existing communication protocols like NETCONF and OPC-UA and propose the essential ingredients (managed objects) for a YANG model for the learning aspects in the bridges, including different working modes.

Industry 4.0 and Industrial Internet of Things projects work towards adoption of standard IT technologies for real-time control networks in industrial automation. For this the IEEE 802.1 Time-Sensitive Networking (TSN) Task Group has developed and continues to develop a set of standards. One of these standards is the IEEE 802.1AS clock synchronization protocol. IEEE 802.1AS can be used to enable time-triggered communication as well as to coordinate distributed actions in industrial networks. In this paper we study the synchronization quality of IEEE 802.1AS and we are interested in whether the clocks can be synchronized with sufficiently low error such that the protocol can be used for demanding industrial automation applications. In particular, we study the protocol behavior in large-scale networks while considering critical implementation details. We report analytical worst-case results as well as probabilistic results based on simulations, that show that implementation details such as the PHY jitter and the clock granularity have a big impact on the time synchronization precision.

This paper proposes an efficient way to handle fault in controller area network (CAN)-based networked control system (NCS). A fault in a bus line of CAN will induce a data error which will result in data dropout or time delay, and subsequently may lead to performance degradation or system instability. A strategy to handle fault occurrence in CAN bus is proposed to properly analyze the effect of the fault to CAN-based NCS performance. The fault occurrences are modeled based on fault interarrival time, fault bursts' duration, and Poisson law. Using fault and messages' attributes, response time analysis (RTA) is performed and the probability of control message missing its deadline is calculated. Utilizing the new error handling algorithm to replace the native error handling of CAN, the probability of a control message missing its deadline can be translated into the probability of data dropout for control message. This methodology is evaluated using steer-by-wire system of vehicle to analyze the effect of fault occurrences in CAN. It is found that the proposed error handling mechanism has resulted in better NCS performance and the range of data dropout probability for control message also could be obtained, which serves as crucial input for NCS controller design.

Fixed priority scheduling is used in many real-time systems, however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive Earliest Deadline First (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulablability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP), which since it matches a recently published upper bound gives the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, i.e., there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive upper and lower bounds on the speed-up factor required to guarantee FP-P feasibility of any FP-NP feasible task set. Empirical evidence suggests that the lower bound may be tight, and hence equate to the exact speed-up factor in this case.

Distributed cyber-physical systems are growing in size and functionality and deterministic communication is an important requirement for those systems. The existing solutions based on the time-triggered paradigm pose certain limitations in regards to the configuration. Usually configuration is seen as a one-time event during the installation of the network. Future realtime networks need to be able to adapt more easily to changes in the network. Thus, the configuration becomes an ongoing service, e.g., as for network maintenance and re-configuration to add and remove new, respectively old, equipment. We postulate that configuration will emerge to a continued service that accompanies a real-time network throughout its different life-cycle phases. In this context of evolving and dynamic networks, we introduce the concept of a configuration agent for real-time networks and demonstrate the concept by a realization based on the time triggered paradigm.

The feasibility of preemptive and non-preemptive scheduling has been well investigated on uniprocessor and multiprocessor platforms under both Fixed Priority Scheduling (FPS) and Earliest Deadline First (EDF) paradigms. While feasibility of limited preemptive scheduling under FPS has been addressed on both uniprocssor and multiprocessor platforms, under EDF it has been investigated only on uniprocessors, and a similar analysis for multiprocessor platforms is still missing. In this paper, we introduce global Limited Preemptive Earliest Deadline First (g-LP-EDF) scheduling, and propose the associated feasibility analysis to complete the above described feasibility analysis spectrum. Specifically, we derive a sufficient condition that guarantees g-LP-EDF feasibility of sporadic real-time tasks which directly provides a global Non-Preemptive Earliest Deadline First (g-NP-EDF) feasibility test. We then study the interplay between g-LP-EDF feasibility and processor speed, in order to quantify the sub-optimality of g-NP-EDF in terms of the minimum speed-up required to guarantee g-NP-EDF feasibility of all feasible task sets. The results presented in this paper complement our previous results on uniprocessors, and provide a unified result on the sub-optimality of non-preemptive EDF on both uniprocessor and multiprocessor platforms.

Reliability is a key requirement in many distributed real-time systems deployed in safety and mission critical applications, and temporal redundancy is a widely employed strategy towards guaranteeing it. The temporal redundancy approach is typically based on task re-executions in form of entire tasks, task alternates or, check-pointing blocks, and each of the re-execution strategies have different impacts on the Fault Tolerance feasibility (FT-feasibility) of the system, which is traditionally defined as the existence of a schedule that guarantees timeliness of all tasks under a specified fault hypothesis. In this paper, we propose the use of resource augmentation to quantify the FT-feasibility of real-time task sets and use it to derive limits on the effectiveness of temporal redundancy in fault-tolerant real-time scheduling under error bursts of bounded lengths. We derive the limits for the general case, and then show that for the specific case when the error burst length is no longer than half the shortest deadline, the lower limit on the effectiveness of temporal redundancy is given by the resource augmentation bound 2, while, the corresponding upper-limit is 6. Our proposed approach empowers a system designer to quantify the effectiveness of a particular implementation of temporal redundancy.

A number of preemptive real-time scheduling algorithms, such as Earliest Deadline First (EDF), are known to be optimal on uni-processor systems under specified assumptions. However, no uni-processor optimal algorithm exists under the non-preemptive scheduling paradigm. Hence preemptive schemes strictly dominate non-preemptive schemes with respect to uni-processor feasibility. However, the 'goodness' of non-preemptive schemes, compared to uni-processor optimal preemptive scheduling schemes such as EDF, which can also be referred to as its sub-optimality, has not been fully investigated yet. In this paper, we apply resource augmentation, specifically processor speed-up, to quantify the sub-optimality of non-preemptive scheduling with respect to EDF, and apply the results to guarantee user specified upper-bounds on the preemption related scheduling costs. In particular, we derive an upper bound on the minimum processor speed-up required to guarantee the non-preemptive feasibility of tasks that are deemed feasible under the preemptive EDF, and we prove that, in the cases where, for all tasks in the task set, the largest execution requirement is not greater than the shortest deadline, this bound is equal to 4. We also show how the proposed approach enables a system designer to choose an optimal processor, in order to, e.g., guarantee specified upper bounds on the preemption related overheads.

Networked embedded systems used in many real-time (RT) applications rely on dependable communication. Controller Area Network (CAN) has gained wider acceptance as a standard in a large number of applications, mostly due to its cost effectiveness, predictable performance, and its fault-tolerance capability. Research so far has focused on rather simplistic error models which assume only singleton errors separated by a minimum inter-arrival time. However, these systems are often subject to faults that manifest as error bursts of various lengths which have an adverse effect on the message response times that needs to be accounted for. Furthermore, an important factor to be considered in this context is the random nature of occurrences of faults and errors, which, if addressed in the traditional schedulability analysis by assuming a rigid worst case occurrence scenario, may lead to inaccurate results. In this paper we first present a stochastic fault and error model which has the capability of modeling error bursts in lieu of the commonly used simplistic error assumptions. We then present a methodology which enables the provision of appropriate probabilistic RT guarantees in distributed RT systems for the particular case of message scheduling on CAN under the assumed error assumptions.

The fundamental requirement for the design of effective and efficient fault-tolerance mechanisms in dependable real-time systems is a realistic and applicable model of potential faults, their manifestations and consequences. Fault and error models also need to be evolved based on the characteristics of the operational environments or even based on technological advances. In this paper we propose a probabilistic burst error model in lieu of the commonly used simplistic fault assumptions in the context of processor scheduling. We present a novel schedulability analysis that accounts for the worst case interference caused by error bursts on the response times of tasks scheduled under the fixed priority scheduling (FPS) policy. Further, we describe a methodology for the calculation of probabilistic schedulability guarantees as a weighted sum of the conditional probabilities of schedulability under specified error burst characteristics. Finally, we identify potential sources of pessimism in the worst case response time calculations and discuss potential means for circumventing these issues.

Dependable communication is becoming a critical factor due to the pervasive usage of networked embedded systems that increasingly interact with human lives in many real-time applications. Controller Area Network (CAN) has gained wider acceptance as a standard in a large number of industrial applications, mostly due to its efficient bandwidth utilization, ability to provide real-time guarantees, as well as its fault-tolerant capability. However, the native CAN fault-tolerant mechanism assumes that all messages transmitted on the bus are equally critical, which has an adverse impact on the message latencies, results in the inability to meet user defined reliability requirements, and, in some cases, even leads to violation of timing requirements. As the network potentially needs to cater to messages of multiple criticality levels (and hence varied redundancy requirements), scheduling them in an efficient fault-tolerant manner becomes an important research issue. We propose a methodology which enables the provision of appropriate guarantees in CAN scheduling of messages with mixed criticalities. The proposed approach involves definition of fault-tolerant feasibility windows of execution for critical messages, and off-line derivation of optimal message priorities that fulfill the user specified level of fault-tolerance.

In this paper, we propose a novel approach for flexible representation of complex timing constraints for scheduling real-time tasks under different scheduling paradigms. It allows different instantiations of the task attributes, depending on which underlying scheduling policy is used. Scheduling parameters are flexibly derived from original timing constrains, rather than using the same set of task attributes for all schedulers. For each real-time task in the system, temporal feasibility windows are identified, such that if the task executes and completes within its feasibility window, the original timing constraints will be met. Then, scheduler dependent parameters are derived to guarantee the tasks' execution and completion within their feasibility windows.

Controlling the number of preemptions in real time systems is highly desirable in order to achieve an efficient system design in multiple contexts. For example, the delays due to context switches account for high preemption overheads which detrimentally impact the system schedulability. Preemption control can also be potentially used for the efficient control of critical section behaviors in multi-threaded applications. At the same time, modern processor architectures provide for the ability to selectively choose operating frequencies, primarily targeting energy efficiency as well as system performance. In this paper, we propose the use of CPU Frequency Scaling for controlling the preemptive behavior of real-time tasks. We present a framework for selectively eliminating preemptions, that does not require modifications to the task attributes or to the underlying scheduler. We evaluate the proposed approach by four different heuristics through extensive simulation studies.

Agile methods hold a significant promise to reduce cycle times and provide greater value to all key stakeholders involved in the software ecosystem. While these methods appear to be well suited for embedded systems development, their use has not become a widespread practice. In analyzing the state-of-the-art, as captured in published literature, we found that there are technical issues (requirements management, and testing), as well as organizational issues (process tailoring, knowledge sharing & transfer, culture change, and support infrastructure). In this paper, we build preliminary guidance for firms around these six areas and presented as a framework that will enable understanding the expected adoption trajectory.

Industrial real-time systems typically have to satisfy complex requirements, mapped to the task attributes, eventually guaranteed by a fixed priority scheduler in a distributed environment. These systems consist of a mix of hard and soft tasks with varying criticality, as well as associated fault tolerance requirements. Time redundancy techniques are often preferred in industrial applications and, hence, it is extremely important to devise resource efficient methodologies for scheduling real-time tasks under failure assumptions. In this paper, we propose a methodology to provide a priori guarantees in distributed real-time systems with redundancy requirements. We do so by identifying temporal feasibility windows for all task executions and re-executions, as well as allocating them on different processing nodes. We then use optimization theory to derive the optimal feasibility windows that maximize the utilization on each node, while avoiding overloads. Finally on each node, we use integer linear programming (ILP) to derive fixed priority task attributes that guarantee the task executions within the derived feasibility windows, while keeping the associated costs minimized.

Dependable real-time systems typically consist of tasks of multiple criticality levels and scheduling them in a fault tolerant manner is a challenging problem. Redundancy in the physical and temporal domains for achieving fault tolerance has been often dealt independently based on the types of errors one needs to tolerate. To our knowledge, there had been no work which tries to integrate fault tolerant scheduling and multiple redundancy mechanisms. In this paper we propose a novel cascading redundancy approach within a generic fault tolerant scheduling framework. The proposed approach is capable of tolerating errors with a wider coverage (with respect to error frequency and error types) than time and space redundancy in isolation, allows tasks with mixed criticality levels, is independent of the scheduling technique and, above all, ensures that every critical task instance can be feasibly replicated in both time and space.

Component-based development (CBD) of software, with its successes in enterprise computing, has the promise of being a good development model due to its cost effectiveness and potential for achieving high quality of components by virtue of reuse. However, for systems with dependability concerns, such as real-time systems, a major challenge in using CBD consists of predicting dependability attributes, or providing dependability assertions, based on the individual component properties and architectural aspects. In this paper, we propose a framework which aims to address this challenge. Specifically, we present a revised error classification together with error propagation aspects, and briefly sketch how to compose error models within the context of component-based systems (CBS). The ultimate goal is to perform the analysis on a given CBS, in order to find bottlenecks in achieving dependability requirements and to provide guidelines to the designer on the usage of appropriate error detection and fault tolerance mechanisms.

Real-time applications typically have to satisfy high dependability requirements and require fault tolerance in both value and time domains. A widely used approach to ensure fault tolerance in dependable systems is the N-modular redundancy (NMR) which typically uses a majority voting mechanism. However, NMR primarily focuses on producing the correct value, without taking into account the time dimension. In this paper, we propose a new approach, Voting on Time and Value (VTV), applicable to real-time systems, which extends the modular redundancy approach by explicitly considering both value and timing failures, such that correct value is produced at a correct time, under specified assumptions. We illustrate our voting approach by instantiating it in the context of the well-known triple modular redundancy (TMR) approach. Further, we present a generalized version targeting NMR that enables a high degree of customization from the user perspective.

Real-time systems typically have to satisfy complex requirements, mapped to the task attributes, eventually guaranteed by the underlying scheduler. These systems consist of a mix of hard and soft tasks with varying criticality, as well as associated fault tolerance requirements. Additionally, the relative criticality of tasks could undergo changes during the system evolution. Time redundancy techniques are often preferred in embedded applications and, hence, it is extremely important to devise appropriate methodologies for scheduling real-time tasks under failure assumptions.In this paper, we propose a methodology to provide a priori guarantees in fixed priority scheduling (FPS) such that the system will be able to tolerate one error per every critical task instance. We do so by using integer linear programming (ILP) to derive task attributes that guarantee re-execution of every critical task instance before its deadline, while keeping the associated costs minimized. We illustrate the effectiveness of our approach, in comparison with fault tolerant (FT) adaptations of the well-known rate monotonic (RM) scheduling, by simulations.

BACKGROUND: Transcriptional regulation of cellular functions is carried out through a complex network of interactions among transcription factors and the promoter regions of genes and operons regulated by them. To better understand the system-level function of such networks simplification of their architecture was previously achieved by identifying the motifs present in the network, which are small, overrepresented, topologically distinct regulatory interaction patterns (subgraphs). However, the interaction of such motifs with each other, and their form of integration into the full network has not been previously examined. RESULTS: By studying the transcriptional regulatory network of the bacterium, Escherichia coli, we demonstrate that the two previously identified motif types in the network (i.e., feed-forward loops and bi-fan motifs) do not exist in isolation, but rather aggregate into homologous motif clusters that largely overlap with known biological functions. Moreover, these clusters further coalesce into a supercluster, thus establishing distinct topological hierarchies that show global statistical properties similar to the whole network. Targeted removal of motif links disintegrates the network into small, isolated clusters, while random disruptions of equal number of links do not cause such an effect. CONCLUSION: Individual motifs aggregate into homologous motif clusters and a supercluster forming the backbone of the E. coli transcriptional regulatory network and play a central role in defining its global topological organization.

The controller area network (CAN) is widely used in a number of industrial applications. We present a method that shows how off-line scheduled messages can be scheduled on a CAN. The paper assumes that a schedule, for a set of tasks transmitting messages on a CAN, has been constructed off-line. We present a method that analyzes the off-line schedule and derives a set of periodic messages with fixed priorities, which can be scheduled on a CAN. Based on the information provided by the off-line schedule, the method derives inequality relations between the priorities of the messages under fixed priority scheduling protocols. In case the priority relations of the messages are not solvable, we split some messages into a number of artifacts, to obtain a new set of messages with consistent priorities. We use integer linear programming to minimize the final number messages.

Off-line scheduling and fixed priority scheduling (FPS) are often considered as complementing and incompatible paradigms. A number of industrial applications demand temporal properties (predictability, jitter constraints, end-to-end deadlines, etc.) that are typically achieved by using off-line scheduling. The rigid off-line scheduling schemes used, however do not provide for flexibility. FPS has been widely studied and used in a number of applications, mostly due to its simple run-time scheduling, and small overhead. It can provide more flexibility, but is limited with respect to predictability, as actual start and completion times of execution depend on run-time events. In this paper we show how off-line scheduling and FPS run-time scheduling can be combined to get the advantages of both the capability to cope with complex timing constraints and flexibility. The paper assumes that a schedule for a set of tasks with complex constraints has been constructed off-line. It presents a method to analyze the off-line schedule and derive an FPS task set with FPS attributes priority, offset, and period, such that the runtime FPS execution matches the off-line schedule. It does so by analyzing the schedule and setting up inequality relations for the priorities of the tasks under FPS. Integer linear programming (ILP) is then used to find a FPS priority assignment that fulfils the relations. In case the priority relations for the tasks of the off-line schedule are not solvable we split tasks into the number of instances, to obtain a new task set with consistent task attributes. Our schedule translation algorithm keeps the number of newly generated artifact tasks minimal.