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'.
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.
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.
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.
- 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.
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.
+---------------------------------------+
| | 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.
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.
[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.
A Sample Implementation
The following is a sample implementation of the protocol described in
this document.
Since many people who might have the deal with this code are familiar
with the Berkeley Unix kernel and its coding style (affectionately known
as kernel normal form), this code was done in that style. It uses the
Berkeley `subroutines' (actually, macros and/or inline assembler
expansions) for converting to/from network byte order and
copying/comparing strings of bytes. These routines are briefly
described in sec. A.5 for anyone not familiar with them.
This code has been run on all the machines listed in the table on page
24. Thus, the author hopes there are no byte order or alignment
problems (although there are embedded assumptions about alignment that
are valid for Berkeley Unix but may not be true for other IP
implementations --- see the comments mentioning alignment in
sl_compress_tcp and sl_decompress_tcp).
There was some attempt to make this code efficient. Unfortunately, that
may have made portions of it incomprehensible. The author apologizes
for any frustration this engenders. (In honesty, my C style is known to
be obscure and claims of `efficiency' are simply a convenient excuse.)
This sample code and a complete Berkeley Unix implementation is
available in machine readable form via anonymous ftp from Internet host
ftp.ee.lbl.gov (128.3.254.68), file cslip.tar.Z. This is a compressed
Unix tar file. It must be ftped in binary mode.
All of the code in this appendix is covered by the following copyright:
/*
* Copyright (c) 1989 Regents of the University of California.
* All rights reserved.
*
* Redistribution and use in source and binary forms are
* permitted provided that the above copyright notice and this
* paragraph are duplicated in all such forms and that any
* documentation, advertising materials, and other materials
* related to such distribution and use acknowledge that the
* software was developed by the University of California,
* Berkeley. The name of the University may not be used to
* endorse or promote products derived from this software
* without specific prior written permission.
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS
* OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE
* IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A
* PARTICULAR PURPOSE.
*/
A.1 Definitions and State Data
#define MAX_STATES 16 /* must be >2 and <255 */
#define MAX_HDR 128 /* max TCP+IP hdr length (by protocol def) */
/* packet types */
#define TYPE_IP 0x40
#define TYPE_UNCOMPRESSED_TCP 0x70
#define TYPE_COMPRESSED_TCP 0x80
#define TYPE_ERROR 0x00 /* this is not a type that ever appears on
* the wire. The receive framer uses it to
* tell the decompressor there was a packet
* transmission error. */
/*
* Bits in first octet of compressed packet
*/
/* flag bits for what changed in a packet */
#define NEW_C 0x40
#define NEW_I 0x20
#define TCP_PUSH_BIT 0x10
#define NEW_S 0x08
#define NEW_A 0x04
#define NEW_W 0x02
#define NEW_U 0x01
/* reserved, special-case values of above */
#define SPECIAL_I (NEW_S|NEW_W|NEW_U) /* echoed interactive traffic */
#define SPECIAL_D (NEW_S|NEW_A|NEW_W|NEW_U) /* unidirectional data */
#define SPECIALS_MASK (NEW_S|NEW_A|NEW_W|NEW_U)
/*
* "state" data for each active tcp conversation on the wire. This is
* basically a copy of the entire IP/TCP header from the last packet together
* with a small identifier the transmit & receive ends of the line use to
* locate saved header.
*/
struct cstate {
struct cstate *cs_next; /* next most recently used cstate (xmit only) */
u_short cs_hlen; /* size of hdr (receive only) */
u_char cs_id; /* connection # associated with this state */
u_char cs_filler;
union {
char hdr[MAX_HDR];
struct ip csu_ip; /* ip/tcp hdr from most recent packet */
} slcs_u;
};
#define cs_ip slcs_u.csu_ip
#define cs_hdr slcs_u.csu_hdr
/*
* all the state data for one serial line (we need one of these per line).
*/
struct slcompress {
struct cstate *last_cs; /* most recently used tstate */
u_char last_recv; /* last rcvd conn. id */
u_char last_xmit; /* last sent conn. id */
u_short flags;
struct cstate tstate[MAX_STATES]; /* xmit connection states */
struct cstate rstate[MAX_STATES]; /* receive connection states */
};
/* flag values */
#define SLF_TOSS 1 /* tossing rcvd frames because of input err */
/*
* The following macros are used to encode and decode numbers. They all
* assume that `cp' points to a buffer where the next byte encoded (decoded)
* is to be stored (retrieved). Since the decode routines do arithmetic,
* they have to convert from and to network byte order.
*/
/*
* ENCODE encodes a number that is known to be non-zero. ENCODEZ checks for
* zero (zero has to be encoded in the long, 3 byte form).
*/
#define ENCODE(n) { \
if ((u_short)(n) >= 256) { \
*cp++ = 0; \
cp[1] = (n); \
cp[0] = (n) >> 8; \
cp += 2; \
} else { \
*cp++ = (n); \
} \
}
#define ENCODEZ(n) { \
if ((u_short)(n) >= 256 || (u_short)(n) == 0) { \
*cp++ = 0; \
cp[1] = (n); \
cp[0] = (n) >> 8; \
cp += 2; \
} else { \
*cp++ = (n); \
} \
}
/*
* DECODEL takes the (compressed) change at byte cp and adds it to the
* current value of packet field 'f' (which must be a 4-byte (long) integer
* in network byte order). DECODES does the same for a 2-byte (short) field.
* DECODEU takes the change at cp and stuffs it into the (short) field f.
* 'cp' is updated to point to the next field in the compressed header.
*/
#define DECODEL(f) { \
if (*cp == 0) {\
(f) = htonl(ntohl(f) + ((cp[1] << 8) | cp[2])); \
cp += 3; \
} else { \
(f) = htonl(ntohl(f) + (u_long)*cp++); \
} \
}
#define DECODES(f) { \
if (*cp == 0) {\
(f) = htons(ntohs(f) + ((cp[1] << 8) | cp[2])); \
cp += 3; \
} else { \
(f) = htons(ntohs(f) + (u_long)*cp++); \
} \
}
#define DECODEU(f) { \
if (*cp == 0) {\
(f) = htons((cp[1] << 8) | cp[2]); \
cp += 3; \
} else { \
(f) = htons((u_long)*cp++); \
} \
}
A.2 Compression
This routine looks daunting but isn't really. The code splits into four
approximately equal sized sections: The first quarter manages a
circularly linked, least-recently-used list of `active' TCP
connections./47/ The second figures out the sequence/ack/window/urg
changes and builds the bulk of the compressed packet. The third handles
the special-case encodings. The last quarter does packet ID and
connection ID encoding and replaces the original packet header with the
compressed header.
The arguments to this routine are a pointer to a packet to be
compressed, a pointer to the compression state data for the serial line,
and a flag which enables or disables connection id (C bit) compression.
Compression is done `in-place' so, if a compressed packet is created,
both the start address and length of the incoming packet (the off and
len fields of m) will be updated to reflect the removal of the original
header and its replacement by the compressed header. If either a
compressed or uncompressed packet is created, the compression state is
updated. This routines returns the packet type for the transmit framer
(TYPE_IP, TYPE_UNCOMPRESSED_TCP or TYPE_COMPRESSED_TCP).
Because 16 and 32 bit arithmetic is done on various header fields, the
incoming IP packet must be aligned appropriately (e.g., on a SPARC, the
IP header is aligned on a 32-bit boundary). Substantial changes would
have to be made to the code below if this were not true (and it would
probably be cheaper to byte copy the incoming header to somewhere
correctly aligned than to make those changes).
Note that the outgoing packet will be aligned arbitrarily (e.g., it
could easily start on an odd-byte boundary).
u_char
sl_compress_tcp(m, comp, compress_cid)
struct mbuf *m;
struct slcompress *comp;
int compress_cid;
{
register struct cstate *cs = comp->last_cs->cs_next;
register struct ip *ip = mtod(m, struct ip *);
register u_int hlen = ip->ip_hl;
register struct tcphdr *oth; /* last TCP header */
register struct tcphdr *th; /* current TCP header */
----------------------------
47. The two most common operations on the connection list are a `find'
that terminates at the first entry (a new packet for the most recently
used connection) and moving the last entry on the list to the head of
the list (the first packet from a new connection). A circular list
efficiently handles these two operations.
register u_int deltaS, deltaA; /* general purpose temporaries */
register u_int changes = 0; /* change mask */
u_char new_seq[16]; /* changes from last to current */
register u_char *cp = new_seq;
/*
* Bail if this is an IP fragment or if the TCP packet isn't
* `compressible' (i.e., ACK isn't set or some other control bit is
* set). (We assume that the caller has already made sure the packet
* is IP proto TCP).
*/
if ((ip->ip_off & htons(0x3fff)) || m->m_len < 40)
return (TYPE_IP);
th = (struct tcphdr *) & ((int *) ip)[hlen];
if ((th->th_flags & (TH_SYN | TH_FIN | TH_RST | TH_ACK)) != TH_ACK)
return (TYPE_IP);
/*
* Packet is compressible -- we're going to send either a
* COMPRESSED_TCP or UNCOMPRESSED_TCP packet. Either way we need to
* locate (or create) the connection state. Special case the most
* recently used connection since it's most likely to be used again &
* we don't have to do any reordering if it's used.
*/
if (ip->ip_src.s_addr != cs->cs_ip.ip_src.s_addr ||
ip->ip_dst.s_addr != cs->cs_ip.ip_dst.s_addr ||
*(int *) th != ((int *) &cs->cs_ip)[cs->cs_ip.ip_hl]) {
/*
* Wasn't the first -- search for it.
*
* States are kept in a circularly linked list with last_cs
* pointing to the end of the list. The list is kept in lru
* order by moving a state to the head of the list whenever
* it is referenced. Since the list is short and,
* empirically, the connection we want is almost always near
* the front, we locate states via linear search. If we
* don't find a state for the datagram, the oldest state is
* (re-)used.
*/
register struct cstate *lcs;
register struct cstate *lastcs = comp->last_cs;
do {
lcs = cs;
cs = cs->cs_next;
if (ip->ip_src.s_addr == cs->cs_ip.ip_src.s_addr
&& ip->ip_dst.s_addr == cs->cs_ip.ip_dst.s_addr
&& *(int *) th == ((int *) &cs->cs_ip)[cs->cs_ip.ip_hl])
goto found;
} while (cs != lastcs);
/*
* Didn't find it -- re-use oldest cstate. Send an
* uncompressed packet that tells the other side what
* connection number we're using for this conversation. Note
* that since the state list is circular, the oldest state
* points to the newest and we only need to set last_cs to
* update the lru linkage.
*/
comp->last_cs = lcs;
hlen += th->th_off;
hlen <<= 2;
goto uncompressed;
found:
/* Found it -- move to the front on the connection list. */
if (lastcs == cs)
comp->last_cs = lcs;
else {
lcs->cs_next = cs->cs_next;
cs->cs_next = lastcs->cs_next;
lastcs->cs_next = cs;
}
}
/*
* Make sure that only what we expect to change changed. The first
* line of the `if' checks the IP protocol version, header length &
* type of service. The 2nd line checks the "Don't fragment" bit.
* The 3rd line checks the time-to-live and protocol (the protocol
* check is unnecessary but costless). The 4th line checks the TCP
* header length. The 5th line checks IP options, if any. The 6th
* line checks TCP options, if any. If any of these things are
* different between the previous & current datagram, we send the
* current datagram `uncompressed'.
*/
oth = (struct tcphdr *) & ((int *) &cs->cs_ip)[hlen];
deltaS = hlen;
hlen += th->th_off;
hlen <<= 2;
if (((u_short *) ip)[0] != ((u_short *) &cs->cs_ip)[0] ||
((u_short *) ip)[3] != ((u_short *) &cs->cs_ip)[3] ||
((u_short *) ip)[4] != ((u_short *) &cs->cs_ip)[4] ||
th->th_off != oth->th_off ||
(deltaS > 5 && BCMP(ip + 1, &cs->cs_ip + 1, (deltaS - 5) << 2)) ||
(th->th_off > 5 && BCMP(th + 1, oth + 1, (th->th_off - 5) << 2)))
goto uncompressed;
/*
* Figure out which of the changing fields changed. The receiver
* expects changes in the order: urgent, window, ack, seq.
*/
if (th->th_flags & TH_URG) {
deltaS = ntohs(th->th_urp);
ENCODEZ(deltaS);
changes |= NEW_U;
} else if (th->th_urp != oth->th_urp)
/*
* argh! URG not set but urp changed -- a sensible
* implementation should never do this but RFC793 doesn't
* prohibit the change so we have to deal with it.
*/
goto uncompressed;
if (deltaS = (u_short) (ntohs(th->th_win) - ntohs(oth->th_win))) {
ENCODE(deltaS);
changes |= NEW_W;
}
if (deltaA = ntohl(th->th_ack) - ntohl(oth->th_ack)) {
if (deltaA > 0xffff)
goto uncompressed;
ENCODE(deltaA);
changes |= NEW_A;
}
if (deltaS = ntohl(th->th_seq) - ntohl(oth->th_seq)) {
if (deltaS > 0xffff)
goto uncompressed;
ENCODE(deltaS);
changes |= NEW_S;
}
/*
* Look for the special-case encodings.
*/
switch (changes) {
case 0:
/*
* Nothing changed. If this packet contains data and the last
* one didn't, this is probably a data packet following an
* ack (normal on an interactive connection) and we send it
* compressed. Otherwise it's probably a retransmit,
* retransmitted ack or window probe. Send it uncompressed
* in case the other side missed the compressed version.
*/
if (ip->ip_len != cs->cs_ip.ip_len &&
ntohs(cs->cs_ip.ip_len) == hlen)
break;
/* (fall through) */
case SPECIAL_I:
case SPECIAL_D:
/*
* Actual changes match one of our special case encodings --
* send packet uncompressed.
*/
goto uncompressed;
case NEW_S | NEW_A:
if (deltaS == deltaA &&
deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {
/* special case for echoed terminal traffic */
changes = SPECIAL_I;
cp = new_seq;
}
break;
case NEW_S:
if (deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {
/* special case for data xfer */
changes = SPECIAL_D;
cp = new_seq;
}
break;
}
deltaS = ntohs(ip->ip_id) - ntohs(cs->cs_ip.ip_id);
if (deltaS != 1) {
ENCODEZ(deltaS);
changes |= NEW_I;
}
if (th->th_flags & TH_PUSH)
changes |= TCP_PUSH_BIT;
/*
* Grab the cksum before we overwrite it below. Then update our
* state with this packet's header.
*/
deltaA = ntohs(th->th_sum);
BCOPY(ip, &cs->cs_ip, hlen);
/*
* We want to use the original packet as our compressed packet. (cp -
* new_seq) is the number of bytes we need for compressed sequence
* numbers. In addition we need one byte for the change mask, one
* for the connection id and two for the tcp checksum. So, (cp -
* new_seq) + 4 bytes of header are needed. hlen is how many bytes
* of the original packet to toss so subtract the two to get the new
* packet size.
*/
deltaS = cp - new_seq;
cp = (u_char *) ip;
if (compress_cid == 0 || comp->last_xmit != cs->cs_id) {
comp->last_xmit = cs->cs_id;
hlen -= deltaS + 4;
cp += hlen;
*cp++ = changes | NEW_C;
*cp++ = cs->cs_id;
} else {
hlen -= deltaS + 3;
cp += hlen;
*cp++ = changes;
}
m->m_len -= hlen;
m->m_off += hlen;
*cp++ = deltaA >> 8;
*cp++ = deltaA;
BCOPY(new_seq, cp, deltaS);
return (TYPE_COMPRESSED_TCP);
uncompressed:
/*
* Update connection state cs & send uncompressed packet
* ('uncompressed' means a regular ip/tcp packet but with the
* 'conversation id' we hope to use on future compressed packets in
* the protocol field).
*/
BCOPY(ip, &cs->cs_ip, hlen);
ip->ip_p = cs->cs_id;
comp->last_xmit = cs->cs_id;
return (TYPE_UNCOMPRESSED_TCP);
}
A.3 Decompression
This routine decompresses a received packet. It is called with a
pointer to the packet, the packet length and type, and a pointer to the
compression state structure for the incoming serial line. It returns a
pointer to the resulting packet or zero if there were errors in the
incoming packet. If the packet is COMPRESSED_TCP or UNCOMPRESSED_TCP,
the compression state will be updated.
The new packet will be constructed in-place. That means that there must
be 128 bytes of free space in front of bufp to allow room for the
reconstructed IP and TCP headers. The reconstructed packet will be
aligned on a 32-bit boundary.
u_char *
sl_uncompress_tcp(bufp, len, type, comp)
u_char *bufp;
int len;
u_int type;
struct slcompress *comp;
{
register u_char *cp;
register u_int hlen, changes;
register struct tcphdr *th;
register struct cstate *cs;
register struct ip *ip;
switch (type) {
case TYPE_ERROR:
default:
goto bad;
case TYPE_IP:
return (bufp);
case TYPE_UNCOMPRESSED_TCP:
/*
* Locate the saved state for this connection. If the state
* index is legal, clear the 'discard' flag.
*/
ip = (struct ip *) bufp;
if (ip->ip_p >= MAX_STATES)
goto bad;
cs = &comp->rstate[comp->last_recv = ip->ip_p];
comp->flags &= ~SLF_TOSS;
/*
* Restore the IP protocol field then save a copy of this
* packet header. (The checksum is zeroed in the copy so we
* don't have to zero it each time we process a compressed
* packet.
*/
ip->ip_p = IPPROTO_TCP;
hlen = ip->ip_hl;
hlen += ((struct tcphdr *) & ((int *) ip)[hlen])->th_off;
hlen <<= 2;
BCOPY(ip, &cs->cs_ip, hlen);
cs->cs_ip.ip_sum = 0;
cs->cs_hlen = hlen;
return (bufp);
case TYPE_COMPRESSED_TCP:
break;
}
/* We've got a compressed packet. */
cp = bufp;
changes = *cp++;
if (changes & NEW_C) {
/*
* Make sure the state index is in range, then grab the
* state. If we have a good state index, clear the 'discard'
* flag.
*/
if (*cp >= MAX_STATES)
goto bad;
comp->flags &= ~SLF_TOSS;
comp->last_recv = *cp++;
} else {
/*
* This packet has an implicit state index. If we've had a
* line error since the last time we got an explicit state
* index, we have to toss the packet.
*/
if (comp->flags & SLF_TOSS)
return ((u_char *) 0);
}
/*
* Find the state then fill in the TCP checksum and PUSH bit.
*/
cs = &comp->rstate[comp->last_recv];
hlen = cs->cs_ip.ip_hl << 2;
th = (struct tcphdr *) & ((u_char *) &cs->cs_ip)[hlen];
th->th_sum = htons((*cp << 8) | cp[1]);
cp += 2;
if (changes & TCP_PUSH_BIT)
th->th_flags |= TH_PUSH;
else
th->th_flags &= ~TH_PUSH;
/*
* Fix up the state's ack, seq, urg and win fields based on the
* changemask.
*/
switch (changes & SPECIALS_MASK) {
case SPECIAL_I:
{
register u_int i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen;
th->th_ack = htonl(ntohl(th->th_ack) + i);
th->th_seq = htonl(ntohl(th->th_seq) + i);
}
break;
case SPECIAL_D:
th->th_seq = htonl(ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len)
- cs->cs_hlen);
break;
default:
if (changes & NEW_U) {
th->th_flags |= TH_URG;
DECODEU(th->th_urp)
} else
th->th_flags &= ~TH_URG;
if (changes & NEW_W)
DECODES(th->th_win)
if (changes & NEW_A)
DECODEL(th->th_ack)
if (changes & NEW_S)
DECODEL(th->th_seq)
break;
}
/* Update the IP ID */
if (changes & NEW_I)
DECODES(cs->cs_ip.ip_id)
else
cs->cs_ip.ip_id = htons(ntohs(cs->cs_ip.ip_id) + 1);
/*
* At this point, cp points to the first byte of data in the packet.
* If we're not aligned on a 4-byte boundary, copy the data down so
* the IP & TCP headers will be aligned. Then back up cp by the
* TCP/IP header length to make room for the reconstructed header (we
* assume the packet we were handed has enough space to prepend 128
* bytes of header). Adjust the lenth to account for the new header
* & fill in the IP total length.
*/
len -= (cp - bufp);
if (len < 0)
/*
* we must have dropped some characters (crc should detect
* this but the old slip framing won't)
*/
goto bad;
if ((int) cp & 3) {
if (len > 0)
OVBCOPY(cp, (int) cp & ~3, len);
cp = (u_char *) ((int) cp & ~3);
}
cp -= cs->cs_hlen;
len += cs->cs_hlen;
cs->cs_ip.ip_len = htons(len);
BCOPY(&cs->cs_ip, cp, cs->cs_hlen);
/* recompute the ip header checksum */
{
register u_short *bp = (u_short *) cp;
for (changes = 0; hlen > 0; hlen -= 2)
changes += *bp++;
changes = (changes & 0xffff) + (changes >> 16);
changes = (changes & 0xffff) + (changes >> 16);
((struct ip *) cp)->ip_sum = ~changes;
}
return (cp);
bad:
comp->flags |= SLF_TOSS;
return ((u_char *) 0);
}
A.4 Initialization
This routine initializes the state structure for both the transmit and
receive halves of some serial line. It must be called each time the
line is brought up.
void
sl_compress_init(comp)
struct slcompress *comp;
{
register u_int i;
register struct cstate *tstate = comp->tstate;
/*
* Clean out any junk left from the last time line was used.
*/
bzero((char *) comp, sizeof(*comp));
/*
* Link the transmit states into a circular list.
*/
for (i = MAX_STATES - 1; i > 0; --i) {
tstate[i].cs_id = i;
tstate[i].cs_next = &tstate[i - 1];
}
tstate[0].cs_next = &tstate[MAX_STATES - 1];
tstate[0].cs_id = 0;
comp->last_cs = &tstate[0];
/*
* Make sure we don't accidentally do CID compression
* (assumes MAX_STATES < 255).
*/
comp->last_recv = 255;
comp->last_xmit = 255;
}
A.5 Berkeley Unix dependencies
Note: The following is of interest only if you are trying to bring the
sample code up on a system that is not derived from 4BSD (Berkeley
Unix).
The code uses the normal Berkeley Unix header files (from
/usr/include/netinet) for definitions of the structure of IP and TCP
headers. The structure tags tend to follow the protocol RFCs closely
and should be obvious even if you do not have access to a 4BSD
system./48/
----------------------------
48. In the event they are not obvious, the header files (and all the
Berkeley networking code) can be anonymous ftp'd from host
The macro BCOPY(src, dst, amt) is invoked to copy amt bytes from src to
dst. In BSD, it translates into a call to bcopy. If you have the
misfortune to be running System-V Unix, it can be translated into a call
to memcpy. The macro OVBCOPY(src, dst, amt) is used to copy when src
and dst overlap (i.e., when doing the 4-byte alignment copy). In the
BSD kernel, it translates into a call to ovbcopy. Since AT&T botched
the definition of memcpy, this should probably translate into a copy
loop under System-V.
The macro BCMP(src, dst, amt) is invoked to compare amt bytes of src and
dst for equality. In BSD, it translates into a call to bcmp. In
System-V, it can be translated into a call to memcmp or you can write a
routine to do the compare. The routine should return zero if all bytes
of src and dst are equal and non-zero otherwise.
The routine ntohl(dat) converts (4 byte) long dat from network byte
order to host byte order. On a reasonable cpu this can be the no-op
macro:
#define ntohl(dat) (dat)
On a Vax or IBM PC (or anything with Intel byte order), you will have to
define a macro or routine to rearrange bytes.
The routine ntohs(dat) is like ntohl but converts (2 byte) shorts
instead of longs. The routines htonl(dat) and htons(dat) do the inverse
transform (host to network byte order) for longs and shorts.
A struct mbuf is used in the call to sl_compress_tcp because that
routine needs to modify both the start address and length if the
incoming packet is compressed. In BSD, an mbuf is the kernel's buffer
management structure. If other systems, the following definition should
be sufficient:
struct mbuf {
u_char *m_off; /* pointer to start of data */
int m_len; /* length of data */
};
#define mtod(m, t) ((t)(m->m_off))
----------------------------
ucbarpa.berkeley.edu, files pub/4.3/tcp.tar and pub/4.3/inet.tar.
B Compatibility with past mistakes
When combined with the modern PPP serial line protocol[9], the use of
header compression is automatic and invisible to the user.
Unfortunately, many sites have existing users of the SLIP described in
[12] which doesn't allow for different protocol types to distinguish
header compressed packets from IP packets or for version numbers or an
option exchange that could be used to automatically negotiate header
compression.
The author has used the following tricks to allow header compressed SLIP
to interoperate with the existing servers and clients. Note that these
are hacks for compatibility with past mistakes and should be offensive
to any right thinking person. They are offered solely to ease the pain
of running SLIP while users wait patiently for vendors to release PPP.
B.1 Living without a framing `type' byte
The bizarre packet type numbers in sec. A.1 were chosen to allow a
`packet type' to be sent on lines where it is undesirable or impossible
to add an explicit type byte. Note that the first byte of an IP packet
always contains `4' (the IP protocol version) in the top four bits. And
that the most significant bit of the first byte of the compressed header
is ignored. Using the packet types in sec. A.1, the type can be encoded
in the most significant bits of the outgoing packet using the code
p->dat[0] |= sl_compress_tcp(p, comp);
and decoded on the receive side by
if (p->dat[0] & 0x80)
type = TYPE_COMPRESSED_TCP;
else if (p->dat[0] >= 0x70) {
type = TYPE_UNCOMPRESSED_TCP;
p->dat[0] &=~ 0x30;
} else
type = TYPE_IP;
status = sl_uncompress_tcp(p, type, comp);
B.2 Backwards compatible SLIP servers
The SLIP described in [12] doesn't include any mechanism that could be
used to automatically negotiate header compression. It would be nice to
allow users of this SLIP to use header compression but, when users of
the two SLIP varients share a common server, it would be annoying and
difficult to manually configure both ends of each connection to enable
compression. The following procedure can be used to avoid manual
configuration.
Since there are two types of dial-in clients (those that implement
compression and those that don't) but one server for both types, it's
clear that the server will be reconfiguring for each new client session
but clients change configuration seldom if ever. If manual
configuration has to be done, it should be done on the side that changes
infrequently --- the client. This suggests that the server should
somehow learn from the client whether to use header compression.
Assuming symmetry (i.e., if compression is used at all it should be used
both directions) the server can use the receipt of a compressed packet
from some client to indicate that it can send compressed packets to that
client. This leads to the following algorithm:
There are two bits per line to control header compression: allowed and
on. If on is set, compressed packets are sent, otherwise not. If
allowed is set, compressed packets can be received and, if an