[talks] Anirudh Badam general exam
Melissa M Lawson
mml at CS.Princeton.EDU
Wed Jan 16 16:38:14 EST 2008
Anirudh Badam will present his research seminar/general exam on Thursday
January 24 at 1PM in Room 402. The members of his committee are:
Vivek Pai (advisor), Jennifer Rexford, and Larry Peterson. Everyone is
invited to attend his talk, and those faculty wishing to remain for the oral
exam following are welcome to do so. His abstract and reading list
Web Caching is the caching of web documents in order to reduce bandwidth usage, server
load and perceived download time for the web object download. A web cache stores copies of
web objects when they are accessed through cache. The stored objects can be used to server
subsequent requests. Web caching has been extensive studied and a plethora of techniques
exist today. Solutions are based on developing good cache replacement algorithms which are
used to figure out storing what objects can provide more savings, improving file systems
which usually involves optimizing file systems for frequent additions, deletions and
accesses, etc. However, the existing solutions have scalability problems with respect to
memory. Some techniques impose lower bounds on the amount of memory needed for a web
cache. Other techniques have huge virtual memory requirements leading to frequent swapping
in low memory systems. Cache replacement policies need metadata for better functionality
and file systems need huge lists or trees (preferably in memory) for any access to files
that it stores. This requires the physical memory to scale as an increasing function of
the number of web objects that the cache can store. This restricts not only the number of
objects that can be stored in a web cache but also the economical affordability of the
system. Hence, we propose a web caching mechanism, the HashCache, a file system
optimization approach, which uses hashing to reduce the physical memory requirements.
HashCache uses hashing techniques to map files to the disk locations. Hashing makes the
cache maintenance and usage to be mostly memory less. Hashing mechanism also allows more
flexible mechanisms for metadata maintenance and does not impose lower bounds on the
requirements of memory to provide performance guarantees. HashCache exploits the
distribution of sizes and contents of web objects to enable an efficient usage of the
secondary storage (optimal bucket sizes). Also, with the help of experiments on an
implementation of the HashCache architecture we show the usefulness of HashCache.
1. Computer Networks by Peterson and Davie
2. Operating System Concepts by Silberschatz, Galvin and Gagne
3. P. Danzig, R. Hall, and M. Schwartz, A Case for Caching File Objects inside
Internetworks, Tech. Report CU-CS-642-93, Dept. of Computer Science, Univ. of Colorado,
Boulder, Colo., 1993.
4. S. Acharya and S.B. Zdonik, An Efficient Scheme for Dynamic Data Replication, Tech.
Report CS-93-43, Dept. of Computer Science, Brown Univ., Providence, R.I., 1993.
5. M.M. Recker and J.E. Pitkow, Predicting Document Access in Large, Multimedia
Repositories, Tech. Report VU-GIT-94-35, Graphics, Visualization, and Usability Center,
Georgia Tech, Atlanta, 1994.
6. D.D. Sleator, R.E. Trajan, Amortized efficiency of list update and paging rules,
Commun. ACM, Vol. 2, p 202-208, 1985.
7. D. Wessels, K. Claffy, ICP and the Squid Web Cache, IEEE JSAC, Vol. 16, No. 3. 1998.
8. H. Bahn, S.H. Noh, L. Min, K. Koh, Using Full Reference History For Efficient Document
Replacement In Web Caches, In Proc. USITS, Colorado, Boulder, 1999.
9. E.P. Markatos, M.G.H. Katevenis, D. Pnevmatikatos, M. Flouris, Secondary Storage
Management For Web Proxies, In Proc Usits 99, Boulder, Colorado, 1999.
10. A. Sweeney, Scalability in the XFS File System, In Proc USENIX 96, San Diego,
11. L. Breslau, P. Cao, L. Fan, G. Phillips, Scott Shenker, Web Caching and Zipf-like
Distributions: Evidence and Implications , In Proc. IEEE Infocom, 1999.
12 C. Agarwal, J. L. Wolf, P. S. Yu, Caching on the World Wide Web, IEEE Tran. Knowledge
and Data Engineering, Vol. 11, No. 1, January, 1999.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the talks