RFC 1144 Compressing TCP/IP Headers February 1990
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).
Jacobson [Page 16]
RFC 1144 Compressing TCP/IP Headers February 1990
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
Jacobson [Page 17]
RFC 1144 Compressing TCP/IP Headers February 1990
sequence number change must indicate a retransmission.
A confused decompressor in the reverse (ack) half of the conversation is
as easy to detect (fig. 7): The sending TCP discards acks (because
they contain checksum errors), eventually times out, then retransmits
some packet. The receiving TCP thus gets a duplicate packet and must
generate an ack for the next expected sequence number[11, p. 69]. This
ack will be a duplicate of the last ack the receiver generated so the
reverse-path compressor will find no ack, seq number, window or urg
change. If this happens for a packet that contains no data, the
compressor assumes it is a duplicate ack sent in response to a
retransmit and sends an UNCOMPRESSED_TCP packet./31/
5 Configurable parameters and tuning
5.1 Compression configuration
There are two configuration parameters associated with header
compression: Whether or not compressed packets should be sent on a
particular line and, if so, how many state slots (saved packet headers)
to reserve. There is also one link-level configuration parameter, the
maximum packet size or MTU, and one front-end configuration parameter,
data compression, that interact with header compression. Compression
configuration is discussed in this section. MTU and data compression
are discussed in the next two sections.
There are some hosts (e.g., low end PCs) which may not have enough
processor or memory resources to implement this compression. There are
also rare link or application characteristics that make header
compression unnecessary or undesirable. And there are many existing
SLIP links that do not currently use this style of header compression.
For the sake of interoperability, serial line IP drivers that allow
header compression should include some sort of user configurable flag to
disable compression (see appendix B.2)./32/
If compression is enabled, the compressor must be sure to never send a
connection id (state index) that will be dropped by the decompressor.
E.g., a black hole is created if the decompressor has sixteen slots and
----------------------------
31. The packet could be a zero-window probe rather than a retransmitted
ack but window probes should be infrequent and it does no harm to send
them uncompressed.
32. The PPP protocol in [9] allows the end points to negotiate
compression so there is no interoperability problem. However, there
should still be a provision for the system manager at each end to
control whether compression is negotiated on or off. And, obviously,
compression should default to `off' until it has been negotiated `on'.
Jacobson [Page 18]
RFC 1144 Compressing TCP/IP Headers February 1990
the compressor uses twenty./33/ Also, if the compressor is allowed too
few slots, the LRU allocator will thrash and most packets will be sent
as UNCOMPRESSED_TCP. Too many slots and memory is wasted.
Experimenting with different sizes over the past year, the author has
found that eight slots will thrash (i.e., the performance degradation is
noticeable) when many windows on a multi-window workstation are
simultaneously in use or the workstation is being used as a gateway for
three or more other machines. Sixteen slots were never observed to
thrash. (This may simply be because a 9600 bps line split more than 16
ways is already so overloaded that the additional degradation from
round-robbining slots is negligible.)
Each slot must be large enough to hold a maximum length TCP/IP header of
128 bytes/34/ so 16 slots occupy 2KB of memory. In these days of 4 Mbit
RAM chips, 2KB seems so little memory that the author recommends the
following configuration rules:
(1) If the framing protocol does not allow negotiation, the compressor
and decompressor should provide sixteen slots, zero through fifteen.
(2) If the framing protocol allows negotiation, any mutually agreeable
number of slots from 1 to 256 should be negotiable./35/ If number
of slots is not negotiated, or until it is negotiated, both sides
should assume sixteen.
(3) If you have complete control of all the machines at both ends of
every link and none of them will ever be used to talk to machines
outside of your control, you are free to configure them however you
please, ignoring the above. However, when your little eastern-block
dictatorship collapses (as they all eventually seem to), be aware
that a large, vocal, and not particularly forgiving Internet
community will take great delight in pointing out to anyone willing
----------------------------
33. Strictly speaking, there's no reason why the connection id should
be treated as an array index. If the decompressor's states were kept in
a hash table or other associative structure, the connection id would be
a key, not an index, and performance with too few decompressor slots
would only degrade enormously rather than failing altogether. However,
an associative structure is substantially more costly in code and cpu
time and, given the small per-slot cost (128 bytes of memory), it seems
reasonable to design for slot arrays at the decompressor and some
(possibly implicit) communication of the array size.
34. The maximum header length, fixed by the protocol design, is 64
bytes of IP and 64 bytes of TCP.
35. Allowing only one slot may make the compressor code more complex.
Implementations should avoid offering one slot if possible and
compressor implementations may disable compression if only one slot is
negotiated.
Jacobson [Page 19]
RFC 1144 Compressing TCP/IP Headers February 1990
to listen that you have misconfigured your systems and are not
interoperable.
5.2 Choosing a maximum transmission unit
From the discussion in sec. 2, it seems desirable to limit the maximum
packet size (MTU) on any line where there might be interactive traffic
and multiple active connections (to maintain good interactive response
between the different connections competing for the line). The obvious
question is `how much does this hurt throughput?' It doesn't.
Figure 8 shows how user data throughput/36/ scales with MTU with (solid
line) and without (dashed line) header compression. The dotted lines
show what MTU corresponds to a 200 ms packet time at 2400, 9600 and
19,200 bps. Note that with header compression even a 2400 bps line can
be responsive yet have reasonable throughput (83%)./37/
Figure 9 shows how line efficiency scales with increasing line speed,
assuming that a 200ms. MTU is always chosen./38/ The knee in the
performance curve is around 2400 bps. Below this, efficiency is
sensitive to small changes in speed (or MTU since the two are linearly
related) and good efficiency comes at the expense of good response.
Above 2400bps the curve is flat and efficiency is relatively independent
of speed or MTU. In other words, it is possible to have both good
response and high line efficiency.
To illustrate, note that for a 9600 bps line with header compression
there is essentially no benefit in increasing the MTU beyond 200 bytes:
If the MTU is increased to 576, the average delay increases by 188%
while throughput only improves by 3% (from 96 to 99%).
----------------------------
36. The vertical axis is in percent of line speed. E.g., `95' means
that 95% of the line bandwidth is going to user data or, in other words,
the user would see a data transfer rate of 9120 bps on a 9600 bps line.
Four bytes of link-level (framer) encapsulation in addition to the
TCP/IP or compressed header were included when calculating the relative
throughput. The 200 ms packet times were computed assuming an
asynchronous line using 10 bits per character (8 data bits, 1 start, 1
stop, no parity).
37. However, the 40 byte TCP MSS required for a 2400 bps line might
stress-test your TCP implementation.
38. For a typical async line, a 200ms. MTU is simply .02 times the line
speed in bits per second.
Jacobson [Page 20]
RFC 1144 Compressing TCP/IP Headers February 1990
5.3 Interaction with data compression
Since the early 1980's, fast, effective, data compression algorithms
such as Lempel-Ziv[7] and programs that embody them, such as the
compress program shipped with Berkeley Unix, have become widely
available. When using low speed or long haul lines, it has become
common practice to compress data before sending it. For dialup
connections, this compression is often done in the modems, independent
of the communicating hosts. Some interesting issues would seem to be:
(1) Given a good data compressor, is there any need for header
compression? (2) Does header compression interact with data
compression? (3) Should data be compressed before or after header
compression?/39/
To investigate (1), Lempel-Ziv compression was done on a trace of 446
TCP/IP packets taken from the user's side of a typical telnet
conversation. Since the packets resulted from typing, almost all
contained only one data byte plus 40 bytes of header. I.e., the test
essentially measured L-Z compression of TCP/IP headers. The compression
ratio (the ratio of uncompressed to compressed data) was 2.6. In other
words, the average header was reduced from 40 to 16 bytes. While this
is good compression, it is far from the 5 bytes of header needed for
good interactive response and far from the 3 bytes of header (a
compression ratio of 13.3) that header compression yielded on the same
packet trace.
The second and third questions are more complex. To investigate them,
several packet traces from FTP file transfers were analyzed/40/ with and
without header compression and with and without L-Z compression. The
L-Z compression was tried at two places in the outgoing data stream
(fig. 10): (1) just before the data was handed to TCP for
encapsulation (simulating compression done at the `application' level)
and (2) after the data was encapsulated (simulating compression done in
the modem). Table 1 summarizes the results for a 78,776 byte ASCII text
file (the Unix csh.1 manual entry)/41/ transferred using the guidelines
of the previous section (256 byte MTU or 216 byte MSS; 368 packets
total). Compression ratios for the following ten tests are shown
(reading left to right and top to bottom):
----------------------------
39. The answers, for those who wish to skip the remainder of this
section, are `yes', `no' and `either', respectively.
40. The data volume from user side of a telnet is too small to benefit
from data compression and can be adversely affected by the delay most
compression algorithms (necessarily) add. The statistics and volume of
the computer side of a telnet are similar to an (ASCII) FTP so these
results should apply to either.
41. The ten experiments described were each done on ten ASCII files
(four long e-mail messages, three Unix C source files and three Unix
manual entries). The results were remarkably similar for different
files and the general conclusions reached below apply to all ten files.
Jacobson [Page 21]
RFC 1144 Compressing TCP/IP Headers February 1990
- data file (no compression or encapsulation)
- data -> L--Z compressor
- data -> TCP/IP encapsulation
- data -> L--Z -> TCP/IP
- data -> TCP/IP -> L--Z
- data -> L--Z -> TCP/IP -> L--Z
- data -> TCP/IP -> Hdr. Compress.
- data -> L--Z -> TCP/IP -> Hdr. Compress.
- data -> TCP/IP -> Hdr. Compress. -> L--Z
- data -> L--Z -> TCP/IP -> Hdr. Compress. -> L--Z
+-----------------------------------------------------+
| | No data | L--Z | L--Z | L--Z |
| |compress. |on data |on wire | on both |
+--------------+----------+--------+--------+---------+
| Raw Data | 1.00 | 2.44 | ---- | ---- |
| + TCP Encap. | 0.83 | 2.03 | 1.97 | 1.58 |
| w/Hdr Comp. | 0.98 | 2.39 | 2.26 | 1.66 |
+-----------------------------------------------------+
Table 1: ASCII Text File Compression Ratios
The first column of table 1 says the data expands by 19% (`compresses'
by .83) when encapsulated in TCP/IP and by 2% when encapsulated in
header compressed TCP/IP./42/ The first row says L--Z compression is
quite effective on this data, shrinking it to less than half its
original size. Column four illustrates the well-known fact that it is a
mistake to L--Z compress already compressed data. The interesting
information is in rows two and three of columns two and three. These
columns say that the benefit of data compression overwhelms the cost of
encapsulation, even for straight TCP/IP. They also say that it is
slightly better to compress the data before encapsulating it rather than
compressing at the framing/modem level. The differences however are
----------------------------
42. This is what would be expected from the relative header sizes:
256/216 for TCP/IP and 219/216 for header compression.
Jacobson [Page 22]
RFC 1144 Compressing TCP/IP Headers February 1990
small --- 3% and 6%, respectively, for the TCP/IP and header compressed
encapsulations./43/
Table 2 shows the same experiment for a 122,880 byte binary file (the
Sun-3 ps executable). Although the raw data doesn't compress nearly as
well, the results are qualitatively the same as for the ASCII data. The
one significant change is in row two: It is about 3% better to compress
the data in the modem rather than at the source if doing TCP/IP
encapsulation (apparently, Sun binaries and TCP/IP headers have similar
statistics). However, with header compression (row three) the results
were similar to the ASCII data --- it's about 3% worse to compress at
the modem rather than the source./44/
+-----------------------------------------------------+
| | No data | L--Z | L--Z | L--Z |
| |compress. |on data |on wire | on both |
+--------------+----------+--------+--------+---------+
| Raw Data | 1.00 | 1.72 | ---- | ---- |
| + TCP Encap. | 0.83 | 1.43 | 1.48 | 1.21 |
| w/Hdr Comp. | 0.98 | 1.69 | 1.64 | 1.28 |
+-----------------------------------------------------+
Table 2: Binary File Compression Ratios
6 Performance measurements
An implementation goal of compression code was to arrive at something
simple enough to run at ISDN speeds (64Kbps) on a typical 1989
----------------------------
43. The differences are due to the wildly different byte patterns of
TCP/IP datagrams and ASCII text. Any compression scheme with an
underlying, Markov source model, such as Lempel-Ziv, will do worse when
radically different sources are interleaved. If the relative
proportions of the two sources are changed, i.e., the MTU is increased,
the performance difference between the two compressor locations
decreases. However, the rate of decrease is very slow --- increasing
the MTU by 400% (256 to 1024) only changed the difference between the
data and modem L--Z choices from 2.5% to 1.3%.
44. There are other good reasons to compress at the source: Far fewer
packets have to be encapsulated and far fewer characters have to be sent
to the modem. The author suspects that the `compress data in the modem'
alternative should be avoided except when faced with an intractable,
vendor proprietary operating system.
Jacobson [Page 23]
RFC 1144 Compressing TCP/IP Headers February 1990
+---------------------------------------+
| | Average per-packet |
| Machine | processing time (us.) |
| | |
| | Compress | Decompress |
+---------------+----------+------------+
|Sparcstation-1 | 24 | 18 |
| Sun 4/260 | 46 | 20 |
| Sun 3/60 | 90 | 90 |
| Sun 3/50 | 130 | 150 |
| HP9000/370 | 42 | 33 |
| HP9000/360 | 68 | 70 |
| DEC 3100 | 27 | 25 |
| Vax 780 | 430 | 300 |
| Vax 750 | 800 | 500 |
| CCI Tahoe | 110 | 140 |
+---------------------------------------+
Table 3: Compression code timings
workstation. 64Kbps is a byte every 122us so 120us was (arbitrarily)
picked as the target compression/decompression time./45/
As part of the compression code development, a trace-driven exerciser
was developed. This was initially used to compare different compression
protocol choices then later to test the code on different computer
architectures and do regression tests after performance `improvements'.
A small modification of this test program resulted in a useful
measurement tool./46/ Table 3 shows the result of timing the
compression code on all the machines available to the author (times were
measured using a mixed telnet/ftp traffic trace). With the exception of
the Vax architectures, which suffer from (a) having bytes in the wrong
order and (b) a lousy compiler (Unix pcc), all machines essentially met
the 120us goal.
----------------------------
45. The time choice wasn't completely arbitrary: Decompression is
often done during the inter-frame `flag' character time so, on systems
where the decompression is done at the same priority level as the serial
line input interrupt, times much longer than a character time would
result in receiver overruns. And, with the current average of five byte
frames (on the wire, including both compressed header and framing), a
compression/decompression that takes one byte time can use at most 20%
of the available time. This seems like a comfortable budget.
46. Both the test program and timer program are included in the
ftp-able package described in appendix A as files tester.c and timer.c.
Jacobson [Page 24]
RFC 1144 Compressing TCP/IP Headers February 1990
7 Acknowlegements
The author is grateful to the members of the Internet Engineering Task
Force, chaired by Phill Gross, who provided encouragement and thoughtful
review of this work. Several patient beta-testers, particularly Sam
Leffler and Craig Leres, tracked down and fixed problems in the initial
implementation. Cynthia Livingston and Craig Partridge carefully read
and greatly improved an unending sequence of partial drafts of this
document. And last but not least, Telebit modem corporation,
particularly Mike Ballard, encouraged this work from its inception and
has been an ongoing champion of serial line and dial-up IP.
References
[1] Bingham, J. A. C. Theory and Practice of Modem Design. John Wiley
& Sons, 1988.
[2] Carey, M. B., Chan, H.-T., Descloux, A., Ingle, J. F., and Park,
K. I. 1982/83 end office connection study: Analog voice and
voiceband data transmission performance characterization of the
public switched network. Bell System Technical Journal 63, 9 (Nov.
1984).
[3] Chiappa, N., 1988. Private communication.
[4] Clark, D. D. The design philosophy of the DARPA Internet
protocols. In Proceedings of SIGCOMM '88 (Stanford, CA, Aug.
1988), ACM.
[5] Farber, D. J., Delp, G. S., and Conte, T. M. A Thinwire Protocol
for connecting personal computers to the Internet. Arpanet Working
Group Requests for Comment, DDN Network Information Center, SRI
International, Menlo Park, CA, Sept. 1984. RFC-914.
[6] Kent, C. A., and Mogul, J. Fragmentation considered harmful. In
Proceedings of SIGCOMM '87 (Aug. 1987), ACM.
[7] Lempel, A., and Ziv, J. Compression of individual sequences via
variable-rate encoding. IEEE Transactions on Information Theory
IT-24, 5 (June 1978).
[8] Nagle, J. Congestion Control in IP/TCP Internetworks. Arpanet
Working Group Requests for Comment, DDN Network Information Center,
SRI International, Menlo Park, CA, Jan. 1984. RFC-896.
[9] Perkins, D. Point-to-Point Protocol: A proposal for
multi-protocol transmission of datagrams over point-to-point links.
Arpanet Working Group Requests for Comment, DDN Network Information
Center, SRI International, Menlo Park, CA, Nov. 1989. RFC-1134.
Jacobson [Page 25]
RFC 1144 Compressing TCP/IP Headers February 1990
[10] Postel, J., Ed. Internet Protocol Specification. SRI
International, Menlo Park, CA, Sept. 1981. RFC-791.
[11] Postel, J., Ed. Transmission Control Protocol Specification. SRI
International, Menlo Park, CA, Sept. 1981. RFC-793.
[12] Romkey, J. A Nonstandard for Transmission of IP Datagrams Over
Serial Lines: Slip. Arpanet Working Group Requests for Comment,
DDN Network Information Center, SRI International, Menlo Park, CA,
June 1988. RFC-1055.
[13] Salthouse, T. A. The skill of typing. Scientific American 250, 2
(Feb. 1984), 128--135.
[14] Saltzer, J. H., Reed, D. P., and Clark, D. D. End-to-end arguments
in system design. ACM Transactions on Computer Systems 2, 4 (Nov.
1984).
[15] Shneiderman, B. Designing the User Interface. Addison-Wesley,
1987.
Jacobson [Page 26]