Featured with good scalability, modularity and large bandwidth, Network-on-Chip (NoC) has been widely applied in manycore Chip Multiprocessor (CMP) and Multiprocessor System-on-Chip (MPSoC) architectures. The provision of guaranteed service emerges as an important NoC design problem due to the application requirements in Quality-of-Service (QoS). Formal analysis of performance bounds plays a critical role in ensuring guaranteed service of NoC by giving insights into how the design parameters impact the network performance. The study in this thesis proposes analysis methods for delay and backlog bounds with Network Calculus (NC). Based on xMAS (eXecutable Micro-Architectural Specification), a formal framework to model communication fabrics, the delay bound analysis procedure is presented using NC. The micro-architectural xMAS representation of a canonical on-chip router is proposed with both the data flow and control flow well captured. Furthermore, a well-defined xMAS model for a specific application on an NoC can be created with network and flow knowledge and then be mapped to corresponding NC analysis model for end-to-end delay bound calculation. The xMAS model effectively bridges the gap between the informal NoC micro-architecture and the formal analysis model. Besides delay bound, the analysis of backlog bound is also crucial for predicting buffer dimensioning boundary in on-chip Virtual Channel (VC) routers. In this thesis, basic buffer use cases are identified with corresponding analysis models proposed so as to decompose the complex flow contention in a network. Then we develop a topology independent analysis technique to convey the backlog bound analysis step by step. Algorithms are developed to automate this analysis procedure. Accompanying the analysis of performance bounds, tightness evaluation is an essential step to ensure the validity of the analysis models. However, this evaluation process is often a tedious, time-consuming, and manual simulation process in which many simulation parameters may have to be configured before the simulations run. In this thesis, we develop a heuristics aided tightness evaluation method for the analytical delay and backlog bounds. The tightness evaluation is abstracted as constrained optimization problems with the objectives formulated as implicit functions with respect to the system parameters. Based on the well-defined problems, heuristics can be applied to guide a fully automated configuration searching process which incorporates cycle-accurate bit-accurate simulations. As an example of heuristics, Adaptive Simulated Annealing (ASA) is adopted to guide the search in the configuration space. Experiment results indicate that the performance analysis models based on NC give tight results which are effectively found by the heuristics aided evaluation process even the model has a multidimensional discrete search space and complex constraints. In order to facilitate xMAS modeling and corresponding validation of the performance analysis models, the thesis presents an xMAS tool developed in Simulink. It provides a friendly graphical interface for xMAS modeling and parameter configuring based on the powerful Simulink modeling environment. Hierarchical model build-up and Verilog-HDL code generation are essentially supported to manage complex models and conduct simulations. Attributed to the synthesizable xMAS library and the good extendibility, this xMAS tool has promising use in application specific NoC design based on the xMAS components. / <p>QC 20150520</p>

Achieving high performance in high capacity data transfers over the Internet has long been a daunting challenge. The current standard of Transmission Control Protocol (TCP), TCP Reno, does not scale efficiently to higher bandwidths. Various congestion controllers have been proposed to alleviate this problem. Most of these controllers primarily use marking/loss or/and delay as distinct feedback signals from the network, and employ separate data transfer control strategies that react to either marking/loss or delay. While these controllers have achieved better performance compared to existing TCP standard, they suffer from various shortcomings. Thus, in our previous work, we designed a congestion control scheme that jointly exploits both delay and marking; D+M (Delay Marking) TCP. We demonstrated that D+M TCP can adapt to highly dynamic network conditions and infrastructure using ns-2 simulations. Yet, an analytical explanation of D+M TCP was needed to explain why it works as observed. Furthermore, D+M TCP needed extensive simulations in order to assess its performance, especially in relation to other high-speed protocols. Therefore, we propose a model for D+M TCP based on distributed resource optimization theory. Based on this model, we argue that D+M TCP solves the network resource allocation problem in an optimal manner. Moreover, we analyze the fairness properties of D+M TCP, and its coexistence with different queue management algorithms. Resource optimization interpretation of D+M TCP allows us to derive equilibrium values of steady state of the controller, and we use ns-2 simulations to verify that the protocol indeed attains the analytical equilibria. Furthermore, dynamics of D+M TCP is also explained in a mathematical framework, and we show that D+M TCP achieves analytical predictions. Modeling the dynamics gives insights to the stability and convergence properties of D+M TCP, as we outline in the thesis. Moreover, we demonstrate that D+M TCP is able to achieve excellent performance in a variety of network conditions and infrastructure. D+M TCP achieved performance superior to most of the existing high-speed TCP versions in terms of link utilization, RTT fairness, goodput, and oscillatory behavior, as confirmed by comparative ns-2 simulations.

