Minimização do conjunto de observadores para geração de matrizes de tráfego

Página do item simplificado
dc.contributor.advisor-co1Moraes, Renato Elias Nunes de
dc.contributor.advisor1Villaça, Rodolfo da Silva
dc.contributor.authorSilveira, Fernando Ávila Fossi
dc.contributor.referee1Zambon, Eduardo
dc.contributor.referee2Verdi, Fábio Luciano
dc.date.accessioned2018-08-02T00:03:50Z
dc.date.available2018-08-01
dc.date.available2018-08-02T00:03:50Z
dc.date.issued2017-08-07
dc.description.abstractActual society rely on computer networks, so the management of these networks is an essential task. In order to manage a computer network it is necessary to know how information travels through it. A way to obtain this knowledge is by generating traffic matrices, which indicates the traffic volume exchanged between each pair of devices in the network. To generate these matrices is necessary to install observers in order to measure the traffic in the links, however this is a very costly operation. In recent years, data streaming algorithms based on probabilistic data structures have enabled traffic monitoring at a low computational cost. The manipulation of probabilistic data structures in observers can be done quickly and with little memory usage. However, even with probabilistic data structures, it is still necessary to install observers on all the devices to be monitored in the network in order to generate the traffic matrices, which leads to high implementation costs. In this context, this master’s thesis proposes and defines the problem of Minimizing the Set of Observers for Generating Traffic Matrices (MCO-MT), which consists of minimizing the number of observers installed in the network, that is, minimizing the size of the set of observers required in generating traffic matrices using probabilistic data structures. The problem is modeled and solved as a Minimum Set Covering Problem. In addition to the definition of MCO-MT, this work proposes: i) the development of a tool, called BitMatrix, for simulating and validating the generation of traffic matrices using data streaming algorithms based on probabilistic data structures; ii) two algorithms to solve the MCO-MT: a greedy heuristic and a greedy randomized heuristic combined with a local search to create a Greedy Randominzed Adpatative Search Procedure (GRASP), and iii) an data streaming algorithm to generate traffic matrices from a reduced set of observers. Extensive computational experiments are presented to validate the effectiveness of the proposed solutions.eng
dc.description.resumoA sociedade atual é dependente de redes de computadores, portanto gerenciar essas redes é tarefa de fundamental importância. Para que se possa gerenciar redes de computadores é necessário que se conheça como a informação trafega por elas. Uma das maneiras de se obter esse conhecimento é através da geração das matrizes de tráfego, que indicam o volume de informações trocadas entre cada par de dispositivos da rede. Para gerar essas matrizes é necessária a instalação de observadores afim de medir o tráfego nos enlaces, entretanto essa operação é muito custosa. Nos últimos anos, algoritmos de processamento de cadeia de dados baseados em estruturas de dados probabilísticas permitiram o monitoramento do tráfego a um baixo custo computacional. A manipulação de estruturas de dados probabilísticas nos observadores pode ser feita de forma rápida e com pouco espaço de memória. Entretanto, mesmo com estruturas de dados probabilísticas, ainda é necessária a instalação de observadores em todos os dispositivos da rede monitorada para geração das matrizes de tráfego, o que incorre em altos custos de implantação. Nesse contexto, esta dissertação propõe e define o problema de Minimização do Conjunto de Observadores para Geração de Matrizes de Tráfego (MCO-MT) que consiste em minimizar a quantidade de observadores instalados na rede, ou seja, minimizar o tamanho do conjunto de observadores necessários para gerar matrizes de tráfego utilizando estruturas de dados probabilísticas. O problema é modelado e resolvido como um problema de Cobertura de Conjuntos. Além da definição do MCO-MT, este trabalho propõe: i) o desenvolvimento de uma ferramenta, denominada BitMatrix, para simulação e validação da geração de matrizes de tráfego utilizando algoritmos de processamento de cadeia de dados baseados em estruturas de dados probabilísticas, ii) dois algoritmos para resolver o MCO-MT: uma heurística gulosa e uma heurística gulosa aleatória combinada com uma busca local para formar um algoritmo GRASP e iii) um algoritmo de processamento de cadeia de dados baseado em estrutura de dados probabilísticas para gerar matrizes de tráfego a partir de um conjunto reduzido de observadores. Extensos experimentos computacionais são apresentados para validar a eficácia das soluções propostas.
dc.formatText
dc.identifier.citationSILVEIRA, Fernando Ávila Fossi. Minimização do conjunto de observadores para geração de matrizes de tráfego. 2017. 67 f. Dissertação (Mestrado em Informática) - Universidade Federal do Espírito Santo, Centro Tecnológico, Vitória, 2017.
dc.identifier.urihttp://repositorio.ufes.br/handle/10/9853
dc.languagepor
dc.publisherUniversidade Federal do Espírito Santo
dc.publisher.countryBR
dc.publisher.courseMestrado em Informática
dc.publisher.departmentCentro Tecnológico
dc.publisher.initialsUFES
dc.publisher.programPrograma de Pós-Graduação em Informática
dc.rightsopen access
dc.subjectTraffic matriceseng
dc.subjectData streaming algorithmseng
dc.subjectCombinatorial optimizationeng
dc.subjectMatrizes de trafego (Computação)por
dc.subjectAlgoritmos de processamento de cadeia de dadospor
dc.subject.br-rjbnAlgoritmos
dc.subject.br-rjbnOtimização combinatória
dc.subject.br-rjbnRedes de computadores - Gerência
dc.subject.cnpqCiência da Computação
dc.subject.udc004
dc.titleMinimização do conjunto de observadores para geração de matrizes de tráfego
dc.typemasterThesis
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Dissertacao-abnt.pdf
Tamanho:
1.6 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Coleções
Mestrado em Informática