Request for Comments: 1144 LBL
February 1990
Compressing TCP/IP Headers
for Low-Speed Serial Links
Status of this Memo
This RFCis a proposed elective protocol for the Internet community and
requests discussion and suggestions for improvement. It describes a
method for compressing the headers of TCP/IP datagrams to improve
performance over low speed serial links. The motivation, implementation
and performance of the method are described. C code for a sample
implementation is given for reference. Distribution of this memo is
unlimited.
NOTE: Both ASCII and Postscript versions of this document are available.
The ASCII version, obviously, lacks all the figures and all the
information encoded in typographic variation (italics, boldface,
etc.). Since this information was, in the author's opinion, an
essential part of the document, the ASCII version is at best
incomplete and at worst misleading. Anyone who plans to work
with this protocol is strongly encouraged obtain the Postscript
version of this RFC.
----------------------------
1. This work was supported in part by the U.S. Department of Energy
under Contract Number DE-AC03-76SF00098.
Contents
1 Introduction 1
2 The problem 1
3 The compression algorithm 4
3.1 The basic idea . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 The ugly details . . . . . . . . . . . . . . . . . . . . . . . 5
3.2.1 Overview. . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2.2 Compressed packet format. . . . . . . . . . . . . . . . . 7
3.2.3 Compressor processing . . . . . . . . . . . . . . . . . . 8
3.2.4 Decompressor processing . . . . . . . . . . . . . . . . . 12
4 Error handling 14
4.1 Error detection . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Error recovery . . . . . . . . . . . . . . . . . . . . . . . . 17
5 Configurable parameters and tuning 18
5.1 Compression configuration . . . . . . . . . . . . . . . . . . 18
5.2 Choosing a maximum transmission unit . . . . . . . . . . . . . 20
5.3 Interaction with data compression . . . . . . . . . . . . . . 21
6 Performance measurements 23
7 Acknowlegements 25
A Sample Implementation 27
A.1 Definitions and State Data . . . . . . . . . . . . . . . . . . 28
A.2 Compression . . . . . . . . . . . . . . . . . . . . . . . . . 31
i
A.3 Decompression . . . . . . . . . . . . . . . . . . . . . . . . 37
A.4 Initialization . . . . . . . . . . . . . . . . . . . . . . . . 41
A.5 Berkeley Unix dependencies . . . . . . . . . . . . . . . . . . 41
B Compatibility with past mistakes 43
B.1 Living without a framing `type' byte . . . . . . . . . . . . . 43
B.2 Backwards compatible SLIP servers . . . . . . . . . . . . . . 43
C More aggressive compression 45
D Security Considerations 46
E Author's address 46
ii
RFC1144 Compressing TCP/IP Headers February 1990
1 Introduction
As increasingly powerful computers find their way into people's homes,
there is growing interest in extending Internet connectivity to those
computers. Unfortunately, this extension exposes some complex problems
in link-level framing, address assignment, routing, authentication and
performance. As of this writing there is active work in all these
areas. This memo describes a method that has been used to improve
TCP/IP performance over low speed (300 to 19,200 bps) serial links.
The compression proposed here is similar in spirit to the Thinwire-II
protocol described in [5]. However, this protocol compresses more
effectively (the average compressed header is 3 bytes compared to 13 in
Thinwire-II) and is both efficient and simple to implement (the Unix
implementation is 250 lines of C and requires, on the average, 90us (170
instructions) for a 20MHz MC68020 to compress or decompress a packet).
This compression is specific to TCP/IP datagrams./2/ The author
investigated compressing UDP/IP datagrams but found that they were too
infrequent to be worth the bother and either there was insufficient
datagram-to-datagram coherence for good compression (e.g., name server
queries) or the higher level protocol headers overwhelmed the cost of
the UDP/IP header (e.g., Sun's RPC/NFS). Separately compressing the IP
and the TCP portions of the datagram was also investigated but rejected
since it increased the average compressed header size by 50% and doubled
the compression and decompression code size.
2 The problem
Internet services one might wish to access over a serial IP link from
home range from interactive `terminal' type connections (e.g., telnet,
rlogin, xterm) to bulk data transfer (e.g., ftp, smtp, nntp). Header
compression is motivated by the need for good interactive response.
I.e., the line efficiency of a protocol is the ratio of the data to
header+data in a datagram. If efficient bulk data transfer is the only
objective, it is always possible to make the datagram large enough to
approach an efficiency of 100%.
Human-factors studies[15] have found that interactive response is
perceived as `bad' when low-level feedback (character echo) takes longer
----------------------------
2. The tie to TCP is deeper than might be obvious. In addition to the
compression `knowing' the format of TCP and IP headers, certain features
of TCP have been used to simplify the compression protocol. In
particular, TCP's reliable delivery and the byte-stream conversation
model have been used to eliminate the need for any kind of error
correction dialog in the protocol (see sec. 4).
than 100 to 200 ms. Protocol headers interact with this threshold three
ways:
(1) If the line is too slow, it may be impossible to fit both the
headers and data into a 200 ms window: One typed character results
in a 41 byte TCP/IP packet being sent and a 41 byte echo being
received. The line speed must be at least 4000 bps to handle these
82 bytes in 200 ms.
(2) Even with a line fast enough to handle packetized typing echo (4800
bps or above), there may be an undesirable interaction between bulk
data and interactive traffic: For reasonable line efficiency the
bulk data packet size needs to be 10 to 20 times the header size.
I.e., the line maximum transmission unit or MTU should be 500 to
1000 bytes for 40 byte TCP/IP headers. Even with type-of-service
queuing to give priority to interactive traffic, a telnet packet has
to wait for any in-progress bulk data packet to finish. Assuming
data transfer in only one direction, that wait averages half the MTU
or 500 ms for a 1024 byte MTU at 9600 bps.
(3) Any communication medium has a maximum signalling rate, the Shannon
limit. Based on an AT&T study[2], the Shannon limit for a typical
dialup phone line is around 22,000 bps. Since a full duplex, 9600
bps modem already runs at 80% of the limit, modem manufacturers are
starting to offer asymmetric allocation schemes to increase
effective bandwidth: Since a line rarely has equivalent amounts of
data flowing both directions simultaneously, it is possible to give
one end of the line more than 11,000 bps by either time-division
multiplexing a half-duplex line (e.g., the Telebit Trailblazer) or
offering a low-speed `reverse channel' (e.g., the USR Courier
HST)./3/ In either case, the modem dynamically tries to guess which
end of the conversation needs high bandwidth by assuming one end of
the conversation is a human (i.e., demand is limited to <300 bps by
typing speed). The factor-of-forty bandwidth multiplication due to
protocol headers will fool this allocation heuristic and cause these
modems to `thrash'.
From the above, it's clear that one design goal of the compression
should be to limit the bandwidth demand of typing and ack traffic to at
most 300 bps. A typical maximum typing speed is around five characters
----------------------------
3. See the excellent discussion of two-wire dialup line capacity in
[1], chap. 11. In particular, there is widespread misunderstanding of
the capabilities of `echo-cancelling' modems (such as those conforming
to CCITT V.32): Echo-cancellation can offer each side of a two-wire
line the full line bandwidth but, since the far talker's signal adds to
the local `noise', not the full line capacity. The 22Kbps Shannon limit
is a hard-limit on data rate through a two-wire telephone connection.
per second/4/ which leaves a budget 30 - 5 = 25 characters for headers
or five bytes of header per character typed./5/ Five byte headers solve
problems (1) and (3) directly and, indirectly, problem (2): A packet
size of 100--200 bytes will easily amortize the cost of a five byte
header and offer a user 95--98% of the line bandwidth for data. These
short packets mean little interference between interactive and bulk data
traffic (see sec. 5.2).
Another design goal is that the compression protocol be based solely on
information guaranteed to be known to both ends of a single serial link.
Consider the topology shown in fig. 1 where communicating hosts A and B
are on separate local area nets (the heavy black lines) and the nets are
connected by two serial links (the open lines between gateways C--D and
E--F)./6/ One compression possibility would be to convert each TCP/IP
conversation into a semantically equivalent conversation in a protocol
with smaller headers, e.g., to an X.25 call. But, because of routing
transients or multipathing, it's entirely possible that some of the A--B
traffic will follow the A-C-D-B path and some will follow the A-E-F-B
path. Similarly, it's possible that A->B traffic will flow A-C-D-B and
B->A traffic will flow B-F-E-A. None of the gateways can count on seeing
all the packets in a particular TCP conversation and a compression
algorithm that works for such a topology cannot be tied to the TCP
connection syntax.
A physical link treated as two, independent, simplex links (one each
direction) imposes the minimum requirements on topology, routing and
pipelining. The ends of each simplex link only have to agree on the
most recent packet(s) sent on that link. Thus, although any compression
scheme involves shared state, this state is spatially and temporally
----------------------------
4. See [13]. Typing bursts or multiple character keystrokes such as
cursor keys can exceed this average rate by factors of two to four.
However the bandwidth demand stays approximately constant since the TCP
Nagle algorithm[8] aggregates traffic with a <200ms interarrival time
and the improved header-to-data ratio compensates for the increased
data.
5. A similar analysis leads to essentially the same header size limit
for bulk data transfer ack packets. Assuming that the MTU has been
selected for `unobtrusive' background file transfers (i.e., chosen so
the packet time is 200--400 ms --- see sec. 5), there can be at most 5
data packets per second in the `high bandwidth' direction. A reasonable
TCP implementation will ack at most every other data packet so at 5
bytes per ack the reverse channel bandwidth is 2.5 * 5 = 12.5 bytes/sec.
6. Note that although the TCP endpoints are A and B, in this example
compression/decompression must be done at the gateway serial links,
i.e., between C and D and between E and F. Since A and B are using IP,
they cannot know that their communication path includes a low speed
serial link. It is clearly a requirement that compression not break the
IP model, i.e., that compression function between intermediate systems
and not just between end systems.
local and adheres to Dave Clark's principle of fate sharing[4]: The two
ends can only disagree on the state if the link connecting them is
inoperable, in which case the disagreement doesn't matter.
3 The compression algorithm
3.1 The basic idea
Figure 2 shows a typical (and minimum length) TCP/IP datagram header./7/
The header size is 40 bytes: 20 bytes of IP and 20 of TCP.
Unfortunately, since the TCP and IP protocols were not designed by a
committee, all these header fields serve some useful purpose and it's
not possible to simply omit some in the name of efficiency.
However, TCP establishes connections and, typically, tens or hundreds of
packets are exchanged on each connection. How much of the per-packet
information is likely to stay constant over the life of a connection?
Half---the shaded fields in fig. 3. So, if the sender and receiver keep
track of active connections/8/ and the receiver keeps a copy of the
header from the last packet it saw from each connection, the sender gets
a factor-of-two compression by sending only a small (<= 8 bit)
connection identifier together with the 20 bytes that change and letting
the receiver fill in the 20 fixed bytes from the saved header.
One can scavenge a few more bytes by noting that any reasonable
link-level framing protocol will tell the receiver the length of a
received message so total length (bytes 2 and 3) is redundant. But then
the header checksum (bytes 10 and 11), which protects individual hops
from processing a corrupted IP header, is essentially the only part of
the IP header being sent. It seems rather silly to protect the
transmission of information that isn't being transmitted. So, the
receiver can check the header checksum when the header is actually sent
(i.e., in an uncompressed datagram) but, for compressed datagrams,
regenerate it locally at the same time the rest of the IP header is
being regenerated./9/
----------------------------
7. The TCP and IP protocols and protocol headers are described in [10]
and [11].
8. The 96-bit tuple <src address, dst address, src port, dst port>
uniquely identifies a TCP connection.
9. The IP header checksum is not an end-to-end checksum in the sense
of [14]: The time-to-live update forces the IP checksum to be
recomputed at each hop. The author has had unpleasant personal
experience with the consequences of violating the end-to-end argument in
[14] and this protocol is careful to pass the end-to-end TCP checksum
through unmodified. See sec. 4.
This leaves 16 bytes of header information to send. All of these bytes
are likely to change over the life of the conversation but they do not
all change at the same time. For example, during an FTP data transfer
only the packet ID, sequence number and checksum change in the
sender->receiver direction and only the packet ID, ack, checksum and,
possibly, window, change in the receiver->sender direction. With a copy
of the last packet sent for each connection, the sender can figure out
what fields change in the current packet then send a bitmask indicating
what changed followed by the changing fields./10/
If the sender only sends fields that differ, the above scheme gets the
average header size down to around ten bytes. However, it's worthwhile
looking at how the fields change: The packet ID typically comes from a
counter that is incremented by one for each packet sent. I.e., the
difference between the current and previous packet IDs should be a
small, positive integer, usually <256 (one byte) and frequently = 1.
For packets from the sender side of a data transfer, the sequence number
in the current packet will be the sequence number in the previous packet
plus the amount of data in the previous packet (assuming the packets are
arriving in order). Since IP packets can be at most 64K, the sequence
number change must be < 2^16 (two bytes). So, if the differences in the
changing fields are sent rather than the fields themselves, another
three or four bytes per packet can be saved.
That gets us to the five-byte header target. Recognizing a couple of
special cases will get us three byte headers for the two most common
cases---interactive typing traffic and bulk data transfer---but the
basic compression scheme is the differential coding developed above.
Given that this intellectual exercise suggests it is possible to get
five byte headers, it seems reasonable to flesh out the missing details
and actually implement something.
3.2 The ugly details
3.2.1 Overview
Figure 4 shows a block diagram of the compression software. The
networking system calls a SLIP output driver with an IP packet to be
----------------------------
10. This is approximately Thinwire-I from [5]. A slight modification
is to do a `delta encoding' where the sender subtracts the previous
packet from the current packet (treating each packet as an array of 16
bit integers), then sends a 20-bit mask indicating the non-zero
differences followed by those differences. If distinct conversations
are separated, this is a fairly effective compression scheme (e.g.,
typically 12-16 byte headers) that doesn't involve the compressor
knowing any details of the packet structure. Variations on this theme
have been used, successfully, for a number of years (e.g., the Proteon
router's serial link protocol[3]).
sent over the serial line. The packet goes through a compressor which
checks if the protocol is TCP. Non-TCP packets and `uncompressible' TCP
packets (described below) are just marked as TYPE_IP and passed to a
framer. Compressible TCP packets are looked up in an array of packet
headers. If a matching connection is found, the incoming packet is
compressed, the (uncompressed) packet header is copied into the array,
and a packet of type COMPRESSED_TCP is sent to the framer. If no match
is found, the oldest entry in the array is discarded, the packet header
is copied into that slot, and a packet of type UNCOMPRESSED_TCP is sent
to the framer. (An UNCOMPRESSED_TCP packet is identical to the original
IP packet except the IP protocol field is replaced with a connection
number---an index into the array of saved, per-connection packet
headers. This is how the sender (re-)synchronizes the receiver and
`seeds' it with the first, uncompressed packet of a compressed packet
sequence.)
The framer is responsible for communicating the packet data, type and
boundary (so the decompressor can learn how many bytes came out of the
compressor). Since the compression is a differential coding, the framer
must not re-order packets (this is rarely a concern over a single serial
link). It must also provide good error detection and, if connection
numbers are compressed, must provide an error indication to the
decompressor (see sec. 4)./11/
The decompressor does a `switch' on the type of incoming packets: For
TYPE_IP, the packet is simply passed through. For UNCOMPRESSED_TCP, the
connection number is extracted from the IP protocol field and
IPPROTO_TCP is restored, then the connection number is used as an index
into the receiver's array of saved TCP/IP headers and the header of the
incoming packet is copied into the indexed slot. For COMPRESSED_TCP,
the connection number is used as an array index to get the TCP/IP header
of the last packet from that connection, the info in the compressed
packet is used to update that header, then a new packet is constructed
containing the now-current header from the array concatenated with the
data from the compressed packet.
Note that the communication is simplex---no information flows in the
decompressor-to-compressor direction. In particular, this implies that
the decompressor is relying on TCP retransmissions to correct the saved
state in the event of line errors (see sec. 4).
----------------------------
11. Link level framing is outside the scope of this document. Any
framing that provides the facilities listed in this paragraph should be
adequate for the compression protocol. However, the author encourages
potential implementors to see [9] for a proposed, standard, SLIP
framing.
3.2.2 Compressed packet format
Figure 5 shows the format of a compressed TCP/IP packet. There is a
change mask that identifies which of the fields expected to change
per-packet actually changed, a connection number so the receiver can
locate the saved copy of the last packet for this TCP connection, the
unmodified TCP checksum so the end-to-end data integrity check will
still be valid, then for each bit set in the change mask, the amount the
associated field changed. (Optional fields, controlled by the mask, are
enclosed in dashed lines in the figure.) In all cases, the bit is set
if the associated field is present and clear if the field is absent./12/
Since the delta's in the sequence number, etc., are usually small,
particularly if the tuning guidelines in section 5 are followed, all the
numbers are encoded in a variable length scheme that, in practice,
handles most traffic with eight bits: A change of one through 255 is
represented in one byte. Zero is improbable (a change of zero is never
sent) so a byte of zero signals an extension: The next two bytes are
the MSB and LSB, respectively, of a 16 bit value. Numbers larger than
16 bits force an uncompressed packet to be sent. For example, decimal
15 is encoded as hex 0f, 255 as ff, 65534 as 00 ff fe, and zero as 00 00
00. This scheme packs and decodes fairly efficiently: The usual case
for both encode and decode executes three instructions on a MC680x0.
The numbers sent for TCP sequence number and ack are the difference/13/
between the current value and the value in the previous packet (an
uncompressed packet is sent if the difference is negative or more than
64K). The number sent for the window is also the difference between the
current and previous values. However, either positive or negative
changes are allowed since the window is a 16 bit field. The packet's
urgent pointer is sent if URG is set (an uncompressed packet is sent if
the urgent pointer changes but URG is not set). For packet ID, the
number sent is the difference between the current and previous values.
However, unlike the rest of the compressed fields, the assumed change
when I is clear is one, not zero.
There are two important special cases:
(1) The sequence number and ack both change by the amount of data in the
last packet; no window change or URG.
(2) The sequence number changes by the amount of data in the last
packet, no ack or window change or URG.
----------------------------
12. The bit `P' in the figure is different from the others: It is a
copy of the `PUSH' bit from the TCP header. `PUSH' is a curious
anachronism considered indispensable by certain members of the Internet
community. Since PUSH can (and does) change in any datagram, an
information preserving compression scheme must pass it explicitly.
13. All differences are computed using two's complement arithmetic.
(1) is the case for echoed terminal traffic. (2) is the sender side of
non-echoed terminal traffic or a unidirectional data transfer. Certain
combinations of the S, A, W and U bits of the change mask are used to
signal these special cases. `U' (urgent data) is rare so two unlikely
combinations are S W U (used for case 1) and S A W U (used for case 2).
To avoid ambiguity, an uncompressed packet is sent if the actual changes
in a packet are S * W U.
Since the `active' connection changes rarely (e.g., a user will type for
several minutes in a telnet window before changing to a different
window), the C bit allows the connection number to be elided. If C is
clear, the connection is assumed to be the same as for the last
compressed or uncompressed packet. If C is set, the connection number
is in the byte immediately following the change mask./14/
From the above, it's probably obvious that compressed terminal traffic
usually looks like (in hex): 0B c c d, where the 0B indicates case (1),
c c is the two byte TCP checksum and d is the character typed. Commands
to vi or emacs, or packets in the data transfer direction of an FTP
`put' or `get' look like 0F c c d ... , and acks for that FTP look like
04 c c a where a is the amount of data being acked./15/
3.2.3 Compressor processing
The compressor is called with the IP packet to be processed and the
compression state structure for the outgoing serial line. It returns a
packet ready for final framing and the link level `type' of that packet.
As the last section noted, the compressor converts every input packet
into either a TYPE_IP, UNCOMPRESSED_TCP or COMPRESSED_TCP packet. A
----------------------------
14. The connection number is limited to one byte, i.e., 256
simultaneously active TCP connections. In almost two years of
operation, the author has never seen a case where more than sixteen
connection states would be useful (even in one case where the SLIP link
was used as a gateway behind a very busy, 64-port terminal multiplexor).
Thus this does not seem to be a significant restriction and allows the
protocol field in UNCOMPRESSED_TCP packets to be used for the connection
number, simplifying the processing of those packets.
15. It's also obvious that the change mask changes infrequently and
could often be elided. In fact, one can do slightly better by saving
the last compressed packet (it can be at most 16 bytes so this isn't
much additional state) and checking to see if any of it (except the TCP
checksum) has changed. If not, send a packet type that means
`compressed TCP, same as last time' and a packet containing only the
checksum and data. But, since the improvement is at most 25%, the added
complexity and state doesn't seem justified. See appendix C.
TYPE_IP packet is an unmodified copy/16/ of the input packet and
processing it doesn't change the compressor's state in any way.
An UNCOMPRESSED_TCP packet is identical to the input packet except the
IP protocol field (byte 9) is changed from `6' (protocol TCP) to a
connection number. In addition, the state slot associated with the
connection number is updated with a copy of the input packet's IP and
TCP headers and the connection number is recorded as the last connection
sent on this serial line (for the C compression described below).
A COMPRESSED_TCP packet contains the data, if any, from the original
packet but the IP and TCP headers are completely replaced with a new,
compressed header. The connection state slot and last connection sent
are updated by the input packet exactly as for an UNCOMPRESSED_TCP
packet.
The compressor's decision procedure is:
- If the packet is not protocol TCP, send it as TYPE_IP.
- If the packet is an IP fragment (i.e., either the fragment offset
field is non-zero or the more fragments bit is set), send it as
TYPE_IP./17/
- If any of the TCP control bits SYN, FIN or RST are set or if the ACK
bit is clear, consider the packet uncompressible and send it as
TYPE_IP./18/
----------------------------
16. It is not necessary (or desirable) to actually duplicate the input
packet for any of the three output types. Note that the compressor
cannot increase the size of a datagram. As the code in appendix A
shows, the protocol can be implemented so all header modifications are
made `in place'.
17. Only the first fragment contains the TCP header so the fragment
offset check is necessary. The first fragment might contain a complete
TCP header and, thus, could be compressed. However the check for a
complete TCP header adds quite a lot of code and, given the arguments in
[6], it seems reasonable to send all IP fragments uncompressed.
18. The ACK test is redundant since a standard conforming
implementation must set ACK in all packets except for the initial SYN
packet. However, the test costs nothing and avoids turning a bogus
packet into a valid one.
SYN packets are not compressed because only half of them contain a valid
ACK field and they usually contain a TCP option (the max. segment size)
which the following packets don't. Thus the next packet would be sent
uncompressed because the TCP header length changed and sending the SYN
as UNCOMPRESSED_TCP instead of TYPE_IP would buy nothing.
The decision to not compress FIN packets is questionable. Discounting
the trick in appendix B.1, there is a free bit in the header that could
be used to communicate the FIN flag. However, since connections tend to
If a packet makes it through the above checks, it will be sent as either
UNCOMPRESSED_TCP or COMPRESSED_TCP:
- If no connection state can be found that matches the packet's source
and destination IP addresses and TCP ports, some state is reclaimed
(which should probably be the least recently used) and an
UNCOMPRESSED_TCP packet is sent.
- If a connection state is found, the packet header it contains is
checked against the current packet to make sure there were no
unexpected changes. (E.g., that all the shaded fields in fig. 3 are
the same). The IP protocol, fragment offset, more fragments, SYN,
FIN and RST fields were checked above and the source and destination
address and ports were checked as part of locating the state. So
the remaining fields to check are protocol version, header length,
type of service, don't fragment, time-to-live, data offset, IP
options (if any) and TCP options (if any). If any of these fields
differ between the two headers, an UNCOMPRESSED_TCP packet is sent.
If all the `unchanging' fields match, an attempt is made to compress the
current packet:
- If the URG flag is set, the urgent data field is encoded (note that
it may be zero) and the U bit is set in the change mask.
Unfortunately, if URG is clear, the urgent data field must be
checked against the previous packet and, if it changes, an
UNCOMPRESSED_TCP packet is sent. (`Urgent data' shouldn't change
when URG is clear but [11] doesn't require this.)
- The difference between the current and previous packet's window
field is computed and, if non-zero, is encoded and the W bit is set
in the change mask.
- The difference between ack fields is computed. If the result is
less than zero or greater than 2^16 - 1, an UNCOMPRESSED_TCP packet
is sent./19/ Otherwise, if the result is non-zero, it is encoded
and the A bit is set in the change mask.
- The difference between sequence number fields is computed. If the
result is less than zero or greater than 2^16 - 1, an
----------------------------
last for many packets, it seemed unreasonable to dedicate an entire bit
to a flag that would only appear once in the lifetime of the connection.
19. The two tests can be combined into a single test of the most
significant 16 bits of the difference being non-zero.
UNCOMPRESSED_TCP packet is sent./20/ Otherwise, if the result is
non-zero, it is encoded and the S bit is set in the change mask.
Once the U, W, A and S changes have been determined, the special-case
encodings can be checked:
- If U, S and W are set, the changes match one of the special-case
encodings. Send an UNCOMPRESSED_TCP packet.
- If only S is set, check if the change equals the amount of user data
in the last packet. I.e., subtract the TCP and IP header lengths
from the last packet's total length field and compare the result to
the S change. If they're the same, set the change mask to SAWU (the
special case for `unidirectional data transfer') and discard the
encoded sequence number change (the decompressor can reconstruct it
since it knows the last packet's total length and header length).
- If only S and A are set, check if they both changed by the same
amount and that amount is the amount of user data in the last
packet. If so, set the change mask to SWU (the special case for
`echoed interactive' traffic) and discard the encoded changes.
- If nothing changed, check if this packet has no user data (in which
case it is probably a duplicate ack or window probe) or if the
previous packet contained user data (which means this packet is a
retransmission on a connection with no pipelining). In either of
these cases, send an UNCOMPRESSED_TCP packet.
Finally, the TCP/IP header on the outgoing packet is replaced with a
compressed header:
- The change in the packet ID is computed and, if not one,/21/ the
difference is encoded (note that it may be zero or negative) and the
I bit is set in the change mask.
- If the PUSH bit is set in the original datagram, the P bit is set in
the change mask.
- The TCP and IP headers of the packet are copied to the connection
state slot.
----------------------------
20. A negative sequence number change probably indicates a
retransmission. Since this may be due to the decompressor having
dropped a packet, an uncompressed packet is sent to re-sync the
decompressor (see sec. 4).
21. Note that the test here is against one, not zero. The packet ID is
typically incremented by one for each packet sent so a change of zero is
very unlikely. A change of one is likely: It occurs during any period
when the originating system has activity on only one connection.
- The TCP and IP headers of the packet are discarded and a new header
is prepended consisting of (in reverse order):
- the accumulated, encoded changes.
- the TCP checksum (if the new header is being constructed `in
place', the checksum may have been overwritten and will have to
be taken from the header copy in the connection state or saved
in a temporary before the original header is discarded).
- the connection number (if different than the last one sent on
this serial line). This also means that the the line's last
connection sent must be set to the connection number and the C
bit set in the change mask.
- the change mask.
At this point, the compressed TCP packet is passed to the framer for
transmission.
3.2.4 Decompressor processing
Because of the simplex communication model, processing at the
decompressor is much simpler than at the compressor --- all the
decisions have been made and the decompressor simply does what the
compressor has told it to do.
The decompressor is called with the incoming packet,/22/ the length and
type of the packet and the compression state structure for the incoming
serial line. A (possibly re-constructed) IP packet will be returned.
The decompressor can receive four types of packet: the three generated
by the compressor and a TYPE_ERROR pseudo-packet generated when the
receive framer detects an error./23/ The first step is a `switch' on
the packet type:
- If the packet is TYPE_ERROR or an unrecognized type, a `toss' flag
is set in the state to force COMPRESSED_TCP packets to be discarded
until one with the C bit set or an UNCOMPRESSED_TCP packet arrives.
Nothing (a null packet) is returned.
----------------------------
22. It's assumed that link-level framing has been removed by this point
and the packet and length do not include type or framing bytes.
23. No data need be associated with a TYPE_ERROR packet. It exists so
the receive framer can tell the decompressor that there may be a gap in
the data stream. The decompressor uses this as a signal that packets
should be tossed until one arrives with an explicit connection number (C
bit set). See the last part of sec. 4.1 for a discussion of why this is
necessary.
- If the packet is TYPE_IP, an unmodified copy of it is returned and
the state is not modified.
- If the packet is UNCOMPRESSED_TCP, the state index from the IP
protocol field is checked./24/ If it's illegal, the toss flag is
set and nothing is returned. Otherwise, the toss flag is cleared,
the index is copied to the state's last connection received field, a
copy of the input packet is made,/25/ the TCP protocol number is
restored to the IP protocol field, the packet header is copied to
the indicated state slot, then the packet copy is returned.
If the packet was not handled above, it is COMPRESSED_TCP and a new
TCP/IP header has to be synthesized from information in the packet plus
the last packet's header in the state slot. First, the explicit or
implicit connection number is used to locate the state slot:
- If the C bit is set in the change mask, the state index is checked.
If it's illegal, the toss flag is set and nothing is returned.
Otherwise, last connection received is set to the packet's state
index and the toss flag is cleared.
- If the C bit is clear and the toss flag is set, the packet is
ignored and nothing is returned.
At this point, last connection received is the index of the appropriate
state slot and the first byte(s) of the compressed packet (the change
mask and, possibly, connection index) have been consumed. Since the
TCP/IP header in the state slot must end up reflecting the newly arrived
packet, it's simplest to apply the changes from the packet to that
header then construct the output packet from that header concatenated
with the data from the input packet. (In the following description,
`saved header' is used as an abbreviation for `the TCP/IP header saved
in the state slot'.)
- The next two bytes in the incoming packet are the TCP checksum.
They are copied to the saved header.
- If the P bit is set in the change mask, the TCP PUSH bit is set in
the saved header. Otherwise the PUSH bit is cleared.
----------------------------
24. State indices follow the C language convention and run from 0 to N
- 1, where 0 < N <= 256 is the number of available state slots.
25. As with the compressor, the code can be structured so no copies are
done and all modifications are done in-place. However, since the output
packet can be larger than the input packet, 128 bytes of free space must
be left at the front of the input packet buffer to allow room to prepend
the TCP/IP header.
- If the low order four bits (S, A, W and U) of the change mask are
all set (the `unidirectional data' special case), the amount of user
data in the last packet is calculated by subtracting the TCP and IP
header lengths from the IP total length in the saved header. That
amount is then added to the TCP sequence number in the saved header.
- If S, W and U are set and A is clear (the `terminal traffic' special
case), the amount of user data in the last packet is calculated and
added to both the TCP sequence number and ack fields in the saved
header.
- Otherwise, the change mask bits are interpreted individually in the
order that the compressor set them:
- If the U bit is set, the TCP URG bit is set in the saved header
and the next byte(s) of the incoming packet are decoded and
stuffed into the TCP Urgent Pointer. If the U bit is clear, the
TCP URG bit is cleared.
- If the W bit is set, the next byte(s) of the incoming packet are
decoded and added to the TCP window field of the saved header.
- If the A bit is set, the next byte(s) of the incoming packet are
decoded and added to the TCP ack field of the saved header.
- If the S bit is set, the next byte(s) of the incoming packet are
decoded and added to the TCP sequence number field of the saved
header.
- If the I bit is set in the change mask, the next byte(s) of the
incoming packet are decoded and added to the IP ID field of the
saved packet. Otherwise, one is added to the IP ID.
At this point, all the header information from the incoming packet has
been consumed and only data remains. The length of the remaining data
is added to the length of the saved IP and TCP headers and the result is
put into the saved IP total length field. The saved IP header is now up
to date so its checksum is recalculated and stored in the IP checksum
field. Finally, an output datagram consisting of the saved header
concatenated with the remaining incoming data is constructed and
returned.
4 Error handling
4.1 Error detection
In the author's experience, dialup connections are particularly prone to
data errors. These errors interact with compression in two different
ways:
First is the local effect of an error in a compressed packet. All error
detection is based on redundancy yet compression has squeezed out almost
all the redundancy in the TCP and IP headers. In other words, the
decompressor will happily turn random line noise into a perfectly valid
TCP/IP packet./26/ One could rely on the TCP checksum to detect
corrupted compressed packets but, unfortunately, some rather likely
errors will not be detected. For example, the TCP checksum will often
not detect two single bit errors separated by 16 bits. For a V.32 modem
signalling at 2400 baud with 4 bits/baud, any line hit lasting longer
than 400us. would corrupt 16 bits. According to [2], residential phone
line hits of up to 2ms. are likely.
The correct way to deal with this problem is to provide for error
detection at the framing level. Since the framing (at least in theory)
can be tailored to the characteristics of a particular link, the
detection can be as light or heavy-weight as appropriate for that
link./27/ Since packet error detection is done at the framing level,
the decompressor simply assumes that it will get an indication that the
current packet was received with errors. (The decompressor always
ignores (discards) a packet with errors. However, the indication is
needed to prevent the error being propagated --- see below.)
The `discard erroneous packets' policy gives rise to the second
interaction of errors and compression. Consider the following
conversation:
+-------------------------------------------+
|original | sent |received |reconstructed |
+---------+--------+---------+--------------+
| 1: A | 1: A | 1: A | 1: A |
| 2: BC | 1, BC | 1, BC | 2: BC |
| 4: DE | 2, DE | --- | --- |
| 6: F | 2, F | 2, F | 4: F |
| 7: GH | 1, GH | 1, GH | 5: GH |
+-------------------------------------------+
(Each entry above has the form `starting sequence number:data sent' or
`?sequence number change,data sent'.) The first thing sent is an
uncompressed packet, followed by four compressed packets. The third
packet picks up an error and is discarded. To reconstruct the fourth
packet, the receiver applies the sequence number change from incoming
compressed packet to the sequence number of the last correctly received
----------------------------
26. modulo the TCP checksum.
27. While appropriate error detection is link dependent, the CCITT CRC
used in [9] strikes an excellent balance between ease of computation and
robust error detection for a large variety of links, particularly at the
relatively small packet sizes needed for good interactive response.
Thus, for the sake of interoperability, the framing in [9] should be
used unless there is a truly compelling reason to do otherwise.
packet, packet two, and generates an incorrect sequence number for
packet four. After the error, all reconstructed packets' sequence
numbers will be in error, shifted down by the amount of data in the
missing packet./28/
Without some sort of check, the preceding error would result in the
receiver invisibly losing two bytes from the middle of the transfer
(since the decompressor regenerates sequence numbers, the packets
containing F and GH arrive at the receiver's TCP with exactly the
sequence numbers they would have had if the DE packet had never
existed). Although some TCP conversations can survive missing data/29/
it is not a practice to be encouraged. Fortunately the TCP checksum,
since it is a simple sum of the packet contents including the sequence
numbers, detects 100% of these errors. E.g., the receiver's computed
checksum for the last two packets above always differs from the packet
checksum by two.
Unfortunately, there is a way for the TCP checksum protection described
above to fail if the changes in an incoming compressed packet are
applied to the wrong conversation: Consider two active conversations C1
and C2 and a packet from C1 followed by two packets from C2. Since the
connection number doesn't change, it's omitted from the second C2
packet. But, if the first C2 packet is received with a CRC error, the
second C2 packet will mistakenly be considered the next packet in C1.
Since the C2 checksum is a random number with respect to the C1 sequence
numbers, there is at least a 2^-16 probability that this packet will be
accepted by the C1 TCP receiver./30/ To prevent this, after a CRC error
indication from the framer the receiver discards packets until it
receives either a COMPRESSED_TCP packet with the C bit set or an
UNCOMPRESSED_TCP packet. I.e., packets are discarded until the receiver
gets an explicit connection number.
To summarize this section, there are two different types of errors:
per-packet corruption and per-conversation loss-of-sync. The first type
is detected at the decompressor from a link-level CRC error, the second
at the TCP receiver from a (guaranteed) invalid TCP checksum. The
combination of these two independent mechanisms ensures that erroneous
packets are discarded.
----------------------------
28. This is an example of a generic problem with differential or delta
encodings known as `losing DC'.
29. Many system managers claim that holes in an NNTP stream are more
valuable than the data.
30. With worst-case traffic, this probability translates to one
undetected error every three hours over a 9600 baud line with a 30%
error rate).
4.2 Error recovery
The previous section noted that after a CRC error the decompressor will
introduce TCP checksum errors in every uncompressed packet. Although
the checksum errors prevent data stream corruption, the TCP conversation
won't be terribly useful until the decompressor again generates valid
packets. How can this be forced to happen?
The decompressor generates invalid packets because its state (the saved
`last packet header') disagrees with the compressor's state. An
UNCOMPRESSED_TCP packet will correct the decompressor's state. Thus
error recovery amounts to forcing an uncompressed packet out of the
compressor whenever the decompressor is (or might be) confused.
The first thought is to take advantage of the full duplex communication
link and have the decompressor send something to the compressor
requesting an uncompressed packet. This is clearly undesirable since it
constrains the topology more than the minimum suggested in sec. 2 and
requires that a great deal of protocol be added to both the decompressor
and compressor. A little thought convinces one that this alternative is
not only undesirable, it simply won't work: Compressed packets are
small and it's likely that a line hit will so completely obliterate one
that the decompressor will get nothing at all. Thus packets are
reconstructed incorrectly (because of the missing compressed packet) but
only the TCP end points, not the decompressor, know that the packets are
incorrect.
But the TCP end points know about the error and TCP is a reliable
protocol designed to run over unreliable media. This means the end
points must eventually take some sort of error recovery action and
there's an obvious trigger for the compressor to resync the
decompressor: send uncompressed packets whenever TCP is doing error
recovery.
But how does the compressor recognize TCP error recovery? Consider the
schematic TCP data transfer of fig. 6. The confused decompressor is
in the forward (data transfer) half of the TCP conversation. The
receiving TCP discards packets rather than acking them (because of the
checksum errors), the sending TCP eventually times out and retransmits a
packet, and the forward path compressor finds that the difference
between the sequence number in the retransmitted packet and the sequence
number in the last packet seen is either negative (if there were
multiple packets in transit) or zero (one packet in transit). The first
case is detected in the compression step that computes sequence number
differences. The second case is detected in the step that checks the
`special case' encodings but needs an additional test: It's fairly
common for an interactive conversation to send a dataless ack packet
followed by a data packet. The ack and data packet will have the same
sequence numbers yet the data packet is not a retransmission. To
prevent sending an unnecessary uncompressed packet, the length of the
previous packet should be checked and, if it contained data, a zero
sequence number change must indicate a retransmission.
A confused decompressor in the reverse (ack) half of the conversation is