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

Detalhes bibliográficos
Ano de defesa: 2017
Autor(a) principal: Silveira, Fernando Ávila Fossi
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Federal do Espírito Santo
BR
Mestrado em Informática
Centro Tecnológico
UFES
Programa de Pós-Graduação em Informática
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
004
Link de acesso: http://repositorio.ufes.br/handle/10/9853
Resumo: Actual 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.