We study the mesh topology design problem in overlay virtual private networks. Given a set of customer nodes and associated traffic matrix, tunnels that are connecting node pairs through a public service provider network subject to degree constraints are determined so as to minimize total multihopped traffic. Valid inequalities strengthening the LP relaxation and a tabu search heuristic are proposed and validated on a set of large test cases, leading to small duality gaps.
Citation
Electronics Letters, Vol. 38, No. 16, August 2002, pp. 939-941.