algorithm
Click on the red underlined text to get to the source
... Con: Gateway algorithms and protocols are still changing,
and they will continue to change as the Internet system
...
... topology of nearby networks -- and self-tuning algorithms are
unavailable and may be insufficient. In some cases,
...
... IP addresses to be featureless 32-bit numbers, avoiding
algorithms that required a knowledge of the IP address
format. Otherwise, any future change in the format or
...
... gateway operations: routing and
queueing algorithms. See Section 2 of [INTRO:1] for
the requirements ...
... route a datagram; this
algorithm is designed to put the primary routing burden on
the gateways ...
... and considering it in the host route algorithm will
provide the necessary mechanism for the future when
Type-of-Service ...
... [IP:11]. Experience to date has not produced a complete
algorithm which is totally satisfactory, though it has
identified several forbidden paths and promising techniques.
...
...
The following specific algorithm has been suggested:
...
... determine when all bytes of the datagram have been
reassembled. We recommend Clark's algorithm [IP:10] that
requires no additional data space for the bookkeeping.
...
... 793std7 was written, there has been extensive work on
TCP algorithms to achieve efficient data communication.
Later sections of the present document describe required and
recommended TCP ...
... Later sections of the present document describe required and
recommended TCP algorithms to determine when to send data
(Section 4.2.3.4), when to send an acknowledgment (Section
4.2.3.2), and when to update ...
... poor TCP performance. Algorithms to avoid SWS are
described below for both the sending side (Section
4.2.3.4) and the receiving ...
... Internet congestion.
The Nagle Algorithm described in Section 4.2.3.4
provides a simple and effective solution to this
problem. It does have the effect of clumping
...
... Note that the Nagle algorithm and the send SWS
avoidance algorithm play complementary roles in
improving performance ...
... roles in
improving performance. The Nagle algorithm discourages
sending tiny segments when the data to be sent
...
... segments when the data to be sent
increases in small increments, while the SWS avoidance
algorithm discourages small segments resulting from the
right window edge ...
... TCP retransmission stability has produced a transmission
algorithm combining "slow start" with "congestion
avoidance". A TCP ...
... recommended, possibly with some maximum interval not
specified here. This procedure is similar to that of
the retransmission algorithm, and it may be possible to
combine the two procedures in the implementation.
...
... segments might be to
support an experimental algorithm known as "fast
retransmit". With this algorithm, the sender ...
... experimental algorithm known as "fast
retransmit". With this algorithm, the sender uses the
"redundant" ACK ...
... segment reordering in the Internet. There is
not yet enough experience with the fast retransmit
algorithm to determine how useful it is.
...
... A host TCP MUST implement Karn's algorithm and Jacobson's
algorithm for computing the retransmission timeout ...
... TCP MUST implement Karn's algorithm and Jacobson's
algorithm for computing the retransmission timeout ("RTO").
...
...
Jacobson's algorithm for computing the smoothed round-
trip ("RTT") time incorporates a simple measure of the
...
... RTTs is difficult when there are retransmissions.
Second, the algorithm to compute the smoothed round-
trip time is inadequate [TCP:7], because it incorrectly
...
... RTT values would be small
and constant. These problems were solved by Karn's and
Jacobson's algorithm, respectively.
...
... performance increase resulting from the use of
these improvements varies from noticeable to dramatic.
Jacobson's algorithm for incorporating the measured RTT
variance is especially important on a low-speed link ...
... link
utilization on a 9.6kb line went from 10% to 90% as a
result of implementing Jacobson's variance algorithm in
TCP.
...
... initialization values
are reasonable, and that in any case the Karn and
Jacobson algorithms make TCP behavior reasonably
insensitive to the initial parameter choices.
...
...
The receiver's SWS avoidance algorithm determines when
the right window edge may be advanced; this is
...
... edge may be advanced; this is
customarily known as "updating the window". This
algorithm combines with the delayed ACK algorithm (see
...
... algorithm combines with the delayed ACK algorithm (see
Section 4.2.3.2) to determine when an ACK segment ...
... USER.
Note that the general effect of this algorithm is to
advance RCV.WND in increments of Eff.snd.MSS (for
...
... coalesce short segments. However, there MUST be a way for
an application to disable the Nagle algorithm on an
individual connection. In all cases, sending data is also
...
... connection. In all cases, sending data is also
subject to the limitation imposed by the Slow Start
algorithm (Section 4.2.2.15).
...
...
The Nagle algorithm is generally as follows:
...
... Some applications (e.g., real-time display window
updates) require that the Nagle algorithm be turned
off, so small data segments can be streamed out at the
...
...
The sender's SWS avoidance algorithm is more difficult
than the receivers's, because the sender ...
... deadlock, it is necessary to have a timeout to force
transmission of data, overriding the SWS avoidance
algorithm. In practice, this timeout should seldom
occur.
...
...
(the bracketed condition is imposed by the Nagle
algorithm);
(3) or if at least a fraction Fs of the maximum window
...
... 4.2.2.17).
Finally, note that the SWS avoidance algorithm just
specified is to be used instead of the sender-side
...
... TCP:1] gives the
implementor much freedom in designing the algorithms
that control the message flow over the connection ...
... | | | | | | |
Retransmissions | | | | | | |
Jacobson Slow Start algorithm |4.2.2.15|x| | | | |
Jacobson Congestion-Avoidance algorithm ...
... Slow Start algorithm |4.2.2.15|x| | | | |
Jacobson Congestion-Avoidance algorithm |4.2.2.15|x| | | | |
Retransmit with same IP ident |4.2.2.15| | |x| | |
...
... Retransmit with same IP ident |4.2.2.15| | |x| | |
Karn's algorithm |4.2.3.1 |x| | | | |
Jacobson's RTO estimation alg. |4.2.3.1 |x| | | | |
...
... ACK'd |4.2.3.2 |x| | | | |
Receiver SWS-Avoidance Algorithm |4.2.3.3 |x| | | | |
| | | | | | |
Sending data | | | | | | |
...
... TTL |4.2.2.19|x| | | | |
Sender SWS-Avoidance Algorithm |4.2.3.4 |x| | | | |
Nagle algorithm |4.2.3.4 | |x| | | |
...
... Sender SWS-Avoidance Algorithm |4.2.3.4 |x| | | | |
Nagle algorithm |4.2.3.4 | |x| | | |
Application can disable Nagle algorithm |4.2.3.4 |x| | | | |
...
... Nagle algorithm |4.2.3.4 | |x| | | |
Application can disable Nagle algorithm |4.2.3.4 |x| | | | |
| | | | | | |
Connection Failures: | | | | | | |
...
... "IP Datagram Reassembly Algorithms," D. Clark, RFC-815, July 1982. This and the following paper should be read by every implementor. ...