Some of the applications in modern data networks are delay sensitive (e.g., video and voice). An end-to-end delay analysis is needed to estimate the required network resources of delay sensitive applications. The schedulers used in the network can impact the resulting delays to the applications. When multiple applications are multiplexed in a switch, a scheduler is used to determine the precedence of the arrivals from different applications. Computing the end-to-end delay and queue sizes in a network of schedulers is difficult and the existing solutions are limited to some special cases (e.g., specific type of traffic). The theory of Network Calculus employs the min-plus algebra to obtain performance bounds. Given an upper bound on the traffic arrival in any time interval and a lower bound on the available service (called the service curve) at a network element, upper bounds on the delay and queue size of the traffic in that network element can be obtained. An equivalent end-to-end service curve of a tandem of queues is the min-plus convolution of the service curves of all nodes along the path. A probabilistic end-to-end delay bound using network service curve scales with O(H logH) in the path length H. This improves the results of the conventional method of adding per-node delay bounds scaling with O(H^3). We have used and advanced Network Calculus for end-to-end delay analysis in a network of schedulers. We formulate a service curve description for a large class of schedulers which we call Delta-schedulers. We show that with this service curve, tight single node delay and backlog bounds can be achieved. In an end-to-end scenario, we formulate a new convolution theoii rem which considerably improves the end-to-end probabilistic delay bounds. We specify our probabilistic end-to-end delay and backlog bounds for exponentially bounded burstniess (EBB) traffic arrivals. We show that the end-to-end delay varies considerably by the type of schedulers along the path. Using these bounds, we also show that a if the number of flows increases, the queues inside a network can be analyzed in isolation and regardless of the network effect.

Some of the applications in modern data networks are delay sensitive (e.g., video and voice). An end-to-end delay analysis is needed to estimate the required network resources of delay sensitive applications. The schedulers used in the network can impact the resulting delays to the applications. When multiple applications are multiplexed in a switch, a scheduler is used to determine the precedence of the arrivals from different applications. Computing the end-to-end delay and queue sizes in a network of schedulers is difficult and the existing solutions are limited to some special cases (e.g., specific type of traffic). The theory of Network Calculus employs the min-plus algebra to obtain performance bounds. Given an upper bound on the traffic arrival in any time interval and a lower bound on the available service (called the service curve) at a network element, upper bounds on the delay and queue size of the traffic in that network element can be obtained. An equivalent end-to-end service curve of a tandem of queues is the min-plus convolution of the service curves of all nodes along the path. A probabilistic end-to-end delay bound using network service curve scales with O(H logH) in the path length H. This improves the results of the conventional method of adding per-node delay bounds scaling with O(H^3). We have used and advanced Network Calculus for end-to-end delay analysis in a network of schedulers. We formulate a service curve description for a large class of schedulers which we call Delta-schedulers. We show that with this service curve, tight single node delay and backlog bounds can be achieved. In an end-to-end scenario, we formulate a new convolution theoii rem which considerably improves the end-to-end probabilistic delay bounds. We specify our probabilistic end-to-end delay and backlog bounds for exponentially bounded burstniess (EBB) traffic arrivals. We show that the end-to-end delay varies considerably by the type of schedulers along the path. Using these bounds, we also show that a if the number of flows increases, the queues inside a network can be analyzed in isolation and regardless of the network effect.

Aujourd'hui, les applications automobiles sont devenues de plus en plus complexes avec des ressources limitées et plus de contraintes de temps et de safety. La vérification temporelle est effectuée très tard aujourd'hui au cours du processus de développement automobile (après l'implémentation et au cours de la phase d'intégration). Pour apporter des solutions aux problèmes du développement logiciel automobile, plusieurs approches de développement dirigé par les modèles ont été définit. Ces approches donnent des langages, des concepts et des méthodologies pour la description de l'architecture des systèmes automobiles. Cependant, ces approches ne donnent aucun guide méthodologique pour intégrer l'analyse temporelle (notamment l'analyse d'ordonnancement) tout au long du processus de développement. Ce travail de thèse propose de développer une méthodologie décrivant un processus d'analyse temporelle dirigé par les modèles. Cette méthodologie décrit les différentes phases du processus de développement dirigé par les modèles et comment l'analyse temporelle est effectuée durant chaque phase. / Automotive systems are characterized today by increasing complexity, limited resources and more and more timing and safety requirements. Timing verification is performed too late during the development process. It is addressed by means of measurements and tests rather than through formal and systematic analysis. To meet the challenges of automotive software development, many model-based approaches have been developed. These approaches give modeling languages, concepts and methodologies allowing the description of automotive architecture. However, these approaches give no guidance for the integration of timing analysis (mainly scheduling analysis) during the phases of the model-based development process. This PhD work aims at defining a methodology that describes a model-based timing analysis process. This methodology describes the different phases of the model-based development process and how timing analysis is performed during each phase. This work has been performed in the context of a technical collaboration between Continental Automotive and the CEA laboratory.

