Uma abordagem distribuída baseada no algoritmo do carteiro chinês para diagnóstico de redes de topologia arbitrária

Abstract

Resumo Em uma rede de computadores tanto nodos como enlaces podem falhar. Este trabalho apresenta um algoritmo de diagnóstico distribuído de redes de topologia arbitrária que permite a monitoração da rede. Os nodos testam os enlaces que os conectam a outros nodos. Quando um nodo detecta uma falha este dissemina em paralelo, para os seus vizinhos, uma mensagem de disseminação contendo informações sobre a falha. Os vizinhos, ao receberem a mensagem, comparam as suas informações locais de diagnóstico com a informação contida na mensagem. Se a informação já é conhecida, a mensagem redundante é descartada, caso contrário as informações locais são atualizadas e disseminadas. As mensagens redundantes empregadas são, na verdade, consideradas uma vantagem do algoritmo, quando comparado a outras abordagens. Os algoritmos de diagnóstico são justamente usados para permitir que os nodos sem falhas possam determinar a situação do sistema quando o sistema está parcialmente inoperante. Desta forma é fundamental que tais algoritmos sejam tolerantes a falhas. Se um nodo recebe uma mensagem redundante, é porque existem dois caminhos disjuntos entre o nodo que gerou a mensagem e o nodo que a recebe. Assim, se durante a disseminação da mensagem de diagnóstico novos eventos de falha ocorrerem na rede, a redundância vai permitir que o algoritmo tolere falhas de caminhos, tantas quantas são as mensagens redundantes. Por outro lado, as mensagens são pequenas, e o número máximo de mensagens por evento é 2*L, onde L é o número de enlaces no sistema. O algoritmo não trabalha com eventos dinâmicos e a falha de um enlace não particiona a rede. Simulações são realizadas em diversas topologías dentre elas a topologia DI>2, hipercubo, grafos randômicos e a topologia da RNP. Os resultados mostram que a latência do algoritmo é proporcional ao diâmetro da rede. Comparações com outros algoritmos são apresentadas. Os parâmetros analisados são o total de mensagens de disseminação, o número de mensagens redundantes e o tempo necessário para realizar o diagnóstico.