A demanda de eficiência no gerenciamento das redes aumenta atualmente devido ao rápido desenvolvimento da computação em nuvem e a implantação em grande escala de centros de dados. O controle da infraestrutura deve ser capaz de classificar os diversos tipos de tráfego para aplicações diferentes, e prover o atendimento adequado no menor tempo possível. Porém, devido ao dinamismo da rede, nem sempre podem ser garantidos os requisitos mínimos necessários na Internet. Os mecanismos propostos para a engenharia de tráfego até hoje, são baseados em arquiteturas inflexíveis com a camada de controle e dados fortemente integrados. Isto dificulta um atendimento diferenciado adaptável aos diversos padrões de tráfego das aplicações modernas. Para enfrentar os problemas de flexibilidade das redes tradicionais, as Redes Definidas por Software, apresentam um paradigma inovador que separa as camadas de controle e encaminhamento de pacotes de forma a garantir a utilização eficiente dos recursos disponíveis, e ao mesmo tempo maior flexibilidade de implementação. Este paradigma permite conhecer o estado da rede e a sua topologia em tempo real, o que faz possível a reconfiguração de rotas e alocação de recursos de forma dinâmica. Esta dissertação apresenta um framework para engenharia de tráfego em SDN que utiliza a teoria matemática Network Calculus como ferramenta para subsidiar a caracterização e o policiamento de fluxos de pacotes. Através desta teoria, as decisões de encaminhamento e a distribuição do tráfego são baseadas não só por valores obtidos monitorando a rede, como também por projeções determinísticas que descrevem o comportamento do tráfego. Os resultados obtidos nos experimentos, comprovaram a eficiência no balanceamento de carga da rede em termos de atraso, demonstrando ganhos em termos de vazão do sistema e possibilitando a diminuição da porcentagem de perda de pacotes dos fluxos trafegados. O framework proposto visa contribuir na solução dos desafios relacionados a se estabelecer Engenharia de Tráfego para SDN com a especificação de mecanismos de gerenciamento adaptáveis as mudanças topológicas da rede, as diferentes características dos fluxos e que sejam capazes de distribuir de forma equilibrada o tráfego na rede. / The demand for network management efficiency is currently boosted by the rapid development of cloud computing and the large-scale deployment of data centers. Infrastructure control should be able to classify the various types of traffic for different applications, and provide adequate service in the shortest time possible. However, due to the dynamism of the network, the necessary minimum requirements on the Internet can not always be guaranteed. The proposed mechanisms for traffic engineering to date are based on inflexible architectures with the control and data layer strongly integrated. This hinders a differentiated service adaptable to the different traffic patterns of modern applications. To address the flexibility problems of traditional networks, Software Defined Networks presents an innovative paradigm that separates packet control and datapath layers to ensure the ecient use of available resources while providing greater deployment flexibility. This paradigm allows to know the state of the network and its topology in real time, which makes it possible to reconfigure routes and allocate resources dynamically. This work presents a framework for SDN traffic engineering that uses the mathematical theory Network Calculus as a tool to subsidize the characterization and policing of packet flows. Through this theory, routing decisions and traffic distribution are based not only on values obtained by monitoring the network, but also on deterministic projections of traffic behavior. The results obtained in the experiments, proved the efficiency in the load balancing of the network based on flow delay, demonstrating gains in terms of total system throughput and enabling the reduction of the percentage of packet loss of the traffic flows. The framework proposed aims to contribute to the solution of the challenges related to establishing Traffic Engineering for SDN with specification of management mechanisms, adaptables to the topological changes of the network, the different characteristics of the flows and capable of distribute in a balanced way the traffic in the network.

