摘要： Overlay 服务网络是一种通用的服务框架，它利用覆盖网络技术来向用户提供各种各样的服务。该文在讨论Overlay 服务网络的基础上，提出了覆盖节点放置的问题，对该问题进行了形式化，并提出了相应的算法，对算法进行了相应的仿真。

关键词: Overlay 网络；覆盖节点；Lagrangian 松弛法

Abstract: Overlay service network (OSN) is a generic framework to support variety new applications based on the traditional Internet infrastructure. This paper surveys the current research on OSN topologies and brings forward the overlay node placement problems (ONPP). A programming model and three algorithms corresponding to the ONPP problems are also proposed. The complexity analysis and the numerical experiments support the model and algorithms from theory and practice as well. The comparison of performances on different algorithms suggests that Lagrangian relaxation method for solving the ONPP problem is feasible and efficient.

Key words: Overlay network; Overlay node; Lagrangian relaxation