A Spare Capacity Planning Methodology for Wide Area Survivable NetworksIn 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
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
References to this book
NETWORKING 2000. Broadband Communications, High Performance Networking, and ... G. Pujolle No preview available - 2000 |