互联网中代理服务器反向定位问题

Reverse Location of Web Proxies with Delay Constraint on the Network

考虑了源服务器数据更新时,如何在不超过预算的情况下改善网络使得原有设施运行更有效,同时还要保证每个用户都能够及时获得最新信息.首先给出该问题的数学模型;然后通过找代理服务器到源服务器的最短路树,把模型转化为修剪总费用最小化和最大时延最小化的两个子问题;最后利用代理服务器放置具有方向性的特征继续转化为只有一个设施点的反向定位问题,采用最小割的算法进行求解,并通过一个实例验证了该算法可行性.

The paper is discussed that how to improve the network construction with the equipments now available running effectively under the given budget when the data in the source server updates, as well as ensuring that every user can get the new information. First, the mathematical model is presented, and then the model is transformed into two subproblems which are the location problems with MinSum and MinMax objective function through finding the shortest path tree for updating proxies. Finally the two subproblems are transformed to reverse location problems with one center according to the feature of proxy, and then the algorithm for minimum cut problem is used to solve them. An example is set to verify the feasibility of this algorithm.