On design of a survivable network architecture for dynamic routing: Optimal solution strategy and an efficient heuristic
✍ Scribed by Iradj Ouveysi; Andrew Wirth
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 262 KB
- Volume
- 117
- Category
- Article
- ISSN
- 0377-2217
No coin nor oath required. For personal study only.
✦ Synopsis
We investigate network planning and design under volatile conditions of link failures and trac overload. Our model is a non-simultaneous multi-commodity problem, with any particular two link failure being considered as one scenario. We show that the optimal solution model is not practically solvable for real-world problems and hence an ecient heuristic is provided which is On 6 faster than the optimal model and is based on synthesizing a modi®ed maximum spanning tree using an algorithm due to Gomory and Hu. The output of this procedure is then used to solve a much smaller linear program. Simulation results indicate that the heuristic is near optimal for problems with up to 40 nodes.