Network Working Group Richard Price, Siemens/Roke Manor
INTERNET-DRAFT Robert Hancock, Siemens/Roke Manor
Expires: January 2002 Stephen McCann, Siemens/Roke Manor
Mark A West, Siemens/Roke Manor
Abigail Surtees, Siemens/Roke Manor
Paul Ollis, Siemens/Roke Manor
9 July, 2001
Enhanced TCP/IP Compression for ROHC
<draft-price-rohc-epic-02.txt>
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of [RFC-2026].
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that other
groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This document is a submission to the IETF ROHC WG. Comments should be
directed to the mailing list of ROHC, rohc@cdt.luth.se.
Abstract
This draft describes an optional enhancement to the ROHC profile
specified in [EPIC-LITE] for the robust compression of TCP/IP.
The RObust Header Compression [ROHC] scheme is designed to compress
packet headers over error prone channels. It is built around an
extensible core framework that can be tailored to compress new
protocol stacks by adding additional ROHC profiles.
The new profile for TCP/IP compression is provided by the Efficient
Protocol Independent Compression (EPIC) scheme.
Price et al. [PAGE 1]
INTERNET-DRAFT Enhanced TCP/IP Compression for ROHC 9 July, 2001
Table of contents
1. Introduction.................................................2
2. Terminology..................................................3
3. Differences between EPIC and EPIC-LITE.......................3
4. Worked example for TCP/IP compression........................3
5. Changes required to implement EPIC...........................5
6. Statement of optimal efficiency..............................8
7. Security Considerations......................................9
8. Acknowledgements.............................................9
9. Intellectual Property Considerations.........................9
10. References...................................................9
11. Authors' Addresses...........................................10
Revision history
-01: Document split into two Internet Drafts:
<draft-ietf-rohc-tcp-epic-01.txt> for the basic TCP/IP profile
<draft-price-rohc-epic-02.txt> for an enhanced TCP/IP profile
Major updates to every section:
Pseudocode added for all parts of the scheme
Language added for the succinct description of new ROHC profiles
Support for IR and IR-DYN packets included
Finite state machine adapted from ROHC RTP
ROHC profile for compression of TCP/IP updated
-00: Document created for robust compression of TCP/IP
1. Introduction
This document describes an enhanced method for compressing TCP/IP
headers within the [ROHC] framework. The new profile for TCP/IP
compression is provided by the Efficient Protocol Independent
Compression (EPIC) scheme.
A companion draft [EPIC-LITE] describes a version of EPIC known as
EPIC-LITE. This draft describes the delta changes required to
implement EPIC itself.
The difference between the two scheme is that EPIC has a higher
compression ratio than EPIC-LITE. In fact, in a well-defined sense
the compressed headers produced by EPIC are optimally efficient: i.e.
the compression ratio achieved by EPIC is provably the maximum
possible for the chosen level of robustness.
A demonstration of this draft has been implemented and is available
from [IMPL].
Price et al. [PAGE 2]
INTERNET-DRAFT Enhanced TCP/IP Compression for ROHC 9 July, 2001
2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC-2119].
3. Differences between EPIC and EPIC-LITE
In general the EPIC and EPIC-LITE schemes are very similar. Both
share the same input language for creating new ROHC profiles, and
both employ the same library of encoding methods. The only difference
lies in the way the value of each compressed field is communicated to
the decompressor.
As stated in [EPIC-LITE] each compressed header generated by the
EPIC-LITE scheme is divided into two distinct parts: the indicator
flags and the compressed fields. This situation is illustrated below:
+---+---+---+---+--------------------+--------------------+---
| 0 | 1 | 1 | 0 | Compressed Field 1 | Compressed Field 2 |...
+---+---+---+---+--------------------+--------------------+---
\ \ / / \ /
\ \ / / \ /
Indicator Flags Compressed Fields
Figure 1 : Structure of an EPIC-LITE compressed header
The indicator flags specify which compressed fields are present in
the header, whilst the compressed fields contain enough information
to transmit each field from the compressor to the decompressor.
In contrast, the headers generated by the full EPIC scheme do not
distinguish between compressed headers and indicator flags:
+--------------------+--------------------+---
| Compressed Field 1 | Compressed Field 2 |...
+--------------------+--------------------+---
Figure 2 : Structure of an EPIC compressed header
Rather than prefix the compressed header with explicit indicator
flags, EPIC reserves certain bit patterns in each compressed field
to indicate whether or not further compressed fields follow. This
approach is very efficient because the probability that further
compressed fields are needed may be low, in which case only a few
bit patterns need be reserved to indicate their presence.
4. Worked example for TCP/IP compression
The key difference between EPIC and EPIC-LITE can be illustrated
effectively by a worked example. Suppose that the schemes are used
to compress TCP/IP headers, and for simplicity assume that there is
Price et al. [PAGE 3]
INTERNET-DRAFT Enhanced TCP/IP Compression for ROHC 9 July, 2001
only one context and no robustness (i.e. no context identifier, no
CRC checksum and no sequence number in the compressed packet).
The only information required in every compressed header is the TCP
Checksum, which must be passed through untouched to preserve end-to-
end integrity. Thus EPIC-LITE can compress each header down to a
minimum of 3 octets as shown below:
+---+---+---+---+---+---+---+---+
| 0 X X X X X X X |
+---+---+---+---+---+---+---+---+
| |
+ TCP Checksum + Base headers
| |
+---+---+---+---+---+---+---+---+
+---+---+---+---+---+---+---+---+
| 1 X X X X X X X |
+---+---+---+---+---+---+---+---+
| |
+ TCP Checksum +
| | Extension headers
+---+---+---+---+---+---+---+---+
: :
/ Extension Fields /
: :
+---+---+---+---+---+---+---+---+
Figure 3 : Compressed TCP/IP headers using EPIC-LITE
The base headers contain 2 octets for the TCP Checksum, plus an
additional octet to hold an indicator flag to distinguish between
base headers and extension headers. The remaining bits in the first
octet are not needed, although they can be filled with sequence
number or CRC to improve robustness if desired.
In contrast, EPIC only requires 2 octets for the majority of the
base headers. The TCP Checksum values 0x0000 through to 0xDFDF
inclusive are carried using 2 octets as shown below:
+---+---+---+---+---+---+---+---+
| 0 0 0 0 0 0 0 0 | Base header
+---+---+---+---+---+---+---+---+
| 0 0 0 0 0 0 0 0 | (Checksum value 0x0000)
+---+---+---+---+---+---+---+---+
: :
: :
: :
+---+---+---+---+---+---+---+---+
| 1 1 0 1 1 1 1 1 | Base header
+---+---+---+---+---+---+---+---+
| 1 1 0 1 1 1 1 0 | (Checksum value 0xDFDF)
+---+---+---+---+---+---+---+---+
Price et al. [PAGE 4]
INTERNET-DRAFT Enhanced TCP/IP Compression for ROHC 9 July, 2001
The remaining checksum values 0xDFE0 through to 0xFFFF must be
carried using 3 octets as illustrated below:
+---+---+---+---+---+---+---+---+
| 1 1 0 1 1 1 1 1 |
+---+---+---+---+---+---+---+---+ Base header
| 1 1 0 1 1 1 1 1 |
+---+---+---+---+---+---+---+---+ (Checksum value 0xDFE0)
| 0 0 0 0 0 0 0 0 |
+---+---+---+---+---+---+---+---+
: :
: :
: :
+---+---+---+---+---+---+---+---+
| 1 1 0 1 1 1 1 1 |
+---+---+---+---+---+---+---+---+ Base header
| 1 1 1 1 1 1 1 1 |
+---+---+---+---+---+---+---+---+ (Checksum value 0xFFFF)
| 0 0 1 0 0 0 0 0 |
+---+---+---+---+---+---+---+---+
Finally, the remaining bit patterns are reserved for extension
headers and for the ROHC framework:
+---+---+---+---+---+---+---+---+
| 1 1 0 1 1 1 1 1 |
+---+---+---+---+---+---+---+---+
| 1 1 1 1 1 1 1 1 |
+---+---+---+---+---+---+---+---+
| 0 0 1 0 0 0 0 1 | Extension headers
+---+---+---+---+---+---+---+---+
: :
/ Extension Fields /
: :
+---+---+---+---+---+---+---+---+
Figure 4 : Compressed TCP/IP headers using EPIC
Note that the exact structure of the compressed headers for both
schemes depends on the input code defined in Chapter 4 of [EPIC-
LITE].
For a well-behaved TCP flow such as an FTP file transfer, the
average size of the compressed headers is just over 3 octets for
EPIC-LITE and just over 2 octets for the full version of EPIC.
5. Changes required to implement EPIC
This chapter describes the delta changes to [EPIC-LITE] required to
implement the full version of EPIC. Note that only changes to the
offline processing section (Appendix A.3) are required.
Price et al. [PAGE 5]
INTERNET-DRAFT Enhanced TCP/IP Compression for ROHC 9 July, 2001
The only procedure that must be modified is BUILD-FLAGS, which
determines the indicator flags for each compressed header format.
The new version of this procedure uses the following list variables:
P_list[] A list containing the probability that each
compressed header format will occur
N_list[] A list containing the number of bits required by
each compressed header format (excluding the
indicator flags)
listpointer1[] A list of pointers into P_list and N_list
listpointer2[] A list of pointers into P_list and N_list
listpointer3[] A list of pointers into P_list and N_list
list_split[] A list of integers
The new version of the procedure is given below:
procedure BUILD-FLAGS (encoding_name)
Sort P_list into ascending order (preserving the original order
where ties are encountered). Reorder N_list using the same
reordering as applied to P_list.
if compressor_state <> "CO" then npatterns = 2^bit_alignment
u = 0
v = max_formats
w = max_formats
do
if (((w = v) or (P_list[u] <= P_list[v])) and u <
max_formats) then chosen = 0 else chosen = 1
if chosen = 0 then base = u else base = v
if N_list[base] mod (2^bit_alignment) = 0 then
P_list[w] = P_list[base] * (2^bit_alignment)
N_list[w] = N_list[base] / (2^bit_alignment)
listpointer1[base] = w
if chosen = 0 then u = u + 1 else v = v + 1
else if N_list[base] > 2^bit_alignment then
P_list[w] = P_list[base] * (2^bit_alignment)
N_list[w] = floor(N_list[base] / (2^bit_alignment))
N_list[base] = N_list[base] mod (2^bit_alignment)
listpointer1[base] = w
else
Price et al. [PAGE 6]
INTERNET-DRAFT Enhanced TCP/IP Compression for ROHC 9 July, 2001
do
P_list[w] = P_list[w] + P_list[base] * N_list[base]
N_list[w] = N_list[w] + N_list[base]
listpointer2[base] = w
if chosen = 0 then u = u + 1 else v = v + 1
if (((w = v) or (P_list[u] <= P_list[v])) and u <
max_formats) then chosen = 0 else chosen = 1
if chosen = 0 then base = u else base = v
loop until (N_list[w] >= (2^bit_alignment))
if (N_list[w] = (2^bit_alignment)) then
listpointer3[base] = w
if chosen = 0 then u = u + 1 else v = v + 1
else
listpointer3[base] = w
list_split[base] = (2^bit_alignment) - N_list[w] +
N_list[base]
N_list[base] = N_list[w] - (2^bit_alignment)
end if
N_list[w] = 1
end if
w = w + 1
loop until u = max_formats and v = w - 1
cumulative_N = 0
for w = 0 to max_formats รป 1 do
totallength1 = 1
z = listpointer1[w]
min_N = cumulative_N
max_N = cumulative_N + N_list[w]
count = 1
while (listpointer1[z] > 0) do
totallength3 = totallength1
x = z
min_N = min_N + list_split[z] * count
while (listpointer3[x] > 0) do
totallength3 = 1 + totallength3
Price et al. [PAGE 7]
INTERNET-DRAFT Enhanced TCP/IP Compression for ROHC 9 July, 2001
x = listpointer3[x]
end while
if (totallength3 > previouslength3) then
code[totallength3] = min_N
end if
previouslength3 = totallength3
totallength2 = totallength1
x = z
max_N = max_N - ((max_N - min_N) mod (2^bit_alignment)) *
count
while (listpointer2[x] > 0) do
totallength2 = 1 + totallength2
x = listpointer2[x]
end while
if (totallength2 < previouslength2) then
code[previouslength2] = max_N
end if
previouslength2 = totallength2
totallength1 = 1 + totallength1
z = listpointer1[z]
count = count * (2^bit_alignment)
end while
cumulative_N = cumulative_N + N_list[w]
end loop
length = 1
flags[0] = 0
do
do
length = length + 1
loop until code[length] > 0
flags[code[length]] = flags[code[old_length]] +
str(length - old_length, 0)
old_length = length
loop
end BUILD-FLAGS
6. Statement of optimal efficiency
An important property of the compressed headers built by EPIC is
that they are optimally efficient. This means that the average
compressed header size of EPIC is provably the minimum possible for
Price et al. [PAGE 8]
INTERNET-DRAFT Enhanced TCP/IP Compression for ROHC 9 July, 2001
the chosen protocol stack. The precise statement of optimal
efficiency is given below:
"If every compressed header format specified by EPIC is used with
the claimed probability, and if the distribution of headers using
each format is uniform, then the EPIC compressed headers are
optimally efficient for the chosen level of robustness and bit
alignment".
Note that the two caveats in the statement just ensure that the
input code is programmed correctly for the protocol stack it is
compressing. If the input to EPIC states that Field 1 will need
LSB(4,0) encoding for 20% of the time then optimal efficiency is
only achieved if this really is the case. If the probabilities
specified in the code do not match the probabilities for the header
stream being compressed then the efficiency will not be optimal;
however the closer the match the better the compression ratio.
7. Security Considerations
EPIC generates compressed header formats for direct use in ROHC
profiles. Consequently the security considerations for EPIC match
those of [ROHC].
8. Acknowledgements
Header compression schemes from [ROHC] have been important sources of
ideas and knowledge. Basic Huffman encoding [HUFF] was enhanced for
the specific tasks of robust, efficient header compression.
Thanks to
Carsten Bormann (cabo@tzi.org)
Christian Schmidt (christian.schmidt@icn.siemens.de)
Max Riegel (maximilian.riegel@icn.siemens.de)
for valuable input and review.
9. Intellectual Property Considerations
This proposal in is full conformity with [RFC-2026].
Siemens may have patent rights on technology described in this
document which employees of Siemens contribute for use in IETF
standards discussions. In relation to any IETF standard incorporating
any such technology, Siemens hereby agrees to license on fair,
reasonable and non-discriminatory terms, based on reciprocity, any
patent claims it owns covering such technology, to the extent such
technology is essential to comply with such standard.
10. References
[ROHC] "RObust Header Compression (ROHC)", Carsten Bormann et
al, RFC3095, Internet Engineering Task Force, July 2001
Price et al. [PAGE 9]
INTERNET-DRAFT Enhanced TCP/IP Compression for ROHC 9 July, 2001
[EPIC-LITE] "TCP/IP Compression for ROHC", Richard Price et al,
<draft-ietf-rohc-tcp-epic-01.txt>, Internet Engineering
Task Force, July 9, 2001
[HUFF] "The Data Compression Book", Mark Nelson and Jean-Loup
Gailly, M&T Books, 1995
[RFC-1144] "Compressing TCP/IP Headers for Low-Speed Serial
Links", V. Jacobson, Internet Engineering Task Force,
February 1990
[RFC-1951] "DEFLATE Compressed Data Format Specification version
1.3", P. Deutsch, Internet Engineering Task Force, May
1996
[RFC-2026] "The Internet Standards Process - Revision 3", Scott
Bradner, Internet Engineering Task Force, October 1996
[RFC-2119] "Key words for use in RFCs to Indicate Requirement
Levels", Scott Bradner, Internet Engineering Task
Force, March 1997
11. Authors' Addresses
Richard Price Tel: +44 1794 833681
Email: richard.price@roke.co.uk
Robert Hancock Tel: +44 1794 833601
Email: robert.hancock@roke.co.uk
Stephen McCann Tel: +44 1794 833341
Email: stephen.mccann@roke.co.uk
Mark A West Tel: +44 1794 833311
Email: mark.a.west@roke.co.uk
Abigail Surtees Tel: +44 1794 833131
Email: abigail.surtees@roke.co.uk
Paul Ollis Tel: +44 1794 833168
Email: paul.ollis@roke.co.uk
Roke Manor Research Ltd
Romsey, Hants, SO51 0ZN
United Kingdom
Price et al. [PAGE 10]