A demanda de eficiência no gerenciamento das redes aumenta atualmente devido ao rápido desenvolvimento da computação em nuvem e a implantação em grande escala de centros de dados. O controle da infraestrutura deve ser capaz de classificar os diversos tipos de tráfego para aplicações diferentes, e prover o atendimento adequado no menor tempo possível. Porém, devido ao dinamismo da rede, nem sempre podem ser garantidos os requisitos mínimos necessários na Internet. Os mecanismos propostos para a engenharia de tráfego até hoje, são baseados em arquiteturas inflexíveis com a camada de controle e dados fortemente integrados. Isto dificulta um atendimento diferenciado adaptável aos diversos padrões de tráfego das aplicações modernas. Para enfrentar os problemas de flexibilidade das redes tradicionais, as Redes Definidas por Software, apresentam um paradigma inovador que separa as camadas de controle e encaminhamento de pacotes de forma a garantir a utilização eficiente dos recursos disponíveis, e ao mesmo tempo maior flexibilidade de implementação. Este paradigma permite conhecer o estado da rede e a sua topologia em tempo real, o que faz possível a reconfiguração de rotas e alocação de recursos de forma dinâmica. Esta dissertação apresenta um framework para engenharia de tráfego em SDN que utiliza a teoria matemática Network Calculus como ferramenta para subsidiar a caracterização e o policiamento de fluxos de pacotes. Através desta teoria, as decisões de encaminhamento e a distribuição do tráfego são baseadas não só por valores obtidos monitorando a rede, como também por projeções determinísticas que descrevem o comportamento do tráfego. Os resultados obtidos nos experimentos, comprovaram a eficiência no balanceamento de carga da rede em termos de atraso, demonstrando ganhos em termos de vazão do sistema e possibilitando a diminuição da porcentagem de perda de pacotes dos fluxos trafegados. O framework proposto visa contribuir na solução dos desafios relacionados a se estabelecer Engenharia de Tráfego para SDN com a especificação de mecanismos de gerenciamento adaptáveis as mudanças topológicas da rede, as diferentes características dos fluxos e que sejam capazes de distribuir de forma equilibrada o tráfego na rede. / The demand for network management efficiency is currently boosted by the rapid development of cloud computing and the large-scale deployment of data centers. Infrastructure control should be able to classify the various types of traffic for different applications, and provide adequate service in the shortest time possible. However, due to the dynamism of the network, the necessary minimum requirements on the Internet can not always be guaranteed. The proposed mechanisms for traffic engineering to date are based on inflexible architectures with the control and data layer strongly integrated. This hinders a differentiated service adaptable to the different traffic patterns of modern applications. To address the flexibility problems of traditional networks, Software Defined Networks presents an innovative paradigm that separates packet control and datapath layers to ensure the ecient use of available resources while providing greater deployment flexibility. This paradigm allows to know the state of the network and its topology in real time, which makes it possible to reconfigure routes and allocate resources dynamically. This work presents a framework for SDN traffic engineering that uses the mathematical theory Network Calculus as a tool to subsidize the characterization and policing of packet flows. Through this theory, routing decisions and traffic distribution are based not only on values obtained by monitoring the network, but also on deterministic projections of traffic behavior. The results obtained in the experiments, proved the efficiency in the load balancing of the network based on flow delay, demonstrating gains in terms of total system throughput and enabling the reduction of the percentage of packet loss of the traffic flows. The framework proposed aims to contribute to the solution of the challenges related to establishing Traffic Engineering for SDN with specification of management mechanisms, adaptables to the topological changes of the network, the different characteristics of the flows and capable of distribute in a balanced way the traffic in the network.

