Real-time multimedia communication applications like video conferencing and screen sharing tools are an integral part of our daily communications. These time-critical services are handled via the Internet, a packet-switched and essentially best-effort network, not explicitly designed for robust real-time communication. From a video conferencing service provider's perspective, network issues cause a lot of user complaints due to various reasons: lossy WLAN channels, poorly configured home routers, or crowded carrier-grade network address translation devices. All of these issues have in common that they are often time-variant and non-deterministic. Furthermore, the end-to-end transmission in these highly inhomogeneous networks often suffers from a mixture of more than one error source. To enable a detailed and impartial analysis of multimedia service quality, it is necessary to analyze packets in defective online scenarios and introduce a broadly similar error pattern in an otherwise stable lab network. In this paper, we present SEDER, a hardware-software design of a layer two transparent Ethernet bridge that can be used for two purposes: error detection and error recreation. Implemented on low-cost hardware, the bridge can be easily deployed anywhere to allow debugging, even at a user's site. It is possible to parameterize our bridge to imitate almost all possible network effects, including complex combinations of more than one effect. In addition, we present two case studies, firstly emphasizing the capabilities of SEDER and secondly showing the need to use SEDER to harden open source Video Conferencing Tools against errors.

In schedulability analysis, the timing of all tasks of a real-time system is verified by finding the worst-case behavior. Two well-studied methods in this field are the demand bound test and the real-time calculus. However, the former is only applicable to specific task models whereas the latter does not formalize concrete task models of complex job patterns. This work presents a new approach to formally describe and analyze the worst-case of any complex job pattern. The approach consists of a task model that reduces all kinds of job patterns to a vector space of jobs. Furthermore, the worst-case analysis searches for local maxima to find the worst-case of any job pattern by differentiating any cumulative function of the real-time calculus. Therefore, the analysis in this work implies an algorithm to compute request as well as demand bounds by construction. This formal approach allows the integration of mathematical results from real-time calculus into real-time scheduling theory. In fact, this is, to our knowledge, the first method to compute a demand bound function with arbitrary deadlines by a min-plus deconvolution in the real-time calculus. This now allows the analysis of complex task models as the generalized multiframe model in the real-time calculus.

In this ongoing research, we investigate the mathematical properties of the scheduling theory and the real-time calculus and their relationship to each other.

Offset-based response time analysis techniques obtain tight worst-case response time (WCRT) bounds by accounting release time dependencies between tasks. The maximum response time variation of a task or a message (i.e., the difference between the worst-case and best-case response time) is used to compute the end-to-end delays of distributed systems (Palencia and Harbour, 1998), (Tindell and Clark, 1994). Hence, the WCRT evaluation plays an important role in determining tight end-to-end delays of distributed systems. In real-time theory, there exist two approaches to compute the WCRT of a task: the classical response time analysis (RTA) approach and the modular performance analysis with the Real-Time Calculus (MPA-RTC). MPA-RTC has its roots in Network Calculus (NC). MPA-RTC offers more powerful abstraction than RTA based techniques and allows composition in terms of tasks, event streams, and resource sharing which makes it a strong candidate to analyze distributed systems (Wandeler, 2006), (Perathoner, 2011). However, one of the key limitations of the MPA-RTC is its inability to handle offset dependencies between tasks, whereas the classical RTA techniques can handle them. In this paper, we propose a method to consider offset dependencies between tasks using an MPA-RTC framework for a fixed priority scheduler in a uniprocessor system. Hence, our approach leverages the advantages of the expressive MPA-RTC framework model. We propose novel heuristics and approximation to reduce the inherent complexity of an offset-based RTA. We quantitatively evaluate the effectiveness of our approach to the state-of-the-art classical offset-based RTA techniques.

