As per Relevance of the word selective, we have this rfc below:
Network Working Group M.
Request for Comments: 2018 J.
Category: Standards Track
S.
A.
Sun
October 1996
TCP Selective Acknowledgment
Status of this
This document specifies an Internet standards track protocol for
Internet community, and requests discussion and suggestions
improvements. Please refer to the current edition of the "
Official Protocol Standards" (STD 1) for the standardization
and status of this protocol. Distribution of this memo is unlimited
TCP may experience poor performance when multiple packets are
from one window of data. With the limited information
from cumulative acknowledgments, a TCP sender can only learn about
single lost packet per round trip time. An aggressive sender
choose to retransmit packets early, but such retransmitted
may have already been successfully received
A Selective Acknowledgment (SACK) mechanism, combined with
selective repeat retransmission policy, can help to overcome
limitations. The receiving TCP sends back SACK packets to the
informing the sender of data that has been received. The sender
then retransmit only the missing data segments
This memo proposes an implementation of SACK and discusses
performance and related issues
Much of the text in this document is taken directly from RFC1072 "
Extensions for Long-Delay Paths" by Bob Braden and Van Jacobson.
authors would like to thank Kevin Fall (LBNL), Christian
(INRIA), Van Jacobson (LBNL), Greg Miller (MITRE), Greg
(Ipsilon), Lixia Zhang (XEROX PARC and UCLA), Dave Borman (BSDI),
Allison Mankin (ISI) and others for their review and
comments
Mathis, et. al. Standards Track [Page 1]
RFC 2018 TCP Selective Acknowledgement Options October 1996
1.
Multiple packet losses from a window of data can have a
effect on TCP throughput. TCP [Postel81] uses a
acknowledgment scheme in which received segments that are not at
left edge of the receive window are not acknowledged. This
the sender to either wait a roundtrip time to find out about
lost packet, or to unnecessarily retransmit segments which have
correctly received [Fall95]. With the cumulative
scheme, multiple dropped segments generally cause TCP to lose
ACK-based clock, reducing overall throughput
Selective Acknowledgment (SACK) is a strategy which corrects
behavior in the face of multiple dropped segments. With
acknowledgments, the data receiver can inform the sender about
segments that have arrived successfully, so the sender
retransmit only the segments that have actually been lost
Several transport protocols, including NETBLT [Clark87],
[Strayer92], RDP [Velten84], NADIR [Huitema81], and VMTP [Cheriton88]
have used selective acknowledgment. There is some empirical
in favor of selective acknowledgments -- simple experiments with
have shown that disabling the selective acknowledgment
greatly increases the number of retransmitted segments over a lossy
high-delay Internet path [Partridge87]. A recent simulation study
Kevin Fall and Sally Floyd [Fall95], demonstrates the strength of
with SACK over the non-SACK Tahoe and Reno TCP implementations
RFC1072 [VJ88] describes one possible implementation of SACK
for TCP. Unfortunately, it has never been deployed in the Internet
as there was disagreement about how SACK options should be used
conjunction with the TCP window shift option (initially
RFC1072 and revised in [Jacobson92]).
We propose slight modifications to the SACK options as proposed
RFC1072. Specifically, sending a selective acknowledgment for
most recently received data reduces the need for long SACK
[Keshav94, Mathis95]. In addition, the SACK option now carries
32 bit sequence numbers. These two modifications represent the
changes to the proposal in RFC1072. They make SACK easier
implement and address concerns about robustness
The selective acknowledgment extension uses two TCP options.
first is an enabling option, "SACK-permitted", which may be sent in
SYN segment to indicate that the SACK option can be used once
connection is established. The other is the SACK option itself
which may be sent over an established connection once permission
been given by SACK-permitted
Mathis, et. al. Standards Track [Page 2]
RFC 2018 TCP Selective Acknowledgement Options October 1996
The SACK option is to be included in a segment sent from a TCP
is receiving data to the TCP that is sending that data; we will
to these TCP's as the data receiver and the data sender
respectively. We will consider a particular simplex data flow;
data flowing in the reverse direction over the same connection can
treated independently
2. Sack-Permitted
This two-byte option may be sent in a SYN by a TCP that has
extended to receive (and presumably process) the SACK option once
connection has opened. It MUST NOT be sent on non-SYN segments
TCP Sack-Permitted Option
Kind: 4
+---------+---------+
| Kind=4 | Length=2|
+---------+---------+
3. Sack Option
The SACK option is to be used to convey extended
information from the receiver to the sender over an established
connection
TCP SACK Option
Kind: 5
Length:
+--------+--------+
| Kind=5 | Length |
+--------+--------+--------+--------+
| Left Edge of 1st Block |
+--------+--------+--------+--------+
| Right Edge of 1st Block |
+--------+--------+--------+--------+
| |
/ . . . /
| |
+--------+--------+--------+--------+
| Left Edge of nth Block |
+--------+--------+--------+--------+
| Right Edge of nth Block |
+--------+--------+--------+--------+
Mathis, et. al. Standards Track [Page 3]
RFC 2018 TCP Selective Acknowledgement Options October 1996
The SACK option is to be sent by a data receiver to inform the
sender of non-contiguous blocks of data that have been received
queued. The data receiver awaits the receipt of data (perhaps
means of retransmissions) to fill the gaps in sequence space
received blocks. When missing segments are received, the
receiver acknowledges the data normally by advancing the left
edge in the Acknowledgement Number Field of the TCP header. The
option does not change the meaning of the Acknowledgement
field
This option contains a list of some of the blocks of
sequence space occupied by data that has been received and
within the window
Each contiguous block of data queued at the data receiver is
in the SACK option by two 32-bit unsigned integers in network
order
* Left Edge of
This is the first sequence number of this block
* Right Edge of
This is the sequence number immediately following the
sequence number of this block
Each block represents received bytes of data that are contiguous
isolated; that is, the bytes just below the block, (Left Edge
Block - 1), and just above the block, (Right Edge of Block), have
been received
A SACK option that specifies n blocks will have a length of 8*n+2
bytes, so the 40 bytes available for TCP options can specify
maximum of 4 blocks. It is expected that SACK will often be used
conjunction with the Timestamp option used for RTTM [Jacobson92],
which takes an additional 10 bytes (plus two bytes of padding);
a maximum of 3 SACK blocks will be allowed in this case
The SACK option is advisory, in that, while it notifies the
sender that the data receiver has received the indicated segments
the data receiver is permitted to later discard data which have
reported in a SACK option. A discussion appears below in Section 8
of the consequences of advisory SACK, in particular that the
receiver may renege, or drop already SACKed data
Mathis, et. al. Standards Track [Page 4]
RFC 2018 TCP Selective Acknowledgement Options October 1996
4. Generating Sack Options: Data Receiver
If the data receiver has received a SACK-Permitted option on the
for this connection, the data receiver MAY elect to generate
options as described below. If the data receiver generates
options under any circumstance, it SHOULD generate them under
permitted circumstances. If the data receiver has not received
SACK-Permitted option for a given connection, it MUST NOT send
options on that connection
If sent at all, SACK options SHOULD be included in all ACKs which
not ACK the highest sequence number in the data receiver's queue.
this situation the network has lost or mis-ordered data, such
the receiver holds non-contiguous data in its queue. RFC 1122,
Section 4.2.2.21, discusses the reasons for the receiver to send
in response to additional segments received in this state.
receiver SHOULD send an ACK for every valid segment that
containing new data, and each of these "duplicate" ACKs SHOULD bear
SACK option
If the data receiver chooses to send a SACK option, the
rules apply
* The first SACK block (i.e., the one immediately following
kind and length fields in the option) MUST specify the
block of data containing the segment which triggered this ACK
unless that segment advanced the Acknowledgment Number field
the header. This assures that the ACK with the SACK
reflects the most recent change in the data receiver's
queue
* The data receiver SHOULD include as many distinct SACK blocks
possible in the SACK option. Note that the maximum
option space may not be sufficient to report all blocks present
the receiver's queue
* The SACK option SHOULD be filled out by repeating the
recently reported SACK blocks (based on first SACK blocks
previous SACK options) that are not subsets of a SACK
already included in the SACK option being constructed.
assures that in normal operation, any segment remaining part of
non-contiguous block of data held by the data receiver is
in at least three successive SACK options, even for large-
TCP implementations [RFC1323]). After the first SACK block,
following SACK blocks in the SACK option may be listed
arbitrary order
Mathis, et. al. Standards Track [Page 5]
RFC 2018 TCP Selective Acknowledgement Options October 1996
It is very important that the SACK option always reports the
containing the most recently received segment, because this
the sender with the most up-to-date information about the state
the network and the data receiver's queue
5. Interpreting the Sack Option and Retransmission Strategy:
Sender
When receiving an ACK containing a SACK option, the data
SHOULD record the selective acknowledgment for future reference.
data sender is assumed to have a retransmission queue that
the segments that have been transmitted but not yet acknowledged,
sequence-number order. If the data sender performs re-
before retransmission, the block boundaries in a SACK option that
receives may not fall on boundaries of segments in the
queue; however, this does not pose a serious difficulty for
sender
One possible implementation of the sender's behavior is as follows
Let us suppose that for each segment in the retransmission
there is a (new) flag bit "SACKed", to be used to indicate that
particular segment has been reported in a SACK option
When an acknowledgment segment arrives containing a SACK option,
data sender will turn on the SACKed bits for segments that have
selectively acknowledged. More specifically, for each block in
SACK option, the data sender will turn on the SACKed flags for
segments in the retransmission queue that are wholly contained
that block. This requires straightforward sequence
comparisons
After the SACKed bit is turned on (as the result of processing
received SACK option), the data sender will skip that segment
any later retransmission. Any segment that has the SACKed bit
off and is less than the highest SACKed segment is available
retransmission
After a retransmit timeout the data sender SHOULD turn off all of
SACKed bits, since the timeout might indicate that the data
has reneged. The data sender MUST retransmit the segment at the
edge of the window after a retransmit timeout, whether or not
SACKed bit is on for that segment. A segment will not be
and its buffer freed until the left window edge is advanced over it
Mathis, et. al. Standards Track [Page 6]
RFC 2018 TCP Selective Acknowledgement Options October 1996
5.1 Congestion Control
This document does not attempt to specify in detail the
control algorithms for implementations of TCP with SACK. However
the congestion control algorithms present in the de facto
TCP implementations MUST be preserved [Stevens94]. In particular,
preserve robustness in the presence of packets reordered by
network, recovery is not triggered by a single ACK reporting out-of
order packets at the receiver. Further, during recovery the
sender limits the number of segments sent in response to each ACK
Existing implementations limit the data sender to sending one
during Reno-style fast recovery, or to two segments during slow-
[Jacobson88]. Other aspects of congestion control, such as
the congestion window in response to congestion, must similarly
preserved
The use of time-outs as a fall-back mechanism for detecting
packets is unchanged by the SACK option. Because the data
is allowed to discard SACKed data, when a retransmit timeout
the data sender MUST ignore prior SACK information in
which data to retransmit
Future research into congestion control algorithms may take
of the additional information provided by SACK. One such area
future research concerns modifications to TCP for a wireless
satellite environment where packet loss is not necessarily
indication of congestion
6. Efficiency and Worst Case
If the return path carrying ACKs and SACK options were lossless,
block per SACK option packet would always be sufficient.
segment arriving while the data receiver holds discontinuous
would cause the data receiver to send an ACK with a SACK
containing the one altered block in the receiver's queue. The
sender is thus able to construct a precise replica of the receiver'
queue by taking the union of all the first SACK blocks
Mathis, et. al. Standards Track [Page 7]
RFC 2018 TCP Selective Acknowledgement Options October 1996
Since the return path is not lossless, the SACK option is defined
include more than one SACK block in a single packet. The
blocks in the SACK option packet increase the robustness of
delivery in the presence of lost ACKs. For a receiver that is
using the time stamp option [Jacobson92], the SACK option has room
include three SACK blocks. Thus each SACK block will generally
repeated at least three times, if necessary, once in each of
successive ACK packets. However, if all of the ACK packets
a particular SACK block are dropped, then the sender might
that the data in that SACK block has not been received,
unnecessarily retransmit those segments
The deployment of other TCP options may reduce the number
available SACK blocks to 2 or even to 1. This will reduce
redundancy of SACK delivery in the presence of lost ACKs. Even so
the exposure of TCP SACK in regard to the unnecessary
of packets is strictly less than the exposure of
implementations of TCP. The worst-case conditions necessary for
sender to needlessly retransmit data is discussed in more detail in
separate document [Floyd96].
Older TCP implementations which do not have the SACK option will
be unfairly disadvantaged when competing against SACK-capable TCPs
This issue is discussed in more detail in [Floyd96].
7. Sack Option
The following examples attempt to demonstrate the proper behavior
SACK generation by the data receiver
Assume the left window edge is 5000 and that the data
sends a burst of 8 segments, each containing 500 data bytes
Case 1: The first 4 segments are received but the last 4
dropped
The data receiver will return a normal TCP ACK
acknowledging sequence number 7000, with no SACK option
Mathis, et. al. Standards Track [Page 8]
RFC 2018 TCP Selective Acknowledgement Options October 1996
Case 2: The first segment is dropped but the remaining 7
received
Upon receiving each of the last seven packets, the
receiver will return a TCP ACK segment that
sequence number 5000 and contains a SACK option
one block of queued data
Triggering ACK Left Edge Right
5000 (lost
5500 5000 5500 6000
6000 5000 5500 6500
6500 5000 5500 7000
7000 5000 5500 7500
7500 5000 5500 8000
8000 5000 5500 8500
8500 5000 5500 9000
Case 3: The 2nd, 4th, 6th, and 8th (last) segments
dropped
The data receiver ACKs the first packet normally.
third, fifth, and seventh packets trigger SACK options
follows
Triggering ACK First Block 2nd Block 3rd
Segment Left Right Left Right Left
Edge Edge Edge Edge Edge
5000 5500
5500 (lost
6000 5500 6000 6500
6500 (lost
7000 5500 7000 7500 6000 6500
7500 (lost
8000 5500 8000 8500 7000 7500 6000 6500
8500 (lost
Mathis, et. al. Standards Track [Page 9]
RFC 2018 TCP Selective Acknowledgement Options October 1996
Suppose at this point, the 4th packet is received out of order
(This could either be because the data was badly misordered in
network, or because the 2nd packet was retransmitted and lost,
then the 4th packet was retransmitted). At this point the
receiver has only two SACK blocks to report. The data
replies with the following Selective Acknowledgment
Triggering ACK First Block 2nd Block 3rd
Segment Left Right Left Right Left
Edge Edge Edge Edge Edge
6500 5500 6000 7500 8000 8500
Suppose at this point, the 2nd segment is received. The
receiver then replies with the following Selective Acknowledgment
Triggering ACK First Block 2nd Block 3rd
Segment Left Right Left Right Left
Edge Edge Edge Edge Edge
5500 7500 8000 8500
8. Data Receiver
Note that the data receiver is permitted to discard data in its
that has not been acknowledged to the data sender, even if the
has already been reported in a SACK option. Such discarding
SACKed packets is discouraged, but may be used if the receiver
out of buffer space
The data receiver MAY elect not to keep data which it has reported
a SACK option. In this case, the receiver SACK generation
additionally qualified
* The first SACK block MUST reflect the newest segment. Even
the newest segment is going to be discarded and the receiver
already discarded adjacent segments, the first SACK block
report, at a minimum, the left and right edges of the
segment
* Except for the newest segment, all SACK blocks MUST NOT
any old data which is no longer actually held by the receiver
Since the data receiver may later discard data reported in a
option, the sender MUST NOT discard data before it is acknowledged
the Acknowledgment Number field in the TCP header
Mathis, et. al. Standards Track [Page 10]
RFC 2018 TCP Selective Acknowledgement Options October 1996
9. Security
This document neither strengthens nor weakens TCP's current
properties
10.
[Cheriton88] Cheriton, D., "VMTP: Versatile Message
Protocol", RFC 1045, Stanford University, February 1988.
[Clark87] Clark, D., Lambert, M., and L. Zhang, "NETBLT: A Bulk
Transfer Protocol", RFC 998, MIT, March 1987.
[Fall95] Fall, K. and Floyd, S., "Comparisons of Tahoe, Reno,
Sack TCP", ftp://ftp.ee.lbl.gov/papers/sacks.ps.Z, December 1995.
[Floyd96] Floyd, S., "Issues of TCP with SACK",
ftp://ftp.ee.lbl.gov/papers/issues_sa.ps.Z, January 1996.
[Huitema81] Huitema, C., and Valet, I., An Experiment on High
File Transfer using Satellite Links, 7th Data
Symposium, Mexico, October 1981.
[Jacobson88] Jacobson, V., "Congestion Avoidance and Control",
Proceedings of SIGCOMM '88, Stanford, CA., August 1988.
[Jacobson88}, Jacobson, V. and R. Braden, "TCP Extensions for Long
Delay Paths", RFC 1072, October 1988.
[Jacobson92] Jacobson, V., Braden, R., and D. Borman, "TCP
for High Performance", RFC 1323, May 1992.
[Keshav94] Keshav, presentation to the Internet End-to-End
Group, November 1994.
[Mathis95] Mathis, M., and Mahdavi, J., TCP Forward
Option, presentation to the Internet End-to-End Research Group,
1995.
[Partridge87] Partridge, C., "Private Communication", February 1987.
[Postel81] Postel, J., "Transmission Control Protocol -
Internet Program Protocol Specification", RFC 793, DARPA,
1981.
[Stevens94] Stevens, W., TCP/IP Illustrated, Volume 1: The Protocols
Addison-Wesley, 1994.
Mathis, et. al. Standards Track [Page 11]
RFC 2018 TCP Selective Acknowledgement Options October 1996
[Strayer92] Strayer, T., Dempsey, B., and Weaver, A., XTP --
xpress transfer protocol. Addison-Wesley Publishing Company, 1992.
[Velten84] Velten, D., Hinden, R., and J. Sax, "Reliable
Protocol", RFC 908, BBN, July 1984.
11. Authors'
Matt Mathis and Jamshid
Pittsburgh Supercomputing
4400 Fifth
Pittsburgh, PA 15213
mathis@psc.
mahdavi@psc.
Sally
Lawrence Berkeley National
One Cyclotron
Berkeley, CA 94720
floyd@ee.lbl.
Allyn
Sun Microsystems, Inc
2550 Garcia Ave., MPK17-202
Mountain View, CA 94043
allyn@eng.sun.
Mathis, et. al. Standards Track [Page 12]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
