| On 2003-06-23 at 15:00:00 (Brussels Time) |
Abstract
The Robust IP (Internet Protocol) Network Design Problem can be shortly stated as follows. Given a set of nodes and a set of traffic demands, we want to define the minimum cost capacity installation such that all the traffic is routed when no faults occur, and a protected subset of the traffic demands is routed even under single node faults. Capacity is provided by means of links of a given capacity and traffic must be loaded on the network according to the OSPF-ECM (Open Shortest Path First - Equal Commodity Multi-flow) protocol, with additional constraints on the maximum number of hops. The problem is NP-Hard and literature proposes local search based heuristics which do not take the reliability and max-hop requirements into account, or assumes a simplified OSPF routing. The core of the optimizing procedure is the network loading algorithm for the evaluation of the neighbor solutions cost; it presents some critical aspects concerning computational efficiency and memory requirements. Starting from a Tabu Search prototype, we show how these aspects deeply impact the definition of the design of a Local Search procedure, even at the logical level. We present some properties of the related network loading problem, allowing us to overcome the critical issues and to perform an efficient incremental solution evaluation.
Keywords
Topological Design, IP Networks, Reliability, OSPF protocol, Local Search Meta-heuristics
