Network design and optimisation based on cost and algebraic connectivity
- 1 September 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21570221,p. 193-200
Abstract
Network design and optimisation has been one of the major focuses of the research community over the past decades. Connectivity of topologies can be improved by simply adding links; however, this incurs cost for addition of links for increased resilience. Therefore, topological design and optimisation requires developing algorithms so that a designer can select optimum parameters to achieve resilience in the least costly manner. In this paper, we develop a heuristic algorithm that optimises a topology based on algebraic connectivity metric that is defined as the second smallest eigenvalue of the Laplacian matrix. Furthermore, the connectivity of a topology is improved based on the available budget, for which we capture network cost in terms of euclidian distance between two connected nodes. We apply our algorithm on three realistic sets of backbone service provider graphs and compare the utility of our algorithm. The heuristic algorithm we introduce in this paper optimises topologies and is computationally less costly than an exhaustive optimisation.Keywords
This publication has 21 references indexed in Scilit:
- On the fitness of geographic graph generators for modelling physical level topologies2013
- Topology connectivity analysis of internet infrastructure using graph spectra2012
- Weighted Spectral Distribution for Internet Topology Analysis: Theory and ApplicationsIEEE/ACM Transactions on Networking, 2009
- Network Reliability Optimization2008
- Characterization of complex networks: A survey of measurementsAdvances in Physics, 2007
- On the point-of-presence optimization problem in IP networksCanadian Journal of Electrical and Computer Engineering, 2005
- Network design optimization from an availability perspective2004
- Hub location in backbone/tributary network design: a reviewLocation Science, 1998
- Topological design of computer communication networks — The overall design problemEuropean Journal of Operational Research, 1992
- Reliability Indices for Topological Design of Computer Communication NetworksIEEE Transactions on Reliability, 1981