Paper Info
Title
On the impact of the solution representation for the Internet Protocol Network Design Problem with max-hop constraints
Abstract
The 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 determine the minimum cost capacity installation such that all the traffic is routed. 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 Multiflow) protocol, with additional constraints on the maximum number of hops. The problem is strongly NP-Hard, and the literature proposes local search-based heuristics that do not take into account max-hop constraints, or assume a simplified OSPF routing. The core in a local search approach is the network loading algorithm for the evaluation of the neighbor solutions costs. It presents critical aspects concerning both computational efficiency and memory requirements. Starting from a tabu search prototype, we show how these aspects deeply impact on the design of a local search procedure, even at the logical level. We present several properties of the related network loading problem, that allow to overcome the critical issues and lead to an efficient solution evaluation. © 2004 Wiley Periodicals, Inc. NETWORKS, VoL. 44(2), 73–83 2004
Year
DOI
Venue
2004
10.1002/net.v44:2
Networks
Keywords
Field
DocType
internet protocol,network design
Open Shortest Path First,Internet Protocol,Mathematical optimization,Telecommunications network,Network planning and design,Shortest path problem,Computer network,Local search (optimization),Network management,Mathematics,Tabu search
Journal
Volume
Issue
ISSN
44
2
0028-3045
Citations 
PageRank 
References 
4
0.52
6
Authors
3
Name
Order
Citations
PageRank
Luigi De Giovanni17710.16
Federico Della Croce239941.60
Roberto Tadei366747.45