Skip to main content

11. Links that reorder packets

Some links reorder packets, for example multi-hop radio links that use deflection routing to route around congested nodes. Packets routed different ways can then arrive at the destination in a different order than they were sent.

11.1. Reordering in non-TCP packet streams

Compressed non-TCP headers do not change the context, and neither do full headers that refresh it. There can be problems only when a full header that changes the context arrives out of order. There are two cases:

   - A packet with a full header with generation G arrives *after*
     a packet with a compressed header with generation G.  This case
     is covered by rule b) ii) in section 9.

   - A packet with a full header with generation G arrives *before*
     a packet with a compressed header with generation G-1 (modulo
     64).  The decompressor MAY then keep both versions of the
     context around for a while to be able to decompress subsequent
     compressed headers with generation G-1 (modulo 64).  The old
     context MUST be discarded after MIN_WRAP seconds.

11.2. Reordering in TCP packet streams

A compressor may avoid sending COMPRESSED_TCP headers and only send COMPRESSED_TCP_NODELTA headers when there is reordering over the link. Compressed headers will typically be 17 octets with that method, significantly larger than the usual 4-7 octets.

To achieve better compression rates the following method, adding only two octets to the compressed header for a total of 6-9 octets, may be used. A packet sequence number, incremented by one for every packet in the TCP stream, is then associated with each compressed and full header. This allows the decompressor to place the packets in the correct sequence and apply their deltas to the context in the correct order. A simple sliding window scheme is used to place the packets in the correct order.

Two octets are needed for the packet sequence numbers. One octet gives only 256 sequence numbers. In a sliding window scheme the window should be no larger than half of the sequence number space, so packets can not arrive more than 127 positions out-of-sequence. This is equivalent to a delay of 260 ms on 2 Mbit/s links with 512 octet segments. Delays of that order are not uncommon over wide-area Internet connections. However, two octets giving 2^16 = 65536 values should be sufficient.

Full TCP/IP headers will only have space for one octet of sequence number when there is no tunneling. It is not feasible to increase the size of full headers since the packet size might be optimized for the MTU of the link. Therefore only the least significant octet of the packet sequence number can be placed in such full headers. We believe

that such full headers can be positioned correctly frequently enough with only the least significant octet of the packet sequence number available.

The packet sequence number zero MUST be skipped over. Avoiding zero takes care of a problem that can occur when the TCP window scale option is used to enlarge the TCP window. When exactly 2^16 octets of TCP data is lost, a compressed header will be decompressed incorrectly without being detected by the TCP checksum. TCP segment sizes are often a power of two. So by using a packet sequence number space that is not a power of two either the TCP sequence number or the packet sequence number will differ when 2^16 octets are lost. Whenever a compressor sees the window scale option on a SYN segment, it MUST use packet sequence numbers when subsequently compressing that packet stream.

In compressed TCP headers the two octet packet sequence number MUST be placed immediately after the TCP Checksum. See section 5.3 for placement of packet sequence numbers in full headers.

Last updated on