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.

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.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2016-04-20T12:24:18Z No. of bitstreams: 2 Dissertação - Marcus Vinícius Gonzaga Ferreira - 2015.pdf: 5767061 bytes, checksum: 8c8e76bfe96355cd9d774d9aa9673b44 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2016-04-20T12:25:56Z (GMT) No. of bitstreams: 2 Dissertação - Marcus Vinícius Gonzaga Ferreira - 2015.pdf: 5767061 bytes, checksum: 8c8e76bfe96355cd9d774d9aa9673b44 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2016-04-20T12:25:56Z (GMT). No. of bitstreams: 2 Dissertação - Marcus Vinícius Gonzaga Ferreira - 2015.pdf: 5767061 bytes, checksum: 8c8e76bfe96355cd9d774d9aa9673b44 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-12-11 / In this work we propose an algorithm to allocate resource blocks for LTE (Long Term Evolution) communication systems that takes into account the maximum delay guarantee and MCS (Modulation and Coding Scheme) constraints on the downlink transmission. At first, we propose an allocation algorithm which tries to reduce user‘s delay using the information of the network real delay and the channel transmission quality. Next, we propose an allocation algorithm which considers the channel transmission quality and the delay target, which is estimated through Network Calculus using service curve and MFBAP (Multifractal Bounded Arrival Process) envelope process, in order to decide on the scheduling of available radio resources. Comparisons with other allocation algorithms are carried out through QoS (Quality of Service) parameters such as average delay, total throughput, loss rate, fairness and processing time, verifying the efficiency of the proposed algorithm. / Neste trabalho é proposto um algoritmo de alocação de blocos de recurso para sistemas de comunicação LTE (Long Term Evolution) onde é levado em conta o critério de retardo máximo e as restrições impostas pelo esquema MCS (Modulation and Coding Scheme) para transmissão downlink. Primeiramente, é proposto um algoritmo de alocação que tenta reduzir o retardo do usuário utilizando a informação do retardo real da rede e a qualidade de transmissão do canal. Em seguida, é proposto um algoritmo de alocação que considera a qualidade de transmissão do canal e o limitante de retardo, estimado através de Cálculo de Rede utilizando curva de serviço e processo envelope MFBAP (Multifractal Bounded Arrival Process), para decidir sobre a alocação de recursos de rádio disponíveis. São realizadas comparações com outros algoritmos de alocação através de parâmetros de QoS (Quality of Service) como retardo médio, vazão total, taxa de perda, índice de justiça (fairness) e tempo de processamento, verificando a eficiência do algoritmo proposto.

