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.

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

DE GIOVANNI, LUIGI;
2003

Abstract

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.
Proceedings of the International Network Optimization Conference – INOC 2003
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11577/180609
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact