Static multi-service deployment algorithm on the overlay network
Tuo Lihen · Journal of Xidian University · 2014
The Static Multi-Service deployment Model SMSPM for short,is proposed to deal with the problem of overlay network multi-service deployment on the Internet.The SMSPM minimizes the scale of service deployment as a target and guarantees the average request forwarding delay to satisfy the quality of service.Based on single service deployment,the SMSPM allocates multiple services to different service nodes We introduce the concurrent upper limit on the number of concurrents in a single node to use reasonably server resources of service nodes.We prove that the SMSPM problem is NP-Complete.We propose two greedy heuristic algorithms,NBND and BND.NBND and BND can solve the problem in the polynomial time.Experimental results show that NBND and BND.SMSPM and two greedy heuristic algorithms can greatly lower the scale of multi-service deployment.BND and NBND can reduce the scale of multi-service deployment to 41%and 47.8%of the original scale of multi-service deployment.