Internet ha supuesto el despegue de las redes de conmutación de paquetes, las ha convertido en un medio al que todo el mundo quiere acceder, y ha obligado a replantear todas las previsiones que manejaban los operadores sobre el tráfico que iban a soportar sus redes en cada una de sus partes: el acceso, la agregación y la dorsal. Precisamente, la evaluación de estas y otras situaciones deben estar incluidas en el proceso de diseño y planificación de cualquier red, en lo que se ha denominado planificación estratégica. La estimación de la demanda de tráfico resulta especialmente importante porque permite al operador anticiparse a situaciones de congestión y bloqueo de la red. Utiliza herramientas de modelado del tráfico, bien para su cálculo analítico o para su estudio mediante simulación, y al ser una herramienta fundamental, existe un extenso catálogo de modelos de tráfico: genéricos y particularizados, de fuentes individuales y de redes completas, de elementos de interconexión y de enlaces. En esta Tesis, se han analizado los diferentes modelos existentes y se ha desarrollado un nuevo modelo que tiene en cuenta el comportamiento del tráfico desde su preparación por parte de la capa de aplicación, hasta su inserción en la capa física. El modelo propuesto parte de la solución ON-OFF tradicional, aunque aplicado a tres niveles diferentes (conexión, sesión y ráfaga), de forma que cada estado ON se encuentra modulado por el modelo correspondiente a la capa inferior. Como alternativa más simple, surgen los modelos multifuente, que intentan introducir el efecto de la interacción entre las diferentes fuentes, también conocido como agregación. Para considerar este caso, se ha realizado un estudio de modelos específicos para su aplicación a puntos de agregación, especialmente los situados en la red de acceso, al ser ésta la parte de la red que más alto coste presenta en su implementación. Partiendo del modelo ON-OFF para una sola fuente, se ha propuesto una variante multifuente, que aprovecha las propiedades de la función de distribución binomial para realizar el cálculo del tráfico agregado por un número determinado de fuentes. El resultado ha sido comparado mediante la observación de flujos reales, tal como propone la teoría del Network Calculus, y que ha sido evaluada y aplicada en este trabajo con ejemplos prácticos que se han incluido en el documento. El estudio realizado en esta Tesis concluye que el tráfico de fuente está condicionado a tres premisas fundamentales: el usuario, el servicio y la tecnología de acceso, de donde surge un nuevo concepto que especifica de forma sistemática y ordenada todas las variaciones, denominada CASUAL (Cubo de Acceso/Servicios/Usuarios de Asignación Libre) y ha sido aplicada en una herramienta realizada a su efecto, junto con los modelos de tráfico de fuente propuestos. / Internet has been the catalyst of the development of packet switched networks, which have become the resource which everyone wants to access. As a consequence, the operators need to recalculate all their forecasts about the traffic to be transported by their networks. In fact, the evaluation of these and other situations should be included within the design and planning phases of any network, in the so called strategic planning overall process.Traffic demand estimation is particularly interesting, since it allows the operator to anticipate bottlenecks and blocking situations of the network. It uses traffic modelling tools, either for their analytical or simulation-based study. Since they have become an essential tool, there is a wide range of traffic models: generic and particularized, for individual sources and complete networks, for interconnection elements and links.In this thesis, we have analyzed the different models and have developed a new model that takes into account traffic patterns from preparation by the application layer to its insertion into the physical layer. The proposed model is based on the traditional on-off solution, but applied to three different levels (connection, session and burst), so that each ON state is modulated by the model corresponding to the bottom layer. As a simpler alternative, multisource models emerge, seeking to introduce the effect of the interaction between different sources, also known as aggregation. To consider this case, it has made a study of specific models for application to aggregation points, especially those located in the access network, as this is the part of the network that has higher cost in implementation. Based on the ON-OFF model for a single source, is a proposed multi-source variant, which exploits the properties of the binomial distribution function for the calculation of the aggregate traffic for a specified number of sources. The result has been compared by observation of actual flows, as proposed by the theory of Network Calculus, and has been evaluated and implemented in this work with practical examples that are included in the document.The study in this thesis concludes that the traffic source is conditioned on three fundamental premises: the user, service and technology access, where there was a new concept that specifies a systematic and orderly all the variations, called CASUAL (Cube of Access / Services / Users with Free Allocation) and has been implemented in a tool made of its effect, along with the traffic source models proposed.

Le Network Calculus est une théorie visant à calculer des bornes pire-cas sur les performances des réseaux de communication. Le réseau est modélisé par un graphe orienté où les noeuds représentent des serveurs, et les flux traversant le réseau doivent suivre les arcs. S'ajoutent à cela des contraintes sur les courbes de trafic (la quantité de données passées par un point depuis la mise en route du réseau) et sur les courbes de service (la quantité de travail fournie par chaque serveur). Pour borner les performances pire-cas, comme la charge en différents points ou les délais de bout en bout, ces enveloppes sont combinées à l'aide d'opérateurs issus notamment des algèbres tropicales : min, +, convolution-(min, +)... Cette thèse est centrée sur l'algorithmique du Network Calculus, à savoir comment rendre effectif ce formalisme. Ce travail nous a amené d'abord à comparer les variations présentes dans la littérature sur les modèles utilisés, révélant des équivalences d'expressivité comme entre le Real-Time Calculus et le Network Calculus. Dans un deuxième temps, nous avons proposé un nouvel opérateur (min, +) pour traiter le calcul de performances en présence d'agrégation de flux, et nous avons étudié le cas des réseaux sans dépendances cycliques sur les flux et avec politique de service quelconque. Nous avons montré la difficulté algorithmique d'obtenir précisément les pires cas, mais nous avons aussi fourni une nouvelle heuristique pour les calculer. Elle s'avère de complexité polynomiale dans des cas intéressants. / Network Calculus is a theory aiming at computing worst-case bounds on performances in communication networks. The network is usually modelled by a digraph : the servers are located on the nodes and the flows must follow path in the digraph. There are constraints on the trafic curves (how much data have been through a given point since the activation of the network) and on the service curves (how much work each server may provide). To derive bounds on the worst-case performances, as the backlog or the end-to-end delay, these envelopes are combined thanks to tropical algebra operators: min, +, convolution... This thesis focuses on Network Calculus algorithmics, that is how effective is this formalism. This work led us to compare various models in the litterature, and to show expressiveness equivalence between Real-Time Calculus and Network Calculus. Then, we suggested a new (min, +) operator to compute performances bounds in networks with agregated flows and we studied feed-forward networks under blind multiplexing. We showed the difficulty to compute these bounds, but we gave an heuristic, which is polynomial for interesting cases.

