| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Coordinated En-Route Web Caching
June 2002 (vol. 51 no. 6)
pp. 595-607
Abstract—Web caching is an important technique for reducing Internet access latency, network traffic, and server load. This paper investigates cache management strategies for the en-route web caching environment, where caches are associated with routing nodes in the network. We propose a novel caching scheme that integrates both object placement and replacement policies and which makes caching decisions on all candidate sites in a coordinated fashion. In our scheme, cache status information along the routing path of a request is used in dynamically determining where to cache the requested object and what to replace if there is not enough space. The object placement problem is formulated as an optimization problem and the optimal locations to cache the object are obtained using a low-cost dynamic programming algorithm. Extensive simulation experiments have been performed to evaluate the proposed scheme in terms of a wide range of performance metrics. The results show that the proposed scheme significantly outperforms existing algorithms which consider either object placement or replacement at individual caches only.
[1] S. Glassman, “A Caching Relay for the World Wide Web,” Computer Networks and ISDN Systems, vol. 27, no. 2, pp. 165-173, Nov. 1994.
[2] J. Wang, “A Survey of Web Caching Schemes for the Internet,” ACM SIGCOMM Computer Comm. Rev., vol. 29, no. 5, pp. 36-46, Oct. 1999.
[3] B.D. Davison, “A Web Caching Primer,” IEEE Internet Computing, vol. 5, no. 4, pp. 38-45, July/Aug. 2001.
[4] L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, Web Caching and Zipf-Like Distributions: Evidence and Implications Proc. Infocom '99, Mar. 1999.
[5] R.P. Wooster and M. Abrams, "Proxy Caching That Estimates Page Load Delays," Computer Networks and ISDN Systems, vol. 29, nos. 8-13, 1997, pp. 977-986.
[6] P. Cao and S. Irani, “Cost-Aware WWW Proxy Caching Algorithms,” Proc. First USENIX Symp. Internet Technologies and Systems (USITS), pp. 193-206, Dec. 1997.
[7] C. Aggarwal, J. Wolf, and P. Yu, "Caching on the World Wide Web," IEEE Trans. Knowledge and Data Eng., vol. 11, no. 1, 1999, pp. 94-107.
[8] J. Shim, P. Scheuermann, and R. Vingralek, "Proxy Cache Design: Algorithms, Implementation, and Performance," IEEE Trans. Knowledge and Data Eng., vol. 11, no. 4, 1999, pp. 549-562.
[9] J.-M. Menaud, V. Issarny, and M. Banâtre, "Improving the Effectiveness of Web Caching," Recent Advances in Distributed Systems, Part 3, Applications Support, S. Krakowiak and S.K. Shrivastava, eds., Springer-Verlag, Berlin, 1999, pp. 375.
[10] S. Jin and A. Bestavros, “Greedydual* Web Caching Algorithm: Exploiting the Two Sources of Temporal Locality in Web Request Streams,” Computer Comm., vol. 24, no. 2, pp. 174-183, Feb. 2001.
[11] A. Chankhunthod, P.B. Danzig, C. Neerdaels, M.F. Schwartz, and K.J. Worrell, “A Hierarchical Internet Object Cache,” Proc. 1996 USENIX Ann. Technical Conf., pp. 153-163, Jan. 1996.
[12] R. Tewari, M. Dahlin, H.M. Vin, and J. Kay, Beyond Hierarchies: Design Considerations for Distributed Caching on the Internet Proc. 19th Int'l Conf. Distributed Computing Systems (ICDCS), June 1999.
[13] P. Rodriguez, C. Spanner, and E.W. Biersack, “Analysis of Web Caching Architectures: Hierarchical and Distributed Caching,” IEEE/ACM Trans. Networking, vol. 9, no. 4, pp. 404-418, Aug. 2001.
[14] “Proxy Cache Comparison,” www.cs.cornell.edu/home/weichen/research/ mypapers/thesis.ps.gzhttp://www.web-caching.com proxy-comparison.html, 2001.
[15] S. Bhattacharjee, K.L. Calvert, and E.W. Zegura, “Self-Organizing Wide-Area Network Caches,” Proc. IEEE INFOCOM '98, pp. 600-608, Mar. 1998.
[16] P. Rodriguez and S. Sibal, “Spread: Scalable Platform for Reliable and Efficient Automated Distribution,” Computer Networks, vol. 33, nos. 1-6, pp. 33-49, June 2000.
[17] P. Krishnan, D. Raz, and Y. Shavitt, “The Cache Location Problem,” IEEE/ACM Trans. Networking, vol. 8, no. 5, pp. 568-582, Oct. 2000.
[18] P. Rodriguez, S. Sibal, and O. Spatscheck, “Tpot: Translucent Proxying of TCP,” Proc. Fifth Int'l Web Caching and Content Delivery Workshop (WCW), May 2000.
[19] M. Rabinovich and H. Wang, “Dhttp: An Efficient and Cache-Friendly Transfer Protocol for Web Traffic,” Proc. IEEE INFOCOM '01, pp. 1597-1606, Apr. 2001.
[20] D.L. Tennenhouse, J.M. Smith, W.D. Sincoskie, D.J. Wetherall, and G.J. Minden, “A Survey of Active Network Research,” IEEE Comm. Magazine, vol. 35, no. 1, pp. 80-86, Jan. 1997.
[21] D. Wessels and K. Claffy, "ICP and the Squid Web Cache," IEEE J. Selected Areas in Comm., vol. 16, no. 3, Apr. 1998.
[22] L. Fan, P. Cao, J. Almeida, and A.Z. Broder, “Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol,” IEEE/ACM Trans. Networking, vol. 8, no. 3, pp. 281-293, June 2000.
[23] M. Rabinovich, J. Chase, and S. Gadde, “Not All Hits Are Created Equal: Cooperative Proxy Caching over a Wide Area Network,” Computer Networks and ISDN Systems, vol. 30, nos. 22-23, pp. 2253-2259, Nov. 1998.
[24] B. Li, M.J. Golin, G.F. Italiano, X. Deng, and K. Sohraby, “On the Optimal Placement of Web Proxies in the Internet,” Proc. IEEE INFOCOM '99, pp. 1282-1290, Mar. 1999.
[25] K.W. Ross, “Hash Routing for Collections of Shared Web Caches,” IEEE Network, vol. 11, no. 6, pp. 37-44, Nov./Dec. 1997.
[26] K.-L. Wu and P.S. Yu, “Load Balancing and Hot Spot Relief for Hash Routing among a Collection of Proxy Caches,” Proc. 19th IEEE Int'l Conf. Distributed Computing Systems (ICDCS), pp. 536-543, June 1999.
[27] P.S. Yu and E.A. MacNair, “Performance Study of a Collaborative Method for Hierarchical Caching in Proxy Servers,” Computer Networks and ISDN Systems, vol. 30, nos. 1-7, pp. 215-224, Apr. 1998.
[28] S. Williams et al., "Removal Policies in Network Caches for World Wide Web Documents," Applications, Technologies, Architectures, and Protocols for Computer Communications, ACM Press, New York, 1996, pp. 293-305.
[29] P. Scheuermann, J. Shim, and R. Vingralek, “A Case for Delay-Conscious Caching of Web Documents,” Computer Networks and ISDN Systems, vol. 29, nos. 8-13, pp. 997-1005, Sept. 1997.
[30] V.N. Padmanabhan and L. Qiu, “The Content and Access Dynamics of a Busy Web Site: Findings and Implications,” Proc. ACM SIGCOMM '00, pp. 111-123, Aug. 2000.
[31] B. Krishnamurthy and C.E. Wills, “Piggyback Server Invalidation for Proxy Cache Coherency,” Computer Networks and ISDN Systems, vol. 30, nos. 1-7, pp. 185-193, Apr. 1998.
[32] V. Paxson, “End-to-End Routing Behavior in the Internet,” IEEE/ACM Trans. Networking, vol. 5, no. 5, pp. 601-615, Oct. 1997.
[33] B. Li, X. Deng, M.J. Golin, and K. Sohraby, “On the Optimal Placement of Web Proxies in the Internet: The Linear Topology,” Proc. Eighth IFIP TC-6 Int'l Conf. High Performance Networking (HPN), pp. 485-495, Sept. 1998.
[34] K.L. Calvert, M.B. Doar, and E.W. Zegura, “Modeling Internet Topology,” IEEE Comm. Magazine, vol. 35, no. 6, pp. 160-163, June 1997.
[35] P. Barford and M. Crovella, “Generating Representative Web Workloads for Network and Server Performance Evaluation,” Proc. ACM SIGMETRICS '98, pp. 151-160, July 1998.
[36] S. Jin and A. Bestavros, “Popularity-Aware Greedydual-Size Web Proxy Caching Algorithms,” Proc. 20th IEEE Int'l Conf. Distributed Computing Systems (ICDCS), pp. 254-261, Apr. 2000.
Index Terms:
Web caching, web cache management, web object placement, transparent web cache, dynamic programming, performance evaluation, World Wide Web.
Citation:
Xueyan Tang, Samuel T. Chanson, "Coordinated En-Route Web Caching," IEEE Transactions on Computers, vol. 51, no. 6, pp. 595-607, June 2002, doi:10.1109/TC.2002.1009146
