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 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: for the basic TCP/IP profile 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, , 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]