Les lanceurs spatiaux actuels, et en particulier Ariane 5, utilisent le réseau déterministe MIL-STD-1553B. Compte tenu des nouveaux objectifs de réduction des coûts et de la masse du système global ainsi que du support de trafic de télémesure multimédia, cette technologie n'est plus forcément optimale. Parmi les différents candidats de remplacement, cette thèse met en évidence les capacités du standard Ethernet à répondre à ces nouveaux objectifs tout en s'appuyant sur une utilisation de composants matériels et d'outils de développement existants à moindre coût (COTS). La première contribution porte sur l'évaluation de performances temporelles des architectures commutées. Les travaux mettent ainsi en évidence les gains et limites liés au choix d'une part du mode de communication (de maître/esclaves à producteurs/consommateur) et d'autre part à une future distribution de l'avionique. Pour cela, cette étude s'appuie sur une évaluation déterministe des délais de bout en bout par calcul réseau, simulations et expérimentations. Ces résultats ont été validés pour deux architectures commutées pour un scénario représentatif des vols actuels. La seconde contribution concerne l'amélioration de la disponibilité du système de communication. Il est proposé une stratégie de reconfiguration "temps réel" des chemins par supervision active du réseau. Dans le cadre d'exigences critiques, il est également proposé l'utilisation d'arbres couvrants multiples permettant d'anticiper la défaillance d'éléments d'interconnexion. Enfin, le choix d'architectures commutées et segmentées ne permet plus d'observer en tout point le réseau comme sur un bus. Pour cela, cette thèse met en avant les conditions et performances dans lesquelles un protocole de synchronisation d'horloges pourra contribuer à générer à partir de plusieurs points de captures une trace unique des échanges sur le réseau. Ce travail permettra d'identifier les tests pour une future validation du standard Ethernet pour les lanceurs spatiaux / Current space launchers, and particularly Ariane 5, use the deterministic network MIL-STD-1553B. According to the new objectives of cost and system mass reduction and of multimedia traffic support, this technology is not optimal anymore. Among the potential candidates, this thesis highlights the fact that such objectives can be achieved through the use of Ethernet standard based on components-on-the-shelf. The first contribution focuses on time performance evaluation of switched architectures. The gain and limits related to the communication mode (from master/slaves to producers/consummers) and future avionic distribution are studied. This study relies on a deterministic evaluation of the end-to-end delay by using network calculus, simulations and experiments. These results are validated with two switched architectures by using a scenario considered as representative of current flights. The second contribution is the network availability improvement. A real-time path reconfiguration strategy is proposed through active network supervision. Based on critical requirements, it is also suggested to use multiple spanning-trees for anticipating network element failures. The last contribution deals with the issue that in switched and segmented architectures it is not possible to collect all the traffic as in a bus. In order to do so, this thesis introduces the configurations under which a clock synchronization protocol could contribute to generate a single network trace from many collecting points. This work will enable to identify the tests for a future Ethernet standard validation in the framework of space launchers

