Network Design and Optimisation Based on Cost and Algebraic Connectivity

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.

Meeting Name

2013 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops, ICUMT 2013 (2013: Sep.10-12, Almaty, Kazakhstan)

Department(s)

Electrical and Computer Engineering

Keywords and Phrases

Algebra; Control Systems; Costs; Design; Eigenvalues and Eigenfunctions; Heuristic Algorithms; Matrix Algebra; Reliability; Robustness (Control Systems); Topology; Algebraic Connectivity; Back-Bone Network; Connectivity; Dependability; Network Costs; Network Design; Network Resilience; Optimisations; Optimization

International Standard Book Number (ISBN)

978-1479911776

International Standard Serial Number (ISSN)

2157-0221

Electronic OCLC #

892190619

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2013 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Jan 2013

Link to Full Text

Share

 
COinS