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 follow below. Abstract: 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, California, 1996. 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.