Network Design and Availability Analysis for Large-Scale Mesh Networks

• Author / Creator

  Wang,Wenjing

• Communication systems have cemented their position in many fields of our daily lives, such as governance, banking, correspondence, and traffic. Such systems often take the form of mesh networks in their topology. With ever-increasing data transmission rate in mesh networks and our growing reliance on continued network services, network availability has become increasingly important than ever before. Since survivable mesh networks are only designed to be 100% restorable under all single-failure scenarios, there is still chances for current networks to be failed, which usually leads to huge data rand revenue loss. In order to improve network availability while maintaining desirable investment cost of network design, the aim of this thesis is investigation on network design strategies and availability optimization algorithms based on the condition that the network has been designed to be fully restorable to all potential single failures. The main contributions of this thesis comprise five parts. First, we provide thorough analysis of existing availability analysis methods for span-restorable networks. Based on this, we propose a more accurate method to evaluate network overall availability for span-restorable mesh networks. Moreover, comparisons between the existing and the new analysis methods are made. Second, we perform detailed investigation on traditional single-flow integer linear programming (ILP) and multi-flow ILP models of shared backup path protection mesh networks, and propose a new multi-flow ILP model. Experiments show that the new model solves 51% faster in terms of runtime than the traditional multi-flow ILP model. Meanwhile, we present an algorithm to analyze network overall availability for shared backup path protection networks. Results show that the new ILP model works better in terms of overall availability in higher connected networks. Third, we present an algorithm to optimize availability for shared backup path protection networks. The core of this algorithm is an ILP model that is used to minimize the total lost flow caused by the second failure in a specified dual-failure scenario. The relationship between network overall availability and spare capacity is studied based on this optimization algorithm. Fourth, similar to the shared backup path protection networks, we also propose an algorithm to optimize network overall availability for path-restorable networks. At the meantime, the relationship between network overall availability and spare capacity is investigated. Fifth, we compare performance of the span-restorable, path-restorable, and shared backup path protection networks in terms of network overall availability. Results show that span-restorable networks have the highest overall network availability among the three above-mentioned types of networks, and that path-restorable networks have a slight advantage over shared backup path protection networks on average. The theoretical analysis of this thesis provide insights in some degree in the understanding of mesh networks, and the algorithms proposed in this thesis is enlightening in the filed of network design and availability analysis. Implementation of the work in this thesis can help to design mesh networks faster with reasonable investment costs.

• Subjects / Keywords

  • Survivability mechanisms
  • Mesh networks
  • Availability analysis
  • Network design

• Graduation date

  Spring 2018

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3Z31P39X

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