Improving end-to-end performance of the Web using server volumes and proxy filters

ABSTRACT

The rapid growth of the World Wide Web has caused serious performance degradation on the Internet. This paper offers an end-to-end approach to improving Web performance by collectively examining the Web components --- clients, proxies, servers, and the network. Our goal is to reduce user-perceived latency and the number of TCP connections, improve cache coherency and cache replacement, and enable prefetching of resources that are likely to be accessed in the near future. In our scheme, server response messages include piggybacked information customized to the requesting proxy. Our enhancement to the existing request-response protocol does not require per-proxy state at a server, and a very small amount of transient per-server state at the proxy, and can be implemented without changes to HTTP 1.1. The server groups related resources into volumes (based on access patterns and the file system's directory structure) and applies a proxy-generated filter (indicating the type of information of interest to the proxy) to tailor the piggyback information. We present efficient data structures for constructing server volumes and applying proxy filters, and a transparent way to perform volume maintenance and piggyback generation at a router along the path between the proxy and the server. We demonstrate the effectiveness of our end-to-end approach by evaluating various volume construction and filtering techniques across a collection of large client and server logs.

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 lnternet Server Performance, June 1998. http: //www. cs. wisc. edu/-cao/WI 8P98. 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 Internet Technologies and Systems, pp. 193-206, December 1997. http://www, cs. wisc. edu/-cao/papers/gd-s ize. 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 Prec. USENIX 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 lnternet middleware services: Deductions from a large client trace," in Prec. USENIX Syrup. on Internet 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 Prec. USENIX Syrup. on {nternet Technologies and Systems, pp. 1-12, December 1997. http://www, research, art. com/~bale/papers/ pcv-us itsg7, 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 Prec. IEEE Inter. Conf. on Communications, pp. 483-489, June 1997. ht tp://millennium, cs. ucla. edu/- j i ang/Research/ Publ i cat i on/pre f e t ch. ps.
• 17: M. Crovella and P. Barford, "The network effects of prefetching," in Prec. 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 J. C. Mogul, "Exploring the bounds of Web latency reduction from caching and prefetching," in Prec. USENIX Syrup. on Internet Technologies and Systems, pp. 13-22, December 1997. ht tp://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/ mar ia-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- i et f-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 Prec. USENIX Syrup. on Internet Technologies and Systems, pp. 147- 158, December 1997. http://www .research. art. com/-bal a/papers/ roc-us its97, 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

Keywords:
Web, caching, coherency, filters, piggybacking, prefetching, volumes