A low-bandwidth network file system

ABSTRACT

Users rarely consider running network file systems over slow or wide-area networks, as the performance would be unacceptable and the bandwidth consumption too high. Nonetheless, efficient remote file access would often be desirable over such networks---particularly when high latency makes remote login sessions unresponsive. Rather than run interactive programs such as editors remotely, users could run the programs locally and manipulate remote files through the file system. To do so, however, would require a network file system that consumes less bandwidth than most current file systems.This paper presents LBFS, a network file system designed for low-bandwidth networks. LBFS exploits similarities between files or versions of the same file to save bandwidth. It avoids sending data over the network when the same data can already be found in the server's file system or the client's cache. Using this technique in conjunction with conventional compression and caching, LBFS consumes over an order of magnitude less bandwidth than traditional network file systems on common workloads.

REFERENCES

• 1: Brian Berliner. CVS II: Parellizing software development. In Proceedings of the Winter 1990 USENIX Technical Conference, Colorado Springs, CO, 1990.
• 2: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 3: Sergey Brin , James Davis , Héctor García-Molina, Copy detection mechanisms for digital documents, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.398-409, May 22-25, 1995, San Jose, California, United States
• 4: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 5: B. Callaghan, B. Pawlowski, and P. Staubach. NFS version 3 protocol specification. RFC 1813, Network Working Group, June 1995.
• 6: FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce/N.I.S.T., National Technical Information Service, Springfield, VA, April 1995.
• 7: C. Gray , D. Cheriton, Leases: an efficient fault-tolerant mechanism for distributed file cache consistency, Proceedings of the twelfth ACM symposium on Operating systems principles, p.202-210, November 1989
• 8: Björn Grönvall , Assar Westerlund , Stephen Pink, The design of a multicast-based distributed file system, Proceedings of the third symposium on Operating systems design and implementation, p.251-264, February 1999, New Orleans, Louisiana, United States
• 9: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• 10: 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]
• 11: Eddie Kohler , Robert Morris , Benjie Chen , John Jannotti , M. Frans Kaashoek, The click modular router, ACM Transactions on Computer Systems (TOCS), v.18 n.3, p.263-297, Aug. 2000 [doi>10.1145/354871.354874]
• 12: Yui-Wah Lee, Kwong-Sak Leung, and M. Satyanarayanan. Operation-based update propagation in a mobile file system. In Proceedings of the 1999 USEN1X Technical Conference, Monterey, CA, June 1999.
• 13: Udi Manber. Finding similar files in a large file system. In Proceedings of the Winter 1994 USENIX Technical Conference, San Francisco, CA, January 1994.
• 14: Timothy Mann , Andrew Birrell , Andy Hisgen , Charles Jerian , Garret Swart, A coherent distributed file cache with directory write-behind, ACM Transactions on Computer Systems (TOCS), v.12 n.2, p.123-164, May 1994 [doi>10.1145/176575.176577]
• 15: David Mazières, A Toolkit for User-Level File Systems, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.261-274, June 25-30, 2001
• 16: David Mazières , Michael Kaminsky , M. Frans Kaashoek , Emmett Witchel, Separating key management from file system security, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.124-139, December 12-15, 1999, Charleston, South Carolina, United States
• 17: 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
• 18: Karin Petersen , Mike J. Spreitzer , Douglas B. Terry , Marvin M. Theimer , Alan J. Demers, Flexible update propagation for weakly consistent replication, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.288-301, October 05-08, 1997, Saint Malo, France
• 19: Michael O. Rabin. Fingerprinting by random polynomials. Technical Report TR-15-81, Center for Research in Computing Technology, Harvard University, 1981.
• 20: S. Shepler, B. Callaghan, D. Robinson, R. Thurlow, C. Beame, M. Eisler, and D. Noveck. NFS version 4 protocol. RFC 3010, Network Working Group, December 2000.
• 21: Neil T. Spring , David Wetherall, A protocol-independent technique for eliminating redundant network traffic, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.87-95, August 28-September 01, 2000, Stockholm, Sweden
• 22: Walter F. Tichy, The string-to-string correction problem with block moves, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.309-321, Nov. 1984 [doi>10.1145/357401.357404]
• 23: Andrew Tridgell. Efficient Algorithms for Sorting and Synchronization. PhD thesis, Australian National University, April 2000.
• 24: Assar Westerlund and Johan Danielsson. Arla--a free AFS client. In Proceedings of the 1998 USENIX, Freenix track, New Orleans, LA, June 1998. USENIX.
• 25: Haifeng Yu and Amin Vahdat. Design and evaluation of a continuous consistency model for replicated services. In Proceedings of the 4rd Symposium on Operating Systems Design and Implementation, San Diego, CA, 2000.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Distributed file systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Network communication

General Terms:
Design, Performance