L'augmentation du nombre de systèmes interconnectés et l’expansion des données échangées dans les réseaux avioniques ont contribué à la complexification des architectures de communication. Pour gérer cette évolution, une nouvelle solution basée sur un réseau cœur haut débit, e.g., l'AFDX (Avionics Full DupleX), a été implémentée sur l'A380. Cependant, il reste des réseaux bas débit, e.g, CAN ou A429, utilisés pour certaines fonctions spécifiques. Cette architecture réduit le délai de développement, mais en contrepartie, elle conduit à de l’hétérogénéité et à de nouveaux challenges pour garantir les contraintes temps-réel. Pour résoudre ces challenges, une architecture homogène basé sur l'AFDX pourrait apporter de grands avantages, tels que une facilité de l'installation et maintenance, et une réduction de poids et coûts. Cette architecture homogène doit supporter des applications de criticités mixtes, où coexistent les trafics critiques (SCT), Best-effort (BE) et le trafic AFDX actuel (RC). Pour atteindre ce but, nous commençons par évaluer les avantages et les inconvénients des solutions existantes par rapport aux contraintes avioniques. Cela nous conduit à sélectionner le Burst Limiting Shaper (BLS) (proposé par le groupe IEEE Time Sensitive Networking (TSN)) allié à un ordonnanceur Static Priority non-preemptif. Ainsi, nous identifions quatre contributions principales dans cette thèse. Tout d'abord, nous spécifions un AFDX étendu avec le TSN/BLS. Une analyse préliminaire basée sur de la simulation a donné des résultats encourageants pour poursuivre sur cette voie. En second, nous détaillons une analyse temporelle de l'AFDX étendu, grâce au Network Calculus, pour calculer des bornes maximales des délais pire cas des différents types de trafic, pour prouver le déterminisme du réseau et le respect des contraintes temporelles. Une analyse de performance préliminaire montre l'efficacité de la solution à améliorer les délais de RC, tout en garantissant les contraintes. Cependant, cette analyse a aussi montré certaines limitations du modèle en termes de pessimisme. Notre troisième contribution est par conséquent la réduction de ce pessimisme, grâce à une seconde modélisation de l'AFDX étendu, et à une méthode de paramétrage des variables système. Cette méthode permet d'améliorer les performances de RC tout en garantissant les contraintes temporelles du SCT et RC. Finalement, nous validons notre proposition à travers des études de cas avioniques réalistes pour vérifier son efficacité. Les résultats montrent une forte amélioration des délais de RC ainsi que de l'ordonnançabilité de SCT et RC, en comparaison à l'AFDX actuel et au Deficit Round Robin. / The growing number of interconnected end-systems and the expansion of exchanged data in avionics have led to an increase in complexity of the communication architecture. To cope with this trend, a first communication solution based on a high rate backbone network, i.e., the AFDX (Avionics Full Duplex Switched Ethernet), has been implemented by Airbus in the A380. Moreover, some low rate data buses, e.g., CAN or ARINC 429, are still used to handle some specific avionics domains. Although this architecture reduces the time to market, it conjointly leads to inherent heterogeneity and new challenges to guarantee the real-time requirements. To handle these emerging issues, a homogeneous avionic communication architecture based the AFDX technology to interconnect different avionics domains may bring significant advantages, such as easier installation and maintenance and reduced weight and costs. Furthermore, this homogeneous communication architecture needs to support mixed-criticality applications, where safety-critical traffic (SCT), current rate constraint AFDX traffic (RC) and best effort traffic (BE) co-exist. To achieve this aim, first, we assess the pros and cons of most relevant existing solutions vs the main avionics requirements, to support mixed-criticality applications on the AFDX network. Afterwards, the Burst Limiting Shaper (BLS) (proposed by IEEE Time Sensitive Networking (TSN) Task group) on top of a Non-Preemptive Static Priority (NP-SP) scheduler has been selected as the most promising solution. Hence, our main contributions in this thesis are fourfold. First, we specify the extended AFDX incorporating the TSN/BLS on top of NP-SP. A preliminary performance analysis based on simulations has been conducted. These first results were encouraging to pursue this proposal. Second, we conduct a timing analysis of the extended AFDX using Network Calculus to compute the delay upper bounds of the different traffic classes and prove the determinism of such a solution. The preliminary performance evaluation has shown the efficiency of the extended AFDX to enhance the RC delay bounds while guaranteeing the constraints. However, they have also highlighted some limitations of the proposed model in terms of pessimism. Third, we introduce a second model of the extended AFDX to enhance the delay bounds tightness. Moreover, we propose a tuning method of TSN/BLS parameters to enhance as much as possible the RC timing performance, while guaranteeing the constraints. Finally, we validate our proposal through representative case studies to assess its efficiency. The results show the enhancements of the RC delay bounds as well as the schedulability level of both SCT and RC traffic, in comparison to the current AFDX and Deficit Round Robin (DRR).

S rostoucím počtem řídicích systémů a jejich distribuovanosti získávájí komunikační sítě na důležitosti a objevují se nové výzkumné trendy. Hlavní problematikou v této oblasti, narozdíl od dřívějších řídicích systémů využívajících dedikovaných komunikačních obvodů, je časově proměnné zpoždění měřicích a řídicích signálů způsobené paketově orientovanými komunikačními prostředky, jako např. Ethernet. Aspekty komunikace v reálném čase byly v těchto sítích již úspěšně vyřešeny. Nicméně, analýzy trendů trhu předpovídají budoucí využití také IP sítí v průmyslové komunikaci pro časově kritickou procesní vyměnu dat. IP komunikace má ovšem pouze omezenou podporu v instrumentaci pro průmyslovou automatizace. Tato výzva byla nedávno technicky vyřešena v rámci projektu Virtual Automation Networks (virtuální automatizační sítě - VAN) zapojením mechanismů kvality služeb (QoS), které jsou schopny zajistit měkkou úroveň komunikace v reálném čase. Předložená dizertační práce se zaměřuje na aspekty výkonnosti reálného času z analytického hlediska a nabízí prostředek pro hodnocení využitelnosti IP komunikace pro budoucí průmyslové aplikace. Hlavním cílem této dizertační práce je vytvoření vhodného modelovacího rámce založeného na network calculus, který pomůže provést worst-case výkonnostní analýzu časového chování IP komunikačních sítí a jejich prvků určených pro budoucí použití v průmyslové automatizaci. V práci byla použita empirická analýza pro určení dominantních faktorů ovlivňujících časového chování síťových zařízení a identifikaci parametrů modelů těchto zařízení. Empirická analýza využívá nástroj TestQoS vyvinutý pro tyto účely. Byla navržena drobná rozšíření rámce network calculus, která byla nutná pro modelování časového chování používaných zařízení. Bylo vytvořeno několik typových modelů zařízení jako výsledek klasifikace různých architektur síťových zařízení a empiricky zjištěných dominantních faktorů. U modelovaných zařízení byla využita nová metoda identifikace parametrů. Práce je zakončena validací časových modelů dvou síťových zařízení (přepínače a směrovače) oproti empirickým pozorováním.

