A Spare Capacity Planning Methodology for Wide Area Survivable Networks

Front Cover
Universal-Publishers, 1999 - Computers - 212 pages

In this dissertation, a new spare capacity planning methodology is proposed utilizing path restoration. The approach is based on forcing working flows/traffic which are on paths that are disjoint to share spare backup capacity. The algorithm for determining the spare capacity assignment is based on genetic algorithms and is capable of incorporating non-linear variables such as non-linear cost function and QoS variables into the objective and constraints. The proposed methodology applies to a wider range of fault scenarios than most of the current literature. It can tolerate link-failures, node-failures, and link-and-node failures. It consists of two stages: the first stage generates a set of network topologies that maximize the sharing between backup paths by forcing them to use a subset of the original network. The second stage utilizes a genetic algorithm to optimize the set of solutions generated by the first stage to achieve an even better final solution. It can optimize the solution based on either minimizing spare capacity or minimizing the total network cost. In addition, it can incorporate QoS variables in both the objective and constraints to design a survivable network that satisfies QoS constraints.

Numerical results comparing the proposed methodology to Integer Programming techniques and heuristics from the literature are presented showing the advantages of the technique. The proposed methodology was applied on 4 different size networks based on spare capacity optimization criteria and it was found that it achieved solutions that were on average 9.3% better than the optimal solution of the IP design that is based on link-restoration. It also achieved solutions that were on average 22.2 % better than the previous heuristic SLPA.

The proposed methodology is very scalable. It was applied on networks with different sizes ranging from a 13-node network to a 70-node network. It was able to solve the 70-node network in less than one hour on a Pentium II PC. The curve-fitting of the empirical execution time of the methodology was found to be O(n3).

 

Contents

1 NETWORK TOPOLOGIES WITH DIFFERENT LEVELS OF FAILURE TOLERANCE
7
5 MESH NETWORK WITH DYNAMIC ROUTING
14
7 CUTS OF MAXFLOW ALGORITHM
20
PREVIOUS WORK
22
A NEW APPROACH TO SPARE CAPACITY PLANNING
35
1 SPARE CAPACITY PLANNING METHODOLOGY
40
2 CALCULATING WORKING AND BACKUP PATHS
48
5 LINK CAPACITY ASSIGNMENT PROCEDURE
54
11 TOTAL NETWORK COST OF SLPA IP GA
103
SCALABILITY OF THE METHODOLOGY AND QOS INCORPORATION 105 6 1 DIFFERENT LEVELS OF RELIABILITY
106
2 13NODE NETWORK NETWORK 1 WITH LINKANDNODEFAILURE TOLERANCE CASE III
109
4 13NODE NETWORK WITH NONSYMMETRICAL TRAFFIC RATE
117
5 THE 13NODE NETWORK WITH LINKFAILURE TOLERANCE THAT SATISFY QOS CONSTRAINTS
121
CONCLUSIONS AND FUTURE WORK
127
APPENDIX B TABLES AND FIGURES FOR CASE I
139
TABLES AND FIGURES FOR CASE II AND III
148

METHODOLOGY IMPLEMENTATION AND SENSITIVITY ANALYSIS
56
1 EXAMPLE OF STAGE I OF THE PROPOSED METHODOLOGY
62
3 TRANSITION BETWEEN TWO SUCCESSIVE GENERATIONS IN GA
72
4 SOME CROSSOVER OPERATOR TYPES
80
METHODOLOGY PERFORMANCE IN COMPARISON WITH PREVIOUS
86
1 17NODE NETWORK NETWORK 3
87
5 IP FORMULATION MODEL FOR MINIMIZING SPARE CAPACITY
97
1 15NODE NETWORK NETWORK 2 WITH NODEFAILURE TOLERANCE CASE II
151
5 20NODE NETWORK NETWORK 4 WITH NODEFAILURE TOLERANCE CASE II
157
TABLES AND FIGURES FOR CASE IV V AND VI
160
9 15NODE NETWORK NETWORK 2 WITH LINKFAILURE TOLERANCE CASE IV
165
14 17NODE NETWORK NETWORK 3 WITH LINKANDNODEFAILURE TOLERANCE CASE VI171
171
APPENDIX E TABLES FOR NONSYMMETRICAL TRAFFIC LOAD AND QOS
180
1 30NODE NETWORK NETWORK 5
184

Common terms and phrases

Popular passages

Page 4 - power systems, gas and oil production, storage and transportation, banking and finance, transportation, water supply systems, government services, and emergency services
Page 5 - the ability of a network to maintain or restore an acceptable level of performance during network failures by applying various restoration techniques, and
Page vii - for his support, encouragement, invaluable guidance throughout the course of this work, and most of all, for being a good friend. His knowledge, dedication, and work ethics have been a constant source of inspiration.
Page vii - deserve special thanks for their encouragement, concern, and for only being a phone call away when I needed them. I save my final,
Page 5 - the mitigation or prevention of service outages from network failures by applying

Bibliographic information