RFC 1144 Compressing TCP/IP Headers February 1990
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]).
Jacobson [Page 5]
RFC 1144 Compressing TCP/IP Headers February 1990
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.
Jacobson [Page 6]
RFC 1144 Compressing TCP/IP Headers February 1990
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.
Jacobson [Page 7]
RFC 1144 Compressing TCP/IP Headers February 1990
(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.
Jacobson [Page 8]
RFC 1144 Compressing TCP/IP Headers February 1990
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
Jacobson [Page 9]
RFC 1144 Compressing TCP/IP Headers February 1990
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.
Jacobson [Page 10]
RFC 1144 Compressing TCP/IP Headers February 1990
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.
Jacobson [Page 11]
RFC 1144 Compressing TCP/IP Headers February 1990
- 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.
Jacobson [Page 12]
RFC 1144 Compressing TCP/IP Headers February 1990
- 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.
Jacobson [Page 13]
RFC 1144 Compressing TCP/IP Headers February 1990
- 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:
Jacobson [Page 14]
RFC 1144 Compressing TCP/IP Headers February 1990
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.
Jacobson [Page 15]