Les systèmes embarqués complexes (avions, satellites, drones...) contiennent de plus en plus de calculateurs. Désormais ce sont des dizaines voire des centaines de calculateurs qui communiquent à travers un réseau partagé. Une fonction est réalisée par la collaboration d'un ensemble de calculateurs qui s'échangent un nombre croissant d'informations. Dans un contexte de temps réel embarqué, il faut non seulement garantir que ces informations échangées sont correctes mais il faut aussi garantir qu'elles vérifient leurs contraintes temporelles. Du point de vue du réseau cela signifie qu'une information doit être échangée en respectant les délais qui lui sont imposés. Ceci implique de pouvoir borner le temps de traversée du réseau de chaque message afin de vérifier qu'il arrive dans les temps. Or les systèmes embarqués étant de plus en plus complexes et le nombre d'informations échangées étant en constante augmentation, cette borne est de plus en plus difficile à calculer. De plus il est important que cette borne soit le moins pessimiste possible afin d'éviter que le système soit surdimensionné. L'objectif de ce travail est de mettre en place un modèle capable de calculer ces bornes.Afin d'y parvenir nous nous sommes basés sur la méthode d'analyse du Calcul Réseau.Ce travail s'est en particulier attardé sur la modélisation des interactions qui existent entre les messages synchrones et les messages asynchrones. Les modèles présentés dans ce manuscrit prennent en compte les dates d'émission sur le réseau des messages synchrones lors du calcul des bornes supérieures de temps de traversée des messages asynchrones.Les principales contributions apportées par ce manuscrit sont :1. la présentation d'une nouvelle façon d'envisager l'utilisation des dates d'émission sur le bus CAN : la synchronisation faible.Ainsi que la modélisation complète d'un tel système et enfin l'évaluation du gain apporté par cette solution.2. une modélisation complète du réseau TTEthernet permettant d'évaluer finement l'impact des flux synchrones sur le tempsde traversée des flux asynchrones.3. une présentation de l'utilisation de la synchronisation dans le réseau TSN ainsi qu'un modèlecomplet permettant d'analyser cette nouvelle technologie. / Complex embedded systems (planes, satellites, drones ...) contain more and more calculators. From now on, these are tens or even hundreds of calculators that communicate through a shared network. A function is achieved by the collaboration of a set of devices that exchange a growing number of information. In an embedded real-time context, it must be ensured that these informations exchanged are correct but it must also be ensured that they verify their temporal constraints. From the network point of view, this means that informations must be exchanged respecting their deadlines. This implies being able to upper bound the traversal time of the network of each message in order to verify that it arrives in time. However, as embedded systems are more and more complex and as the amount of information exchanged is constantly increasing, this bound is increasingly difficult to compute. Furthermore, it is important that this upper bound to be the least pessimistic possible to avoid an oversized system.The goal of this work is to develop new methods of analysis in order to be able to compute these bounds.In order to achieve this, we used the Network Calculus method of analysis.This work focuses on the modeling of interactions between synchronous messages and asynchronous messages.The models presented in this work take into account the transmission dates on the network of synchronous messageswhen calculating the upper bounds of traversal time of the asynchronous messages.The main contributions are:1. the presentation of a new way of considering the use of the dates of emission on the CAN bus: the weak synchronization.As well as the complete modeling of such a system and finally the evaluation of the gain provided by this solution.2. a complete modeling of the TTEthernet network allowing to evaluate the impact of the synchronous flows on the traversal time of the asynchronous flows.3. a presentation of the use of synchronization in the TSN network and a complete model for analyzing this new technology.