A main challenge of modem design lies in selecting a suitable combination of subsystems (e.g. ADCs/DACs, (de)modulators, scramblers, interleavers, and coding and filtering modules), each of which can be implemented in a multitude of ways. At the same time, the complete modem configuration needs to be tailored to the specific requirements of the intended communication channel or scenario. Therefore, model-based design methodologies have been popularized in this field, since their application facilitates the specification of individual modem components that are easily exchanged during the automated synthesization of the modem. However, this development has resulted in a tremendous increase in the number of synthesizable modem options. In fact, the optimal modem configuration for a communication scenario can not readily be determined, since an exhaustive analysis of all configuration possibilities is computationally intractable. As a remedy, we propose a fully automated Design Space Exploration (DSE) methodology for model-based modem design that combines the metaheuristic optimization of modem-configuration possibilities with an integrated simulative analysis of suitable communication-quality measures. The presented case study for an acoustic underwater communication scenario supports the described need for novel, automated methodologies in the area of model-based design, since the modem configurations discovered during a comparably short DSE are demonstrated to significantly outperform state-of-the-art modems from literature.

In automotive embedded real-time systems, e.g., the engine control unit, tasks are activated whenever the engine arrives at a specific angular position. In consequence the frequency of activation changes with the speed of the engine. Additionally, the execution times and deadlines may also depend on the engine speed. In recently published works analytical methods for tasks with this rate-dependent behavior were introduced. Though those methods do not consider angular phases between tasks. For instance, in a typical engine control unit one event is displaced a certain angular position after an event of another task. This paper introduces a sufficient analysis, which considers such angular phases. A number of experimental results are reported to compare our method with existing analysis. These illustrate the improvement in terms of precision and runtime.

In embedded real-time systems, the schedulability analysis is an important method to verify whether the real-time constraints are satisfied. Especially, engine control systems in the automotive industry are particular challenging regarding their real-time analysis. Some of the tasks of such systems are triggered at predetermined angular values of the crankshaft. Thus, the frequency of activation increases for higher crankshaft rotation speeds. To avoid overloads, these tasks reduce their computational demand for higher rotation speeds. The variable rate-dependent behavior (VRB) task model has been proposed as a means of modeling such rate-dependent behavior. In this paper, we introduce a new method for the exact computation of interference for VRB-tasks. A number of experimental results are reported to validate our approach and compare it with existing analysis. These experimental results illustrate that our method outperforms previous results in terms of precision and runtime.

When designing networked control system (NCS), a main design goal is to reduce the resource usage as far as possible while guaranteeing a predefined control performance. A sensor node that skips samples reduces the resource usage of the control application, but also causes a performance degradation of the NCS. To obtain an efficient co-design, this paper makes use of an expressive model that bounds the occurrence of dropped samples in the interval domain. With such a model, the borderline of the specified control performance is reached while introducing minimal pessimism. Furthermore, we present in this paper a sensitivity analysis that derives the maximum density of dropped samples from the impulse response behavior of a control system with respect to a predefined performance threshold. This bound on the density of dropped samples allows a resource reduction, which can be used by sporadic tasks in mixed criticality systems without endangering the control performance threshold.

Automotive embedded real-time systems such as Engine Management utilise cyclic tasks that are activated periodically based on angular rotation rather than time. As well as having variable inter-arrival times, these tasks also have deadlines and worst-case execution times that are dependent on angular velocity i.e. engine speed or rpm. Such tasks exhibit Variable Rate-dependent Behaviour (VRB). In this paper, we introduce response time analysis for systems comprising VRB and sporadic tasks under fixed priority scheduling. Sufficient schedulability tests are introduced; from simple linear upper bounds on interference, to a more complex analysis using information about the physical limitations of the system to provide constraints for an ILP formulation of the problem.

