An Efficient Constructive Approximation Approach to Design A K-Connected Network Topology

摘要

The purpose of designing an optimal and fault tolerant communication network is to achieve a precise performance without any disruption at a minimal cost. A network is said to be k-link fault tolerant (nodes are assumed reliable) if it is able to maintain connectivity in the presence of failures in any set of arbitrarily k links simultaneously. . Communication network topology design cost depends on the number of the links used to design a desired fault tolerant communication network and is equal to the sum of the cost of all required links. The main objective of a fault tolerant network design approach is therefore to select the minimum number of low cost links while satisfying the pre-specified fault tolerance/ connectivity. It has also been proved that designing a minimum cost communication network topology under the connectivity constraint is a NP hard problem. Several constructive approximation algorithms have been proposed to design a fault tolerant network topology. But the existing algorithms are not so much effective for selecting minimum number of low cost links to design a computer network topology. In this paper, we have proposed an efficient constructive approximation approach for designing a k-connected network which is survivable in the presence of k-1 links failures in the network. The design cost and number of links required to design such network using proposed approach is less than the existing approaches. Effectiveness of proposed approach is also checked using various examples.