Diagnóstico em Redes de Topologia Arbitrária: Um Algoritmo Baseado em Inundação de Mensagens
Resumo
Considere uma rede de computadores de topologia arbitrária. Um algoritmo de diagnóstico distribuído permite que os nodos sem falha desta rede determinem quais outros nodos da rede são alcançáveis em um determinado momento. Este trabalho apresenta um algoritmo de diagnóstico em redes de topologia arbitrária. Cada nodo da rede testa os seus vizinhos. Quando um nodo detecta a falha de um link este dissemina, em paralelo, para os seus vizinhos, uma pequena mensagem contendo três campos, o identificador dos nodos envolvidos e um contador indicando a falha, avisando-os da falha encontrada. Cada nodo, ao receber a mensagem, atualiza as informações locais de diagnóstico e dissemina a mensagem para seus vizinhos, exceto para aquele do qual a mensagem foi recebida. Quando um nodo ja conhece o evento propagado pela mensagem, esta é simplesmente descartada. Experimentos obtidos através de simulação em redes de diferentes topologias confirmam que a latência do algoritmo é a melhor possível, isto é, proporcional ao diâmetro da rede. Os experimentos mostram que o número prático de mensagens redundantes geradas é, na média, menor que o máximo possivel, isto é, o dobro do número de links.
Referências
S. L. Hakim, and A. T. Amin, “Characterization of Connection Diagnosable Systems,” IEEE Trans. Comput., vol. C-23, Jan, 1974.
A. Bagchi, and S. L. Hakimi, “An Optimal Algorithm for Distributed System-Level Diagnosis,” Proc. 21st Fault Tolerant Computing Symp., June, 1991.
M. Stahl, R. Buskens, and R. Bianchini, “Simulation of the Adapt On-Line Diagnosis Algorithm for General Topology Networks,” Proc. IEEE 11th Symp. Reliable Distributed Systems, October, 1992.
S. Rangarajan, A. T. Dahbura, and E. A. Ziegler, “A Distributed System-Level Diagnosis Algorithm for Arbitrary Network Topologies,” IEEE Transactions and Computers, Vol. 44, pp. 312-333, 1995.
E. P. Duarte Jr., T. Nanya, G. Mansfield, and S. Nogushi, “Non-Broadcast Network Fault-Monitoring Based on System-Level Diagnosis,” Proc. IEEE/IFIP IM'97, 1997.
E. P. Duarte Jr., “Um Algoritmo para Diagnóstico de Redes de Topologia Arbitrária,” I Workshop de Tolerância a Falhas da SBC, Porto Alegre, 1998.
J. E. B. Maia, M. A. C. Branco, “Um Algoritmo de Diagnóstico para Redes Considerando Falhas nos Links,” XIX Congresso Nacional da Sociedade Brasileira de Computação, Rio de Janeiro, 1999.
J. I. Siqueira, E. Fabris, E. P. Duarte Jr., “A Token Based Testing Strategy for Non-Broadcast Network Diagnosis,” 1st IEEE Latin American Test Workshop, pp. 166-171, Rio de Janeiro, 2000.
M. H. MacDougall, Simulating Computer Systems: Techniques and Tools, The MIT Press, Cambridge, MA, 1987.
RNP — Rede Nacional de Pesquisa. http://www.rnp.br/backbone/bkb-mapa.html.
P. Jalote, Fault-Tolerance in Distributed Systems, Prentice-Hall, 1994.
