Exploiting regularities in Web traffic patterns for cache replacement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Exploiting regularities in Web traffic patterns for cache replacement

Full text

Pdf (979 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 109 - 118

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Edith Cohen	AT&T Labs-Research, 180 Park Avenue, Florham Park, NJ
Haim Kaplan	AT&T Labs-Research, 180 Park Avenue, Florham Park, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 15, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/301250.301281 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Susanne Albers , Sanjeev Arora , Sanjeev Khanna, Page replacement for general caching problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.31-40, January 17-19, 1999, Baltimore, Maryland, United States
	2	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]
	3	Hari Balakrishnan , Mark Stemm , Srinivasan Seshan , Randy H. Katz, Analyzing stability in wide-area network performance, Proceedings of the 1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.2-12, June 15-18, 1997, Seattle, Washington, United States
	4	L. A. Belady. A study of replacement algorithms for virtual storage computers, iBM systems journal, 5:78-101, 1966.
	5	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]
	6	Allan Borodin , Prabhakar Raghavan , Sandy Irani , Baruch Schieber, Competitive paging with locality of reference, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.249-259, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103422]
	7	Pei Cax) and Sandy Irani. Cost-aware www proxy caching algorithms. In P~ceedings of the USENIX Symposium on lnte~aet Technologies and Systems, Monterey, California, December 1997. http: //ww. us enix. org/events/usit sg?.
	8	Edith Cohen , Haim Kaplan, LP-based analysis of greedy-dual-size, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.879-880, January 17-19, 1999, Baltimore, Maryland, United States
	9	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
	10	Edith Cohen , Balachander Krishnamurthy , Jennifer Rexford, Improving end-to-end performance of the Web using server volumes and proxy filters, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.241-253, August 31-September 04, 1998, Vancouver, British Columbia, Canada
	11	Amos Fiat , Ziv Rosen, Experimental studies of access graph based heuristics: beating the LRU standard?, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.63-72, January 05-07, 1997, New Orleans, Louisiana, United States
	12	Steven D. Gribble and Eric A. Brewer. System design issues for Internet middleware services: Deductions from a large client trace. In Proceedings of the USENIX Symposium on Internet Technologies and Systems, Monterey, California, December 1997. http: //~wv. usenix, org/event s/us it sg?.
	13	Sandy Irani, Page replacement with multi-size pages and applications to Web caching, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.701-710, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258666]
	14	A. Karlin, S. Phillips, and P. Raghavan. Markov paging. In Proc. 33rd IEEE Annual Symposium on Foundations of Compurer Science. IEEE, 1992.
	15	S. Keshav, C. Lund, S. Phillips, N. Reingold, and H. Saran. An empirical evaluation of virtual circuit holding time policies in IP-over-ATM networks. J. on selected areas in communication, 13, 1995.
	16	S. Keshav and H. Saran. An empirical evaluation of virtual circuit holding times policies in IP-over-ATM networks. In Pro~xiings o} the IEEE INFOCOM'94 Conference, 1994. http: //v~v. ca. cornell, edu/ske shay/papers/hold, ps.
	17	C. Lund, N. Reingold, and S. Phillips. IP over connection oriented networks and distributional paging. In Proc. 35th IEEE Annual Symposium on Foundations of Computer Science. IEEE, 1994. http://m, ca. cornell, edu/skeshav/doc/94/2-16, ps.
	18	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]
	19	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]
	20	Luigi Rizzo and Lorenzo Viclsano. Replacement policies for a proxy cache. http://wa~, iet. unipi, it/'luigi/lrv98, ps. gz, January 1998. Technical Report, University of Pisa.
	21	Neal E. Young, On-line file caching, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.82-86, January 25-27, 1998, San Francisco, California, United States

CITED BY 5

	Friedhelm Meyer auf der Heide , Berthold Vöcking , Matthias Westermann, Caching in networks (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.430-439, January 09-11, 2000, San Francisco, California, United States
	Edith Cohen , Haim Kaplan, Aging through cascaded caches: performance issues in the distribution of web content, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.41-53, October 2001
	Edith Cohen , Haim Kaplan, Refreshment policies for web content caches, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.6, p.795-808, 22 April 2002
	Yoon-Jung Rhee , Eun-Sil Hyun , Tai-Yun Kim, Connection management for QoS service on the web, Journal of Network and Computer Applications, v.25 n.1, p.57-68, January 2002
	Adam Meyerson , Kamesh Munagala , Serge Plotkin, Web caching using access statistics, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.354-363, January 07-09, 2001, Washington, D.C., United States