An Efficient Connectivity Measuring Approach for the Communication Network
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 fault tolerant network is able to maintain connectivity under the failure conditions only if there are multiple links disjoint paths for each node pair (nodes are assumed reliable). Main objective in designing a network topology is to minimize the cost of the network while satisfying the pre specified connectivity. It has also been proved that designing a minimum cost topology under the connectivity constraint is a NP hard problem. Several Meta- heuristic iterative techniques like Genetic Algorithm, Simulated Annealing, Tabu Search etc have been proposed by many researchers for designing the network topologies. There is a need to measure the connectivity of each intermediate solution in these iterative techniques. Measuring connectivity by finding all disjoint paths for each node pair is a very time consuming task. Researchers also proposed to use node degree as a parameter for measuring the connectivity rather than exploring all disjoint paths for each node pair. But it is also true that node degree is not a sufficient condition for measuring the connectivity of the network. In this paper, an approach for measuring the connectivity of a given network is proposed which is as efficient as finding all disjoint paths in determining the connectivity at less computational effort. Performance of the proposed approach is evaluated using several examples.
Keywords: Connectivity, Disjoint paths, Degree, K-connected network.
Download Full-Text
ABOUT THE AUTHORS
Maneesha
Netaji Subhas Institute of Technology, Delhi University, Delhi, India
P.C. Saxena
Jawaharlal Nehru University, Delhi, India
Sangeeta Sabharwal
Netaji Subhas Institute of Technology, Delhi University, Delhi, India
Maneesha
Netaji Subhas Institute of Technology, Delhi University, Delhi, India
P.C. Saxena
Jawaharlal Nehru University, Delhi, India
Sangeeta Sabharwal
Netaji Subhas Institute of Technology, Delhi University, Delhi, India