Solving the Internet Protocol Network Design Problem with Max-Hop Constraints by Local Search based Heuristics

The Robust IP (Internet Protocol) Network Design Problem can be shortly state 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 reliability and max-hop constraint into account, or assume a simplified OSPF routing. The core of the optimizing procedure we propose is the network loading algorithm for the evaluation of the neighbor solution 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 design of a Local Search procedure, even at the logical level. We present some properties of the network loading problem, allowing us to overcome the critical issues and to perform an efficient incremental solution evaluation.