<p>Recently, wireless sensor network (WSN) has become a promising technologywith a wide range of applications such as supply chain monitoringand environment surveillance. It is typically composed of multiple tiny devicesequipped with limited sensing, computing and wireless communicationcapabilities. Design of such networks presents several technique challengeswhile dealing with various requirements and diverse constraints. Performanceanalysis techniques are required to provide insight on design parametersand system behaviors.</p><p>Based on network calculus, we present a deterministic analysis methodfor evaluating the worst-case delay and buffer cost of sensor networks. Tothis end, three general traffic flow operators are proposed and their delayand buffer bounds are derived. These operators can be used in combinationto model any complex traffic flowing scenarios. Furthermore, the methodintegrates a variable duty cycle to allow the sensor nodes to operate at lowrates thus saving power. In an attempt to balance traffic load and improveresource utilization and performance, traffic splitting mechanisms areintroduced for mesh sensor networks. Based on network calculus, the delayand buffer bounds are derived in non-splitting and splitting scenarios.In addition, analysis of traffic splitting mechanisms are extended to sensornetworks with general topologies. To provide reliable data delivery in sensornetworks, retransmission has been adopted as one of the most popularschemes. We propose an analytical method to evaluate the maximum datatransmission delay and energy consumption of two types of retransmissionschemes: hop-by-hop retransmission and end-to-end retransmission.</p><p>We perform a case study of using sensor networks for a fresh food trackingsystem. Several experiments are carried out in the Omnet++ simulationenvironment. In order to validate the tightness of the two bounds obtainedby the analysis method, the simulation results and analytical results arecompared in the chain and mesh scenarios with various input traffic loads.From the results, we show that the analytic bounds are correct and tight.Therefore, network calculus is useful and accurate for performance analysisof wireless sensor network.</p> / Ipack VINN Excellence Center

Le Network Calculus est une théorie visant à calculer des bornes pire-cas sur les performances des réseaux de communication. Le réseau est modélisé par un graphe orienté où les noeuds représentent des serveurs, et les flux traversant le réseau doivent suivre les arcs. S'ajoutent à cela des contraintes sur les courbes de trafic (la quantité de données passées par un point depuis la mise en route du réseau) et sur les courbes de service (la quantité de travail fournie par chaque serveur). Pour borner les performances pire-cas, comme la charge en différents points ou les délais de bout en bout, ces enveloppes sont combinées à l'aide d'opérateurs issus notamment des algèbres tropicales : min, +, convolution-(min, +)... Cette thèse est centrée sur l'algorithmique du Network Calculus, à savoir comment rendre effectif ce formalisme. Ce travail nous a amené d'abord à comparer les variations présentes dans la littérature sur les modèles utilisés, révélant des équivalences d'expressivité comme entre le Real-Time Calculus et le Network Calculus. Dans un deuxième temps, nous avons proposé un nouvel opérateur (min, +) pour traiter le calcul de performances en présence d'agrégation de flux, et nous avons étudié le cas des réseaux sans dépendances cycliques sur les flux et avec politique de service quelconque. Nous avons montré la difficulté algorithmique d'obtenir précisément les pires cas, mais nous avons aussi fourni une nouvelle heuristique pour les calculer. Elle s'avère de complexité polynomiale dans des cas intéressants.

