Efficient Algorithms for Locating Web Proxies

摘要

With the increasing popularity of the World Wide Web (Web), it is very difficult for a single popular Web server to handle the explosive demand from its clients. Web caching (proxy) is an effective technique to reduce a Web server's load, alleviate Internet traffic, and reduce user's response time when accessing a Web service. A fundamental question is where to locate proxies throughout the network to minimize total access time. We consider the problem of locating k Web proxies on a network of n nodes. The objective is to minimize the overall cost for accessing Web services to satisfy a given level of demand. We present O(n~2) time algorithms which computes optimal proxy locations for unidirectional and bidirectional rings. We develop heuristic algorithms for finding proxy locations for a general network topology and compare the heuristic algorithms with optimal solution through simulations.