Dismiss
InnovationQ/InnovationQ Plus content will be updated on Sunday, June 25, 10am ET, with new patent and non-patent literature collections. Click here to learn more.
Browse Prior Art Database

TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms (RFC2001)

IP.com Disclosure Number: IPCOM000002555D
Original Publication Date: 1997-Jan-01
Included in the Prior Art Database: 2000-Sep-13
Document File: 5 page(s) / 12K

Publishing Venue

Internet Society Requests For Comment (RFCs)

Related People

W. Stevens: AUTHOR

Abstract

Modern implementations of TCP contain four intertwined algorithms that have never been fully documented as Internet standards: slow start, congestion avoidance, fast retransmit, and fast recovery. [2] and [3] provide some details on these algorithms, [4] provides examples of the algorithms in action, and [5] provides the source code for the 4.4BSD implementation. RFC 1122 requires that a TCP must implement slow start and congestion avoidance (Section 4.2.2.15 of [1]), citing [2] as the reference, but fast retransmit and fast recovery were implemented after RFC 1122. The purpose of this document is to document these four algorithms for the Internet.

This text was extracted from a ASCII Text document.
This is the abbreviated version, containing approximately 25% of the total text.

Network Working Group W. Stevens

Request for Comments: 2001 NOAO

Category: Standards Track January 1997

TCP Slow Start, Congestion Avoidance,

Fast Retransmit, and Fast Recovery Algorithms

Status of this Memo

This document specifies an Internet standards track protocol for the

Internet community, and requests discussion and suggestions for

improvements. Please refer to the current edition of the "Internet

Official Protocol Standards" (STD 1) for the standardization state

and status of this protocol. Distribution of this memo is unlimited.

Abstract

Modern implementations of TCP contain four intertwined algorithms

that have never been fully documented as Internet standards: slow

start, congestion avoidance, fast retransmit, and fast recovery. [2]

and [3] provide some details on these algorithms, [4] provides

examples of the algorithms in action, and [5] provides the source

code for the 4.4BSD implementation. RFC 1122 requires that a TCP

must implement slow start and congestion avoidance (Section 4.2.2.15

of [1]), citing [2] as the reference, but fast retransmit and fast

recovery were implemented after RFC 1122. The purpose of this

document is to document these four algorithms for the Internet.

Acknowledgments

Much of this memo is taken from "TCP/IP Illustrated, Volume 1: The

Protocols" by W. Richard Stevens (Addison-Wesley, 1994) and "TCP/IP

Illustrated, Volume 2: The Implementation" by Gary R. Wright and W.

Richard Stevens (Addison-Wesley, 1995). This material is used with

the permission of Addison-Wesley. The four algorithms that are

described were developed by Van Jacobson.

1. Slow Start

Old TCPs would start a connection with the sender injecting multiple

segments into the network, up to the window size advertised by the

receiver. While this is OK when the two hosts are on the same LAN,

if there are routers and slower links between the sender and the

receiver, problems can arise. Some intermediate router must queue

the packets, and it's possible for that router to run out of space.

[2] shows how this naive approach can reduce the throughput of a TCP

connection drastically.

The algorithm to avoid this is called slow start. It operates by

observing that the rate at which new packets should be injected into

the network is the rate at which the acknowledgments are returned by

the other end.

Slow start adds another window to the sender's TCP: the congestion

window, called "cwnd". When a new connection is established with a

host on another network, the congestion window is initialized to one

segment (i.e., the segment size announced by the other end, or the

default, typically 536 or 512). Each time an ACK is received, the

congestion window is increased by one segment. The sender can

transmit up to the minimum of the conges...