In this paper, we address the challenge of overlay topology design by considering which overlay topology best minimizes cost function, taking into account overlay link creation cost and routing cost. First, we formulate the problem as Integer Linear Programming (ILP) given a traffic matrix and assuming cooperative behavior of nodes. Then, we propose some heuristics to find near-optimal overlay topologies with a reduced complexity. The solutions to the ILP problem on real network topologies have been analyzed, showing that the traffic demands between the nodes affect the decision to create new overlay links. Next, the obtained optimal and near-optimal overlay topologies are thoroughly analyzed and the heuristics are compared through extensive numerical evaluations. Finally guidelines for the selection of the best heuristic as a function of the cost parameters are also provided.