Simulation of a Distributed Connectivity Algorithm for General Topology Networks
Resumo
The Distributed Network Connectivity algorithm allows every node in a general topology network to determine to which portions of the network it is connected, and which portions are unreachable. The algorithm consists of three phases: test, dissemination, and connectivity computation. During the testing phase each fault-free node tests all its neighbors at each testing interval. Upon the detection of a new fault event, the tester starts the dissemination phase, in which a reliable broadcast algorithm is employed to inform the other connected nodes about the event. At any time, any working node may run the third phase, in which a graph connectivity algorithm shows the complete network connectivity. Extensive simulation results are presented, considering various topologies such as the hypercube and random graphs. Results are compared to those of other algorithms.
Referências
F. Preparata, G. Metze, and R.T. Chien, “On The Connection Assignment Problem of Diagnosable Systems,” IEEE Transactions on Electronic Computers, Vol. 16, pp. 848-854, 1968.
E.P. Duarte Jr., G. Mansfield, T. Nanya, and S. Noguchi, “Non-Broadcast Network Fault Monitoring Based on System-Level Diagnosis,” Proc. IEEE/IFIP IM’97, pp.597-609, San Diego, May 1997.
E.P. Duarte Jr., “Um algoritmo para Diagnóstico de Redes de Topologia Arbitrária,” in portuguese, In Proceedings of the 1st SBC Workshop on and Fault Tolerance, SBC-WTF’1, pp. 50-55, Porto Alegre, Brazil, 1998.
E. P. Duarte Jr., and T. Nanya, “A Hierarchical Adaptive Distributed System-Level Algorithm Diagnosis,” IEEE Transactions on Computers, Vol. 47, pp. 34-45, No. 1, Jan 1998.
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 11" 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 on Computers, Vol.44, pp. 312-333, 1995.
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.
P. Jalote, Fault Tolerance in Distributed Systems, Prentice Hall, 1994.
M.-H. MacDougall, Simulating Computer Systems: Techniques and Tools, The MIT Press, Cambridge, MA, 1987.
E.P. Duarte Jr., and G.O. Mattos, “Diagnóstico em Redes de Topologia Arbitrária: Um Algoritmo Baseado em Inundação de Mensagens”, in portuguese, In Proceedings of the 2nd SBC Workshop on Test and Fault Tolerance, SBC-WTF’2, pp. 82-87, Curitiba, Brazil, 2000.
E.P. Duarte Jr., and J.M.A.P. Cestari, “O Agente Chines para Diagnstico de Redes de Topologia Arbitrária” in portuguese, In Proceedings of the 2nd SBC Workshop on Test and Fault Tolerance, SBC-WTF’2, pp. 88-93, Curitiba, Brazil, 2000.
