Schedule
9h-10h30: Session 1 (Chairman: Giovanni Stea)
Anne Bouillard. Composition of service curves in Network Calculus
Abstract: In this article, we study the composition of simple and strict service curves in Network calculus for two operations: the concatenation of servers and the residual service curves. Whereas strict service curves enable more operation, the strict character of the curves is not stable by those two operations. We show that, beyond the already known results about stability for those two classes of service, no stable class of service curve can be defined in between.
Marc Boyer, Nicolas Navet and Jörn Migge. An efficient and simple class of function to model arrival curve of packetised flows
Abstract: Network calculus is a generic theory designed to compute upper bound on network traversal time (WCTT -- Worst Case Traversal Time). This theory models traffic constraints and service contract with arrival curves and service curves. As usual in modelling, the closer to the reality the model is, the better the results are, and, as usual also, a detailed modelling implies a lot of computation. Then, an happy medium must be found between result accuracy and computation time. This paper show how a combination of two simple class of curves can be used to produce some accurate result with very low computation complexity to analyse an AFDX network.
Thomas Ferrandiz, Fabrice Frances and Christian Fraboul. Modeling Spacewire networks with Network Calculus
Abstract: Network calculus is a generic theory designed to compute upper bound on network traversal time (WCTT -- Worst Case Traversal Time). This theory models traffic constraints and service contract with arrival curves and service curves. As usual in modelling, the closer to the reality the model is, the better the results are, and, as usual also, a detailed modelling implies a lot of computation. Then, an happy medium must be found between result accuracy and computation time. This paper show how a combination of two simple class of curves can be used to produce some accurate result with very low computation complexity to analyse an AFDX network.
Thomas Ferrandiz, Fabrice Frances and Christian Fraboul. Modeling Spacewire networks with Network Calculus
Abstract: The Spacewire network standard is promoted by the ESA and is scheduled to be used as the sole on-board network for future satellites. This network uses a wormhole routing mechanism that can lead to packet blocking in routers and consequently to variable end-to-end delays. As the network will be shared by real-time and non real- time traffic, network designers require a tool to check that temporal constraints are verified for all the critical messages. Network Calculus can be used for evaluating worst- case end-to-end delays. However, we first have to model Spacewire components through the definition of service curves. In this paper, we propose a new Network Calculus element that we call the Wormhole Section. This element allows us to better model a wormhole network than the usual multiplexer and demultiplexer elements used in the context of usual Store-and-Forward networks. Then, we show how to combine Wormhole Section elements to compute the end-to-end service curve offered to a flow and illustrate its use on a industrial case study.
11h-12h30: Session 2 (Chairman: Marc Boyer)
Karine Altisen and Matthieu Moy. Causality Closure for a New Class of Curves in Real-Time Calculus
Abstract: Real-Time Calculus (RTC) is a framework to analyze heterogeneous real-time systems that process event streams of data. The streams are characterized by arrival curves which express upper and lower bounds on the number of events that may arrive over any specified time interval. System properties may then be computed using algebraic techniques in a compositional way. The property of causality on arrival curves essentially characterizes the absence of deadlock in the corresponding generator. A mathematical operation called causality closure transforms arbitrary curves into causal ones. In this paper, we extend the existing theory on causality to the class Upac of infinite curves represented by a finite set of points plus piecewise affine functions, where existing algorithms did not apply. We show how to apply the causality closure on this class of curves, prove that this causal representative is still in the class and give algorithms to compute it. This provides the tightest pair of curves among the curves which accept the same sets of streams.
Victor Pollex, Henrik Lipskoch, Steffen Kollmann and Frank Slomka. Runtime Improved Computation of Path Latencies with the Real-Time Calculus
Abstract: In distributed real-time systems an application can comprehend several electronic control units interconnected by buses. To verify the real-time requirements of the application a bound for the worst-case response time or the path latency is required. With the real-time calculus a bound can be computed by using an aggregated service curve. The calculation of this aggregated service curve requires the convolution of functions which can be computational expensive. The systems we consider are event driven. This fact is exploited by the methods we present in this paper in order to reduce the runtime of the computation of the path latency. As basis we use the RTC Toolbox which provides the core operators of the real-time calculus and through experiments we show the runtime improvements of our new methods.
Sara Medlej, Steven Martin and Jean-Marie Cottin. Deterministic performance guarantee: Worst case end-to-end delay analysis. (Oral presentation only)
Abstract. In recent years, Switched Ethernet has been used in critical industrial networks such as in avionic and nuclear sectors. However, a performance study is required to guarantee a secure functioning of the system before its deployment. In this paper, we are interested in methods that can be used to determine deterministic upper bounds on the end-to-end response time of flows coexisting in hard real-time systems. This paper presents an overview of existing techniques that may be used for this purpose. We examine classical approaches such as Model Checking and Network Calculus. A recent method called Trajectory Approach addressing the same problem is also presented. The latter approach in its basic and optimized versions are compared on a sample configuration. We show that the error introduced in certain cases by the optimized trajectory approach is enormous and should not be neglected.
14h-15h30: Session 3 (Chairman: Christian Fraboul)
Simon Bliudze. Compositional Timing Analysis: Power Plant Protection System Case Study
Abstract: We introduce a method for studying temporal behaviour of the so-called Globally Asynchronous, Locally Synchronous (GALS) systems, that is systems consisting of synchronous computing elements communicating over asynchronous channels. Our method is based on the combined use of transitional logics and timed automata. The former is used to compute, by abstract interpretation, an over-approximation of the shape of the output signal, whereas the latter provide the time-stamps for the edges. Both are applied iteratively to a hierarchical model of the system in order to avoid state space explosion. We use the IF/TCA tool-chain developed at Verimag to apply this method to a case study based on the software protection system of a P4 nuclear reactor.
Philipp Berndt and Odej Kao. Time Bounds for Periodic Hypercube Gossiping
Abstract: Hypercube gossiping facilitates highly efficient data dissemination for a wide range of applications whereat live streaming, not limited to multimedia, marks the periodic exchange of data. Applications of periodic hypercube gossiping range from the estimation of system state vectors, such as object tracking or real-time business intelligence to audio communication. In such real-time applications, the ability to bound latency is of vital importance. Traversal time denotes the multi-hop latency between sending a data packet from a source node of the overlay network and receiving it at the destination node. For periodic gossiping, it depends on the abstract communication complexity of the network topology, the physical properties of the underlay network, and last but not least, the timing mode employed in the algorithmic implementation of the high-level gossiping communication scheme. In this paper, we analyze the magnitude of worst-case latency for periodic gossiping in F1 mode on a binary hypercube overlay network. We show that due to wait delay caused by data sojourning at intermediate overlay nodesit is highly dependent on the timing or synchronization of the communication. We present four basic timing modes and derive worst case wait latency and traversal time bounds and compare these analytic measures to results from a simulation with a life-like network delay distribution derived from large-scale latency measurements.
Moris Behnam, Zahid Iqbal, Pedro Silva, Ricardo Marau, Luis Almeida and Paulo Portugal. Engineering and Analyzing Multi-Switch Networks with Single Point of Control
Abstract: Recent trends in distributed embedded systems have shown an increase in the amount and heterogeneity of the information that needs to be exchanged, together with a growing importance of supporting dynamic reconfiguration and adaptive behaviors. In this paper we focus on Ethernet technology and we address the case of middle-size networking infrastructure with a few switches. We use the FTT-SE protocol to support dynamic heterogeneous real-time transactions with temporal isolation and we propose the needed scheduling adaptations to support multi-hop network configurations. The paper also includes a companion worst-case response-time analysis that allows verifying the timeliness of the system.