Emulating low-priority transport at the application layer: a background transfer service

ABSTRACT

Low priority data transfer across the wide area is useful in several contexts, for example for the dissemination of large files such as OS updates, content distribution or prefetching. Although the design of such a service is reasonably easy when the underlying network supports service differentiation, it becomes more challenging without such network support. We describe an application level approach to designing a low priority service -- one that is 'lower than best-effort' in the context of the current Internet. We require neither network support nor changes to TCP. Instead, we use a receive window control to limit the transfer rate of the application, and the optimal rate is determined by detecting a change-point. We motivate this joint control-estimation problem by considering a fluid-based optimisation framework, and describe practical solutions, based on stochastic approximation and binary search techniques. Simulation results demonstrate the effectiveness of the approach.

REFERENCES

• 1: A. Venkataramani, P. Yalagandula, R. Kokku, S. Sharif, and M. Dahlin. The potential costs and benefits of long term prefetching for content distribution. Computer Communication Journal, 25(4):367--375, 2002.
• 2: 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
• 3: Arun Venkataramani , Ravi Kokku , Mike Dahlin, TCP Nice: a mechanism for background transfers, 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.1060320]
• 4: A. Kuzmanovic and E. Knightly. TCP-LP: A distributed algorithm for low priority data transfer. In Proc. IEEE INFOCOM, 2003.
• 5: B. Huffaker, M. Fomenkov, D. Moore, and K. Claffy. Macroscopic analyses of the infrastructure: Measurement and visualization of Internet connectivity and performance. In A Workshop on passive and active measurements, April, 2001.
• 6: V. Ribeiro, M. Coates, R. Riedi, S. Sarvotham, and R. G. Baraniuk. Multifractal cross-traffic estimation. In Proc. ITC Specialist Seminar on IP Traffic Measurement, Modeling and Management, September 2000.
• 7: B. Melander, M. Bjorkman, and P. Gunningberg. A new end-to-end probing and analysis method for estimating bandwidth bottlenecks. In Proc. IEEE GLOBECOM, November 2000.
• 8: Manish Jain , Constantinos Dovrolis, End-to-end available bandwidth: measurement methodology, dynamics, and relation with TCP throughput, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 9: Neil T. Spring, Maureen Chesire, Mark Berryman, Vivek Sahasranaman, Thomas Anderson, and Brian N. Bershad. Receiver based management of low bandwidth access links. In Proc. IEEE INFOCOM, volume 1, pages 245--254, 2000.
• 10: Puneet Mehra, Avideh Zakhor, and Christophe De Vleeschouwer. Receiver-driven bandwidth sharing for TCP. In Proc. IEEE INFOCOM, 2003.
• 11: M. Crovella and P. Barford. The network effects of prefetching. In Proc. IEEE INFOCOM, 1998.
• 12: Jon Crowcroft , Philippe Oechslin, Differentiated end-to-end Internet services using a weighted proportional fair sharing TCP, ACM SIGCOMM Computer Communication Review, v.28 n.3, p.53-69, July 1998 [doi>10.1145/293927.293930]
• 13: Y. Dong, R. Rohit, and Z. Zhang. A practical technique to support controlled quality assurance in video streaming across the Internet. In Proc. Packet Video Workshop, 2002.
• 14: Jeffrey Semke , Jamshid Mahdavi , Matthew Mathis, Automatic TCP buffer tuning, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.315-323, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 15: Manish Jain, Ravi Prasad, and Constantinos Dovrolis. The TCP bandwidth-delay product revisited: network buffering, cross traffic, and socket buffer auto-sizing. Technical Report GIT-CERCS-03-02, College of Computing, Georgia Tech, 2003.
• 16: Harold J. Kushner and George Yin. Stochastic Approximation Algorithms and Applications. Springer Verlag, 1997.
• 17: Laurent Massoulie and James Roberts. Bandwidth sharing: Objectives and algorithms. In Proc. IEEE INFOCOM, volume 3, pages 1395--1403, 1999.
• 18: T.R. Rockafellar. Convex Analysis. Princeton University Press, 1970.
• 19: S. Kunniyur and R. Srikant. End-to-end congestion control schemes: Utility functions, random losses and ECN marks. In INFOCOM 2000, 2000.
• 20: R. J. Gibbens and F. P. Kelly. Resource pricing and the evolution of congestion control. Automatica, 35:1969--1985, 1999. http://www.statslab.cam.ac.uk/.frank/PAPERS/evol.html.
• 21: F. P. Kelly, A. K. Maulloo, and D. K. H Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49:237--252, 1998.
• 22: F. P. Kelly. Mathematical modelling of the Internet. In Proceedings of the Fourth International Congress on Industrial and Applied Mathematics, 2000.
• 23: S. McCanne and S. Floyd. ns-LBNL network simulator. http://www-nrg.ee.lbl.gov/ns/.
• 24: R. Karp , E. Koutsoupias , C. Papadimitriou , S. Shenker, Optimization problems in congestion control, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.66, November 12-14, 2000
• 25: H. Robbins and S Munro. A stochastic approximation method. Annals of Mathematical Statistics, 22:400--407, 1951.
• 26: Jean-Claude Fort , Gilles Pagès, Asymptotic Behavior of a Markovian Stochastic Algorithm with Constant Step, SIAM Journal on Control and Optimization, v.37 n.5, p.1456-1482, Sept. 1999 [doi>10.1137/S0363012997328610]
• 27: Jeonghoon Mo , Jean Walrand, Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.556-567, Oct. 2000 [doi>10.1109/90.879343]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Performance

Keywords:
application reaction, background transfer, binary search, low priority, stochastic approximation