While common task models in real-time analysis assume a task as being activated by a single event and producing a single outgoing event after its full completion, the event dependency analysis extended the model to allow for multiple outgoing events to occur already during the run-time of a single job. It uses the structure of a timing-annotated control flow graph to calculate the maximal densities of outgoing events. Previous work has shown that knowledge about infeasible paths in the control flow graph can be used to relax the event densities by modifying the graph prior to performing the event dependency analysis. However, that approach leads to a nearly explicit path enumeration. In this paper, we show how the event dependency analysis can be modified to directly exclude infeasible paths in order to relax the densities of outgoing events.

In event triggered control systems, events occur aperiodically. For the real-time analysis of such systems, an appropriate approximation of the events' stimulation is necessary. Upper bounds have already been found for event triggered systems. For now, lower bounds have been assumed zero within the real-time analysis of event triggered systems. This work derives an approximated lower bound representing the maximum inter-sampling time. The bounds depend on the control system and the event generating mechanism. The beneficial effect is shown by analyzing an event triggered control system in a real-time analysis framework.

Engine control units in the automotive industry are particular challenging real-time systems regarding their real-time analysis. Some of the tasks of such an engine control unit are triggered by the engine, i.e. the faster the angular velocity of the engine, the more frequent the tasks are executed. Furthermore, the execution time of a task may vary with the angular velocity of the engine. As a result the worst case does not necessarily occur when all tasks are activated simultaneously. Hence this behavior cannot be addressed appropriately with the currently available real-time analysis methods. In this paper we make a first step towards a real-time analysis for an engine control unit. We present a sufficient real-time analysis assuming that the angular velocity of the engine is arbitrary but fixed.

Controller Area Network (CAN) is widely used in automotive applications. Existing schedulability analysis for CAN is based on the assumption that the highest priority message ready for transmission at each node on the network will be entered into arbitration on the bus. However, in practice, some CAN device drivers implement FIFO rather than priority-based queues invalidating this assumption. In this paper, we introduce response time analysis and optimal priority assignment policies for CAN messages in networks where some nodes use FIFO queues while other nodes use priority queues. We show, via a case study and experimental evaluation, the detrimental impact that FIFO queues have on the real-time performance of CAN.

High-end cars today consist of more than 100 electronic control units (ECUs) that are connected to a set of sensors and actuators and run multiple distributed control applications. The design flow of such architectures consists of specifying control applications as Simulink/Stateflow models, followed by generating code from them and finally mapping such code onto multiple ECUs. In addition, the scheduling policies and parameters on both the ECUs and the communication buses over which they communicate also need to be specified. These policies and parameters are computed from high-level timing and control performance constraints. The proposed tutorial will cover different aspects of this design flow, with a focus on timing and schedulability problems. After reviewing the basic concepts of worst-case execution time analysis and schedulability analysis, we will discuss the differences between meeting timing constraints (as in classical real-time systems) and meeting control performance constraints (e.g., stability, steady and transient state performance). We will then describe various control performance related schedulability analysis techniques and how they may be tied to model-based software development. Finally, we will discuss various schedule synthesis techniques, both for ECUs as well as for communication protocols like FlexRay, so that control performance constraints specified at the model-level may be satisfied. Throughout the tutorial different commercial as well as academic tools will be discussed and demonstrated.

In real-time theory, basically two approaches for the computation of response-times exist. One of them is the busy window method, the other is the real-time calculus, an extension of the network calculus. While both can be used to compute the bounds of response-times, they have different properties that make them suitable for different system architectures. The busy window approach on the one hand is able to obtain tight bounds for scheduling policies like round-robin. It is also capable of considering offsets, therefore delivering better results in the relevant cases. Hierarchical scheduling on the other hand can be better accounted for by the real-time calculus, where this is an inherent feature of the underlying concept. The approach we present in this paper takes the theory of hierarchy from the real-time calculus and uses it to generalize the response-time analysis. This is implemented as an extension of the busy window method, which enables it to analyze scheduling hierarchies of an arbitrary depth.

