Algebraic connectivity metric for spare capacity allocation problem in survivable networks

摘要

For studying survivability of telecommunication networks, one should be able to differentiate topologies of networks by means of a robust numerical measure that can characterize the degree of immunity of a given network to possible failures of its elements. An ideal metric should be also sensitive to such topo-logical features as the existence of nodes or links whose failures are catastrophic in that they lead to disintegration of a given network structure. In this paper, we show that the algebraic connectivity, adopted from spectral graph theory, namely the second smallest eigenvalue of the Laplacian matrix of the network topology, is a numerical index that characterizes a network's survivability better than the average node degree that has been traditionally used for this purpose. This proposition is validated by extensive studies involving solutions of the spare capacity allocation problem for a variety of networks.