Network Working Group V. Jacobson/1/
Request for Comments: 1144 LBL
February 1990
Compressing TCP/IP Headers
for Low-Speed Serial Links
Status of this Memo
This RFC is 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
RFC 1144 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).
Jacobson [Page 1]
RFC 1144 Compressing TCP/IP Headers February 1990
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.
Jacobson [Page 2]
RFC 1144 Compressing TCP/IP Headers February 1990
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.
Jacobson [Page 3]
RFC 1144 Compressing TCP/IP Headers February 1990
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
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.
Jacobson [Page 4]