karn@UCSD.EDU (Phil Karn) (03/03/88)
During conversations with Van Jacobsen here at the IETF meeting, I discovered an abiguity in the TCP spec (RFC-793 at least), to wit: What response (if any) should you make when you receive an out-of-order segment? RFC-793 says pretty clearly that you should return an empty ACK (indicating the sequence number you expect to receive next) if the packet is "unacceptable" (i.e., not in the window) but it doesn't say whether you should respond if the packet is in the window but not the next one expected. It says only that they should be kept for future processing. My TCP in fact makes no response to an out-of-order data segment. Others apparently respond with "do-nothing" ACKs. One of Van's performance tricks depends on that behavior. Any guidance on what is the Right Thing here? Thanks, Phil Karn
CERF@A.ISI.EDU (03/03/88)
My recollection of intent in RFC 793 was to have the TCP invite the proper next packet by responding with the "next packet" ACK and not with an ACK that references anything about the out of order packet. Perhaps others will either remember differently or have a better notion for how to behave under the circumstances described. Obviously, if TCP had "out of order" acking and selective retransmission, the response would be more complex. Vint
haverty@CCV.BBN.COM (03/03/88)
Phil - even if a TCP sends 'do-nothing' ACKs, nothing should depend on that behavior, since the ACK is unreliable - as a datagram, it might get lost in transit. Jack
karn@UCSD.EDU (Phil Karn) (03/04/88)
Nothing really "depends" on those do-nothing ACKs, in the sense that the protocol still operates correctly even if they are lost. I should probably let Van describe his own technique, but basically it involves interpreting a flurry of do-nothing ACKs as an indication that an early packet was lost. This triggers a retransmission before the timer would ordinarily expire and do it. This appears to be a big performance win over networks with large bandwidth*delay products (e.g., the Wideband net). Phil
DCP@QUABBIN.SCRC.SYMBOLICS.COM (David C. Plummer) (03/04/88)
[I wasn't on the design team.] I would strongly suggest that any next-packet ACKs generated by out of order segments wait until the network input queue is empty. For a multitude of reasons, the medium or the implementation may reverse some packets on you. (E.g., in past releases, the 3600 had LIFO transmit and receive queues, but since transmitting a packet is fast the transmit queue is effectively FIFO, and the receive queue is processed by a process/task. We now reverse the receive list.) I agree that encouraging the sender to retransmit a packet that should have arrived helps performance. I'm asking that people be careful in making the "should" determination.
rfox@AMES-NAS.ARPA (Richard Fox) (03/04/88)
>During conversations with Van Jacobsen here at the IETF meeting, I discovered >an abiguity in the TCP spec (RFC-793 at least), to wit: > >What response (if any) should you make when you receive an out-of-order >segment? RFC-793 says pretty clearly that you should return an empty ACK >(indicating the sequence number you expect to receive next) if the packet >is "unacceptable" (i.e., not in the window) but it doesn't say whether >you should respond if the packet is in the window but not the next one >expected. It says only that they should be kept for future processing. > >My TCP in fact makes no response to an out-of-order data segment. Others >apparently respond with "do-nothing" ACKs. One of Van's performance tricks >depends on that behavior. Any guidance on what is the Right Thing here? Getting a packet out-of-order can mean 1 of 2 things: 1. Preceding packets were dropped or corrupted and dropped. 2. The preceding packets are taking a different path than the one just received. In case 1, responding with a "do-nothing" ACK, would get the original sender to resend the packets before the timeout period elapses. In the case of a high delay large bandwidth link this is very advantageous to do. Our TCP will keep out-of-sequence packets on a queue and try to reassemble packets as they come in until we are caught up. This is a win situation if you delay your acks. If you immediately send a "do-nothing" ACK the sender will resend whats already been sent again. Since the packets need to be resent anyways, being that they will never make it, sending a "do-nothing" packet seems to be a winner. Also, we might assume that the packet was lost/dropped because of congestion ( since less than 1% of dropped packets is due to corruption due to link errors) and then this would set the congestion control algos. into action much quicker. Thus, congestion can be stopped much quicker! As an aside: So the question at this point is do we really want to keep the extra complexity of doing reassembling of packets in the TCP layer as well as the IP? In case 2, responding with a "do-nothing" ACK would, like in case 1, get the sender to resend the packets before the timeout period elapses. But since the packets are going to make it, just a little later than the out-of-seq packet, this would cause excess packets to be sent over the net. If we assume that the packets took different paths because of congestion on a particular link, this could potentially aggravate the congestion problem. Of course, Van;s algorithm will back off a bit to control the congestion. Ultimately this could mean that the receiver would tell the sender to re-xmit all of the packets again, the sender will assume that the network is congested and should use caution in resending the packets, the receiver receives all of the packets before the sender has time to re-xmit them all. The receiver then sends an ACK for all of the data and the sender will not have to re-xmit all of the packets and can go on transferring new data by opening back up its congestion window. I think in case 2 this will work if the assumption that the packets took different routes because of congestion, with the use of Van's algo. If a gateway puts packets on different links for the purpose of load balancing and congestion avoidance then the scenario above for case 2 would break down and the best solution would be to delay any acking for a period to see if the data is still yet to come. W might still want to wait for a small period, being that the period be less than the normal timeout periods currently used. I am not convinced that load balancing is a good idea, thus, would like to be able to assume that the only time a packet would travel on a different route than the previous packet is due to congestion. Then I think immediately sending a "do-nothing" ACK would be feasible even for out-of-seq packets that are in the window. >Perhaps others will either remember differently or have a better >notion for how to behave under the circumstances described. >Obviously, if TCP had "out of order" acking and selective >retransmission, the response would be more complex. > >Vint Up above I have stated that sending a "do-nothing" ACK immediately is probably the correct thing to do because to try and do anything else would require more complexity, complexity that TCP was not intended to handle. If we want the extra complexity, this would mean moving towards a transport level protocol like VTMP or something like a NETBLT type protocol, which is quite different than TCP. In the future I think we will need to move in the direction of a VTMP like protocol so would like to keep it out of TCP. Rich
slevy@UC.MSC.UMN.EDU ("Stuart Levy") (03/04/88)
Be aware that packets may have other reasons for arriving out of order than that they've followed multiple paths. One possible strategy for giving interactive traffic priority over bulk data on a crowded link is to preferentially forward small packets. I don't know of any specification that says this shouldn't be done. We've used an Ethernet bridge that actually does this, and caused a 4.2 TCP bug to be exercised (when a FIN arrived earlier than some trailing data, the FIN was ignored. The peer TCP had a bug that caused it to never retransmit a FIN, and so...).
markl@ALLSPICE.LCS.MIT.EDU (03/05/88)
Date: Fri, 4 Mar 88 09:59:41 CST From: "Stuart Levy" <slevy@uc.msc.umn.edu> > Be aware that packets may have other reasons for arriving out of order than > that they've followed multiple paths. I recall that at one point Wideband Network BSATS also had a tendency to re-order packets--by pushing to the end of the queue those packets which had missed their satellite reservations. markl Internet: markl@ptt.lcs.mit.edu Mark L. Lambert MIT Laboratory for Computer Science Distributed Systems Group ----------
CASNER@VENERA.ISI.EDU (Stephen Casner) (03/09/88)
Mark Lambert remarked that the Wideband Network would re-order packets that missed their satellite reservations. This is true, but such packets are not "pushed to the end of the queue" as Mark stated. A new reservation is sent for the packet as soon as the BSAT determines that the previous reservation was lost. In a sense the packet sits at the head of the queue, but with the high data rate and long delay time of the satellite channel, several later packets whose reservations were not lost may be transmitted while the unfortunate packet is waiting for the repeated reservation to be received. -- Steve Casner -------