- 210 views
- 244 downloads
Heuristic Approaches for Survivable Network Optimization
-
- Author / Creator
- Kasem, Ahmed, M
-
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.
-
- Subjects / Keywords
-
- Graduation date
- Spring 2015
-
- Type of Item
- Thesis
-
- Degree
- Doctor of Philosophy
-
- License
- This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.