TCP Nice: a mechanism for background transfers

ABSTRACT

Many distributed applications can make use of large background transfers - transfers of data that humans are not waiting for -- to improve availability, reliability, latency or consistency. However, given the rapid fluctuations of available network bandwidth and changing resource costs due to technology trends, hand tuning the aggressiveness of background transfers risks (1) complicating applications, (2) being too aggressive and interfering with other applications, and (3) being too timid and not gaining the benefits of background transfers. Our goal is for the operating system to manage network resources in order to provide a simple abstraction of near zero-cost background transfers. Our system, TCP Nice, can provably bound the interference inflicted by background flows on foreground flows in a restricted network model. And our microbenchmarks and case study applications suggest that in practice it interferes little with foreground flows, reaps a large fraction of spare network bandwidth, and simplifies application construction and deployment. For example, in our prefetching case study application, aggressive prefetching improves demand performance by a factor of three when Nice manages resources; but the same prefetching hurts demand performance by a factor of six under standard network congestion control.

REFERENCES

• 1: Anurag Acharya and Joel Saltz. A study of internet round-trip delay. Technical Report CS-TR-3736, University of Maryland, 1996.
• 2: Akamai, Inc. http://www.akamai.com.
• 3: D. Andersen, D. Bansal, D. Curtis, S. Seshan, and H. Balakrishnan. System support for bandwidth management and content adaptation in internet applications. In OSDI, pages 213--226, 2000.
• 4: D. Bansal and H. Balakrishnan. Binomial Congestion Control Algorithms. In Infocom, 2001.
• 5: S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss. An architecture for differentiated services, 1998.
• 6: T. Bonald. Comparision of TCP Reno and TCP Vegas via fluid approximation. INRIA Research Report 3563, Nov 1998.
• 7: Lawrence S. Brakmo and Larry L. Peterson. TCP vegas: End to end congestion avoidance on a global internet. IEEE Journal on Selected Areas in Communications, 13(8):1465--1480,1995.
• 8: L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web caching and zipf-like distributions: Evidence and implications. In Infocom, 1999.
• 9: B. Chandra. Web workloads influencing disconnected service access. Master's thesis, University of Texas at Austin, May 2001.
• 10: Bharat Chandra , Mike Dahlin , Lei Gao , Amjad-Ali Khoja , Amol Nayate , Asim Razzaq , Anil Sewani, Resource management for scalable disconnected access to Web services, Proceedings of the 10th international conference on World Wide Web, p.245-256, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372059]
• 11: B. Chandra, M. Dahlin, L. Gao, and A. Nayate. End-to-end WAN Service Availability. In USITS, 2001.
• 12: D.-M. Chiu , R. Jain, Analysis of the increase and decrease algorithms for congestion avoidance in computer networks, Computer Networks and ISDN Systems, v.17 n.1, p.1-14, June 10, 1989 [doi>10.1016/0169-7552(89)90019-6]
• 13: Junghoo Cho , Hector Garcia-Molina, Synchronizing a database to improve freshness, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.117-128, May 15-18, 2000, Dallas, Texas, United States
• 14: J. Cleary and I. Witten. Data compression using adaptive coding and partial string matching. IEEE Transactions on Communications, 1984.
• 15: M. Crovella and P. Barford. The network effects of prefetching. In Infocom, 1998.
• 16: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 17: M. Dahlin. http://www.cs.utexas.edu/users/dahlin/techTrends/data/diskPrices/data, Jan 2002.
• 18: D. Duchamp. Prefetching Hyperlinks. In USITS, 1999.
• 19: S. Dykes and K. A. Robbins. A viability analysis of cooperative proxy caching. In Infocom, 2001.
• 20: Tivoli Data Exchange. http://www.tivoli.com/products/documents/datasheets/data_exchange_ds.pdf.
• 21: R. Fielding, J. Gettys, J. Mogul, H. Frystyk, L. Masinter, P. Leach, and T. Berners-Lee. Hypertext transfer protocol -- http/1.1, June 1999.
• 22: S. Floyd, M. Handley, J. Padhye, and J. Widmer. Equation-based congestion control for unicast applications: the extended version. Technical Report TR-00-003, ICSI, March 2000.
• 23: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 24: Pawan Goyal , Xingang Guo , Harrick M. Vin, A hierarchial CPU scheduler for multimedia operating systems, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.107-121, October 29-November 01, 1996, Seattle, Washington, United States
• 25: Rules of Thumb in Data Engineering, Proceedings of the 16th International Conference on Data Engineering, p.3, February 28-March 03, 2000
• 26: J. Griffioen and R. Appleton. Automatic Prefetching in a WAN. In IEEE Workshop on Advances in Parallel and Distributed Systems, October 1993.
• 27: J. S. Gwertzman , M. Seltzer, The case for geographical push-caching, Proceedings of the Fifth Workshop on Hot Topics in Operating Systems (HotOS-V), p.51, May 04-05, 1995
• 28: 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]
• 29: Norman C. Hutchinson , Stephen Manley , Mike Federwisch , Guy Harris , Dave Hitz , Steven Kleiman , Sean O'Malley, Logical vs. physical file system backup, Proceedings of the third symposium on Operating systems design and implementation, p.239-249, February 1999, New Orleans, Louisiana, United States
• 30: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 31: R. Kokku, P. Yalagandula, A. Venkataramani, and M. Dahlin. A non-interfering deployable web prefetching system. Technical Report TR-02-51, Computer Sciences, UT Austin, May 2002.
• 32: T. M. Kroeger, D. E. Long, and J. C. Mogul. Exploring the bounds of web latency reduction from caching and prefetching. In USITS, 1997.
• 33: C. Lumb, J. Schindler, G. Ganger, D. Nagle, and E. Riedel. Towards higher disk head utilization: Extracting free bandwidth from busy disk drives. In OSDI, 2000.
• 34: C. Maltzahn, K. Richardson, D. Grunwald, and J. Martin. On bandwidth smoothing. In 4th International Web Caching Workshop, 1999.
• 35: R. Morris, TCP behavior with many flows, Proceedings of the 1997 International Conference on Network Protocols (ICNP '97), p.205, October 28-31, 1997
• 36: The network simulator -- ns-2. http://www.isi.edu/nsnam/ns.
• 37: A. Odlyzko. Internet growth: Myth and reality, use and abuse. Journal of Computer Resource Management, pages 23--27, 2001.
• 38: V. N. Padmanabhan and J. C. Mogul. Using predictive prefetching to improve World-Wide Web latency. In SIGCOMM, 1996.
• 39: 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
• 40: Vern Paxson, End-to-end routing behavior in the Internet, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.25-38, August 28-30, 1996, Palo Alto, California, United States
• 41: G. Popek, R. Guy, T. Page, and J. Heidemann. Replication in the Ficus Distributed File System. In Workshop on the Management of Replicated Data, pages 5--10, November 1990.
• 42: R. Rejaie, M. Handley, and D. Estrin. RAP: An end-to-end rate-based congestion control mechanism for realtime streams in the internet. In Infocom, 1999.
• 43: Antony Rowstron , Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 44: Dheeraj Sanghi, Ashok K. Agrawala, Olafur Gudmundsson, and Bijendra N. Jain. Experimental assessment of end-to-end behavior on internet. In Infocom (2), pages 867--874, 1993.
• 45: Prashant J. Shenoy , Harrick M. Vin, Cello: a disk scheduling framework for next generation operating systems, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.44-55, June 22-26, 1998, Madison, Wisconsin, United States
• 46: Neil T. Spring, Maureen Chesire, Mark Berryman, Vivek Sahasranaman, Thomas Anderson, and Brian N. Bershad. Receiver based management of low bandwidth access links. In Infocom, 2000.
• 47: D. B. Terry , M. M. Theimer , Karin Petersen , A. J. Demers , M. J. Spreitzer , C. H. Hauser, Managing update conflicts in Bayou, a weakly connected replicated storage system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.172-182, December 03-06, 1995, Copper Mountain, Colorado, United States
• 48: Arun Venkataramani , Phoebe Weidmann , Mike Dahlin, Bandwidth constrained placement in a WAN, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.134-143, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384002]
• 49: A. Venkataramani, R. Kokku, and M. Dahlin. System support for background replication. Technical Report TR-02-30, Computer Sciences, UT Austin, May 2002.
• 50: A. Venkataramani, P. Yalagandula, R. Kokku, S. Sharif, and M. Dahlin. Potential costs and benefits of long-term prefetching for content distribution. Computer Communications Journal, 25(4):367--375, 2002.
• 51: D. Wessels. Squid Internet object cache. http://squid.nlanr.net/Squid, Jan 1998.
• 52: Y. R. Yang , S. S. Lam, General AIMD congestion control, Proceedings of the 2000 International Conference on Network Protocols, p.187, November 14-17, 2000
• 53: Haifeng Yu , Amin Vahdat, The costs and limits of availability for replicated services, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 54: Y. Zhang, V. Paxson, and S. Shenkar. The Stationarity of Internet Path Properties: Routing, Loss, and Throughput. Technical report, ICSI Center for Internet Research, May 2000.