Despiste the fact that many scheduling models teoretically capable of high system resource utilization were proposed with the development of the real-time system, the industry still uses the first scheduling model proposed for multi-processor real-time systems, the partitioned scheduling model. This scheduling model can guarantee scheduling of task sets up to around 69% processor utilization, which falls pale in comparison to recent scheduling models that can guarantee scheduling up to 97% processor utilization. The motive behind the utilization of the partitioned scheduling as industrial model is the amount of studies made on this model and the development of scheduling analysis capable of providing temporal guarantees for this model on a real system environment. Recent scheduling models, like semi-partitioned scheduling, offer the possibility of a higher system resource utilization, it still lack studies and scheduling analysis capable of provide temporal guarantees under a real environment. The current scheduling analysis for most of the more recent models take advantage of a series of abstractions, failing to provide guarantees under real circumstances. This papers primary objective is to produce a new scheduling analysis for semi-partitioned scheduling, capable of achieving temporal guarantees taking some of the previously abstracted factors, like task communication and the impact f task migration on its communications flows, approximating the scheduling model to real environmental conditions. With the development of such analysis preliminary studies were made on heuristic task mapping algorithms for semipartitioned systems. / Com a popularização de sistemas multi-processador, surgiu uma série de propostas de modelos de escalonamento, na área de sistemas de tempo real que, teoricamente, são capazes de obter um alto aproveitamento dos recursos do sistema. Entretanto, o modelo de escalonamento mais adotado continua sendo um dos primeiros modelos de escalonamento propostos na área, o modelo de escalonamento particionado. O modelo de escalonamento particionado só pode garantir o escalonamento de conjuntos com até cerca de 69% de utilização de processador, sendo limitado se comparado com garantias de escalonamento de até 97% de utilização de modelos mais recentes. O motivo pelo qual o escalonamento particionado continua sendo utilizado é a grande concentração de estudos a respeito do modelo e o desenvolvimento de análises de escalonamento capazes de garantir o escalonamento do modelo em condições reais do sistema. Modelos mais recentes, como o escalonamento semi-particionado, apresentam uma possibilidade de um maior aproveitamento do sistema, porém, ainda possuem estudos limitados e não dispõe de análises de escalonamento capazes de prover garantias temporais para o sistema em condições reais, devido à presença de diversas abstrações no modelo. Neste sentido, este trabalho foca em arquiteturas Network-on-Chip que apresentam comunicação explícita, abstraída nos trabalhos encontrados na literatura. Este trabalho tem como objetivo primário o desenvolvimento de uma análise de escalonamento capaz de prover garantias temporais para o modelo de escalonamento semi-particionado levando em consideração fatores previamente abstraídos, como a necessidade de comunicação entre tarefas e o impacto da migração das tarefas nos seus fluxos de comunicação, aproximando o modelo da realidade. O desenvolvimento de tal análise possibilita o estudo preliminar de algoritmos heurísticos de mapeamento de tarefas, capazes de mapear conjuntos de tarefas levando em consideração migrações de tarefas e comunicação entre tarefas em um modelo de escalonamento semi-particionado.

When designing architectures and protocols for data traffic requiring real-time services, one of the major design goals is to guarantee that traffic deadlines can be met. However, many real-time applications also have additional requirements such as high throughput, high reliability, or energy efficiency. High-performance embedded systems communicating heterogeneous traffic with high bandwidth and strict timing requirements are in need of more efficient communication solutions, while wireless industrial applications, communicating control data, require support of reliability and guarantees of real-time predictability at the same time. To meet the requirements of high-performance embedded systems, this thesis work proposes two multi-wavelength high-speed passive optical networks. To enable reliable wireless industrial communications, a framework in­corporating carefully scheduled retransmissions is developed. All solutions are based on a single-hop star topology, predictable Medium Access Control algorithms and Earliest Deadline First scheduling, centrally controlled by a master node. Further, real-time schedulability analysis is used as admission control policy to provide delay guarantees for hard real-time traffic. For high-performance embedded systems an optical star network with an Arrayed Waveguide Grating placed in the centre is suggested. The design combines spatial wavelength re­use with fixed-tuned and tuneable transceivers in the end nodes, enabling simultaneous transmis­sion of both control and data traffic. This, in turn, permits efficient support of heterogeneous traf­fic with both hard and soft real-time constraints. By analyzing traffic dependencies in this mul­tichannel network, and adapting the real-time schedulability analysis to incorporate these traffic dependencies, a considerable increase of the possible guaranteed throughput for hard real-time traffic can be obtained. Most industrial applications require using existing standards such as IEEE 802.11 or IEEE 802.15.4 for interoperability and cost efficiency. However, these standards do not provide predict­able channel access, and thus real-time guarantees cannot be given. A framework is therefore de­veloped, combining transport layer retransmissions with real-time analysis admission control, which has been adapted to consider retransmissions. It can be placed on top of many underlying communication technologies, exemplified in our work by the two aforementioned wireless stan­dards. To enable a higher data rate than pure IEEE 802.15.4, but still maintaining its energy saving properties, two multichannel network architectures based on IEEE 802.15.4 and encompassing the framework are designed. The proposed architectures are evaluated in terms of reliability, utiliza­tion, delay, complexity, scalability and energy efficiency and it is concluded that performance is enhanced through redundancy in the time and frequency domains.