In the design and development of embedded real-time systems the aspect of timing behavior plays a central role. Especially, the evaluation of different scheduling approaches, algorithms and configurations is one of the elementary preconditions for creating not only reliable but also efficient systems - a key for success in industrial mass production. This is becoming even more important as multi-core systems are more and more penetrating the world of embedded systems together with the large (and growing) variety of scheduling policies available for such systems. In this work simple mathematical concepts are used to define performance indicators allowing to quantify the benefit of different solutions of the scheduling challenge for a given application. As a sample application some aspects of analyzing the dynamic behavior of an combustion engine management system for the automotive domain are shown. However, the described approach is flexible in order to support the specific optimization needs arising from the timing requirements defined by the application domain and can be used with simulation data as well as target system measurements.

Fast real-time feasibility tests and analysis algorithms are necessary for a high acceptance of the formal techniques by industrial software engineers. This paper presents a possibility to reduce the computation time required to calculate the worst-case response time of a task in a fixed-priority task set with jitter by a considerable amount of time. The correctness of the approach is proven analytically and experimental comparisons with the currently fastest known tests show the improvement of the new method.

Earliest deadline first scheduling performs processor utilization up to 100 percent and improved robustness in overload situations. However, most automotive applications are running under static priority policy. Because of this, the standard operating system in the automotive industry, OSEK/VDX, just supports priority scheduling. This paper describes an EDF scheduler plug-in for OSEK/VDX. The plug-in provides EDF scheduling without changes to the operating system by delaying task activations. The add-on was tested for an engine management system developed by SiemensVDO. Results of this experiment are presented and discussed, showing that the EDF scheduling techniques can improve the system in aspects of robustness and resource utilization.

Analyzing future distributed real-time systems, automotive and avionic systems, is requiring compositional hard real-time analysis techniques. Well known established techniques as SymTA/S and the real-time calculus are candidates solving the mentioned problem. However both techniques use quite simple event models. SymTA/S is based on discrete events the real-time calculus on continuous functions. Such simple models has been choosen because of the computational complexity of the considered mathematical operations required for real-time analysis. Advances in approximation techniques are allowing the consideration of more expressive descriptions of events. In this paper such a new expressive event model and its analysis algorithm are described. It integrates the models of both techniques. It is also possible in this module to integrate an approximative real-time analysis into the event model. This allows to propagate the approximation through the analysis of a distributed system leading to a much more efficient analysis.

One of the important aspects of schedulability analysis is the model used to describe the system and its timing behavior. On one side, the accuracy of the test strongly depends on the accuracy of the model. On the other side, a detailed model could lead to an unaccaptable evaluation time. In this paper we propose a new model, the hierarchical event streams, which allows a high accuracy. We provide an efficient feasibility test for the model based on the context of demand and request bound function. Additionally we will provide a methodology to extract this model out of a control-flow graph efficiently. Together this allows a more accurate and efficient schedulability analysis of event driven real-time systems

This paper presents new fast exact feasibility tests for uniprocessor real-time systems using preemptive EDF (earliest deadline first) scheduling. Task sets which are accepted by previously described sufficient tests are evaluated in nearly the same time as with the old tests by the new algorithms. Many task sets are not accepted by the earlier tests despite them being feasible. These task sets are evaluated by the new algorithms a lot faster than with known exact feasibility tests. Therefore, it is possible to use them for many applications for which only sufficient test are suitable. Additionally this paper shows that the best previous known sufficient test, the best known feasibility bound and the best known approximation algorithm can be derived from these new tests. As a result, this leads to an integrated schedulability theory for EDF.

Summary form only given. An essential characteristic of embedded systems is real-time, but the commonly used specification techniques do not consider temporal aspects in general like fulfilment of high level timing requirements or dynamic reactions on timing violations. We show a new formal time model that fills this gap: timing requirements specify the timing behaviour of real-time systems. Different models allow the specification of clock properties and the relations between clocks. With this time model, timing requirements as well as the desired properties of the involved clocks can be specified within a formal description technique.