L’analyse de flux de données est utilisée dans beaucoup de contexte où la masse des données et/ou le débit auquel elles sont générées, excluent d’autres approches (par exemple le traitement par lots). Le modèle flux fourni des solutions aléatoires et/ou fondées sur des approximations pour calculer des fonctions d’intérêt sur des flux (repartis) de n-uplets, en considérant le pire cas, et en essayant de minimiser l’utilisation des ressources. En particulier, nous nous intéressons à deux problèmes classiques : l’estimation de fréquence et les poids lourds. Un champ d’application moins courant est le traitement de flux qui est d’une certaine façon un champ complémentaire aux modèle flux. Celui-ci fournis des systèmes pour effectuer des calculs génériques sur les flux en temps réel souple, qui passent à l’échèle. Cette dualité nous permet d’appliquer des solutions du modèle flux pour optimiser des systèmes de traitement de flux. Dans cette thèse, nous proposons un nouvel algorithme pour la détection d’éléments surabondants dans des flux repartis, ainsi que deux extensions d’un algorithme classique pour l’estimation des fréquences des items. Nous nous intéressons également à deux problèmes : construire un partitionnement équitable de l’univers des n-uplets par rapport à leurs poids et l’estimation des valeurs de ces n-uplets. Nous utilisons ces algorithmes pour équilibrer et/ou délester la charge dans les systèmes de traitement de flux. / Nowadays stream analysis is used in many context where the amount of data and/or the rate at which it is generated rules out other approaches (e.g., batch processing). The data streaming model provides randomized and/or approximated solutions to compute specific functions over (distributed) stream(s) of data-items in worst case scenarios, while striving for small resources usage. In particular, we look into two classical and related data streaming problems: frequency estimation and (distributed) heavy hitters. A less common field of application is stream processing which is somehow complementary and more practical, providing efficient and highly scalable frameworks to perform soft real-time generic computation on streams, relying on cloud computing. This duality allows us to apply data streaming solutions to optimize stream processing systems. In this thesis, we provide a novel algorithm to track heavy hitters in distributed streams and two extensions of a well-known algorithm to estimate the frequencies of data items. We also tackle two related problems and their solution: provide even partitioning of the item universe based on their weights and provide an estimation of the values carried by the items of the stream. We then apply these results to both network monitoring and stream processing. In particular, we leverage these solutions to perform load shedding as well as to load balance parallelized operators in stream processing systems.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-03-27T14:11:27Z No. of bitstreams: 2 Dissertação - Mário Augusto da Cruz - 2014.pdf: 990265 bytes, checksum: 491a60613f98d994e59969035aa281ca (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-03-27T14:49:41Z (GMT) No. of bitstreams: 2 Dissertação - Mário Augusto da Cruz - 2014.pdf: 990265 bytes, checksum: 491a60613f98d994e59969035aa281ca (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-03-27T14:49:41Z (GMT). No. of bitstreams: 2 Dissertação - Mário Augusto da Cruz - 2014.pdf: 990265 bytes, checksum: 491a60613f98d994e59969035aa281ca (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-12-16 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Software Defined Networking represents a new paradigm that eases the operation, monitoring and network managing through the decoupling between the control plane and the data plane. However, in this new context, some classic solutions in the network monitoring field need to be revisited, as there are new constraints, but there are also new opportunities. In monitoring context, one strategy commonly used, mainly in high capacity networks, is the tracking of the most frequent items, also known as heavy hitters. One approach to monitoring the most frequent items consists in detecting the hierarchical heavy hitters, which allows an efficient real time monitoring. In this work, we propose and evaluate a new monitoring solution capable of online detection of hierarchical heavy hitters, using the characteristics of software defined networks, in special the OpenFlow protocol. Our proposal, combines a flexible accounting of flow rules, from OpenFlow switches, with inspection of traffic samples through a dedicated device. We evaluate our proposal in a simulated and emulated environments, both using packet traces generated artificially and also from real networks. The results show that our proposal has satisfactory accuracy and low convergence time in comparison to a previous solution to OpenFlow networks, in addition to identify heavy hitters in two dimensions. / As Redes Definidas por Software representam um novo paradigma que flexibiliza a operação, o monitoramento e a gerência de redes através do desacoplamento entre o plano de controle e o plano de dados. No entanto, nesse novo contexto, algumas soluções clássicas da área de monitoramento de redes precisam ser revistas, pois há novas restrições, mas também novas oportunidades. No contexto de monitoramento, uma estratégia comumente utilizada, sobretudo em redes de alta capacidade, é o acompanhamento dos itens mais frequentes, também conhecidos como heavy hitters. Uma das abordagens para monitoramento dos itens mais frequentes consiste em detectar as agregações hierárquicas de fluxos, a qual possibilita realizar um monitoramento eficiente em tempo real. Neste trabalho, propomos e avaliamos uma nova solução de monitoramento capaz de detectar de maneira online as agregações hierárquicas de fluxos, utilizando características de redes definidas por software, em especial do protocolo OpenFlow. Nossa proposta, combina uma contabilização flexível de regras de fluxos, proveniente dos comutadores OpenFlow, com uma inspeção de amostras de tráfego através de um dispositivo dedicado. Avaliamos nossa proposta em ambientes simulado e emulado, utilizando traces de pacotes gerados artificialmente e também de redes reais. Os resultados mostram que nossa proposta possui uma acurácia satisfatória e baixo tempo de convergência em comparação a uma solução anterior para redes OpenFlow, além de identificar heavy hitters em duas dimensões.