Summary cache: a scalable wide-area Web cache sharing protocol

ABSTRACT

The sharing of caches among Web proxies is an important technique to reduce Web traffic and alleviate network bottlenecks. Nevertheless it is not widely deployed due to the overhead of existing protocols. In this paper we propose a new protocol called "Summary Cache"; each proxy keeps a summary of the URLs of cached documents of each participating proxy and checks these summaries for potential hits before sending any queries. Two factors contribute to the low overhead: the summaries are updated only periodically, and the summary representations are economical --- as low as 8 bits per entry. Using trace-driven simulations and a prototype implementation, we show that compared to the existing Internet Cache Protocol (ICP), Summary Cache reduces the number of inter-cache messages by a factor of 25 to 60, reduces the bandwidth consumption by over 50%, and eliminates between 30% to 95% of the CPU overhead, while at the same time maintaining almost the same hit ratio as ICP. Hence Summary Cache enables cache sharing among a large number of proxies.

REFERENCES

• 1: B. M. Duska, D. Marwood, and M. J. Feeley, "The measured access characteristics of World-Wide-Web client proxy caches," in Proc. USENiX Syrup. on Internet Technologies and Systems, pp. 23-35, December 1997. http://www, cs. ubc. ca/spider/marwood/Proj ects/ SPA/wwwap.
• 2: "Squid intemet object cache." http://squid.nlanr .net/Squid.
• 3: R. Caceres, F. Douglis, A. Feldmann, G. Glass, and M. Rabinovich, "Web proxy caching: The devil is in the details," in Proc. Workshop on Internet Server Performance, June 1998. http: //www. cs. wisc. edu/-cao/WiSP98, html.
• 4: A. Bestavros , R. L. Carter , M. E. Crovella , C. R. Cunha , A. Heddaya , S. A. Mirdad, Application-level document caching in the Internet, Proceedings of the 2nd International Workshop on Services in Distributed and Networked Environments, p.166, June 05-08, 1995
• 5: P. Cao and S. Irani, "Cost-aware WWW proxy caching algorithms," in Proc. USENIX Syrup. on lnternet Technoloyies and Systems, pp. 193-206, December 1997. http://www, cs. wisc. edu/-cao/papers/gd- size. html.
• 6: Marc Abrams , Charles R. Standridge , Ghaleb Abdulla , Edward A. Fox , Stephen Williams, Removal policies in network caches for World-Wide Web documents, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.293-305, August 28-30, 1996, Palo Alto, California, United States
• 7: V. Cate, "Alex- A global filesystem," in Proc. USENfX File System Workshop, pp. 1-12, May 1992.
• 8: Adam Dingle , Tomáš Pártl, Web cache coherence, Proceedings of the fifth international World Wide Web conference on Computer networks and ISDN systems, p.907-920, May 1996, Paris, France
• 9: S. D. Gribble and E. A. Brewer, "System design issues for Internet middleware services: Deductions from a large client trace," in Proc. USENIX Syrup. on fnternet Technologies and Systems, December 1997. http://www, usenix, org/events/us it s97.
• 10: B. Krishnamurthy and C. E. Wills, "Study of piggyback cache validation for proxy caches in the World Wide Web," in Proc. USENIX Syrup. on Internet Technologies and Systems, pp. 1-12, December 1997. http: //www. research, att. corn/~bala/papers/ pcv-u$ it s97. ps. gz
• 11: Venkata N. Padmanabhan , Jeffrey C. Mogul, Improving HTTP latency, Computer Networks and ISDN Systems, v.28 n.1-2, p.25-35, Dec. 1995 [doi>10.1016/0169-7552(95)00106-1]
• 12: Henrik Frystyk Nielsen , James Gettys , Anselm Baird-Smith , Eric Prud'hommeaux , Håkon Wium Lie , Chris Lilley, Network performance effects of HTTP/1.1, CSS1, and PNG, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.155-166, September 14-18, 1997, Cannes, France
• 13: Jeffrey C. Mogul, Hinted caching in the web, Proceedings of the 7th workshop on ACM SIGOPS European workshop: Systems support for worldwide applications, September 09-11, 1996, Connemara, Ireland [doi>10.1145/504450.504470]
• 14: Azer Bestavros, Using speculation to reduce server load and service time on the WWW, Proceedings of the fourth international conference on Information and knowledge management, p.403-410, November 29-December 02, 1995, Baltimore, Maryland, United States [doi>10.1145/221270.221653]
• 15: Venkata N. Padmanabhan , Jeffrey C. Mogul, Using predictive prefetching to improve World Wide Web latency, ACM SIGCOMM Computer Communication Review, v.26 n.3, p.22-36, July 1996 [doi>10.1145/235160.235164]
• 16: Z. Jiang and L. Kleinrock, "Prefetching links on the WWW," in Proc. IEEE Inter. Conf. on Communications, pp. 483-489, June 1997. http://millennium, cs. ucla. edu/' j iang/Research/ Publ i cat i on/pre fet ch. ps.
• 17: M. Crovella and P. Barford, "The network effects of prefetching," in Proc. IEEE INFOCOM, pp. 1232-1240, April 1998. http: //www. cs. bu. edu/f aculty/crovella/ papers, html.
• 18: T. M. Kroeger, D. E. Long, and O. C. Mogul, "Exploring the bounds of Web latency reduction from caching and prefetching," in Proc. USENIX Syrnp. on }nternet Technologies and Systems, pp. 13-22, December 1997. http://www, cse. ucsc. edu/~ tmk/ideal, ps.
• 19: C. Liu , P. Cao, Maintaining Strong Cache Consistency in the World-Wide Web, Proceedings of the 17th International Conference on Distributed Computing Systems (ICDCS '97), p.12, May 27-30, 1997
• 20: Balachander Krishnamurthy , Craig E. Wills, Piggyback server invalidation for proxy cache coherency, Proceedings of the seventh international conference on World Wide Web 7, p.185-193, April 1998, Brisbane, Australia
• 21: E. Cohen, B. Krishnamurthy, and J. Rexford, "Improving end-to-end performance of the web using server volumes and proxy filters," Tech. Rep. 980206-01, AT&T Labs- Research, February 1998. http://www .research. att. com/~bala/papers/ mafia-tm.ps, gz.
• 22: R. Fielding, J. Gettys, J. C. Mogul, H. Frystyk, and T. Berners-Lee, "Hypertext transfer protocol- HTTP/1.1,', Internet Draft, March 13 1998. This is a work in progress. http://www, w3. org/Prot ocols/HTTP/1.1/ draft - ietf -http-v 11-spec-rev-03. txt.
• 23: Jeffrey C. Mogul , Fred Douglis , Anja Feldmann , Balachander Krishnamurthy, Potential benefits of delta encoding and data compression for HTTP, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.181-194, September 14-18, 1997, Cannes, France
• 24: Edith Cohen , Balachander Krishnamurthy , Jennifer Rexford, Evaluating Server-Assisted Cache Replacement in the Web, Proceedings of the 6th Annual European Symposium on Algorithms, p.307-319, August 24-26, 1998
• 25: F. DougHs, A. Feldmann, B. Krishnamurthy, and J. Mogul, "Rate of change and other metrics: A live study of the World Wide Web," in Proc. USENIX Syrup. on Internet Technologies and Systems, pp. 147- 158, December 1997. http://www .research. art. com/-bala/papers/ roc-usits97.ps.gz
• 26: Martin F. Arlitt , Carey L. Williamson, Internet Web servers: workload characterization and performance implications, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.631-645, Oct. 1997 [doi>10.1109/90.649565]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

          Nouns: World Wide Web (WWW)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Performance