Heuristic Approaches for Survivable Network Optimization Open Access
- Other title
- Type of item
- Degree grantor
University of Alberta
- Author or creator
Kasem, Ahmed, M
- Supervisor and department
Ivan Fair (Electrical and Computer Engineering)
John Doucette (Mechanical Engineering)
- Examining committee member and department
Gungxiang Shen (Soochow University, China)
Mike Lipsett (Mechanical Engineering)
Hooman Askari-Nasab (Civil and Environmental Engineering)
Department of Electrical and Computer Engineering
- Date accepted
- Graduation date
Doctor of Philosophy
- Degree level
Over the last two decades, many important developments have been made in the field of communication networks, opening the door to new applications in various fields such as transportation, banking and financial services, e-health services, etc. Wavelength division multiplexing (WDM) is one technique used to transfer these vast amounts of data over networks of fibre optic cables. But because WDM permits such high bandwidth, any cut in a fibre optic cable can result in a major financial loss due to the volume of traffic at risk. Therefore, survivability is an important consideration in the design of modern large-scale telecommunication networks. Several survivability schemes have been developed for use in WDM networks. Our work will focus on three of these schemes, namely meta-mesh span restoration, p-cycles, and node-encircling p-cycles (NEPCs). Span restoration and path restoration are well known survivability schemes, widely addressed in the open literature. While path restoration is more capacity efficient, span restoration is simpler and faster. The meta-mesh scheme had previously been proposed to bridge the gap between the two approaches, because it enhances the capacity efficiency of the span restorable mesh networks while maintaining much of its simplicity. In the present work, we introduce a node-arc ILP model to investigate the effect of the meta-mesh scheme on the capacity efficiency of the span-restorable networks. Then we modify an existing integer linear programming (ILP) design model to allow for incremental network evolution. In this work, we formulate two models, one of which applies the conventional span restoration technique and another that uses the meta-mesh span restoration scheme. p-Cycle restoration has attracted considerable interest in the network survivability literature in recent years. However, most of the existing work assumes a known network topology upon which to apply p-cycle restoration. In the present work, we develop an incremental topology optimization ILP model for p-cycle network design, where a known topology can be amended with new fibre links selected from a set of eligible spans. The ILP model proves to be relatively easy to solve for small test case instances, but becomes computationally intensive on larger networks. We then follow with a relaxation-based decomposition approach to overcome this challenge. In our test cases, the decomposition approach significantly reduces computational complexity of the problem, allowing the ILP model to be solved in reasonable time with a minimal impact on the solution optimality. NEPCs have been proposed as a technique for node and span protection. A key step in obtaining an optimal solution in most existing NEPC network design methods is the enumeration of candidate cycles. The present work introduces two novel algorithms for enumerating an efficient set of candidate cycles for an NEPC network design: the node-disjoint path partitioning (NDPP) method and the level partitioning method. Furthermore, we develop a capacitated iterative design algorithm (CIDA) approach for providing fully capacitated NEPC networks, as well as a genetic algorithm model to investigate the best values for the weighting factors in the key a priori efficiency equation used in the NEPC-CIDA algorithm. Finally, we propose a node-encircling p-cycle ILP design with enhanced span-failure protection to further minimize the total network design cost.
- Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
- Citation for previous publication
A. Kasem, J. Doucette, “Incremental Optical Network Topology Optimization Using Meta-Mesh Span Restoration”, Design of Reliable Communication Networks (DRCN 2011), Krakow, Poland, 10-12 October 2011.Md. Noor-E-Alam, A. Kasem, J. Doucette “ILP Model and Relaxation-Based Decomposition Approach for Incremental Topology Optimization in p-Cycle Networks,” Journal of Computer Networks and Communications, Vol. 2012, pp. 1-10, 2012.A. Kasem, J. Doucette, “Algorithmic Approaches for Efficient Enumeration of Candidate Node-Encircling p-Cycles”, (INFORMS Telecommunication) Conference, Montreal, Quebec, 5 – 7 May 2010.A. Kasem, R. Gallardo, J. Doucette, “An Enhanced ILP Design Model for Node-Encircling p-Cycle Networks”, Design of Reliable Communication Networks (DRCN 2014), Ghent, Belgium, 1-3 April 2014.
- Date Uploaded
- Date Modified
- Audit Status
- Audits have not yet been run on this file.
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 4378362
Last modified: 2015:10:21 00:54:12-06:00
Original checksum: 888d05bbcb5aa5e52b7b6efd79c457c9
Activity of users you follow