High-density model for server allocation and placement

ABSTRACT

It is well known that optimal server placement is NP-hard. We present an approximate model for the case when both clients and servers are dense, and propose a simple server allocation and placement algorithm based on high-rate vector quantization theory. The key idea is to regard the location of a request as a random variable with probability density that is proportional to the demand at that location, and the problem of server placement as source coding, i.e., to optimally map a source value (request location) to a code-word (server location) to minimize distortion (network cost). This view has led to a joint server allocation and placement algorithm that has a time-complexity that is linear in the number of clients. Simulations are presented to illustrate its performance.

REFERENCES

• 1: Vincenzo Auletta , Domenico Parente , Giuseppe Persiano, Dynamic and static algorithms for optimal placement of resources in a tree, Theoretical Computer Science, v.165 n.2, p.441-461, Oct. 10, 1996 [doi>10.1016/0304-3975(96)00089-8]
• 2: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 3: S. Bhattacharjee, K. Calvert, and E. W. Zegura. Self-organizing wide-area network caches. In Proceedings of IEEE Infocom, March/April 1998.
• 4: C. M. Bowman, P. B. Danzig, D. R. Hardy, U. Manber, and M. F. Schwartz. The Harvest information discovery and access system. In Proc. of the Second International Conf. on the World Wide Web, pages 763-771, 1994.
• 5: Lee Breslau, Pei Cao, Li Fan, Graham Phillips, and Scott Shenker. Web caching and Zipf-like distributions: Evidence and implications. In Proceedings of the IEEE Infocom, March 1999.
• 6: Anawat Chankhunthod, Michael Schwartz, Peter Danzig, Kurt Worrell, and Chuck Neerdaels. A hierarchical internet object cache. In Proceedings of the 1996 Usenix Technical Conference, pages 153-163, 1996.
• 7: Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha, Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.114-123, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276719]
• 8: Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.1-10, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301257]
• 9: Moses Charikar , Sudipto Guha, Improved Combinatorial Algorithms for the Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.378, October 17-18, 1999
• 10: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 11: Robert M. Gray, Source Coding Theory, Kluwer Academic Publishers, Norwell, MA, 1989
• 12: Kamal Jain , Vijay V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM (JACM), v.48 n.2, p.274-296, March 2001 [doi>10.1145/375827.375845]
• 13: J. Kangasharju, K. W. Ross, and J. W. Roberts. Locating copies of objects using the domain name system. In Proceedings of the 4th International Caching Workshop, March 1999.
• 14: David Karger , Alex Sherman , Andy Berkheimer , Bill Bogstad , Rizwan Dhanidina , Ken Iwamoto , Brian Kim , Luke Matkins , Yoav Yerushalmi, Web caching with consistent hashing, Proceeding of the eighth international conference on World Wide Web, p.1203-1213, May 1999, Toronto, Canada
• 15: O. Kariv and S. L. Hakimi. An algorithmic approach to network location problems. II: the p-medians. SIAM J. Appl. Math., 37(3):539-560, December 1979.
• 16: Balachander Krishnamurthy , Jia Wang, On network-aware clustering of Web clients, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.97-110, August 28-September 01, 2000, Stockholm, Sweden
• 17: P. Krishnan , Danny Raz , Yuval Shavitt, The cache location problem, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.568-582, Oct. 2000 [doi>10.1109/90.879344]
• 18: Bo Li, Mordecai Golin, Giuseppe Italiano, Xin Deng, and Kazem Sohraby. On the optimal placement of web proxies in the internet. In Proceedings of IEEE Infocom, March 1999.
• 19: B. S. Michel, K. Nikoloudakis, P. Reiher, and L. Zhang. URL forwarding and compression in adaptive web caching. In Proc. of IEEE Infocom, volume 2, pages 670-678, March 2000.
• 20: Scott Michel , Khoi Nguyen , Adam Rosenstein , Lixia Zhang , Sally Floyd , Van Jacobson, Adaptive web caching: towards a new global caching architecture, Computer Networks and ISDN Systems, v.30 n.22-23, p.2169-2177, Nov. 25, 1998 [doi>10.1016/S0169-7552(98)00246-3]
• 21: C. Papadimitriou. Worst-case and probabilistic analysis of a geometric location problem. SIAM J. Comput., 10:542-557, 1981.
• 22: L Qiu, V. Padmanabhan, and G. Voelker. On the placement of web server replicas. In Proceedings of IEEE Infocom, April 2001.
• 23: Michael Rabinovich , Amit Aggarwal, RaDaR: a scalable architecture for a global Web hosting service, Proceeding of the eighth international conference on World Wide Web, p.1545-1561, May 1999, Toronto, Canada
• 24: K. W. Ross. Hash-routing for collections of shared web caches. IEEE Network Magazine, pages 37-45, November/December 1997.
• 25: A. Shaikh, R. Tewari, and M. Agrawal. On the effectiveness of DNS-based server selection. In Proceedings of IEEE Infocom, April 2001.
• 26: A. Tamir. An O(pn2) algorithm for the p-median and related problems on tree graphs. Oper. Res. Lett., 19:59-64, 1996.
• 27: J. Touch. The LSAM proxy cache - a multicast distributed virtual caceh. In Proc. of the 3rd Int. WWW Caching Workshop, June 1998.
• 28: Duane Wessels and K. Claffy. Icp and the squid web cache. IEEE Journal on Selected Areas in Communication, 16(3):345-357, April 1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Performance, Theory

Keywords:
content distribution, high density, server placement and allocation