Premium
On the impact of the solution representation for the Internet Protocol Network Design Problem with max‐hop constraints
Author(s) -
De Giovanni L.,
Croce F. Della,
Tadei R.
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20018
Subject(s) - computer science , open shortest path first , tabu search , heuristics , distributed computing , computer network , network planning and design , routing protocol , mathematical optimization , the internet , routing (electronic design automation) , link state routing protocol , mathematics , algorithm , operating system , world wide web
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