Rethinking FTP: Aggressive block reordering for large file transfers

ABSTRACT

Whole-file transfer is a basic primitive for Internet content dissemination. Content servers are increasingly limited by disk arm movement, given the rapid growth in disk density, disk transfer rates, server network bandwidth, and content size. Individual file transfers are sequential, but the block access sequence on a content server is effectively random when many slow clients access large files concurrently. Although larger blocks can help improve disk throughput, buffering requirements increase linearly with block size.

This article explores a novel block reordering technique that can reduce server disk traffic significantly when large content files are shared. The idea is to transfer blocks to each client in any order that is convenient for the server. The server sends blocks to each client opportunistically in order to maximize the advantage from the disk reads it issues to serve other clients accessing the same file. We first illustrate the motivation and potential impact of aggressive block reordering using simple analytical models. Then we describe a file transfer system using a simple block reordering algorithm, called Circus. Experimental results with the Circus prototype show that it can improve server throughput by a factor of two or more in workloads with strong file access locality.

REFERENCES

• 1: Swarup Acharya , Michael Franklin , Stanley Zdonik, Balancing push and pull for data broadcast, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.183-194, May 11-15, 1997, Tucson, Arizona, United States
• 2: Bill Allcock , Joe Bester , John Bresnahan , Ann L. Chervenak , Ian Foster , Carl Kesselman , Sam Meder , Veronika Nefedova , Darcy Quesnel , Steven Tuecke, Data management and transfer in high-performance computational grid environments, Parallel Computing, v.28 n.5, p.749-771, May 2002 [doi>10.1016/S0167-8191(02)00094-7]
• 3: Jussara M. Almeida , Jeffrey Krueger , Derek L. Eager , Mary K. Vernon, Analysis of educational media server workloads, Proceedings of the 11th international workshop on Network and operating systems support for digital audio and video, p.21-30, January 2001, Port Jefferson, New York, United States [doi>10.1145/378344.378348]
• 4: Stergios V. Anastasiadis , Kenneth C. Sevcik , Michael Stumm, Modular and efficient resource management in the exedra media server, Proceedings of the 3rd conference on USENIX Symposium on Internet Technologies and Systems, p.3-3, March 26-28, 2001, San Francisco, California
• 5: Stergios V. Anastasiadis , Rajiv G. Wickremesinghe , Jeffrey S. Chase, Circus: Opportunistic Block Reordering for Scalable Content Servers, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 6: Martin F. Arlitt , Carey L. Williamson, Web server workload characterization: the search for invariants, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.126-137, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 7: Mary G. Baker , John H. Hartman , Michael D. Kupfer , Ken W. Shirriff , John K. Ousterhout, Measurements of a distributed file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.198-212, October 13-16, 1991, Pacific Grove, California, United States
• 8: Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States
• 9: Angela Demke Brown , Todd C. Mowry , Orran Krieger, Compiler-based I/O prefetching for out-of-core applications, ACM Transactions on Computer Systems (TOCS), v.19 n.2, p.111-170, May 2001 [doi>10.1145/377769.377774]
• 10: John Byers , Jeffrey Considine , Michael Mitzenmacher , Stanislav Rost, Informed content delivery across adaptive overlay networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 11: John W. Byers , Michael Luby , Michael Mitzenmacher , Ashutosh Rege, A digital fountain approach to reliable distribution of bulk data, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.56-67, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 12: Pei Cao , Edward W. Felten , Anna R. Karlin , Kai Li, A study of integrated prefetching and caching strategies, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.188-197, May 15-19, 1995, Ottawa, Ontario, Canada
• 13: Maureen Chesire , Alec Wolman , Geoffrey M. Voelker , Henry M. Levy, Measurement and analysis of a streaming-media workload, Proceedings of the 3rd conference on USENIX Symposium on Internet Technologies and Systems, p.1-1, March 26-28, 2001, San Francisco, California
• 14: D. D. Clark , D. L. Tennenhouse, Architectural considerations for a new generation of protocols, Proceedings of the ACM symposium on Communications architectures & protocols, p.200-208, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 15: K. G. Coffman , A. M. Odlyzko, Internet growth: is there a "Moore's law" for data traffic?, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 16: Cohen, B. 2003. Incentives build robustness in bittorrent. bitconjurer.org.
• 17: Diot, C. and Gagnon, F. 1999. Impact of out-of-sequence processing on the performance of data transmission. Comput. Netw. 31, 475--492.
• 18: Doyle, R. P., Chase, J. S., Gadde, S., and Vahdat, A. M. 2001. The trickle-down effect: Web caching and server request distribut ion. In Proceedings of the International Workshop on Web Caching and Content Delivery.
• 19: Derek Eager , Mary Vernon , John Zahorjan, Minimizing Bandwidth Requirements for On-Demand Data Delivery, IEEE Transactions on Knowledge and Data Engineering, v.13 n.5, p.742-757, September 2001 [doi>10.1109/69.956098]
• 20: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 21: Shudong Jin , Azer Bestavros, Scalability of multicast delivery for non-sequential streaming access, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 22: Michael Luby, LT Codes, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.271, November 16-19, 2002
• 23: Nimrod Megiddo , Dharmendra S. Modha, ARC: A Self-Tuning, Low Overhead Replacement Cache, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 24: Jitendra Padhye , Victor Firoiu , Donald F. Towsley , James F. Kurose, Modeling TCP Reno performance: a simple model and its empirical validation, IEEE/ACM Transactions on Networking (TON), v.8 n.2, p.133-145, April 2000 [doi>10.1109/90.842137]
• 25: Vivek S. Pai , Mohit Aron , Gaurov Banga , Michael Svendsen , Peter Druschel , Willy Zwaenepoel , Erich Nahum, Locality-aware request distribution in cluster-based network servers, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.205-216, October 02-07, 1998, San Jose, California, United States
• 26: KyoungSoo Park , Vivek S. Pai, Scale and performance in the CoBlitz large-file distribution service, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.3-3, May 08-10, 2006, San Jose, CA
• 27: R. H. Patterson , G. A. Gibson , E. Ginting , D. Stodolsky , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
• 28: J. Postel , J. K. Reynolds, File Transfer Protocol, RFC Editor, 1985
• 29: S. Raman , H. Balakrishnan , M. Srinivasan, An image transport protocol for the Internet, Proceedings of the 2000 International Conference on Network Protocols, p.209, November 14-17, 2000
• 30: Luigi Rizzo, Dummynet: a simple approach to the evaluation of network protocols, ACM SIGCOMM Computer Communication Review, v.27 n.1, p.31-41, Jan. 1997 [doi>10.1145/251007.251012]
• 31: Rost, S., Byers, J., and Bestavros, A. 2001. The cyclone server architecture: Streamlining delivery of popular content. In Proceedings of the International Workshop on Web Caching and Content Distribution. Boston, MA.
• 32: Stefan Saroiu , Krishna P. Gummadi , Richard J. Dunn , Steven D. Gribble , Henry M. Levy, An analysis of internet content delivery systems, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060319]
• 33: Saroiu, S., Gummadi, P. K., and Gribble, S. D. 2002. A measurement study of peer-to-peer file sharing systems. In Proceedings of the SPIE/ACM Multimedia Computing and Networking Conference.
• 34: David C. Steere, Exploiting the non-determinism and asynchrony of set iterators to reduce aggregate file I/O latency, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.252-263, October 05-08, 1997, Saint Malo, France
• 35: Kishar Shridharbhai Trivedi, Probability and Statistics with Reliability, Queuing and Computer Science Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1982
• 36: Jeffrey Scott Vitter , P. Krishnan, Optimal prefetching via data compression, Journal of the ACM (JACM), v.43 n.5, p.771-793, Sept. 1996 [doi>10.1145/234752.234753]
• 37: Werner Vogels, File system usage in Windows NT 4.0, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.93-109, December 12-15, 1999, Charleston, South Carolina, United States
• 38: Limin Wang , Vivek Pai , Larry Peterson, The effectiveness of request redirection on CDN robustness, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060321]
• 39: Yin Zhang , Lee Breslau , Vern Paxson , Scott Shenker, On the characteristics and origins of internet flow rates, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Measurements

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
Disk access, file transfer protocols, scheduling