[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article

FAST TCP: motivation, architecture, algorithms, performance

Published: 01 December 2006 Publication History

Abstract

We describe FAST TCP, a new TCP congestion control algorithm for high-speed long-latency networks, from design to implementation.We highlight the approach taken by FAST TCP to address the four difficulties which the current TCP implementation has at large windows. We describe the architecture and summarize some of the algorithms implemented in our prototype. We characterize its equilibrium and stability properties. We evaluate it experimentally in terms of throughput, fairness, stability, and responsiveness.

References

[1]
{1} M. Allman, V. Paxson, and W. Stevens, "TCP Congestion Control," RFC 2581, Apr. 1999.]]
[2]
{2} D. Bertsekas, Nonlinear Programming. Belmont, MA: Athena, 1995.]]
[3]
{3} L. S. Brakmo and L. L. Peterson, "TCP Vegas: end-to-end congestion avoidance on a global internet," IEEE J. Sel. Areas Commun., vol. 13, no. 8, pp. 1465-1480, Oct. 1995.]]
[4]
{4} H. Bullot, R. L. Cottrell, and R. Hughes-Jones, "Evaluation of advanced TCP stacks on fast long-distance production networks," J. Grid Computing, vol. 1, no. 4, pp. 345-359, Aug. 2004.]]
[5]
{5} C. Casetti, M. Gerla, S. Mascolo, M. Sansadidi, and R. Wang, "TCP Westwood: end-to-end congestion control for wired/wireless networks," Wireless Netw. J., vol. 8, pp. 467-479, 2002.]]
[6]
{6} C. S. Chang and Z. Liu, "A bandwidth sharing theory for a large number of HTTP-like connections," IEEE/ACM Trans. Netw., vol. 12, no. 5, pp. 952-962, Oct. 2004.]]
[7]
{7} D. Chiu and R. Jain, "Analysis of the increase and decrease algorithms for congestion avoidance in computer networks," Comput. Netw., vol. 17, pp. 1-14, 1989.]]
[8]
{8} H. Choe and S. H. Low, "Stabilized Vegas," in Advances in Communication Control Networks, Lecture Notes in Control and Information Sciences, S. Tarbouriech, C. Abdallah, and J. Chiasson, Eds. New York: Springer Press, 2004.]]
[9]
{9} J.-Y. Choi, K. Koo, J. S. Lee, and S. H. Low, "Global stability of FAST TCP in single-link single-source network," in Proc. IEEE Conf. Decision and Control, Dec. 2005, pp. 1837-1841.]]
[10]
{10} T. Dunigan, Floyd's TCP Slow-Start and AIMDMods {Online}. Available: http://www.csm.ornl.gov/~dunigan/net100/floyd.html]]
[11]
{11} X. Fan, M. Arcak, and J. T. Wen, "Robustness of network flow control against disturbances and time-delay," Syst. Contr. Lett., vol. 53, no. 11, pp. 13-29, 2004.]]
[12]
{12} W. Feng and S. Vanichpun, "Enabling compatibility between TCP Reno and TCP Vegas," in IEEE Symp. Applications and the Internet (SAINT 2003), Jan. 2003, pp. 301-308.]]
[13]
{13} S. Floyd, M. Handley, J. Padhye, and J. Widmer, "Equation-based congestion control for unicast applications," presented at the ACM SIGCOMM 2000, Stockholm, Sweden.]]
[14]
{14} S. Floyd and T. Henderson, "The NewReno modification to TCP's fast recovery algorithm," RFC 2582, Apr. 1999.]]
[15]
{15} S. Floyd, High speed TCP for large congestion windows. Internet draft draft-floyd-tcp-highspeed-02.txt, work in progress, Feb. 2003 {Online}. Available: http://www.icir.org/floyd/hstcp.html]]
[16]
{16} C. P. Fu and S. C. Liew, "A remedy for performance degradation of TCP Vegas in asymmetric networks," IEEE Commun. Lett., vol. 7, no. 1, pp. 42-44, Jan. 2003.]]
[17]
{17} S. Hegde, D. Lapsley, J. Lindheim, B. Wydrowski, D. Wei, C. Jin, and S. H. Low, "FAST TCP in high-speed networks: an experimental study," presented at the GridNets 2004, San Jose, CA.]]
[18]
{18} J. Hoe, "Improving the startup behavior of a congestion control scheme for TCP," presented at the ACM SIGCOMM'96, Stanford {Online}. Available: http://www.acm.org/sigcomm/sigcomm96/program.html]]
[19]
{19} C. V. Hollot, V. Misra, D. Towsley, and W. B. Gong, "Analysis and design of controllers for AQM routers supporting TCP flows," IEEE Trans. Autom. Contr., vol. 47, no. 6, pp. 945-959, Jun. 2002.]]
[20]
{20} V. Jacobson, "Congestion avoidance and control," presented at the ACM SIGCOMM'88, Stanford, CA {Online}. Available: ftp://ftp.ee.lbl.gov/papers/congavoid.ps.Z]]
[21]
{21} V. Jacobson, R. Braden, and D. Borman, "TCP extensions for high performance," RFC 1323, May 1992.]]
[22]
{22} R. Jain, The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation and Modeling . New York: Wiley, 1991.]]
[23]
{23} R. Jain, "A delay-based approach for congestion avoidance in interconnected heterogeneous computer networks," ACM Comput. Commun. Rev., vol. 19, no. 5, pp. 56-71, Oct. 1989.]]
[24]
{24} C. Jin, D. X. Wei, and S. H. Low, "FAST TCP: Motivation, architecture, algorithms, performance," Caltech, Tech. Rep. CSTR: 2003.010, Dec. 2003 {Online}. Available: http://netlab.caltech.edu/FAST]]
[25]
{25} C. Jin, D. X. Wei, and S. H. Low, "TCP FAST: motivation, architecture, algorithms, performance," in Proc. IEEE INFOCOM, Mar. 2004, pp. 2490-2501 {Online}. Available: http://netlab.caltech.edu]]
[26]
{26} C. Jin, D. X. Wei, S. H. Low, J. Bunn, D. H. Choe, J. C. Doyle, H. Newman, S. Ravot, S. Singh, F. Paganini, G. Buhrmaster, R. L. A. Cottrell, O. Martin, and W. Feng, "FAST TCP: from theory to experiments," IEEE Network, vol. 19, no. 1, pp. 4-11, Jan.-Feb. 2005.]]
[27]
{27} S. Jin, L. Guo, I. Matta, and A. Bestavros, "A spectrum of TCP-friendly window-based congestion control algorithms," IEEE/ACM Trans. Netw., vol. 11, no. 3, pp. 341-355, Jun. 2003.]]
[28]
{28} D. Katabi, M. Handley, and C. Rohrs, "Congestion control for high-bandwidth delay product networks," presented at the ACM SIGCOMM 2002, Pittsburgh, PA {Online}. Available: http://www.ana.lcs.mit.edu/ dina/XCP/]]
[29]
{29} F. P. Kelly, "Mathematical modelling of the internet," in Mathematics Unlimited--2001 and Beyond, B. Engquist and W. Schmid, Eds. Berlin, Germany: Springer-Verlag, 2001, pp. 685-702.]]
[30]
{30} F. P. Kelly, "Fairness and stability of end-to-end congestion control," Eur. J. Control, vol. 9, pp. 159-176, 2003.]]
[31]
{31} F. P. Kelly, A. Maulloo, and D. Tan, "Rate control for communication networks: shadow prices, proportional fairness and stability," J. Oper. Res. Soc., vol. 49, no. 3, pp. 237-252, Mar. 1998.]]
[32]
{32} T. Kelly, "Scalable TCP: improving performance in highspeed wide area networks," Comput. Commun. Rev. vol. 32, no. 2, Apr. 2003 {On-line}. Available: http://www-lce.eng.cam.ac.uk/ctk21/scalable/]]
[33]
{33} S. Kunniyur and R. Srikant, "Designing AVQ parameters for a general topology network," presented at the Asian Control Conf. Singapore, Sep. 2002.]]
[34]
{34} S. Kunniyur and R. Srikant, "A time-scale decomposition approach to adaptive explicit congestion notification (ECN) marking," IEEE Trans. Autom. Contr., vol. 47, no. 6, pp. 882-894, Jun. 2002.]]
[35]
{35} S. Kunniyur and R. Srikant, "End-to-end congestion control: utility functions, random losses and ECN marks," IEEE/ACM Trans. Netw., vol. 11, no. 5, pp. 689-702, Oct. 2003.]]
[36]
{36} A. Kuzmanovic and E. Knightly, "TCP-LP: a distributed algorithm for low priority data transfer," in Proc. IEEE INFOCOM, 2003, pp. 1691-1701.]]
[37]
{37} T. V. Lakshman and U. Madhow, "The performance of TCP/IP for networks with high bandwidth-delay products and random loss," IEEE/ACM Trans. Netw., vol. 5, no. 3, pp. 336-350, Jun. 1997.]]
[38]
{38} Y. Li, Implementing high-speed TCP. {Online}. Available: http://www. hep.ucl.ac.uk/~ytl/tcpip/hstcp/index.html]]
[39]
{39} S. H. Low, F. Paganini, J. Wang, and J. C. Doyle, "Linear stability of TCP/RED and a scalable control," Comput. Netw. J. vol. 43, no. 5, pp. 633-647, 2003 {Online}. Available: http://netlab.caltech.edu]]
[40]
{40} S. H. Low and R. Srikant, "A mathematical framework for designing a low-loss, low-delay internet," Networks and Spatial Economics, Special Issue on Crossovers Between Transportation Planning and Telecommunications, vol. 4, pp. 75-101, Mar. 2004.]]
[41]
{41} S. H. Low, "A duality model of TCP and queue management algorithms," IEEE/ACM Trans. Netw. vol. 11, pp. 525-536, Aug. 2003.]]
[42]
{42} S. H. Low and D. E. Lapsley, "Optimization flow control, I: basic algorithm and convergence," IEEE/ACM Trans. Netw. vol. 7, no. 6, pp. 861-874, Dec. 1999 {Online}. Available: http://netlab.caltech.edu]]
[43]
{43} S. H. Low, F. Paganini, and J. C. Doyle, "Internet congestion control," IEEE Contr. Syst. Mag., vol. 22, no. 1, pp. 28-43, Feb. 2002.]]
[44]
{44} S. H. Low, L. Peterson, and L. Wang, "Understanding Vegas: a duality model," J. ACM, vol. 49, no. 2, pp. 207-235, Mar. 2002 {Online}. Available: http://netlab.caltech.edu]]
[45]
{45} J. Martin, A. Nilsson, and I. Rhee, "Delay-based congestion avoidance for TCP," IEEE/ACM Trans. Netw., vol. 11, no. 3, pp. 356-369, Jun. 2003.]]
[46]
{46} L. Massoulie and J. Roberts, "Bandwidth sharing: objectives and algorithms," IEEE/ACM Trans. Netw., vol. 10, no. 3, pp. 320-328, Jun. 2002.]]
[47]
{47} M. Mathis, J. Mahdavi, S. Floyd, and A. Romanow, "TCP selective acknowledgment options," RFC 2018, Oct. 1996.]]
[48]
{48} M. Mathis, J. Semke, J. Mahdavi, and T. Ott, "The macroscopic behavior of the TCP congestion avoidance algorithm," ACM Comput. Commun. Rev., vol. 27, no. 3, Jul. 1997 {Online}. Available: http:// www.psc.edu/networking/papers/model_ccr97.ps]]
[49]
{49} J. Mo, R. La, V. Anantharam, and J. Walrand, "Analysis and comparison of TCP Reno and Vegas," in Proc. IEEE INFOCOM'99, pp. 1556-1563.]]
[50]
{50} J. Mo and J. Walrand, "Fair end-to-end window-based congestion control," IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 556-567, Oct. 2000.]]
[51]
{51} F. Paganini, J. C. Doyle, and S. H. Low, "Scalable laws for stable network congestion control," in Proc. Conf. Decision and Control, Dec. 2001 {Online}. Available: http://www.ee.ucla.edu/~paganini]]
[52]
{52} F. Paganini, Z. Wang, J. C. Doyle, and S. H. Low, "Congestion control for high performance, stability and fairness in general networks," IEEE/ACM Trans. Netw., vol. 13, no. 1, pp. 43-56, Feb. 2005.]]
[53]
{53} F. Paganini, Z. Wang, S. H. Low, and J. C. Doyle, "A new TCP/AQM for stable operation in fast networks," in Proc. IEEE INFOCOM 2003, pp. 96-105 {Online}. Available: http://www.ee.ucla.edu/~paganini]]
[54]
{54} A. Pásztor and D. Veitch, "PC based precision timing without GPS," presented at the ACM SIGMETRICS 2002 Marina Del Rey, CA.]]
[55]
{55} L. Rizzo, Dummynet. {Online}. Available: http://info.iet.unipi.it/ ~luigi/ip_dummynet/]]
[56]
{56} R. Shorten, D. Leith, J. Foy, and R. Kilduff, "Analysis and design of congestion control in synchronised communication networks," in Proc. 12th Yale Workshop on Adaptive and Learning Systems, Yale, Univ., New Haven, CT, May 2003 {Online}. Available: http://www. hamilton.ie/doug_leith.htm]]
[57]
{57} R. Srikant, The Mathematics of Internet Congestion Control. Cambridge, MA: Birkhauser, 2004.]]
[58]
{58} W. Stevens, "TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms," RFC 2001, Jan. 1997.]]
[59]
{59} L. Tan, C. Yuan, and M. Zukerman, "FAST TCP: fairness and queuing issues," IEEE Commun. Lett., vol. 9, no. 8, pp. 762-764, Aug. 2005.]]
[60]
{60} A. Tang, J. Wang, S. Hegde, and S. H. Low, "Equilibrium and fairness of networks shared by TCP Reno and FAST," Telecommun. Syst., vol. 30, no. 4, pp. 417-439, Dec. 2005.]]
[61]
{61} A. Tang, J.Wang, S. H. Low, and M. Chiang, "Equilibrium of heterogeneous congestion control protocols," in Proc. IEEE INFOCOM 2005, pp. 1338-1349.]]
[62]
{62} D. Veitch, S. Babu, and A. Pásztor, "Robust remote synchronisation of a new clock for PCs," presented at the Internet Measurement Conf., Taormina, Italy, Oct. 2004.]]
[63]
{63} G. Vinnicombe, "On the stability of networks operating TCP-like congestion control," in Proc. IFAC World Congress on Automatic Control, Barcelona, Spain, 2002.]]
[64]
{64} G. Vinnicombe, "Robust congestion control for the Internet", Tech. Rep., Univ. Cambridge, 2002.]]
[65]
{65} J. Wang, A. Tang, and S. H. Low, "Local stability of FAST TCP," in Proc. IEEE Conf. Decision and Control, Dec. 2004, pp. 1023-1028.]]
[66]
{66} J. Wang, D. X. Wei, and S. H. Low, "Modeling and stability of FAST TCP," in Proc. IEEE INFOCOM 2005, pp. 938-948.]]
[67]
{67} J. Wang, D. X. Wei, and S. H. Low, "Modeling and stability of FAST TCP," in IMA Volumes in Mathematics and its Applications, Vol. 143, Wireless Communications, P. Agrawal, M. Andrews, P. J. Fleming, G. Yin, and L. Zhang, Eds. New York: Springer Science, 2006.]]
[68]
{68} R. Wang, M. Valla, M. Sanadidi, B. Ng, and M. Gerla, "Using adaptive rate estimation to provide enhanced and robust transport over heterogeneous networks," in Proc. IEEE ICNP 2002, pp. 206-215.]]
[69]
{69} Z. Wang and J. Crowcroft, "Eliminating periodic packet losses in the 4.3-Tahoe BSD TCP congestion control algorithm," ACM Comput. Commun. Rev., vol. 22, no. 2, pp. 9-16, Apr. 1992.]]
[70]
{70} D. X. Wei, "Congestion control algorithms for high speed long distance TCP connections" Masters thesis, California Inst. Technol., Pasadena, CA, Jun. 2004 {Online}. Available: http://netlab.caltech.edu/pub/projects/FAST/msthesis-dwei]]
[71]
{71} D. X. Wei, S. H. Low, and S. Hegde, "A burstiness control for TCP," presented at the Workshop on Protocols for Fast Long-Distance Networks (PFLDnet'2005) Lyon, France, Feb. 2005.]]
[72]
{72} E. Weigle and W. Feng, "A case for TCP Vegas in high-performance computational grids," in Proc. 9th Int. Symp. High Performance Distributed Computing (HPDC'01), Aug. 2001, pp. 158-167.]]
[73]
{73} J. T. Wen and M. Arcak, "A unifying passivity framework for network flow control," IEEE Trans. Autom. Contr., vol. 49, no. 2, pp. 162-174, Feb. 2004.]]
[74]
{74} B. Wydrowski, High-resolution one-way delay measurement using RFC1323, Preprint, Aug. 2004.]]
[75]
{75} L. Xu, K. Harfoush, and I. Rhee, "Binary increase congestion control (BIC) for fast long-distance networks," in Proc. IEEE INFOCOM 2004, pp. 2514-2524.]]
[76]
{76} H. Yaiche, R. R. Mazumdar, and C. Rosenberg, "A game theoretic framework for bandwidth allocation and pricing in broadband networks," IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 667-678, Oct. 2000.]]
[77]
{77} The Network Simulator--ns-2. {Online}. Available: http://www.isi. edu/nsnam/ns/]]
[78]
{78} FAST TCP Simulator Module for ns-2. CUBIN Lab {Online}. Available: http://www.cubinlab.ee.mu.oz.au/ns2fasttcp/]]
[79]
{79} Caltech ns-2 Simulation Results of FAST. NetLab {Online}. Available: http://netlab.caltech.edu/pub/projects/FAST/ns2-test]]

