p-Cycle Spare Capacity Allocation for Large-Scale Networks

• Author / Creator

  Shi, Tiange

• Optical transport network failures are destructive, costly and inevitable. Therefore, extensive work has been conducted on survivable network designs. Survivable network designs are primarily built around network span failures, and a common approach for improving network resilience against span failures is by adding redundancy in span capacities. In recent years, a relatively new p-cycle survivable network design has drawn much attention due to its ring-mesh dichotomy that allows p-cycles to provide ring-like restoration speed with mesh-like protection efficiency. One approach to enhancing the p-cycle survivable network design is by optimizing the allocation of its spare capacities. The spare capacity allocation problem optimizes spare capacity designs by placing selective pre-enumerated candidate cycles onto the network to achieve 100% network survivability with minimal allocation cost. Integer linear programming (ILP), heuristics, and meta-heuristics are commonly-adopted approaches for optimizing the p-cycle spare capacity allocation problem. Although extensive work has been conducted on p-cycle survivable network designs and p-cycle SCA problems using either linear programming or heuristic methods, there are still great opportunities for enhancement. For example, to the best of our knowledge, there has not been a p-cycle spare capacity allocation method proposed and tested particularly for large-scale networks.
  The work herein addresses the problem of p-cycle spare capacity allocation by developing and evaluating two new algorithms. The first algorithm is a novel heuristic algorithm for generating efficient candidate p-cycles, referred to as the disjoint-paths Dijkstra cycle development (DDCD) algorithm. The DDCD is an iterative cycle development method that is capable of generating high-performance candidate p-cycles in networks of any size. The DDCD outperforms some conventional cycle enumeration methods in small and large networks and is particularly desirable for large-scale networks that are over 80 nodes. The second algorithm is a novel GA model for optimizing the p-cycle spare capacity allocation problem, referred to as a GA-SCA model. The GA-SCA model provides a better optimized spare capacity allocation solution than that of CIDA. The GA operators, especially the mutation operator, are specifically designed and tuned to enhance the performance of the GA-SCA model.

• Subjects / Keywords

  • p-Cycle
  • spare capacity allocation
  • network optimization
  • survivable networks
  • genetic algorithm

• Graduation date

  Spring 2021

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-spgv-y737

• 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.