覆盖网络中多服务静态部署算法

Static multi-service deployment algorithm on the overlay network

针对因特网的覆盖网络中多服务在不同服务节点的部署问题,提出了一种保证平均请求转发延迟满足服务质量要求,以最小化服务部署规模为目标的服务部署模型.该模型在传统的单服务部署问题的基础上,增加了多服务的分配任务;为了合理均衡利用服务节点的服务器资源,引入并发上限限制单节点的并发数目.证明了该模型属于非确定性多项式时间完全问题,提出了两种贪婪启发式算法,两种算法可以在多项式时间内求解.实验结果表明,所提出模型和启发式方法能够大大降低服务部署规模,分别将服务部署规模降低为原始规模的41%和47.8%.

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.