Roteamento tolerante a falhas baseado em desvios de alta conectividade

Orientador: Elias Procópio Duarte JuniorDissertaçao (mestrado) - Universidade Federal do Paraná, Setor de Ciencias Exatas, Programa de Pós-Graduaçao em Informática. Defesa: Curitiba, 2003Inclui bibliografiaResumo: Este trabalho apresenta uma abordagem para roteamento tolerante a falhas baseada em desvios de alta conectividade. O objetivo desta abordagem é permitir que os nodos da rede continuem a se comunicar, mesmo durante o período de tempo em que o protocolo de roteamento utilizado ainda não atualizou as tabelas de rotas dos roteadores para refletir uma falha ocorrida na rede. O protocolo de roteamento BGP-4 (Border Gateway Protocol versão 4), utilizado no roteamento da Internet, pode levar minutos para atualizar as tabelas de rotas dos roteadores de modo a refletir urna falha ocorrida na rede. gerando potenciais perdas de pacotes e de conexão entre as aplicações que se comunicam através da rede. Para evitar que tal situação ocorra, rotas alternativas são criadas antes do protocolo de roteamento atualizar as tabelas de rotas dos roteadores, ou seja, sem a informação de qual parte da rede está falha. Desta forma, as rotas alternativas devem possuir grande probabilidade de desviar de uma falha ocorrida na rede, sem o conhecimento da localização da falha. As rotas alternativas são criadas através de nodos da rede chamados desvios, que pertencem a componentes que possuem alta conectividade. Tais componentes possuem um maior número cie caminhos distintos. Desta forma, é maior a probabilidade da rota alternativa criada através de um desvio pertencente a um componente de alta conectividade ser funcional, mesmo na presença de falhas na rede. Critérios de conectividade são utilizados na seleção dos desvios. Além do algoritmo exato para cálculo dos critérios de conectividade, uma heurística também é apresentada. Grafos utilizados na obtenção dos resultados experimentais foram gerados aleatoriamente utilizando o método Waxman, que se propõe a capturar a característica cie localidade existente nas redes reais. Os resultados experimentais, obtidos pela implementação dos algoritmos na linguagem Java, demonstram que a cobertura de falhas obtida pela utilização do melhor desvio, selecionado a partir dos critérios de conectividade propostos, chega a 90%. Já a cobertura de falhas obtida pela utilização dos três melhores desvios chega a 98%. Tais resultados visam comprovar que as rotas alternativas criadas através de desvios selecionados a partir dos critérios de conectividade propostos possuem boa probabilidade de desviar de uma falha ocorrida na rede, mesmo sem a informação da localização da falha.Abstract: This work presents a novel approach for fault-tolerant routing based on highly connected detours. Routing protocols present a convergence latency for all routers to update their routing tables after a fault occurs in the network. During this time interval, which may be of up to minutes, packets may be lost, before reaching their destinations. In order to allow nodes to continue communicating during the convergence latency interval, we propose the use of alternative routes that are employed to send packets that were lost. These alternative routes are chosen without the knowledge of which node or link is faulty. Furthermore, alternative routes must present a good probability of being able to bypass the faulty element. In the proposed approach, alternative routes are created through network nodes called detours, that belong to network components that have high connectivity. These components present a larger number of distinct paths, thus the probability that the alternative route created through a detour is faulty-free is higher. The connectivity criteria used to select detours are presented. An exact algorithm to compute those criteria, as well as an efficient heuristic are also presented. Experimental results were obtained with random graths generated with the Waxman method, which aims at producing Internet-like topologies. Results show that the fault coverage obtained through the usage of the best detour, computed based on the proposed connectivity criterias, is up to 90%. When the three best detours are considered, the fault coverage is up to 98%. These results confirm the effectiveness of the proposed criteria for selecting detours that avoid unknown faulty elements