Le calcul réseau (network calculus) est une théorie basée sur l’algèbre min-plus. Il offre un cadre formel de modélisation des réseaux de communication. Il a été utilisé pour certifier le réseau AFDX embarqué dans l’A380 de Airbus. Seulement, les bornes sur le délai annoncés par ces travaux de certification souffrent d’une sur-approximation dans le cas précis de l’agrégation dans un contexte de priorité statique non préemptive.L’objectif de nos travaux est de réduire cette sur-approximation. Dans cette thèse, nous proposons un service résiduel permettant d’obtenir de meilleurs bornes sur le délai dans le cas de la politique à priorité statique non préemptive et de la politique DRR. Nous montrons aussi comment ces deux politiques peuvent être combinées dans une politique hiérarchique à deux niveaux. / The thesis addresses performance analysis of embedded real time network using network calculus. Network calculus is a theory based on min-plus algebra. We use network calculus to assess the quality of service of a residual flow in two context : aggregation with non-preemptive priority policy and DRR policy. The main contribution concerns the evaluation of residual service, given to each flow. We also present how to handle DRR and non-preemptive priority policy hierrachically.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2015-10-22T17:54:48Z No. of bitstreams: 2 Dissertação - Rosana de Paula Lucas - 2014.pdf: 2188388 bytes, checksum: 3657f86e73f4c67924c818227205f5d6 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2015-10-22T17:56:21Z (GMT) No. of bitstreams: 2 Dissertação - Rosana de Paula Lucas - 2014.pdf: 2188388 bytes, checksum: 3657f86e73f4c67924c818227205f5d6 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-10-22T17:56:21Z (GMT). No. of bitstreams: 2 Dissertação - Rosana de Paula Lucas - 2014.pdf: 2188388 bytes, checksum: 3657f86e73f4c67924c818227205f5d6 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-12-04 / In this thesis, we present an algorithm for adaptive estimation of the parameter (Hurst parameter) that measures the selfsimilar degree of the network traffic process. Using this parameter, called the Global Scale parameter, we developed an adaptive bandwidth allocation scheme. We evaluate the performance of this transmission rate allocation scheme with adaptive global parameter, comparing its performance to that of another algorithm that uses only one value for the Hurst parameter. Additionally, using the concepts of Network Calculus, specifically the Effective envelope, we obtain estimates for the quality of service (QoS) parameters. That is, we present a proposal for estimating average queue size (backlog) and delay for different network traffic traces. To this end, we derive an equation for the effective envelope of network traffic trace that can be seen as a generalization of the Multifractal Bounded Arrival Process (MFBAP). Comparisons between the real backlog and delay values are carried out to those estimated by using the proposed Effective Envelope for various violation probabilities and with those obtained by other Envelop Processes. / Nesta dissertação, apresentamos um algoritmo para estimação adaptativa do parâmetro que mede o grau de autossimilaridade do processo de tráfego. Utilizando esse parâmetro, denominado de Parâmetro de Escala Global, elaboramos um esquema de alocação adaptativo de banda. Avaliamos o desempenho deste esquema de alocação de banda com parâmetro de escala global adaptativo comparando seu desempenho com outro algoritmo que utiliza apenas um valor para o parâmetro de Hurst. Além disso, utilizando os conceitos de Cálculo de Rede (Network Calculus), mais especificamente de Envelope Efetivo, obtemos estimativas para parâmetros de qualidade de serviço. Ou seja, apresentamos uma proposta de método para estimação de tamanho médio da fila (backlog) e retardo (delay) para diferentes séries de tráfego de redes. Para tal, deduzimos uma equação para o Envelope Efetivo de séries de tráfego, que pode ser vista como uma generalização do Processo Envelope do modelo Processo de Chegada com Limitante (MFBAP-Multifractal Multifractal Bounded Arrival Process). São realizadas comparações entre os valores de backlog e delay reais (séries de tráfego reais) com os valores limitantes estimados utilizando o Envelope Efetivo proposto para vários valores de probabilidade de violação e com obtidos por outros Processos Envelopes.