Cited By

View all
  • (2024)PudicaProceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation10.5555/3691825.3691832(113-129)Online publication date: 16-Apr-2024
  • (2024)Rethinking Explicit Congestion Notification: A Multilevel Congestion Feedback PerspectiveProceedings of the 34th edition of the Workshop on Network and Operating System Support for Digital Audio and Video10.1145/3651863.3651885(64-70)Online publication date: 15-Apr-2024
  • (2024)DiffPerf: Toward Performance Differentiation and Optimization With SDN ImplementationIEEE Transactions on Network and Service Management10.1109/TNSM.2023.329796621:1(1012-1031)Online publication date: 1-Feb-2024
  • Show More Cited By

Index Terms

  1. FAST TCP: motivation, architecture, algorithms, performance

        Recommendations

        Comments

        Please enable JavaScript to view thecomments powered by Disqus.

        Information & Contributors

        Information

        Published In

        cover image IEEE/ACM Transactions on Networking
        IEEE/ACM Transactions on Networking  Volume 14, Issue 6
        December 2006
        247 pages

        Publisher

        IEEE Press

        Publication History

        Published: 01 December 2006
        Published in TON Volume 14, Issue 6

        Author Tags

        1. FAST TCP
        2. implementation
        3. internet congestion control
        4. protocol design
        5. stability analysis

        Qualifiers

        • Article

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)8
        • Downloads (Last 6 weeks)2
        Reflects downloads up to 11 Jan 2025

        Other Metrics

        Citations

        Cited By

        View all
        • (2024)PudicaProceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation10.5555/3691825.3691832(113-129)Online publication date: 16-Apr-2024
        • (2024)Rethinking Explicit Congestion Notification: A Multilevel Congestion Feedback PerspectiveProceedings of the 34th edition of the Workshop on Network and Operating System Support for Digital Audio and Video10.1145/3651863.3651885(64-70)Online publication date: 15-Apr-2024
        • (2024)DiffPerf: Toward Performance Differentiation and Optimization With SDN ImplementationIEEE Transactions on Network and Service Management10.1109/TNSM.2023.329796621:1(1012-1031)Online publication date: 1-Feb-2024
        • (2024)A bandwidth delay product based modified Veno for high-speed networksJournal of Network and Computer Applications10.1016/j.jnca.2024.103983231:COnline publication date: 1-Nov-2024
        • (2024)DCCSComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2024.110457247:COnline publication date: 18-Jul-2024
        • (2023)Amphis: Rearchitecturing Congestion Control for Capturing Internet Application VarietyProceedings of the 7th Asia-Pacific Workshop on Networking10.1145/3600061.3600076(95-101)Online publication date: 29-Jun-2023
        • (2022)Starvation in end-to-end congestion controlProceedings of the ACM SIGCOMM 2022 Conference10.1145/3544216.3544223(177-192)Online publication date: 22-Aug-2022
        • (2022)Elasticity detectionProceedings of the ACM SIGCOMM 2022 Conference10.1145/3544216.3544221(158-176)Online publication date: 22-Aug-2022
        • (2022)The Value of CooperationACM SIGMETRICS Performance Evaluation Review10.1145/3543146.354314949:4(8-13)Online publication date: 6-Jun-2022
        • (2022)Revisiting Loss Recovery for High-Speed Transmission2022 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC51071.2022.9771838(1987-1992)Online publication date: 10-Apr-2022
        • Show More Cited By

        View Options

        Login options

        Full Access

        View options

        PDF

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        Media

        Figures

        Other

        Tables

        Share

        Share

        Share this Publication link

        Share on social media