Simulação de um Algoritmo de Diagnóstico Distribuído para Redes Particionáveis de Topologia Arbitrária
Abstract
This work presents experimental results of the evaluation of the Distributed Network Reachability algorithm. DNR is a distributed system-level diagnosis algorithm that allows every node of a partitionable general topology network to determine which portions of the network are reachable and unreachable. Extensive simulation results of dynamic fault and repair events on nodes and links are presented. The systems considered are highly dynamic, the occurrence of the events is modeled by a Poisson process. All the results are presented within a 95% confidence interval. Simulated topologies included random graphs as well as regular graphs, such as meshes and hypercubes.References
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
Published
2008-05-27
How to Cite
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: FAULT TOLERANCE WORKSHOP (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.
