Um novo gerador de topologias na internet

Abstract

Resumo: A geração de topologias sintéticas da Internet tem aplicação fundamental em experimentos com novos protocolos e serviços, propostos com frequência pela comunidade de pesquisa na área de redes de computadores e sistemas distribuídos. As novas propostas são testadas em laboratório, usando simuladores de redes, sobre topologias sintéticas geradas para o experimento. Os resultados obtidos e sua exatidão em relação ao comportamento do sistema proposto na rede real dependem da similaridade entre a rede real e a topologia sintética utilizada nos testes. Além disso, as topologias sintéticas auxiliam em atividades de planejamento da rede e no estudo de sua evolução, pois podemos utilizá-las para simular o crescimento da rede no futuro. Este trabalho apresenta uma caracterização da evolução da topologia dos sistemas autônomos da Internet, bem como uma comparação da topologia real com topologias sintéticas geradas pelo gerador de topologias Inet. A comparação é feita com base em métricas de distância em grafos e suas derivadas, métricas de conectividade da rede e a distribuição dos graus dos vértices. Os resultados indicam que as métricas baseadas em distância são invariantes e muito apropriadas para caracterizar a topologia. Este trabalho também propõe um novo gerador de topologias sintéticas da Internet denominado NIT. Este gerador é baseado no gerador Inet, porém utiliza modelos mais atuais para as métricas, além de incluir novas métricas no processo de geração da topologia. Os resultados do gerador NIT são melhores do que os do Inet em todas as métricas avaliadas. Em consequência, o NIT produz topologias sintéticas mais similares às da Internet atual do que o Inet. Os resultados evidenciam que a associação de métricas de distância, conectividade e distribuição dos graus dos vértices pode ser utilizada para fundamentar uma nova geração de geradores de topologias que representem de forma mais exata as características da Internet atual.

Abstract: The generation of synthetic topologies that resemble the Internet autonomous systems graph has applications in studies of new protocols and services, often proposed by the research community in computer networks and distributed systems areas. The new proposals are tested in experiments using network simulators that generate synthetic topologies, and test the proposals over these topologies. The similarity between the actual network and the synthetic topologies used in the tests is crucial to the accuracy of the results. Moreover, synthetic topologies also help in network planning and network evolution studies, since they can be used to simulate the Internet growth. This dissertation presents a characterization of the evolution of the Internet autonomous systems topology, and a comparison of the actual topology with synthetic topologies generated by the Inet topology generator. This comparison is based on metrics of distance in graphs and its derivatives, metrics of connectivity and the distribution of vertex degrees. The results indicate that the distance-based metrics are invariant and appropriate to characterize the topology. This work also proposes a new topology generator called NIT. This generator is based on the Inet generator, but it takes advantage of the new models for the metrics, described in this work. It also includes new metrics in the topology generation process. The results of the NIT topology generator are better than those of the Inet in all evaluated metrics. In this way, the NIT produces synthetic topologies more similar to the current Internet than the Inet does. The results show that the composition of distance and distance-based metrics, connectivity metric and degree distribution may be used to build a new generation of topology generators that resemble the current Internet characteristics more accurately.