J4 ›› 2014, Vol. 41 ›› Issue (4): 137-143.doi: 10.3969/j.issn.1001-2400.2014.04.024

• Original Articles • Previous Articles     Next Articles

Static multi-service deployment algorithm on the overlay network

TUO Liheng1,2;NI Hong2;LI Mantian1,2;LIU Xue2   

  1. (1. School of Physics, University of Chinese Academy of Sciences, Beijing  100049， China;
    2. National Network New Media Engineering Research Center, Institute of Acoustics Chinese Academy of Sciences, Beijing  100190， China)
  • Received:2013-04-01 Online:2014-08-20 Published:2014-09-25
  • Contact: TUO Liheng E-mail:tuolh@dsp.ac.cn

PDF (PC)

671

Like

Cited

1

Abstract:

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.

Key words: overlay network, service deployment, heuristic algorithms, request forwarding delay

CLC Number: 

  • TP393

Copyright © 2018 Journal of Xidian University, All Rights Reserved.
Powered by Beijing Magtech Co. Ltd