Messages in this thread | | | Subject | Re: IP: optimize as a router not host | Date | Wed, 20 Mar 1996 05:42:56 -0500 | From | "Jon 'tex' Boone" <> |
| |
-----BEGIN PGP SIGNED MESSAGE-----
> > Rogier Wolff <r.e.wolff@et.tudelft.nl> writes: > > > > > > Suppose a sender sends packets 1,2,3,4 and 5. At the receiving > > > end you get 1,2,4,5. What you do is you ack that you got packet > > > 1 and two. When you get 4 and 5 you ack that you got 2 again > > > and again. When a sender gets these it is supposed to conclude > > > that packet 3 got lost and try re-sending that. > > > > There is a RFC which implements selective reject -- i.e., in the > > ack, you add some TCP options which tell the sender that you do > > have packets 4 and 5 (or rather, the sequence numbers for which 4 > > and 5 contained data). > > The selective ack RFC never went anywhere because you can use a > scheme known as fast retransmit instead to avoid pipeline stalls on > a loss of 1 frame/window or less. What happens is the sender sends 1 > 2 3 4 5 6 the receive gets 1 2 4 5 6. The acks from the receiver > thus go 1 2 2 2 2 .. seeing 3 acks for an old frame in a row the > sender now sends frame 3 again immediately, then will get an ack of > 7 and continue.
This is not entirely accurate. Alan is correct in saying that the fast retransmit algorithm is used to recover from a single lost frame per window size. However, quoting from RFC 1323 [Van Jacobsen, the author of the algorithm is a co-author of RFC 1323]:
There are three fundamental performance problems with the current TCP over LFN paths: ...
(1) Window Size Limit
...
(2) Recovery from Losses
Packet losses in an LFN can have a catastrophic effect on throughput. Until recently, properly-operating TCP implementations would cause the data pipeline to drain with every packet loss, and require a slow-start action to recover. Recently, the Fast Retransmit and Fast Recovery algorithms [Jacobson90c] have been introduced. Their combined effect is to recover from one packet loss per window, without draining the pipeline. However, more than one packet loss per window typically results in a retransmission timeout and the resulting pipeline drain and slow start.
Expanding the window size to match the capacity of an LFN results in a corresponding increase of the probability of more than one packet per window being dropped. This could have a devastating effect upon the throughput of TCP over an LFN. In addition, if a congestion control mechanism based upon some form of random dropping were introduced into gateways, randomly spaced packet drops would become common, possible increasing the probability of dropping more than one packet per window.
To generalize the Fast Retransmit/Fast Recovery mechanism to handle multiple packets dropped per window, selective acknowledgments are required. Unlike the normal cumulative acknowledgments of TCP, selective acknowledgments give the sender a complete picture of which segments are queued at the receiver and which have not yet arrived. Some evidence in favor of selective acknowledgments has been published [NBS85], and selective acknowledgments have been included in a number of experimental Internet protocols -- VMTP [Cheriton88], NETBLT [Clark87], and RDP [Velten84], and proposed for OSI TP4 [NBS85]. However, in the non-LFN regime, selective acknowledgments reduce the number of packets retransmitted but do not otherwise improve performance, making their complexity of questionable value. However, selective acknowledgments are expected to become much more important in the LFN regime.
RFC-1072 defined a new TCP "SACK" option to send a selective acknowledgment. However, there are important technical issues to be worked out concerning both the format and semantics of the SACK option. Therefore, SACK has been omitted from this package of extensions. It is hoped that SACK can "catch up" during the standardization process.
So, as you can see, selective acknowledgment has been disconnected from the other improvements of RFC 1323 and is now being worked on by the TCP for Large Windows working group of the IETF (tcplw) and there is a current draft for sack - draft-ietf-tcplw-sack-00.txt.
Also, please note the following from the draft-ietf-tcplw-sack-00.txt:
4. GENERATING SACK OPTIONS: DATA RECEIVER BEHAVIOR
If the data receiver has received a SACK-Permitted option on the SYN for this connection, the data receiver MAY elect to generate SACK options as described below. If the data receiver generates SACK options under any circumstance, it SHOULD generate them under all permitted circumstances. If the data receiver has not received a SACK-Permitted option for a given connection, it MUST NOT send SACK options on that connection.
If sent at all, SACK options SHOULD be included in all ACKs which do not ACK the highest sequence number in the data receiver's queue. In this situation the network has lost or mis-ordered data, such that the receiver holds non-contiguous data in its queue. RFC 1122, Section 4.2.2.21, discusses the reasons for the receiver to send ACKs in response to additional segments received in this state. The receiver SHOULD send an ACK for every valid segment that arrives containing new data, and each of these "duplicate" ACKs SHOULD bear a SACK option. If the data receiver chooses to send a SACK option, the following rules apply:
* The first SACK block (i.e., the one immediately following the kind and length fields in the option) MUST specify the contiguous block of data containing the segment which triggered this ACK, unless that segment advanced the Acknowledgment Number field in the header. This assures that the ACK with the SACK option reflects the most recent state change at the data receiver.
* The data receiver SHOULD include as many distinct SACK blocks as possible in the SACK option. Note that the maximum available option space may not be sufficient to report all blocks present in the receiver's queue.
* The SACK option SHOULD be filled out by repeating the most recently reported SACK blocks (based on first SACK blocks in previous SACK options) that are not subsets of a SACK block already included in the SACK option being constructed. This assures that in normal operation every SACK block is repeated several times. (At least three times for large-window TCP implementations [RFC1323]).
It is very important that the SACK option always reports the block containing the most recently received segment, because this provides the sender with the most up-to-date information about the state of the network and the data receiver's queue.
So, if the draft for SACK becomes a standard, then while you are not required to send a SACK, if you do use SACK, it should be used in all circumstances (including the loss of a single packet per window where now you just use the fast retransmit/fast recovery) where it is permitted. This seems to indicate that SACK is intended as a replacement for fast retransmit/fast recovery once standardized.
<tex@isc.upenn.edu>
-----BEGIN PGP SIGNATURE----- Version: 2.6.2
iQCVAwUBMU/hIK3OmEV1jeMFAQFLaQQApspgy2P+ZC2QzPGImCwQ6a0fLiN1cjpp x5pA8LhSUVmKU/imr1Mo/h8JwFA15o4nahX4ijgM89FDOwSls/zaXv0WrgrLOsHp ByUQMd1PNMiJwiE9QJy/ZzK2flHbV7Vxaf3tMvYbAipOvO3zKmQHQpN3J++Lqtsj gMWLX3ViIgY= =aeYV -----END PGP SIGNATURE-----
| |