Knapsack-model-based Schemes and WLB Algorithm for the Capacity and Efficiency Management of Web Cache


  • Anbo Xiang Development Research Center of the State Council, Beijing, 100010, China
  • Liang Xu Department of Logistics Management, School of Business Administration, Southwestern University of Finance and Economics, Chengdu, 611130, China
  • Baozhuang Niu Lingnan College, Sun Yat-sen University, Guangzhou, 510275, China


web cache placement/replacement scheme, Knapsack model, load balancing and routing algorithm, performance analysis


Web cache refers to the temporary storage of web files/documents. In reality, a set of caches can be grouped into a cluster to improve the server system's performance. In this paper, to achieve the overall cluster efficiency, we propose a weighted load balancing (WLB) routing algorithm by considering both the cache capability and the content property to determine how to direct an arrival request to the right node. Based on Knapsack models, we characterize three new placement/replacement schemes for Web contents caching and then conduct the comparison based on WLB algorithm. We also compare WLB algorithm with two other widely used algorithms: Pure load balancing (PLB) algorithm and Round-Robin (RR) algorithm. Extensive simulation results show that the WLB algorithm works well under the examined cluster content placement/replacement schemes. It generally results in shorter response time and higher cache hit ratio, especially when the cache cluster capacity is scarce.


Datta, A. et al (2003); World Wide Wait: A Study of Internet Scalability and Cache-based Approaches to Alleviate It, Management Science, ISSN 0025-1909, 49: 1425-1444.

Kumar, C. ; and Norris, J. (2008); A New Approach for A Proxy-level Web Caching Mechanism, Decision Support Systems, ISSN 0167-9236, 46: 52-60.

Xiang, A. (2006); Essays on information service systemes. PhD Dissertation. Hong Kong University of Science and Technology.

Bahat, O.; Makowski, A. M.; (2003) Optimal Replacement Policies for Non-uniform Cache Objects with Optional Eviction. IEEE INFOCOM 2003, San Francisco, California, April.

Wang, B. et al (2002); Proxy-based Distribution of Streaming Video over Unicast/Multicast Connections. Proceedings of IEEE Infocom, New York, June.

Otoo, E. et al (2002); Disk Cache Replacement Algorithms for Storage Resource Managers in Data Grids. The 15th Annual Supercomputer Conference, Baltimore, Maryland, November.

Rabinovich, M.; Spatscheck, O. (2002); Web Caching and Replication. Addison-Wesley, Boston, MA, US.

Feenan,J. et al (2002); Clustering Web Accelerators. IEEE WECWIS Proceedings, San Diego, June.

Zhang, X., et al (1999); HACC: An Architecture for Cluster-basedWeb Servers. 3rd USENIX Windows NT Symposium, Seattle, Washington, July.

Clevenot, F., et al (2005); Stochastic Fluid Models for Cache Cluster. ISSN 0166-5316, Performance Evaluation, 59: 1-18.

Bertsimas, D.; Demir, R. (2002); An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems. ISSN 0025-1909, Management Science, 48: 550-565.

Breslau, L., et al (1999); Web Caching and Zipf-like Distributions: Evidence and Implications. ISSN 0743-166X, IEEE INFOCOM, 1, 126-134.

Liu, L. et al (2005); Weighted Load Balancing for Web Server Clusters with Caching. Working paper. Hong Kong University of Science and Technology.



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.