Heuristic Approaches to Network Design
Topology design: two distinct classes
- Start with a fully-meshed network and remove capacity by link reduction. Examples of link reduction techniques are the Branch X-change and Concave Branch elimination algorithms.
- Start with an empty network and add links as traffic is routed.
Ring design
- Route traffic using Dijkstra’s (or other) shortest path algorithm
- Determine link capacities
- Use a modified depth first search (DFS) algorithm to generate ring covering