Improving Reliability of Hierarchical Networks using Probabilistic Testing Algorithms
01 January 2005
As networks are expanding to larger areas the control and maintenance of routing information are becoming a formidable task. To cope with its size and complexity and to make the network scalable and reliable hierarchical structure has been proposed with new features to support such information infrastructure. However, the network hierarchy adds more complications to the network design and implementations and that hampers the network reliability and quality of services. Conformance testing has proved to be a powerful tool for network fault detection yet most of the works in the published literature are on networks without hierarchy. We describe a formal model for hierarchical networks and present probabilistic algorithms for testing the hierarchical networks along with the added features. We study test equivalence classes to significantly reduce the number of tests. We provide a formal analysis that shows that our probabilistic algorithms guarantee a high fault coverage with a reasonable number of tests. Experimental results on Internet OSPF protocol are reported.