Simulação de um Algoritmo de Diagnóstico Distribuído para Redes Particionáveis de Topologia Arbitrária
Resumo
Este trabalho apresenta resultados experimentais da avaliação do algoritmo Distributed Network Reachability. DNR é um algoritmo de diagnóstico distribuído em nível de sistema que permite que cada nodo de uma rede particionável de topologia arbitrária determine quais porções da mesma estão atingíveis e inatingíveis. São apresentados extensivos resultados de simulação de eventos dinâmicos de falha e recuperação de nodos e enlaces. São considerados sistemas fortemente dinâmicos, com a ocorrência de eventos modelada por um processo de Poisson. Todos os resultados apresentados têm intervalo de confiança de 95%. Os resultados foram obtidos para grafos aleatórios e também para topologias regulares, como meshes e hipercubos.Referências
Bagchi, A. and Hakimi, S. L. (1991). “An Optimal Algorithm for Distributed System-Level Diagnosis,” Proc. 21 st Int’l Symp. Fault Tolerant Computing, pp. 214-221, 1991.
Bu, T. and Towsley, D. (2002) “On Distinguishing between Internet Power Law Topology Generators,” IEEE INFOCOM, vol. 2, pp 638-647, 2002.
Chessa, S. and Santi, P. (2001) “Comparison-Based System-Level Fault Diagnosis in Ad Hoc Networks,” Proc. 20th IEEE Symp. on Reliable Distributed Systems, 2001.
Chessa, S. and Santi, P. (2002) “Crash Faults Identification in Wireless Sensor Networks,” Computer Communications, Vol. 25, No. 14, Sept. 2002.
Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2001) Introduction to Algorithms, The MIT Press, 2001.
Culler, D. E. and Singh, J. P. (1999) Parallel Computer Architecture - A Hardware/Software Approach, Morgan Kaufmann, 1999.
Ding, M., Chen, D., Xing, K. and Cheng, X. (2005) “Localized Fault-Tolerant Event Boundary Detection in Sensor Networks,” Proc. 24th Annual IEEE Conf. Computer and Communication Societies, 2005.
Duarte Jr., E. P., Mansfield, G., Nanya, T. and Noguchi, S. (1997) “Non-Broadcast Network Fault Monitoring Based on System-Level Diagnosis,” Proc. IEEE/IFIP IM’97, pp.597-609, San Diego, May 1997.
Duarte Jr., E. P. and Weber, A. (2003) “A Distributed Network Connectivity Algorithm,” Proc. IEEE/ISADS’03, pp.285-292, Pisa, April 2003.
Elhadef, M., Boukerche, A. and Elkadiki, H. (2004) “An Adaptive Fault Identification Protocol for an Emergency/Rescue-Based Wireless and Mobile Ad Hoc Network,” Proc. Symp. Parallel and Distributed Processing, pp.1-8, 2007.
Khanna, G., Cheng, M. Y., Varadharajan, P., Bagchi, S., Correia, M. P. and Verı́ssimo, P. J. (2007) “Automated Rule-Based Diagnosis through a Distributed Monitor System,” IEEE Transactions on Dependable and Secure Computing, Vol. 4, No. 4, pp. 266-279, October-December 2007.
Lee, M. H. and Choi, Y. H. (2007) “Distributed Diagnosis of Wireless Sensor Networks,” Proc. IEEE Region 10 Conference, pp.1-4, 2007.
MacDougall, M. H. (1987) Simulating Computer Systems: Techniques and Tools, The MIT Press, Cambridge, MA, 1987.
Rangarajan, S., Dahbura, A. T. and Ziegler, E. A. (1995) “A Distributed System-Level Diagnosis Algorithm for Arbitrary Network Topologies,” IEEE Trans. Computers, Vol.44, pp. 312-333, 1995.
Santi, P. and Blough, D. M. (2002) ”An Evaluation of Connectivity in Mobile Wireless Ad Hoc Networks,” Proc. IEEE Int’l. Conf. Dependable Systems and Networks, pp. 89-102, Washington, 2002.
Stahl, M., Buskens, R. and Bianchini, R. (1992) “Simulation of the Adapt On-Line Diagnosis Algorithm for General Topology Networks,” Proc. IEEE 11 th Symp. Reliable Distributed Systems, October 1992.
Subbiah, A. and Blough, D. M. (2004) “Distributed Diagnosis in Dynamic Fault Environments,” IEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 5, pp. 453-467, May 2004.
Weber, A. (2008) Um Algoritmo de Diagnóstico Distribuı́do para Redes Particionáveis de Topologia Arbitrária Tese de Doutorado, UTFPR, 2008. (previsão de defesa - maio 2008)
Weber, A., Duarte Jr., E. P. and Fonseca, K. O. (2006) “An Optimal Test Assignment for Monitoring General Topology Networks,” Proc. 7th IEEE Latin-American Test Workshop, pp. 131-136, Buenos Aires, 2006
Bu, T. and Towsley, D. (2002) “On Distinguishing between Internet Power Law Topology Generators,” IEEE INFOCOM, vol. 2, pp 638-647, 2002.
Chessa, S. and Santi, P. (2001) “Comparison-Based System-Level Fault Diagnosis in Ad Hoc Networks,” Proc. 20th IEEE Symp. on Reliable Distributed Systems, 2001.
Chessa, S. and Santi, P. (2002) “Crash Faults Identification in Wireless Sensor Networks,” Computer Communications, Vol. 25, No. 14, Sept. 2002.
Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2001) Introduction to Algorithms, The MIT Press, 2001.
Culler, D. E. and Singh, J. P. (1999) Parallel Computer Architecture - A Hardware/Software Approach, Morgan Kaufmann, 1999.
Ding, M., Chen, D., Xing, K. and Cheng, X. (2005) “Localized Fault-Tolerant Event Boundary Detection in Sensor Networks,” Proc. 24th Annual IEEE Conf. Computer and Communication Societies, 2005.
Duarte Jr., E. P., Mansfield, G., Nanya, T. and Noguchi, S. (1997) “Non-Broadcast Network Fault Monitoring Based on System-Level Diagnosis,” Proc. IEEE/IFIP IM’97, pp.597-609, San Diego, May 1997.
Duarte Jr., E. P. and Weber, A. (2003) “A Distributed Network Connectivity Algorithm,” Proc. IEEE/ISADS’03, pp.285-292, Pisa, April 2003.
Elhadef, M., Boukerche, A. and Elkadiki, H. (2004) “An Adaptive Fault Identification Protocol for an Emergency/Rescue-Based Wireless and Mobile Ad Hoc Network,” Proc. Symp. Parallel and Distributed Processing, pp.1-8, 2007.
Khanna, G., Cheng, M. Y., Varadharajan, P., Bagchi, S., Correia, M. P. and Verı́ssimo, P. J. (2007) “Automated Rule-Based Diagnosis through a Distributed Monitor System,” IEEE Transactions on Dependable and Secure Computing, Vol. 4, No. 4, pp. 266-279, October-December 2007.
Lee, M. H. and Choi, Y. H. (2007) “Distributed Diagnosis of Wireless Sensor Networks,” Proc. IEEE Region 10 Conference, pp.1-4, 2007.
MacDougall, M. H. (1987) Simulating Computer Systems: Techniques and Tools, The MIT Press, Cambridge, MA, 1987.
Rangarajan, S., Dahbura, A. T. and Ziegler, E. A. (1995) “A Distributed System-Level Diagnosis Algorithm for Arbitrary Network Topologies,” IEEE Trans. Computers, Vol.44, pp. 312-333, 1995.
Santi, P. and Blough, D. M. (2002) ”An Evaluation of Connectivity in Mobile Wireless Ad Hoc Networks,” Proc. IEEE Int’l. Conf. Dependable Systems and Networks, pp. 89-102, Washington, 2002.
Stahl, M., Buskens, R. and Bianchini, R. (1992) “Simulation of the Adapt On-Line Diagnosis Algorithm for General Topology Networks,” Proc. IEEE 11 th Symp. Reliable Distributed Systems, October 1992.
Subbiah, A. and Blough, D. M. (2004) “Distributed Diagnosis in Dynamic Fault Environments,” IEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 5, pp. 453-467, May 2004.
Weber, A. (2008) Um Algoritmo de Diagnóstico Distribuı́do para Redes Particionáveis de Topologia Arbitrária Tese de Doutorado, UTFPR, 2008. (previsão de defesa - maio 2008)
Weber, A., Duarte Jr., E. P. and Fonseca, K. O. (2006) “An Optimal Test Assignment for Monitoring General Topology Networks,” Proc. 7th IEEE Latin-American Test Workshop, pp. 131-136, Buenos Aires, 2006
Publicado
27/05/2008
Como Citar
WEBER, Andréa; SANTOS, Aline Wolpert dos; DUARTE JR., Elias Procópio; FONSECA, Keiko V. O..
Simulação de um Algoritmo de Diagnóstico Distribuído para Redes Particionáveis de Topologia Arbitrária. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 9. , 2008, Rio de Janeiro/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2008
.
p. 101-114.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2008.23149.