Real-time system refers to the computing, communication, and information system with deadline requirements. To meet these deadline requirements, most systems use a mechanism known as the schedulability test which determines whether each of the admitted tasks can meet its deadline. A new task will not be admitted unless it passes the schedulability test. Schedulability tests can be either direct or indirect. The utilization based schedulability test is the most common schedulability test approach, in which a task can be admitted only if the total system utilization is lower than a pre-derived bound. While the utilization bound based schedulability test is simple and effective, it is often difficult to derive the bound. For its analytical complexity, utilization bound results are usually obtained on a case-by-case basis. In this dissertation, we develop a general framework that allows effective derivation of schedulability bounds for different workload patterns and schedulers. We introduce an analytical model that is capable of describing a wide range of tasks' and schedulers'€™ behaviors. We propose a new definition of utilization, called workload rate. While similar to utilization, workload rate enables flexible representation of different scheduling and workload scenarios and leads to uniform proof of schedulability bounds. We introduce two types of workload constraint functions, s-shaped and r-shaped, for flexible and accurate characterization of the task workloads. We derive parameterized schedulability bounds for arbitrary static priority schedulers, weighted round robin schedulers, and timed token ring schedulers. Existing utilization bounds for these schedulers are obtained from the closed-form formula by direct assignment of proper parameters. Some of these results are applied to a cluster computing environment. The results developed in this dissertation will help future schedulability bound analysis by supplying a unified modeling framework and will ease the implementation practical real-time systems by providing a set of ready to use bound results.

Recently, wireless sensor network (WSN) has become a promising technology with a wide range of applications such as supply chain monitoring and environment surveillance. It is typically composed of multiple tiny devices equipped with limited sensing, computing and wireless communication capabilities. Design of such networks presents several technique challenges while dealing with various requirements and diverse constraints. Performance analysis and deployment techniquesare required to provide insight on design parameters and system behaviors. Based on network calculus, a deterministic analysis method is presented for evaluating the worst-case delay and buffer cost of sensor networks. To this end,traffic splitting and multiplexing models are proposed and their delay and buffer bounds are derived. These models can be used in combination to characterize complex traffic flowing scenarios. Furthermore, the method integrates a variable duty cycle to allow the sensor nodes to operate at low rates thus saving power. In an attempt to balance traffic load and improve resource utilization and performance,traffic splitting mechanisms are introduced for sensor networks with general topologies. To provide reliable data delivery in sensor networks, retransmission has been one of the most popular schemes. We propose an analytical method to evaluate the maximum data transmission delay and energy consumption of two types of retransmission schemes: hop-by-hop retransmission and end-to-end retransmission.In order to validate the tightness of the bounds obtained by the analysis method, the simulation results and analytical results are compared with various input traffic loads. The results show that the analytic bounds are correct and tight. Stochastic network calculus has been developed as a useful tool for Qualityof Service (QoS) analysis of wireless networks. We propose a stochastic servicecurve model for the Rayleigh fading channel and then provide formulas to derive the probabilistic delay and backlog bounds in the cases of deterministic and stochastic arrival curves. The simulation results verify that the tightness of the bounds are good. Moreover, a detailed mechanism for bandwidth estimation of random wireless channels is developed. The bandwidth is derived from the measurement of statistical backlogs based on probe packet trains. It is expressed by statistical service curves that are allowed to violate a service guarantee with a certain probability. The theoretic foundation and the detailed step-by-step procedure of the estimation method are presented. One fundamental application of WSNs is event detection in a Field of Interest(FoI), where a set of sensors are deployed to monitor any ongoing events. To satisfy a certain level of detection quality in such applications, it is desirable that events in the region can be detected by a required number of sensors. Hence, an important problem is how to conduct sensor deployment for achieving certain coverage requirements. In this thesis, a probabilistic event coverage analysis methodis proposed for evaluating the coverage performance of heterogeneous sensor networks with randomly deployed sensors and stochastic event occurrences. Moreover,we present a framework for analyzing node deployment schemes in terms of three performance metrics: coverage, lifetime, and cost. The method can be used to evaluate the benefits and trade-offs of different deployment schemes and thus provide guidelines for network designers. / <p>QC 20120906</p>