A performance analysis of a cache-based file prediction protocol for mobile file systems

ABSTRACT

File prediction is the process of bringing necessary files into cache before they are needed, while file caching is the process of maintaining required data in memory for future reuse. Our combined concept, which is the cache-based file prediction, is designed to support the main objectives of the Paradise File System, which are to provide high available and reliable storage for files, and guarantees that file operations are executed in spite of concurrency and failures. In this paper, we show that our cache-based file prediction scheme is efficient and practical by describing its design and implementation. Moreover, we report on its performance evaluation using a cluster of workstations. Our results indicate clearly that our design exhibits a significant degree of files availability and prediction accuracy

REFERENCES

• 1: Gary A. S. Whittle , Jehan-François Pâris , Ahmed Amer , Darrell D. E. Long , Randal Burns, Using Multiple Predictors to Improve the Accuracy of File Access Predictions, Proceedings of the 20 th IEEE/11 th NASA Goddard Conference on Mass Storage Systems and Technologies (MSS'03), p.230, April 07-10, 2003
• 2: Griffioen, J., Appleton, R., "Reducing File System Latency using a Predictive Approach", Proceedings of USENIX Conference, 1994.
• 3: Tom M. Kroeger , Darrell D. E. Long, Design and Implementation of a Predictive File Prefetching Algorithm, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.105-118, June 25-30, 2001
• 4: H. Lei and D. Duchamp, "An Analytical Approach to File Prefetching", in Proc. 1997 USENIX Annual Technical Conference, Jan. 1997.
• 5: E. Shriver, C. Small, and K. Smith. "Why does the system prefetching work?", USENIX (Monterey, California), pages 71--83, 1999.
• 6: C. Bouras, A. Konidaris, D. Kostoulas, "A Most Popular Approach of Predictive Prefetching on a WAN to Efficiently Improve WWW Response Times", The Second International Workshop on Grid and Cooperative Computing, Shangai, China, December 2003, pp. 344--351.
• 7: Ahmed Amer, Darrell D. E. Long, Jehan-Francois Paris, and Randal C. Burns. "File Access Prediction with Adjustable Accuracy," Proceedings of the International Performance Conference on Computers and Communication (IPCCC 2002), Phoenix, Arizona: IEEE, April 2002.
• 8: Tsozen Yeh , Darrell D. E. Long , Scott A. Brandt, Performing File Prediction with a Program-Based Successor Model, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.193, August 15-18, 2001
• 9: Tsozen Yeh, Darrell D. E. Long, and Scott A. Brandt. "Using program and user information to improve file prediction performance", In Proceedings of the International Symposium on Performance Analysis of Systems and Software (ISPASS '01), pages 111--119, Tucson, November 2001. IEEE.
• 10: Tsozen Yeh, Darrell D. E. Long, and Scott A. Brandt. "Increasing predictive accuracy through limited prefetching", In Proceedings of Communications Networks and Distributed Systems Modeling and Simulation (CNDS 2002), pages 131--138, San Antonio, January 2001. Society for Computer Simulation.
• 11: J. Griffioen and R. Appleton, "Improving File System Performance via Predictive Caching", September 1995.
• 12: Ebling, M.R., Mummert, L.B., Steere, D.C., Overcoming the Network Bottleneck in Mobile Computing, Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, Santa Cruz, CA, Dec. 1994.
• 13: Silvano Maffeis, Cache management algorithms for flexible filesystems, ACM SIGMETRICS Performance Evaluation Review, v.21 n.2, p.16-25, Dec. 1993 [doi>10.1145/174215.174219]
• 14: Willick, D.L., Eager, D.L. and Bunt, R.B., Disk Cache Replacement Policies for Network Fileservers, Proc. 13th International Conference on Distributed Computing Systems, May 1993, 2--11.
• 15: Michael N. Nelson , Brent B. Welch , John K. Ousterhout, Caching in the Sprite network file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.134-154, Feb. 1988 [doi>10.1145/35037.42183]
• 16: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
• 17: A. Boukerche, R. AlShaikh, B. Maeleau, "Highly Available File System for Mobile Distributed Computing", Proc. of the 30th IEEE LCN Conference, November 2005, Australia.
• 18: A. Boukerche, R. AlShaikh, "Towards Building a Fault Tolerant and Conflict-Free Distributed File System for Mobile Clients", 1st IEEE International Workshop on Performance Analysis and Enhancement of Wireless Networks, Austria, April 2006.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: File organization

Additional Classification:
  E. Data
  E.5 FILES
      Subjects: Backup/recovery

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms, Performance

Keywords:
caching algorithm, distributed file systems, paradise file system, pre-fetching algorithm