Study on Topology Design for Large Scale Service Overlay Networks

Service Overlay Network (SON) is a kind of overlay networks which provides end-to-end QoS guarantees in the Internet. Without requiring significant changes to the underlying network infrastructure, SON deploys the nodes in the Internet and purchases the bandwidth from ISPs to support QoS application service for users. The deployment of a SON can be a capital-intensive investment, including the overlay nodes´ placement and purchasing the bandwidth from ISPs. Topology design with minimizing the SON installation cost and satisfying users´ requirement is important for SON study. The problem for SON topology design is NP-hard. The algorithms of earlier researches on SON topology design are too poor efficiency to apply to the large scale network. In this paper we propose a linear programming model based on multi-commodity flow to solve the problem for large scale SON construction. We validate the effectiveness of our algorithm through simulation.