分布式交互应用中服务器放置问题的启发式算法

Heuristic Algorithm for Server Placement in Distributed Interactive Applications

分布式交互应用是允许分散在不同地点的多个参与者能实时进行交互的网络系统,它的交互质量在很大程度上取决于网络延迟,而通过对服务器位置的合理布局可以降低网络延迟。因此,服务器放置是影响分布式交互应用的交互性能的关键因素。针对分布式交互应用中服务器放置问题,提出了模拟退火算法和禁忌搜索算法,并与已有的遗传算法进行了比较。通过实验可以看出,尽管在求得较好解的速度方面,遗传算法占据优势,但在求得解的质量方面,提出的模拟退火算法和禁忌搜索算法均优于遗传算法,在服务器数量相同的条件下,延迟平均降低了15.5%和15.2%,更加有效地提高了交互质量。

Distributed interactive applications（DIAs）are networked systems that allow multiple participants at different locations to interact with each other in real time.The interaction quality heavily depends on network latencies which can be reduced by reasonable distribution of location where the servers of the DIAs are placed.Thus,the placement of servers is a key factor to the interactivity performance of DIAs.The simulated annealing algorithm and tabu search algorithm were used to solve the server placement problem in this paper.Then these two algorithms were compared with genetic algorithm.The experiment results show that the genetic algorithm is much faster in the speed of obtaining a better solution,but simulated annealing algorithm and tabu search algorithm outperform genetic algorithm in the quality of the solution and obtain average latency reduction of 15.5% and 15.2% respectively for the same number of server,which effectively improve the quality of the interaction.