A STRICT TABU SEARCH ALGORITHM FOR OSPF WEIGHT OPTIMIZATION

摘要

In this paper, a novel strict tabu search algorithm is pre-sented to optimize administrative link weights for OSPF routing. An immediate neighborhood structure is defined by modifying the weight value of a link while minimizing the number of flows affected by such a modification. A new method is developed to efficiently explore the neighbor-hood of a solution. This method does not need to take into account all demand pairs and their traffic crossing every link, resulting in less computational time and less storage space requirements. In addition, we realize a 32-bit hashing table (i.e. tabu list) to store 16-bit link weight settings and reduce the impact of random collisions in conjunction with an aspiration criterion. The experimental results show that the new method for exploring the immediate neighborhood reduces the running time by about 60% on average com-pared to the simple method considering all demand pairs. Our experiments also show that the performance of our al-gorithm is indistinguishable from the algorithms presented by Fortz et al and Ericsson et al.