Network Working Group R. Price Internet-Draft R. Hancock Expires: August 2, 2002 S. McCann A. Surtees P. Ollis M. West Siemens/Roke Manor February 2002 Framework for EPIC-LITE draft-ietf-rohc-epic-lite-01.txt Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. 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 Internet-Draft will expire on August 2, 2002. Copyright Notice Copyright (C) The Internet Society (2002). All Rights Reserved. Abstract This draft describes the framework of the Efficient Protocol Independent Compression (EPIC-LITE) scheme. The RObust Header Compression ROHC [1] 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. Price, et al. Expires August 2, 2002 [Page 1] Internet-Draft Framework for EPIC-LITE February 2002 EPIC-LITE extends the basic ROHC framework by introducing a BNF-based input language that simplifies the creation of new ROHC [1] profiles. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . 8 2. Terminology . . . . . . . . . . . . . . . . . . . . . . 8 3. The EPIC-LITE framework for generating new ROHC profiles 10 3.1 Structure of the EPIC-LITE compressed headers . . . . . 10 3.2 Compression and decompression procedures . . . . . . . . 11 3.3 BNF input language for creating new ROHC profiles . . . 14 3.4 Huffman compression . . . . . . . . . . . . . . . . . . 15 4. Overview of the BNF input language for EPIC-LITE . . . . 16 4.1 Information stored at compressor and decompressor . . . 18 4.2 Generated data . . . . . . . . . . . . . . . . . . . . . 19 5. Library of EPIC-LITE encoding methods . . . . . . . . . 20 5.1 STATIC . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.2 IRREGULAR . . . . . . . . . . . . . . . . . . . . . . . 21 5.2.1 IRREGULAR-PADDED . . . . . . . . . . . . . . . . . . . . 21 5.3 VALUE . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.4 LSB . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.5 UNCOMPRESSED . . . . . . . . . . . . . . . . . . . . . . 22 5.6 STACK encoding methods . . . . . . . . . . . . . . . . . 23 5.6.1 STACK-TO-CONTROL . . . . . . . . . . . . . . . . . . . . 23 5.6.2 STACK-FROM-CONTROL . . . . . . . . . . . . . . . . . . . 23 5.6.3 STACK-PUSH-MSN . . . . . . . . . . . . . . . . . . . . . 23 5.6.4 STACK-POP-MSN . . . . . . . . . . . . . . . . . . . . . 24 5.6.5 STACK-ROTATE . . . . . . . . . . . . . . . . . . . . . . 24 5.7 INFERRED encoding methods . . . . . . . . . . . . . . . 24 5.7.1 INFERRED-TRANSLATE . . . . . . . . . . . . . . . . . . . 24 5.7.2 INFERRED-SIZE . . . . . . . . . . . . . . . . . . . . . 25 5.7.3 INFERRED-OFFSET . . . . . . . . . . . . . . . . . . . . 25 5.7.4 INFERRED-IP-CHECKSUM . . . . . . . . . . . . . . . . . . 26 5.8 NBO . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.9 SCALE . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.10 OPTIONAL . . . . . . . . . . . . . . . . . . . . . . . . 27 5.11 MANDATORY . . . . . . . . . . . . . . . . . . . . . . . 28 5.12 CONTEXT . . . . . . . . . . . . . . . . . . . . . . . . 28 5.13 LIST . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.13.1 LIST-NEXT . . . . . . . . . . . . . . . . . . . . . . . 30 5.14 FLAG encoding methods . . . . . . . . . . . . . . . . . 31 5.14.1 N flag . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.14.2 U flag . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.15 FORMAT . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.16 CRC . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.17 MSN encoding methods . . . . . . . . . . . . . . . . . . 34 5.17.1 MSN-LSB . . . . . . . . . . . . . . . . . . . . . . . . 34 5.17.2 MSN-IRREGULAR . . . . . . . . . . . . . . . . . . . . . 34 Price, et al. Expires August 2, 2002 [Page 2] Internet-Draft Framework for EPIC-LITE February 2002 5.17.3 SET-MSN . . . . . . . . . . . . . . . . . . . . . . . . 34 6. Creating a new ROHC profile . . . . . . . . . . . . . . 35 6.1 Profile identifier . . . . . . . . . . . . . . . . . . . 35 6.2 Maximum number of header formats . . . . . . . . . . . . 35 6.3 Control of header alignment . . . . . . . . . . . . . . 36 6.4 Compressed header formats . . . . . . . . . . . . . . . 36 7. Security considerations . . . . . . . . . . . . . . . . 37 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . 37 References . . . . . . . . . . . . . . . . . . . . . . . 37 Authors' Addresses . . . . . . . . . . . . . . . . . . . 38 A. EPIC-LITE compressor and decompressor . . . . . . . . . 39 A.1 Compressor . . . . . . . . . . . . . . . . . . . . . . . 49 A.1.1 Step 1: Packet classification . . . . . . . . . . . . . 49 A.1.2 Step 2: Using the state machine . . . . . . . . . . . . 50 A.1.3 Step 3: Compressing the header . . . . . . . . . . . . . 50 A.1.4 Step 4: Determining the indicator flags . . . . . . . . 53 A.1.5 Step 5: Encapsulating in ROHC packet . . . . . . . . . . 56 A.2 Decompressor . . . . . . . . . . . . . . . . . . . . . . 56 A.2.1 Step 1: Decapsulating from ROHC packet . . . . . . . . . 56 A.2.2 Step 2: Running the state machine . . . . . . . . . . . 56 A.2.3 Step 3: Reading the indicator flags . . . . . . . . . . 56 A.2.4 Step 4: Decompressing the fields . . . . . . . . . . . . 59 A.2.5 Step 5: Verifying correct decompression . . . . . . . . 60 A.3 Offline processing . . . . . . . . . . . . . . . . . . . 61 A.3.1 Step 1: Building the header formats . . . . . . . . . . 61 A.3.2 Step 2: Generating the indicator flags . . . . . . . . . 66 A.4 Library of methods . . . . . . . . . . . . . . . . . . . 73 A.4.1 STATIC . . . . . . . . . . . . . . . . . . . . . . . . . 73 A.4.2 IRREGULAR . . . . . . . . . . . . . . . . . . . . . . . 74 A.4.2.1 IRREGULAR-PADDED . . . . . . . . . . . . . . . . . . . . 75 A.4.3 VALUE . . . . . . . . . . . . . . . . . . . . . . . . . 76 A.4.4 LSB . . . . . . . . . . . . . . . . . . . . . . . . . . 77 A.4.5 UNCOMPRESSED . . . . . . . . . . . . . . . . . . . . . . 79 A.4.6 STACK encoding methods . . . . . . . . . . . . . . . . . 80 A.4.6.1 STACK-TO-CONTROL . . . . . . . . . . . . . . . . . . . . 80 A.4.6.2 STACK-FROM-CONTROL . . . . . . . . . . . . . . . . . . . 81 A.4.6.3 STACK-PUSH-MSN . . . . . . . . . . . . . . . . . . . . . 82 A.4.6.4 STACK-POP-MSN . . . . . . . . . . . . . . . . . . . . . 83 A.4.6.5 STACK-ROTATE . . . . . . . . . . . . . . . . . . . . . . 84 A.4.7 INFERRED encoding methods . . . . . . . . . . . . . . . 84 A.4.7.1 INFERRED-TRANSLATE . . . . . . . . . . . . . . . . . . . 84 A.4.7.2 INFERRED-SIZE . . . . . . . . . . . . . . . . . . . . . 86 A.4.7.3 INFERRED-OFFSET . . . . . . . . . . . . . . . . . . . . 86 A.4.7.4 INFERRED-IP-CHECKSUM . . . . . . . . . . . . . . . . . . 87 A.4.8 NBO . . . . . . . . . . . . . . . . . . . . . . . . . . 88 A.4.9 SCALE . . . . . . . . . . . . . . . . . . . . . . . . . 90 A.4.10 OPTIONAL . . . . . . . . . . . . . . . . . . . . . . . . 91 A.4.11 MANDATORY . . . . . . . . . . . . . . . . . . . . . . . 92 Price, et al. Expires August 2, 2002 [Page 3] Internet-Draft Framework for EPIC-LITE February 2002 A.4.12 CONTEXT . . . . . . . . . . . . . . . . . . . . . . . . 93 A.4.13 LIST . . . . . . . . . . . . . . . . . . . . . . . . . . 94 A.4.13.1 LIST-NEXT . . . . . . . . . . . . . . . . . . . . . . . 98 A.4.14 FLAG encoding methods . . . . . . . . . . . . . . . . . 101 A.4.14.1 N . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 A.4.14.2 U . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 A.4.15 FORMAT . . . . . . . . . . . . . . . . . . . . . . . . . 103 A.4.16 CRC . . . . . . . . . . . . . . . . . . . . . . . . . . 106 A.4.16.1 MSN-LSB . . . . . . . . . . . . . . . . . . . . . . . . 106 A.4.16.2 MSN-IRREGULAR . . . . . . . . . . . . . . . . . . . . . 109 A.4.16.3 SET-MSN . . . . . . . . . . . . . . . . . . . . . . . . 110 A.5 ABNF description of the input language . . . . . . . . . 110 Full Copyright Statement . . . . . . . . . . . . . . . . 113 Price, et al. Expires August 2, 2002 [Page 4] Internet-Draft Framework for EPIC-LITE February 2002 1. Introduction This document describes a plug-in extension for the ROHC [1] framework which simplifies the creation of new compression profiles. The Efficient Protocol Independent Compression (EPIC-LITE) scheme for generating new ROHC profiles takes as its input a choice of one or more compression techniques for each field in the protocol stack to be compressed. Using this input EPIC-LITE derives a set of compressed header formats that can be used to quickly and efficiently compress and decompress headers. Chapter 2 explains some of the terminology used in the draft. Chapter 3 gives an overview of the EPIC-LITE scheme. Chapter 4 describes the language used by EPIC-LITE to create new profiles. Chapter 5 considers the basic techniques available in the EPIC- LITE library of compression routines. Chapter 6 specifies the parameters used to define a ROHC [1] profile. Appendix A gives a normative description of EPIC-LITE in pseudocode. 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 [5]. Profile A ROHC [1] profile is a description of how to compress a certain protocol stack over a certain type of link. Each profile includes one or more sets of compressed header formats and a state machine to control the compressor and the decompressor. Context The context is memory which stores one or more previous values of fields in the uncompressed header. The compressor and decompressor both maintain a copy of the context, and fields can be compressed relative to their stored values for better Price, et al. Expires August 2, 2002 [Page 5] Internet-Draft Framework for EPIC-LITE February 2002 compression efficiency. Compressed header format A compressed header format describes how to compress each field in the chosen protocol stack. It consists of two parts: a bit pattern to indicate to the decompressor which format is being used, followed by a list of the compressed versions of each field. Encoding method An encoding method is a procedure for compressing fields. Examples include STATIC encoding (field is the same as the context), INFERRED-OFFSET encoding (field is calculated at the decompressor) and IRREGULAR encoding (field must be transmitted in full). Indicator flags Each EPIC-LITE compressed packet contains a set of indicator flags. The flags are placed at the front of the packet as a single bit pattern, and indicate to the decompressor exactly which encoding method has been applied to which field. Set of compressed header formats A complete set of compressed header formats uses up all of the indicator bit patterns available at the start of the compressed header. A profile may have several sets of compressed header formats available, but only one set can be in use at a given time. Library of encoding methods The library of encoding methods contains a number of commonly used procedures that can be called to compress fields in the chosen protocol stack. More encoding methods can be added to the library if they are needed. BNF (Backus Naur Form) BNF is a "metasyntax" commonly used to describe the syntax of protocols and languages. BNF input language EPIC-LITE describes a new ROHC profile using a simple BNF-based input language. The BNF description of the ROHC profile assigns one or more encoding methods to each field in the chosen stack. Price, et al. Expires August 2, 2002 [Page 6] Internet-Draft Framework for EPIC-LITE February 2002 Control data The term 'control data' refers to any data passed between the compressor and decompressor, that is not part of the uncompressed header. An example of control data is the header checksum calculated by EPIC-LITE over the uncompressed header to ensure robustness against bit errors and dropped packets. 3. The EPIC-LITE framework for generating new ROHC profiles This chapter outlines the EPIC-LITE framework for the creation of new ROHC profiles. 3.1 Structure of the EPIC-LITE compressed headers Each compressed header is divided into two distinct parts: the indicator flags and the compressed fields as 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 how every field in the uncompressed header has been compressed, whilst the compressed fields contain enough information to transmit each field from the compressor to the decompressor. This information might be the entire uncompressed field, it might be LSBs (Least Significant Bits) of the uncompressed field etc. Note that for simplicity EPIC-LITE always places the indicator flags at the front of the compressed header followed by each complete compressed field in turn. As for RFC-1144 [3] the compressed fields are in reverse order compared to the uncompressed header (this is a useful trick to speed up parsing at the decompressor). Unlike other compression schemes, the header formats used by EPIC- LITE are not designed by hand but instead are generated automatically using a special algorithm. This means that EPIC-LITE can be applied to any protocol stack provided that it has been correctly programmed using the BNF-based input language described in Section 3.3. Price, et al. Expires August 2, 2002 [Page 7] Internet-Draft Framework for EPIC-LITE February 2002 3.2 Compression and decompression procedures Figure 2 illustrates the processing which is done by EPIC-LITE for each header to be compressed and decompressed. Note that references are given to pseudocode in Appendix A which describes each of the stages explicitly. --------------------------------------------------------------------- Price, et al. Expires August 2, 2002 [Page 8] Internet-Draft Framework for EPIC-LITE February 2002 | Uncompressed packet Uncompressed packet ^ v | +-------------------+ +-------------------+ | Selecting the | | Verifying correct | | context | | decompression | | (Section A.1.1) | | (Section A.2.5) | +-------------------+ +-------------------+ | ^ | Uncompressed packet Uncompressed packet | v Context | +-------------------+ +-------------------+ | Running the | | Decompressing | | state machine | | the fields | | (Section A.1.2) | | (Section A.2.4) | +-------------------+ +-------------------+ | Set of header formats Chosen format ^ | Uncompressed packet Compressed fields | v Context Context | +-------------------+ +-------------------+ | Compressing | | Reading the | | the fields | | indicator flags | | (Section A.1.3) | | (Section A.2.3) | +-------------------+ +-------------------+ | ^ | Chosen format Compressed header | v Compressed fields Context | +-------------------+ +-------------------+ | Determining the | | Running the | | indicator flags | | state machine | | (Section A.1.4) | | (Section A.2.2) | +-------------------+ +-------------------+ | ^ | Compressed header Compressed header | v Context | +-------------------+ +-------------------+ | Encapsulating in | |Decapsulating from | | ROHC packet | ---------------> | ROHC packet | | (Section A.1.5) | ROHC | (Section A.2.1) | +-------------------+ packet +-------------------+ Figure 2: EPIC-LITE compression/decompression --------------------------------------------------------------------- Each of these steps is described in more detail below. At the compressor: Price, et al. Expires August 2, 2002 [Page 9] Internet-Draft Framework for EPIC-LITE February 2002 Step 1: The input to the compressor is simply an uncompressed packet (with known length). In order to compress the packet it is first necessary to classify it and choose the context relative to which the packet will be compressed. If no suitable context is available then an existing context must be overwritten. Step 2: Once the context has been chosen the compressor knows which ROHC [1] profile will be used to compress the packet. In particular it can run the state machine that determines which set of header formats will be used to compress the packet (IR, IR-DYN or CO). Step 3: Given the uncompressed packet and a set of compressed header formats, the compressor can choose a header format to robustly carry this information to the decompressor using as few bits as possible. Note that EPIC-LITE chooses the header format simultaneously with compressing the header to improve the overall speed of compression. Step 4: Each compressed header format has a unique set of indicator flags that communicate to the decompressor which format is in use. The compressor determines these indicator flags and appends them to the front of the compressed fields to create a compressed header. Step 5: Once the compressed header has been calculated, the compressor encapsulates it within a ROHC packet by adding 0 or more octets of context identifier together with any padding and segmentation that is required. At the decompressor: Step 1: The input to the decompressor is a ROHC packet. From this packet the decompressor can determine the attached context identifier, which in turn specifies the context relative to which the packet should be decompressed. Step 2: Once the context has been identified, the decompressor can run the state machine to determine if the packet may be decompressed. Step 3: The decompressor then reads the indicator flags in the header to determine which compressed header format has been used. This allows the compressed value of each field to be extracted. Step 4: Using the compressed value of each field and the context, the decompressor can apply the encoding methods to reconstruct the uncompressed packet. Note that fields are decompressed in reverse order to compression (this ensures that fields which are inferred from other field values are reconstructed correctly). Step 5: Finally, the decompressor verifies that correct decompression Price, et al. Expires August 2, 2002 [Page 10] Internet-Draft Framework for EPIC-LITE February 2002 has occurred by applying the header checksum. If the packet is successfully verified then it can be forwarded. 3.3 BNF input language for creating new ROHC profiles EPIC-LITE is a protocol-independent compression scheme because it can generate new compressed header formats automatically using a special algorithm. In order for EPIC-LITE to compress a new protocol stack however, it must be given a description of how the stack behaves. EPIC-LITE uses a simple BNF-based input language for the fast creation of new compression schemes. The language is designed to be easy to use without detailed knowledge of the mathematics underlying EPIC-LITE. The only information required to create a new ROHC [1] profile using EPIC-LITE is a description of how the chosen protocol stack behaves. EPIC-LITE converts the input into one or more sets of compressed header formats that can be used by a ROHC [1] compressor and decompressor. As with all version of BNF the input language has a rule-based structure, which makes it easy to build new profiles out of existing ones (e.g. when adding new layers to a protocol stack). Figure 3 describes the process of building a set of compressed header formats from the BNF input, which is done once only and the results stored at the compressor and decompressor. References are given to pseudocode in Appendix A which describes the various stages explicitly. Price, et al. Expires August 2, 2002 [Page 11] Internet-Draft Framework for EPIC-LITE February 2002 --------------------------------------------------------------------- +-----------------------+ | Input Stage 1: | | Resolve input | | into set of compressed| | header formats | | (Section A.3.1) | +-----------------------+ | v +-----------------------+ | Input Stage 2: | | Run Huffman algorithm | | to generate flags | | (Section A.3.2) | +-----------------------+ Figure 3: Building EPIC-LITE compressed header formats --------------------------------------------------------------------- Note that since the EPIC-LITE compressed header formats can be generated offline, the fact that profiles are specified using an input language does not affect the processing requirements of compression and decompression. 3.4 Huffman compression Huffman compression [2] is a well known technique used in many popular compression schemes. EPIC-LITE uses ordinary Huffman compression to generate a new set of compressed header formats. The basic Huffman algorithm is designed to compress an arbitrary stream of characters from a character set such as ASCII. The idea is to create a new set of compressed characters, where each normal character maps onto a compressed character and vice versa. Common characters are given shorter compressed equivalents than rarely used characters, reducing the average size of the data stream. EPIC-LITE uses Huffman compression to generate the indicator flags for each compressed header format. Each format is treated as one character in the Huffman character set, so more common compressed header formats are indicated using fewer bits than rare header formats. The most commonly used header format is often indicated by the presence of a single "0" flag at the front of the compressed header. Price, et al. Expires August 2, 2002 [Page 12] Internet-Draft Framework for EPIC-LITE February 2002 The following chapters describe the mechanisms of EPIC-LITE in greater detail. 4. Overview of the BNF input language for EPIC-LITE This chapter describes the BNF-based input language provided by EPIC- LITE for the creation of new ROHC [1] profiles. The language is designed to be flexible but at the same time easy to use without detailed knowledge of the mathematics underlying EPIC- LITE. The only requirement for writing an efficient EPIC-LITE profile is a description of how the relevant protocol stack behaves. As with all versions of BNF, the description of the protocol is built up using the following two constructs: New BNF rule A new encoding method is created from existing ones by writing a new BNF rule for the encoding method Set of choices One or more encoding methods can be assigned to a given field by using the choice ("|") operator EPIC-LITE also contains a library of fundamental encoding methods (STATIC compression, LSB compression etc.) as described in Chapter 5. The BNF description of how to compress a new protocol stack always resolves into a selection of these fundamental encoding methods. The exact syntax of the BNF-based input language can itself be described using an existing version of BNF. A suitable variant is "Augmented BNF" (ABNF) as described in RFC-2234 [6]. For example, in ABNF the syntax for defining a new encoding method in terms of existing ones is as follows: = "=" 1*( ) = *( "|" ) Each instance of calls an encoding method that converts a certain number of uncompressed bits into a certain number of compressed bits. Note also that is white space, used to delimit the various encoding methods. A complete description of the BNF-based input language can be found Price, et al. Expires August 2, 2002 [Page 13] Internet-Draft Framework for EPIC-LITE February 2002 in Appendix A.5. An example of how to create a new encoding method is given below. An encoding method known as IPv6_Header is constructed from the basic encoding methods available in the library. This new method is designed to compress an entire IPv6 header. IPv6_Header_co = Version Traffic_Class_co ECT_Flag_co CE_Flag Flow_Label_co Payload_Length Next_Header Hop_Limit_co Source_Address_co Destination_Address_co Version = VALUE(4,6,100%) Traffic_Class = STATIC(100%) ECT_Flag = STATIC(100%) CE_Flag = VALUE(1,0,99%) | VALUE(1,1,1%) Flow_Label = STATIC(100%) Payload_Length = INFERRED-SIZE(16,288) Next_Header = STACK-TO-CONTROL(8) Hop_Limit = STATIC(100%) Source_Address = STATIC(100%) Destination_Address = STATIC(100%) Each field in the IPv6 header is given a choice of possible encoding methods. If an encoding method is not implicitly used 100% of the time for that field (e.g. INFERRED-SIZE) then one of the parameters is the probability that it will be used to encode the field in question. This is very important since EPIC-LITE ensures that common encoding methods require fewer bits to carry the compressed data than rarely used encoding methods. For optimal compression, the probability should equal the percentage Price, et al. Expires August 2, 2002 [Page 14] Internet-Draft Framework for EPIC-LITE February 2002 of time for which the encoding method is selected to compress the field. Note that there is no requirement for probabilities to add up to exactly 100%, as EPIC-LITE will automatically scale the probabilities by a constant factor if they do not. Note also that the BNF input language is designed to be both human- readable and machine-readable. If only one protocol stack needs to be compressed, the input language can simply be converted by hand directly to an implementation. However, since the input language provides a complete description of the protocol stack to be compressed, it is possible to compress headers using only the information contained in the BNF description and without any additional knowledge of the protocol stack. This means that it is possible to implement a protocol-independent compressor that can download a new ROHC [1] profile described in the BNF input language and immediately use it to compress headers. 4.1 Information stored at compressor and decompressor Any ROHC compressor maintains a number of contexts as described in Section 5.1.3 of ROHC [1]. Each context at the compressor and decompressor includes the following: Compression profile: Compressed header formats State machine Field values: One or more previously processed headers The compression profile describes how to compress a certain protocol stack over a certain type of link. It includes the profile parameters that describe the set of compressed header formats (as discussed in Chapter 6) and additionally records the current state of the state machine. The compressor also stores one or more sets of field values from previously processed headers. Each new header can be compressed relative to these field values to improve the compression ratio. For the profiles generated using EPIC-LITE, the compressor and decompressor maintain a context value for some or all of the "field encodings" specified in the BNF description (recall that a field encoding is a set of one or more encoding methods that can be used to compress a given field). This context value is taken from the last header to be successfully compressed or decompressed. Furthermore, in order to provide robustness the compressor can maintain more than one context value for each field. These values represent the r most likely candidates values for the context at the Price, et al. Expires August 2, 2002 [Page 15] Internet-Draft Framework for EPIC-LITE February 2002 decompressor, given that bit errors and dropped packets may prevent the compressor from being 100% certain exactly which values are contained in the decompressor context. EPIC-LITE ensures that the compressed header contains enough information so that the uncompressed header can be extracted no matter which one of the compressor context values is actually stored at the decompressor. The only problem arises if the decompressor has a context value that does not belong to the set of values stored at the compressor; this situation is detected by a checksum over the uncompressed header and the packet is discarded at the decompressor. If more than one value for a field is stored in the compressor context, some of the library encoding methods will automatically fail or only succeed under certain conditions. For example, STATIC encoding will fail and LSB encoding will only succeed if sufficient LSBs are sent to infer correct value of the field regardless of the precise value stored in the decompressor context. Note that the rules for extracting fields from the uncompressed header and updating the context values are given in Appendix A. The number of context values per field to be stored at the compressor is implementation-specific. Storing more values reduces the chance that the decompressor will have a context value different from any of the values stored at the compressor (which could cause the packet to be decompressed incorrectly). The trade-off is that the compressed header will be larger because it must contain enough information to decompress relative to any of the candidate context values. As an example, an implementation may choose to store the last r values of each field in the compressor context. In this case robustness is guaranteed against up to r - 1 consecutive dropped packets between the compressor and the decompressor. 4.2 Generated data There is some data that is passed from the compressor to the decompressor, but which is not present in the uncompressed header. This data communicates additional information that might be useful to the decompressor: for example a checksum over the uncompressed header to ensure correct decompression has occurred. This data may be generated by certain encoding methods and then added either to the uncompressed header to be compressed immediately or to the control data stack to be compressed later. Price, et al. Expires August 2, 2002 [Page 16] Internet-Draft Framework for EPIC-LITE February 2002 5. Library of EPIC-LITE encoding methods The ROHC [1] standard contains a number of different encoding methods (LSB encoding, scaled timestamp encoding, list-based compression etc.) for compressing header fields. EPIC-LITE treats these encoding methods as library functions to be called by the BNF input language when they are needed. The following library contains a wide range of basic encoding methods. Moreover new encoding methods can be added to the library as and when they are needed. Note that this chapter contains an informative description only. The normative pseudocode description of every encoding method can be found in Appendix A.4. The syntax of each encoding method is given using ABNF as defined in RFC-2234 [6]. Note that each of the encoding methods may have one or more parameters of the following type: A non-negative integer (specified as decimal, binary or hex). Binary values are prefixed by 0b and hex values are preceded by 0x. An integer (positive or negative) A non-negative integer used to indicate the length of the field being compressed A probability expressed as a percentage with at most 2 decimal places The name of another encoding method including all parameters The ABNF description of these parameters is found in Appendix A.5. 5.1 STATIC ABNF notation: "STATIC(" ")" The STATIC encoding method can be used when the header field does not change relative to the context. If a field is STATIC then no information concerning the field need be transmitted in the compressed header. Price, et al. Expires August 2, 2002 [Page 17] Internet-Draft Framework for EPIC-LITE February 2002 The only parameter for the STATIC encoding method is a probability that indicates how often the method will be used. Encoding methods with high probability values require fewer bits in the compressed header than encoding methods that are allocated low probability values. In general the probability should reflect as accurately as possible the chance that the field will be encoded as STATIC. 5.2 IRREGULAR ABNF notation: "IRREGULAR(" "," ")" The IRREGULAR encoding method is used when the field cannot be compressed relative to the context, and hence must be transmitted in full in the compressed header. The IRREGULAR encoding method has a length parameter to indicate the length of the field in bits and a probability that indicates how often it will be used. A modified version of IRREGULAR encoding is given below: 5.2.1 IRREGULAR-PADDED ABNF notation: "IRREGULAR-PADDED(" "," "," ")" The IRREGULAR-PADDED encoding method compresses any field that is large in terms of number of bits but has a small actual value (and hence the most significant bits are zero). The encoding method transmits a certain number of LSBs (Least Significant Bits) of the field. The first parameter gives the overall length of the field, whilst the next parameter specifies the number of LSBs to be transmitted in the compressed header. The bits not transmitted are all taken to be 0 by the decompressor. The probability gives an indication of how often IRREGULAR-PADDED will be used. The IRREGULAR-PADDED encoding method is useful for compressing fields that take small integer values with a high probability. 5.3 VALUE ABNF notation: "VALUE(" "," "," ")" Price, et al. Expires August 2, 2002 [Page 18] Internet-Draft Framework for EPIC-LITE February 2002 The VALUE encoding method can be used to transmit one particular value for a field. It is followed by parameters to indicate the length and integer value of the field as well as the probability of the field taking this value. 5.4 LSB ABNF notation: "LSB(" "," "," ")" The LSB encoding method compresses the field by transmitting only its LSBs (Least Significant Bits). The first parameter indicates the number of LSBs to transmit in the compressed header. The second parameter is the offset of the LSBs: it describes whether the decompressor should interpret the LSBs as increasing or decreasing the field value contained in its context. Again the probability indicates how often LSB encoding will be used. To illustrate how the second parameter works, suppose that k LSBs are transmitted with offset p. The decompressor uses these LSBs to replace the k LSBs of the value of this field stored in the context (val), and then adds or subtracts multiples of 2^k so that the new field value lies between (val - p) and (val - p + 2^k - 1). In particular, if p = 0 then the field value can only stay the same or increase. If p = -1 then it can only increase, whereas if p = 2^k then it can only decrease. Recall that for robustness the compressor can store r values for each field in its context. If this is the case then enough LSBs are transmitted so that the decompressor can reconstruct the correct field value, no matter which of the r values it has stored in its context. This is equivalent to Window-based LSB encoding as described in ROHC [1]. 5.5 UNCOMPRESSED ABNF notation: "UNCOMPRESSED(" "," "," "," ")" The UNCOMPRESSED encoding method transmits a field uncompressed without alteration. All uncompressed fields are transmitted as-is at the end of the compressed header. The UNCOMPRESSED encoding method differs from the IRREGULAR encoding method in that the size of the field is not fixed, but instead is Price, et al. Expires August 2, 2002 [Page 19] Internet-Draft Framework for EPIC-LITE February 2002 specified by a control field. The first parameter gives the length n of the control field: UNCOMPRESSED encoding obtains this control field simply by removing the first value (which should be n bits) from the control data stack. The next three parameters specify a divisor, multiplier and offset for the control field. These parameters scale the value of the control field so that it specifies the exact size of the UNCOMPRESSED field in bits. If the parameters are d, m and p respectively then: size of UNCOMPRESSED field = floor(control field value / d) * m + p UNCOMPRESSED encoding is usually used in conjunction with one of the STACK encoding methods, which write to the control data stack as explained below: 5.6 STACK encoding methods These methods are used to move values around for use by future encoding methods. They take as a parameter the number of bits to be transferred and always have 100% probability of being used. 5.6.1 STACK-TO-CONTROL ABNF notation: "STACK-TO-CONTROL(" ")" This encoding method takes the specified number of bits from the uncompressed header and transfers them to the control data stack. It does the reverse at the decompressor. 5.6.2 STACK-FROM-CONTROL ABNF notation: "STACK-FROM-CONTROL(" ")" This encoding method takes an item with the specified number of bits from the control data stack and transfers it to the uncompressed header. It does the reverse at the decompressor. 5.6.3 STACK-PUSH-MSN ABNF notation: "STACK-PUSH-MSN(" ")" The MSN (Master Sequence Number) is a width defined value that increases by one for each packet received at the compressor. Price, et al. Expires August 2, 2002 [Page 20] Internet-Draft Framework for EPIC-LITE February 2002 This encoding method copies the least significant specified number of bits of the MSN to the top of the control data stack. Conversely, it removes these bits at the decompressor. 5.6.4 STACK-POP-MSN ABNF notation: "STACK-POP-MSN(" ")" This encoding method removes the specified number of bits of the MSN from the uncompressed data or adds it at the decompressor. 5.6.5 STACK-ROTATE ABNF notation: "STACK-ROTATE(" "," ")" This encoding method rotates the top n items on the top control stack m times where n is the first parameter and m the second. A rotation of n items by 1 moves the nth element on the control stack to the top of the stack (and the top n-1 items down one place). 5.7 INFERRED encoding methods The following versions of INFERRED encoding are available: 5.7.1 INFERRED-TRANSLATE ABNF notation: "INFERRED-TRANSLATE(" "," *("," "," ) ")" The INFERRED-TRANSLATE encoding method translates a field value under a certain mapping. The first pair of parameters specifies the length of the field before and after the translation. This is followed by additional pairs of integers, representing the field value before and after it is translated. Note that the final field value at the compressor (or equivalently, the original field value at the decompressor) appears first in each pair. For example: INFERRED-TRANSLATE(8,16,41,0x86DD,4,0x0800) ; GRE Protocol The GRE Protocol field behaves in the same manner as the Next Header field in other extension headers, except that it indicates that the subsequent header is IPv6 or IPv4 using the values 0x86DD and 0x0800 instead of 41 and 4. The INFERRED-TRANSLATE encoding method can convert the standard values (as provided by LIST compression defined Price, et al. Expires August 2, 2002 [Page 21] Internet-Draft Framework for EPIC-LITE February 2002 in Section 5.11) into the values required by the GRE Protocol field. At the compressor, once the translation is complete the field is copied to the control data stack. At the decompressor the field is removed from the control data stack, translated and then added to the uncompressed data. 5.7.2 INFERRED-SIZE ABNF notation: "INFERRED-SIZE(" "," ")" The INFERRED-SIZE encoding method infers the value of a field from the size of the uncompressed packet. The first parameter specifies the uncompressed field length in bits, and the second parameter specifies the offset of the uncompressed packet size (i.e. the amount of packet which has already been compressed). If the INFERRED-SIZE field value is v, the offset is p and the total packet length after (but not including) the INFERRED- SIZE field is L then the following equation applies (assuming 8 bits in a byte): L = 8 * v + p 5.7.3 INFERRED-OFFSET ABNF notation: "INFERRED-OFFSET(" ")" The INFERRED-OFFSET encoding method compresses a field that usually has a constant offset relative to a certain base field. The parameter describes the length of the field to be compressed. The base field will already be on the control data stack - put there using one of the STACK methods. The encoding subtracts the base field from the field to be compressed and replaces the field value by these "offset" bits in the uncompressed header. The offset bits are then compressed by the next encoding method in the input code. For example, a typical sequence number can be compressed as follows: Price, et al. Expires August 2, 2002 [Page 22] Internet-Draft Framework for EPIC-LITE February 2002 STACK-PUSH-MSN(32) ; Put MSN on control stack INFERRED-OFFSET(32) ; Sequence Number STACK-POP-MSN(32) ; Remove MSN STATIC(99%) | ; Sequence Number offset LSB(8,-1,0.7%) | LSB(16,-1,0.2%) | IRREGULAR(32,0.1%) In this case the offset field is expected to change rarely and only by small amounts, and hence it is compressed using mainly STATIC and LSB encodings. 5.7.4 INFERRED-IP-CHECKSUM ABNF notation: "INFERRED-IP-CHECKSUM(" ")" This method is used for calculating the IP checksum. At the compressor it replaces the bits representing the IP checksum with "0" bits (these are a known distance from the beginning of this method). It then continues to compress using encoding_name. At the decompressor it decompresses encoding_name as usual. A 16-bit one's complement sum is then computed over the length of data which has been decompressed in this method and the result copied into the appropiate bits (at a fixed offset) in the header. 5.8 NBO ABNF notation: "NBO(" ")" The NBO encoding method may be used if there is a possibility that the following field will be in reverse byte order from the rest of the header, as is sometimes seen with the IP ID, for example. The method looks at the specified number of bits (typically 16 or 32) and, using a history, decides whether or not they are in network byte order. If they are it removes them from the stack, puts a 1-bit flag with the value "1" on the stack and replaces the original value. If the value is not in NBO it removes the bits, puts a flag with the value "0" on the stack and replaces the byte-swapped value. This method can be used prior to other methods, for example: Price, et al. Expires August 2, 2002 [Page 23] Internet-Draft Framework for EPIC-LITE February 2002 NBO (16) ; Check for network byte order STACK-PUSH-MSN(16) ; Put MSN on control stack INFERRED-OFFSET(16) ; IP ID STACK-POP-MSN(16) ; Remove MSN STATIC(80%) | ; IP ID offset LSB(5,-1,15%) | IRREGULAR(16,5%) STATIC(99%) | ; NBO flag IRREGULAR(1,1%) 5.9 SCALE ABNF notation: "SCALE(" ")" The SCALE encoding method is used for fields which change by a regular (usually large) amount every packet. The number of bits specified are removed and a suitable scale factor chosen. Three values each with the specified length are then replaced on the stack. If the original field has value v and the chosen scale is s then these values are: v / s = the scaled value of v when v is divided by s using integer arithmetic v mod s = the remainder when v is divided by s s = the scale value They are placed on the stack in the order above so that the next value to be compressed is the scale value. 5.10 OPTIONAL ABNF notation: "OPTIONAL(" ")" The OPTIONAL encoding method is used to compress fields that are optionally present in the uncompressed header. OPTIONAL encoding requires a 1 bit indicator flag to specify whether or not the optional field is present in the uncompressed header. Price, et al. Expires August 2, 2002 [Page 24] Internet-Draft Framework for EPIC-LITE February 2002 This flag is extracted from the control data stack. The value of the flag is added to the stack by another encoding method (such as STACK- TO-CONTROL or LIST). For example: STACK-TO-CONTROL(1) ; GRE Key flag OPTIONAL(KEY-ENCODING) ; GRE Key In this case the encoding method KEY-ENCODING is called to compress the GRE Key field, but only if the Key Flag is set to 1. If the Key Flag is set to 0 (indicating that the GRE Key is not present) then some padding bits of 0 may be added to the compressed header (the number of bits added is determined by the compressor - the compressor chooses a format for KEY-ENCODING, which though not used provides the number of bits with which to pad). If there is a U method encompassing the OPTIONAL method then the number of bits with which to pad is automatically zero. 5.11 MANDATORY ABNF notation: "MANDATORY(" ")" This encoding method may be used where another encoding method has appended a flag indicating the presence of a field in the uncompressed header. If the field is optionally present then the OPTIONAL encoding (above) may be used. If the field is always present then the MANDATORY encoding can be used. This checks that the value of the flag on the stack is 1 (indicating that the field is present). If the value of the flag is 0 then the MANDATORY encoding method will fail. 5.12 CONTEXT ABNF notation: "CONTEXT(" "," ")" The CONTEXT encoding method is used to store multiple copies of the same field in the context. This encoding method is useful when compressing fields that take a small number of values with high probability, but when these values are not known a-priori. CONTEXT encoding can also be applied to larger fields: even an entire TCP header. This can be very useful when multiple TCP flows are sent to the same IP address, as a single ROHC [1] context can be used to compress the packets in all of the TCP flows. Price, et al. Expires August 2, 2002 [Page 25] Internet-Draft Framework for EPIC-LITE February 2002 The first parameter specifies the encoding method that should be used to compress the field. The second parameter specifies how many copies of the field should be stored in the context. CONTEXT encoding applies the specified encoding method to the uncompressed header, compressing relative to any of the copies of the field stored in its context. It then appends an "index" value to the uncompressed header to indicate to the decompressor which context value should be used for decompression. Consider the following example using the TCP Window field: CONTEXT(TCP-WINDOW,4) ; Window VALUE(2,0,89%) | ; Window context index VALUE(2,1,10%) | VALUE(2,2,0.5%) | VALUE(2,3,0.5%) At most 4 copies of the Window field can be stored in the context. The Window field can be compressed relative to any of these values: the value chosen by the compressor is transmitted to the decompressor using the "index". 5.13 LIST ABNF notation: "LIST(" "," "," "," "," "," *("," ) *("," ) ")" The LIST encoding method compresses a list of items that do not necessarily occur in the same order for every uncompressed header. Example applications for the LIST encoding method include TCP options and TCP SACK blocks. The size of the list is determined by a control field in exactly the same manner as for UNCOMPRESSED encoding. The first four integer parameters are defined as in UNCOMPRESSED. The fifth parameter gives the number of bits which should be read from the uncompressed_data stack to decide which of the encoding methods in the list to use to compress the next list item. These parameters are followed by a set of encoding methods that can be used to compress individual items in the list and a set of integers to identify which method to use. If the integer obtained using the fifth parameter matches the nth integer then use the nth Price, et al. Expires August 2, 2002 [Page 26] Internet-Draft Framework for EPIC-LITE February 2002 encoding method. This continues until data amounting to the size of the list has been compressed. Once the list size is reached, LIST encoding appends the order in which the encoding methods were applied to the uncompressed data and the presence of data for the methods. The profile defines whether the order and presence can change in a compressed packet or not. For example: LIST(4,1,32,0,8, OPTIONAL(TCP-SACK), OPTIONAL(TCP-TIMESTAMP), OPTIONAL(TCP-END), OPTIONAL(TCP-GENERIC), 5,8,0) ; TCP Options STATIC(99.9%) | ; TCP Options order IRREGULAR(8, 0.1%) STATIC(75%) | ; TCP Options presence IRREGULAR(4,25%) The order in which the methods are applied is irrelevant in the mapping between methods chosen and the indicator flags. They are always considered to be compressed in the order in which they appear in the profile and the order and presence fields deal with the actual order in which they were processed. 5.13.1 LIST-NEXT ABNF notation: "LIST-NEXT(" "," *("," ) *("," ) ")" LIST-NEXT encoding is similar to basic LIST encoding, except that the next list item to compress is known a-priori from a control field. IP extension headers can be compressed using LIST-NEXT. The first parameter specifies the number of bits to extract from the control data stack before each list item is compressed. This is followed by the set of encoding methods available to LIST-NEXT and a set of 0 or more integers. The nth encoding method can only be called when the nth integer value is obtained from the control data stack. Price, et al. Expires August 2, 2002 [Page 27] Internet-Draft Framework for EPIC-LITE February 2002 For example: LIST-NEXT(8, OPTIONAL(AH-ENCODING), OPTIONAL(ESP-ENCODING), OPTIONAL(GRE-ENCODING), OPTIONAL(GENERIC-ENCODING), 51,50,47) ; Header Chain STATIC(99.9%) | ; Header Chain order IRREGULAR(8,0.01%) STATIC(75%) | ; Header Chain presence IRREGULAR(4,25%) The IP extension header chain can have a number of specific encoding methods designed for one type of extension header (AH, ESP or GRE) as well as a "generic" encoding method that can cope with arbitrary extension headers but at reduced compression efficiency. Just as with basic LIST encoding, LIST-NEXT also adds the order in which the encoding methods are applied and their presence or absence to the uncompressed header, so that the decompressor can reconstruct the list in the correct order. 5.14 FLAG encoding methods The flag encoding methods are used to modify the behavior of another encoding method. Each flag encoding has a single parameter, which is the name of another encoding method. The flag encoding method calls this encoding method, but additionally modifies the input or output in some manner. Note that flag encoding methods do not require the original encoding method to be rewritten (as they only modify its input or output). 5.14.1 N flag ABNF notation: "N(" ")" The N flag runs the encoding method specified by its parameter, with the exception that it does not update the context. This is useful when a field takes an unexpected value for one header and then reverts back to its original behavior in subsequent headers. An example of the N flag in use is given below: Price, et al. Expires August 2, 2002 [Page 28] Internet-Draft Framework for EPIC-LITE February 2002 STATIC(99%) | ; Window N(LSB(11,2048,0.9%)) | IRREGULAR(16,0.1%) In the above example the N flag is applied to the TCP Window field. The field is compressed by transmitting only the last few LSBs, which are always interpreted at the decompressor as a decrease in the field value. However, because the context is not updated the field reverts back to its original value following the decrease. 5.14.2 U flag ABNF notation: "U(" ")" The U flag changes the destination of any compressed bits produced by the encoding method specified as its parameter. Instead of putting them on the compressed_data stack it puts them on the unc_fields stack. They no longer contribute to the length of the compressed header so this is taken account of in the build method. This means that if an OPTIONAL method is surrounded by a U flag and the optional part is not actually present then no padding bits are required. An example of the U flag in use is given below: U(OPTIONAL(crsc_entry)) ; CSRC-list entry where csrc_entry = IRREGULAR(32) This means that if the CSRC entry is present then it will be compressed as IRREGULAR (i.e. the full 32 bits will be sent) and these bits will be pushed on the uncompressed stack. However, if it is not present then no padding bits will need to be sent. 5.15 FORMAT ABNF notation: "FORMAT(" "," *() ")" The FORMAT encoding method is used to create more than one set of compressed header formats. Recall that each set of compressed header formats uses up all of the indicator bit patterns available at the start of the compressed Price, et al. Expires August 2, 2002 [Page 29] Internet-Draft Framework for EPIC-LITE February 2002 header. Thus a profile can have several sets of compressed header formats, but only one set can be in use at a given time. FORMAT encoding is followed by a list of k encoding methods. Each encoding method is given its own set of compressed header formats in the CO packets. Note however that all encoding methods are present in the IR(-DYN) packets, so an IR(-DYN) packet may be sent to change to a new set of compressed header formats. An index flag is appended to the uncompressed header to indicate which set of formats is currently in use, as illustrated by the following example of an IR(-DYN) format (for CO the index flag would be STATIC(100%)): FORMAT(SEQUENTIAL-IP-ID,RANDOM-IP-ID) ; IP ID IRREGULAR(1,100%) ; IP_ID Index Two sets of compressed header formats are provided: one for an IP ID that increases sequentially, and one for a randomly behaving IP ID. Note that the Index flag is only sent in the IR(-DYN) packets. 5.16 CRC ABNF notation: "CRC(" "," ")" The CRC encoding method generates a CRC checksum calculated across the entire uncompressed header. At the decompressor this CRC is used to validate that correct decompression has occurred. Note that it is possible for different header formats to have different amounts of CRC protection, so extra CRC bits can be allocated to protect important context-updating information. This is illustrated in the example below: CRC(3,99%) | ; Checksum Coverage CRC(7,1%) The uncompressed header is recorded in the crc_static and crc_dynamic variables. Note that the fields that either never change or only change in the IR packet are placed in crc_static, and the remaining fields are placed in crc_dynamic. The CRC is calculated over crc_static + crc_dynamic, with the static fields placed first to speed up computation. Price, et al. Expires August 2, 2002 [Page 30] Internet-Draft Framework for EPIC-LITE February 2002 In general an EPIC-LITE profile can use any CRC length for which a CRC polynomial has been explicitly defined. The following CRC lengths are currently supported: 3-bit: C(x) = 1 + x + x^3 6-bit: C(x) = 1 + x + x^3 + x^4 + x^6 7-bit: C(x) = 1 + x + x^2 + x^3 + x^6 + x^7 8-bit: C(x) = 1 + x + x^2 + x^8 10-bit: C(x) = 1 + x + x^4 + x^5 + x^9 + x^10 12-bit: C(x) = 1 + x + x^2 + x^3 + x^11 + x^12 16-bit: C(x) = 1 + x^2 + x^15 + x^16 5.17 MSN encoding methods These methods are used to send the MSN (Master Sequence Number) to the decompressor. Separate encoding methods are required because the MNS does not appear in the uncompressed data itself. There are two encoding methods which compress the MSN and one which can be used to assign a particular field to be the MSN (for example, RTP sequence number): 5.17.1 MSN-LSB ABNF notation: "MSN-LSB(" "," "," ")" This method uses ordinary LSB encoding on the value in MSN rather than on the uncompressed_data stack. It also stores some information for use if extra bits of MSN are to be sent to pad the compressed header to a specific bit alignment. 5.17.2 MSN-IRREGULAR ABNF notation: "MSN-IRREGULAR(" "," ")" As with MSN-LSB this method uses ordinary IRREGULAR encoding and stores the extra information described above. 5.17.3 SET-MSN ABNF notation: "SET-MSN(" ")" The parameter of this method specifies the number of bits to assign Price, et al. Expires August 2, 2002 [Page 31] Internet-Draft Framework for EPIC-LITE February 2002 to be MSN. The bits are taken from the uncompressed stack. This value can then be used for INFERRED-OFFSET methods and compressed using MSN-LSB or MSN-IRREGULAR when no more fields need it. 6. Creating a new ROHC profile This chapter describes how to generate new ROHC [1] profiles using EPIC-LITE. It is important that the profiles are specified in an unambiguous manner so that any compressor and decompressor using the profiles will be able to interoperate. The following eight variables are required by EPIC-LITE to create a new ROHC [1] profile: profile_identifier max_formats max_sets bit_alignment npatterns CO_packet IR_DYN_packet IR_packet Once a value has been assigned to each variable the profile is well- defined. A compressor and decompressor using the same values for each variable should be able to successfully interoperate. Each of the variables is described in more detail below: 6.1 Profile identifier The profile_identifier is a 16-bit integer that is used when negotiating a common set of profiles between the compressor and decompressor. Official profile identifiers are assigned by IANA to ensure that two distinct profiles do not receive the same profile identifier. Note that the 8 MSBs of the profile identifier are used to specify the version of the profile (so that old profiles can be obsoleted by new profiles). 6.2 Maximum number of header formats The max_formats parameter controls the number of compressed header formats to be stored at the compressor and decompressor. If more compressed header formats are generated than can be stored then EPIC-LITE discards all but the max_formats most probable formats to be used. Note that the max_formats parameter affects the EPIC- LITE compressed header formats, and so for interoperability it MUST Price, et al. Expires August 2, 2002 [Page 32] Internet-Draft Framework for EPIC-LITE February 2002 be specified as part of the profile. If more than max_formats header formats are generated for the IR packet then this means that there are headers which it may be impossible to compress using this profile (resulting in a switch to a different profile). Hence it is RECOMMENDED that no more than max_formats distinct header formats are generated for the IR packet of any profile. In a similar manner the max_sets parameter controls the total number of sets of compressed header formats to be stored. Recall that a profile can have several sets of compressed header formats, but only one set may be in use at a given time. It is important to note that the maximum size specified by max_formats applies to each individual set of header formats, so the total overall number of formats that need to be stored is equal to max_formats * (max_sets + 2) including the 2 sets of formats for the IR and IR-DYN packets. 6.3 Control of header alignment The alignment of the compressed headers is controlled using the bit_alignment parameter. The output of the EPIC-LITE compressor is guaranteed to be an integer multiple of bit_alignment bits long. Additionally, the parameter npatterns can be used to reserve bit patterns in the compressed header. The parameter specifies the number of bit patterns in the first word (i.e. the first bit_alignment bits) of the compressed header that are available for use by EPIC-LITE. Consequently npatterns takes a value between 1 and 2^bit_alignment. For compatibility with ROHC [1], it is important for EPIC-LITE not to use the bit patterns 111XXXXX in the first octet of each compressed header because they are reserved by the ROHC framework. So to produce a set of header formats compatible with ROHC [1] the bit_alignment parameter MUST be set to 8 and npatterns MUST be set to 224. 6.4 Compressed header formats The profile parameter CO_packet specifies an encoding method that is used to generate the EPIC-LITE CO packets. This encoding method may be described using the BNF-based input language provided in Chapter 4 (or in fact can be described in any manner provided that it is unambiguous). The distinction between the eight variables required to define a new ROHC [1] profile and the input language defined in Chapter 4 is Price, et al. Expires August 2, 2002 [Page 33] Internet-Draft Framework for EPIC-LITE February 2002 important. The only requirement for compatibility with the profile is that the correct compressed header formats are used: the fact that they are specified in the input language is not important, and they can be implemented in any manner. The profile parameters IR_packet and IR_DYN_packet specify an encoding method which is used to generate the EPIC-LITE IR and IR-DYN packets respectively. Note that the IR_DYN_packet parameter is optional. If it is not given then EPIC-LITE generates the IR-DYN packet using the same encoding method as specified by the CO_packet parameter. The IR_packet parameter is also optional. If it is not given then EPIC- LITE generates the IR packet using the same encoding method as specified by the IR_DYN_packet parameter (or CO_packet if IR_DYN_packet is also not given). 7. Security considerations EPIC-LITE generates compressed header formats for direct use in ROHC profiles. Consequently the security considerations for EPIC-LITE inherit those of ROHC [1]. EPIC-LITE profiles also describe how to compress and decompress headers. As such they are interpreted or compiled by the compressor and decompressor. An error in the profile description may cause undefined behaviour. In a situation where profiles could be dynamically updated consideration MUST be given to authenticating and verifying the integrity of the profile. 8. Acknowledgements Header compression schemes from ROHC [1] have been important sources of ideas and knowledge. Basic Huffman encoding [2] 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. References [1] Bormann, C., Burmeister, C., Degermark, M., Fukushima, H., Price, et al. Expires August 2, 2002 [Page 34] Internet-Draft Framework for EPIC-LITE February 2002 Hannu, H., Jonsson, L-E., Hakenberg, R., Koren, T., Le, K., Liu, Z., Martensson, A., Miyazaki, A., Svanbro, K., Wiebke, T., Yoshimura, T. and H. Zheng, "RObust Header Compression (ROHC): Framework and four profiles: RTP, UDP, ESP, and uncompressed", RFC 3095, July 2001. [2] Nelson, M. and J-L. Gailly, "The Data Compression Book", M&T Books , 1995. [3] Jacobson, V., "Compressing TCP/IP headers for low-speed serial links", RFC 1144, February 1990. [4] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996. [5] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [6] Crocker, D. and P. Overell, "Augmented BNF for Syntax Specifications: ABNF", RFC 2234, November 1997. Authors' Addresses Richard Price Siemens/Roke Manor Roke Manor Research Ltd. Romsey, Hants SO51 0ZN UK Phone: +44 (0)1794 833681 EMail: richard.price@roke.co.uk URI: http://www.roke.co.uk Robert Hancock Siemens/Roke Manor Roke Manor Research Ltd. Romsey, Hants SO51 0ZN UK Phone: +44 (0)1794 833601 EMail: robert.hancock@roke.co.uk URI: http://www.roke.co.uk Price, et al. Expires August 2, 2002 [Page 35] Internet-Draft Framework for EPIC-LITE February 2002 Stephen McCann Siemens/Roke Manor Roke Manor Research Ltd. Romsey, Hants SO51 0ZN UK Phone: +44 (0)1794 833341 EMail: stephen.mccann@roke.co.uk URI: http://www.roke.co.uk Abigail Surtees Siemens/Roke Manor Roke Manor Research Ltd. Romsey, Hants SO51 0ZN UK Phone: +44 (0)1794 833131 EMail: abigail.surtees@roke.co.uk URI: http://www.roke.co.uk Paul Ollis Siemens/Roke Manor Roke Manor Research Ltd. Romsey, Hants SO51 0ZN UK Phone: +44 (0)1794 833168 EMail: paul.ollis@roke.co.uk URI: http://www.roke.co.uk Mark A. West Siemens/Roke Manor Roke Manor Research Ltd. Romsey, Hants SO51 0ZN UK Phone: +44 (0)1794 833311 EMail: mark.a.west@roke.co.uk URI: http://www.roke.co.uk Appendix A. EPIC-LITE compressor and decompressor This appendix gives a complete pseudocode description of the EPIC- LITE compressor and decompressor. Price, et al. Expires August 2, 2002 [Page 36] Internet-Draft Framework for EPIC-LITE February 2002 The appendix contains the following sections: Compressor operation (Section A.1) Decompressor operation (Section A.2) Offline processing (Section A.3) Library of methods (Section A.4) BNF description of input language (Section A.5) Recall that each EPIC-LITE profile for ROHC [1] is described by the following eight variables: profile_identifier 16-bit integer uniquely identifying the ROHC profile generated by EPIC-LITE max_formats Maximum number of header formats per set max_sets Total number of sets of header formats bit_alignment Number of bits for alignment (all compressed headers will be multiples of bit_alignment bits). (Set to 8 for compatibility with ROHC [1].) npatterns Number of bit patterns available for EPIC-LITE in the first word of the compressed header (set to 224 for compatibility with ROHC [1].) CO_packet Name of the method that generates the CO packet formats IR_DYN_packet Name of the method that generates the IR-DYN packet formats IR_packet Name of the method that generates the IR packet formats Additionally, the following general functions are used in the pseudocode description of EPIC-LITE: The functions used for list manipulation are given below: Price, et al. Expires August 2, 2002 [Page 37] Internet-Draft Framework for EPIC-LITE February 2002 empty (list) Empties the list sort-natural (list, compare) Sorts the list as defined by the compare function (which compares 2 elements). Sort is 'natural' in that original ordering of elements is preserved in the event of 2 elements being equal append (list, item) Appends an item to a list prepend (list, item) Prepend an item to head of list concatenate (list, list) Appends all the entries from the second list to the first one copy (list, list) Replaces the first list with a copy of the second list head-of (list) Finds first item in list tail-of (list) Finds last item in list next-item (curr_item) Finds the next item in the list from curr_item previous-item (curr_item) Finds the previous item in the list from curr_item at-end (list) Checks whether at the end of the list size-of (list) Returns the number of elements in list The following functions are used to traverse the BNF input language describing the new ROHC profile. Note that the relevant information can be extracted from the input language by hand or automatically via a suitable BNF parser: Price, et al. Expires August 2, 2002 [Page 38] Internet-Draft Framework for EPIC-LITE February 2002 first-field (method_name) finds the first instance of referenced in the encoding method (applies to a non-library encoding method only) next-field (method_name) finds the next instance of in the method (if none can be found then NULL-ENCODING is returned) prev-field (method_name) finds the previous instance of in the method last-field (method_name) finds the last instance of in the method (these functions allow iteration over the different field encodings in a method. This must be in the order defined in the profile) first-method (field_encoding) find the first encoding method listed within the field encoding next-method (field_encoding) find the next encoding method listed within the field encoding (this and the previous function allow iteration over the encoding methods for a given field. This must be in the order defined in the profile. If none can be found then NULL-METHOD is returned) extract-name (method) finds the name of the encoding method extract-probability (method) finds the probability of the method being invoked Method function handling: Price, et al. Expires August 2, 2002 [Page 39] Internet-Draft Framework for EPIC-LITE February 2002 lookup-build-function (method) finds the 'BUILD' function that relates to the method. If this is a library method, then the function returns a reference to the 'BUILD' subfunction for that method. Otherwise it returns a reference to the main 'BUILD' function which is then called recursively lookup-compress-function (method) as above but for the 'COMPRESS' function lookup-decompress-function (method) as above but for the 'DECOMPRESS' function context-size (method) looks up the number of context entries that will be needed to compress using this method. This can be worked out off line as part of the 'BUILD' function and stored for reference during compression and decompression. count-bits (method, enc) counts the number of bits that would be present in a compressed header for data compressed with format enc for this method (This can be worked out off line as part of the 'BUILD' function and stored for use during compression and decompression). Data handling: Value based functions: Price, et al. Expires August 2, 2002 [Page 40] Internet-Draft Framework for EPIC-LITE February 2002 length (var) Returns the length in bits of var value (var) Returns the value of var str (len, val) Returns a variable with length len and containing the value val lsb (var, k) Returns the least significant k bits of a (width defined or not) value (var) in a width defined value msb (var, k) Returns the most significant k bits of a width defined value (var) in a width defined value concat (var_1, var_2) Returns a width defined value with most significant bits being var_1 and least being var_2 - ie concatenates the two strings Addition, subtraction and multiplication can be done on width defined values as long as the two values have the same length (i.e. this translates into modular arithmetic) but must be done carefully. Stack functions: In the functions below an item has a length and value associated with it which can be found using the functions above. push (stack_name, n, var) For a bit-overlay stack, this function adds n bits with value var to the top of the stack (stack_name). For an item stack, this function pushes an item with length n and value var to the top of the stack (stack_name) push (stack_name, item) For a bit-overlay stack, this function adds n bits with value var to the top of the stack (stack_name) where n is the length of item and it has value var. For an item stack, this function pushes item on var to the top of the stack (stack_name) pop (stack_name, n, item) Pop n bits of data off a bit based stack (stack_name) and put into item Price, et al. Expires August 2, 2002 [Page 41] Internet-Draft Framework for EPIC-LITE February 2002 pop (stack_name, item) Pop item off an item based stack (stack_name) top (stack_name, n) Returns the item made up of the top n bits on a bit based stack (stack_name) top (stack_name) Returns the top item from an item based stack (stack_name) stack-size (stack) Returns the size in bits of a bit based stack add (stack_1, stack_2) Pushes stack_1 onto stack_2 but leaves the outcome in stack_1 rotate (stack_name, n, m) Rotate the top n items on an item based stack (stack_name) m times. Take the nth item from the stack and put it on the top. stack-pointer (stack_name) Returns the position of the top of a stack (stack_name) NB this is never used for accessing the stack and can be of arbitrary form Context based functions: The enc_index counter is used to access information stored in the context for each field encoding. It is initially 1 and is incremented throughout compression and decompression. Some encoding methods do not have any context associated with them, for example, INFERRED-SIZE. This incremental way of accessing context information means that if a choice of two or more encoding methods is available for a given field, each in turn should contain the same number of subfields as each other, otherwise the alignment of the context will be lost. NB leaving a value in the context empty is NOT the same as storing something which zero-bits wide. Price, et al. Expires August 2, 2002 [Page 42] Internet-Draft Framework for EPIC-LITE February 2002 context (enc_index, i, var) Put the value stored at the ith position in the context associated with enc_index into var. If there isn't a value in the ith position then return empty save (enc_index, var, storage) Store the value in var in storage associated with enc_index (to be transferred to the context if (de)compression is successful clear (enc_index, storage) Remove the value in storage associated with enc_index and leave it empty (for use if non-context-updating method) transfer (storage, context) Transfer the information in storage into the context Miscellaneous: convert-percentage (pc) Converts the percentage (in floating point) to the fixed point representation used store (list, method, field_encoding) Add method associated with field_encoding to list get-method (list, field_encoding) Return the method associated with field_encoding from list get-method-list (main_list_elt, method_chosen) Finds method_chosen such that method_chosen <=> main_list_item.id format-get-method-list (main_list_elt, method_chosen, method) Finds method_chosen such that method_chosen <=> main_list_item.id assuming that a specific method has been chosen using the FORMAT method (this is used to ensure correct decompression of an IR(-DYN) packet) Price, et al. Expires August 2, 2002 [Page 43] Internet-Draft Framework for EPIC-LITE February 2002 get-format (main_list_elt, method_chosen) Finds the main_list_item such that method_chosen <=> main_list_item.id get-header-length (method_chosen) Returns the length in bits of the compressed header format (excluding flags) for this list element (sum of number of bits in each compressed field) lookup-crc-function (n) Finds the function for computing an n-bit crc over a specified amount of data and putting the value into a given width defined variable byte-swap (item) Returns another item the same as item but stored in the opposite byte ordering compute-16-checksum (data, length) Compute a 16-bit one's complement sum over data of length Other constructs: foreach item in [reverse] list : end loop provides for iteration over all the elements of a list [in reverse order] call function (...) indicates a reference to a function is being invoked choose (...) the choice of whatever is specified is implementation specific - it may affect efficiency but whatever choice is made will not affect interoperability, for example, choose (j < k) - pick an arbitrary value j which is less than k. Some global variables: Price, et al. Expires August 2, 2002 [Page 44] Internet-Draft Framework for EPIC-LITE February 2002 uncompressed_data Bit based stack Compression - initially header and payload, finally empty Decompression - initially empty, finally original header and payload compressed_data Bit based stack Compression - initially empty, finally compressed header and payload Decompression - initially compressed header, finally empty unc_fields Bit based stack Compression - initially empty, used to store fields to be sent uncompressed for transfer to compressed_data Decompression - initially data which has been sent uncompressed, finally only payload for transfer to uncompressed_data received_data Bit based stack Decompression - initially packet received, splits into compressed_data and unc_fields control_data Item based stack Compression and Decompression - initially and finally empty - storage for control fields if not used immediately after generation u_flag A flag which starts with value zero. It keeps track of which stack (compressed_data or unc_fields) has the compressed data added to/ removed from it. compression_stack Pointer to either compressed_data or unc_fields, whichever is the one that is currently having data put onto it according to the value of u_flag. Initially at both compression and decompression compression_stack = compressed_data. Price, et al. Expires August 2, 2002 [Page 45] Internet-Draft Framework for EPIC-LITE February 2002 context Storage of data as reference for compression and decompression - referenced by 'enc_index' storage Storage of data during (de)compression to be transferred to context if successful - referenced by 'enc_index' enc_index A counter to keep track of the field encodings and context data associated with them method_chosen List of methods used to compress a given header - lists the encoding method chosen for each 'enc_index' compressor_state The current state at the compressor (can be set to "IR", "IR-DYN" or "CO") current_set The set of compressed header formats currently in use crc_static The static part of the header crc_dynamic The dynamic part of the header crc The decompressed crc for checking against one calculated over full header (a width defined value) MSN The Master Sequence Number - a width defined value (its value increases by one for each packet received at the compressor or it is set to be a specific value using the SET-MSN method if the header contains a suitable field) msn_bits The number of bits chosen to encode the MSN msn_lsbs The LSBs of MSN used for padding (a width defined value) A.1 Compressor This section describes the EPIC-LITE header compressor. A.1.1 Step 1: Packet classification The input to the EPIC-LITE compressor is simply an uncompressed Price, et al. Expires August 2, 2002 [Page 46] Internet-Draft Framework for EPIC-LITE February 2002 packet. The compressor does not know whether the packet contains an RTP header, TCP header or other type of header, and hence the first step is to determine which (if any) ROHC context can be used to compress the packet. With any profile generated by EPIC-LITE the packet classification is performed automatically, since the profile will reject any packet that it cannot successfully compress relative to the chosen context. Note however that additional packet classification MAY be performed before the packet is passed to the EPIC-LITE compressor. For example the compressor MAY wish to check that the values that are initialised in the IR packet, or fixed for all states take the values specified in the prospective context before compression is attempted, as if they do not then compression will not succeed. A.1.2 Step 2: Using the state machine The job of the state machine is to choose whether to send IR, IR-DYN or compressed (CO) packets. Since EPIC-LITE currently operates in a unidirectional mode of compression only there is no need to synchronize the decision with the decompressor, and hence the choice can be left as an implementation decision. A.1.3 Step 3: Compressing the header The next step is to choose the compressed header format that will be used to transmit the header from the compressor to the decompressor. Given the selected profile the compressor has exactly max_sets + 2 possible sets of header formats available: a total of max_sets different sets of CO packets, as well as a set of IR-DYN packets and a set of IR packets. The choice of which header formats to use depends on the current state of the state machine. The compressor calls the function COMPRESS to compress the header. The function takes one parameter - the name of the method that is currently being used. The global variable enc_index is initially 1. Note that is not necessary to provide EPIC-LITE with a description of where the fields occur in the uncompressed header, as this information is provided automatically as part of each method (written in the BNF input language). Each encoding method has a specific number of bits associated with it which is the number of bits that encoding method can compress - this splits the header into fields. The function has a single output: a Boolean value indicating whether or not compression has successfully occurred. Additionally, if compression succeeds then the stack compressed_data will contain the Price, et al. Expires August 2, 2002 [Page 47] Internet-Draft Framework for EPIC-LITE February 2002 compressed value of every field in the uncompressed header. The function also modifies the value of the global variable, method_chosen. If compression is successful then for each field in the profile, method_chosen will contain an indicator of which encoding method has been selected for the field. This is mapped onto a set of indicator flags in Section A.1.4. The compression commences with a call to the COMPRESS function for the method specified in CO_packet (or IR_DYN_packet or IR_packet depending on the compressor state). The function may call itself recursively with a different input. For one particular aspect of profile complexity there are two distinct categories. For a profile in the first category, if a header is compressible, then compression is guaranteed to complete successfully in a single pass. The second category of profiles cannot make this guarantee. This is due either to a change of packet format (as indicated through the FORMAT encoding method) or to the failure of a non-library encoding method. A change of format requires IR-DYN packets to be sent indicating the change. Multiple formats may need to be tried in order to find one that can successfully compress the packet, and the compressor should implement such a mechanism. Where a non-library encoding method fails, alternative encoding methods may be available. However, some encoding methods may have been applied, altering the contents of the stacks used to store state information for compression. The compressor should implement a mechanism, such as rolling back the compression state information, to allow alternative encoding methods to be tried. This ensures that all possible combinations of encoding methods can be tried to find one which will successfully compress the packet. If the method is specified as part of the EPIC-LITE library, the pseudocode for the COMPRESS procedure is specified separately (in Appendix A.4.). function COMPRESS (method_name) var enc, method var compress_function enc = first-field (method_name) while (enc <> NULL_ENCODING) Price, et al. Expires August 2, 2002 [Page 48] Internet-Draft Framework for EPIC-LITE February 2002 method = first-method (enc) do # compress_function will be for the method if it is a # library method or a recursive call to this function for # a composite method... compress_function = lookup-compress-function (extract-name (method)) can_compress = call compress_function (extract-name (method)) if can_compress = true then # store the method selected from this field_encoding in # method_chosen store (method_chosen, method, enc) else # otherwise try another method in the field_encoding method = next-method (enc) endif loop until (can_compress = true) or (method = NULL_METHOD) if can_compress = true then enc = next-field (method_name) else return false endif end while return true end COMPRESS Price, et al. Expires August 2, 2002 [Page 49] Internet-Draft Framework for EPIC-LITE February 2002 N.B. This procedure shows the encoding methods for a field being checked in the order in which they appear in the profile. The order in which they are checked is actually implementation specific but is shown in the form above for simplicity of the pseudocode. But, for interoperability the "store" function must have a unique mapping dictated by the order of the encoding methods in the profile between the field and the encoding method. Note that once the header has been compressed, the variable "storage" should contain the uncompressed value of each field which has context associated with it. This information is then transferred to the context in the compressor (possibly overwriting one of the copies of information already stored). A.1.4 Step 4: Determining the indicator flags The next step is to determine the correct indicator flags for the chosen compressed header format. Once the indicator flags have been added the header should be padded to be a multiple of bit_alignment bits and the uncompressed fields and payload added. The compressor must run the following procedures: function get-indicator-flags (method_chosen, flags_list_elt, Mvalue) var main_list_item, old_item, ml var last_N_before_item, w, length, length_item, next_length, num var last_N_of_smaller_length var found_length, n_diff var fl # How this mapping is done is implementation dependent at the # compressor get-format (main_list_item, method_chosen) old_item = next-item (main_list_item) last_N_before_item = tail-of (old_item.cum_N_list) w = head-of (main_list_item.cum_N_list) length = head-of (main_list_item.length_list) found_length = 0 # If length_list only has one item then this loop will only # be done once (as in EPIC-LITE), otherwise loop until the # cumulative_N which covers Mvalue is found. This gives the Price, et al. Expires August 2, 2002 [Page 50] Internet-Draft Framework for EPIC-LITE February 2002 # length of the flags while (found_length = 0) n_diff = w - last_N_before_item if (n_diff < Mvalue) then w = next-item (w) length = next-item (length) else found_length = 1 endif end loop # Find first flags of this length from the flag list found_length = 0 fl = head-of (flag_list) while (found_length = 0) if length = fl.length then found_length = 1 else fl = next-item (fl) endif end loop # Find the last cumulative N which has flags of smaller length # than fl found_length = 0 ml = tail-of (main_list) while (found_length = 0) if (head-of (ml.length_list) < length) then ml = previous-item (ml) else found_length = 1 ml = next-item (ml) endif end loop length_item = head-of (ml.length_list) num = head-of (cum_N_list) next_length = next-item (length_item) found_length = 0 while (next_length <> NULL and found_length = 0) if next_length <> length then length_item = next-item (length_item) Price, et al. Expires August 2, 2002 [Page 51] Internet-Draft Framework for EPIC-LITE February 2002 next_length = next-item (next_length) num = next-item (num) else found_length = 1 endif end loop last_N_of_smaller_length = num # Work out what the indicator flags will be for this Mvalue flags = Mvalue + fl.flags + last_N_before_item - last_N_of_smaller_length return length end get-indicator-flags procedure INDICATOR-FLAGS var n, bit, temp, length var extra_bits # Take account of the currently selected FORMAT set choose (main_list or formats and associated flag_list according to the value of current_set) length = get-indicator-flags (method_chosen, flags, 0) push (compressed_data, length, flags) # pad the compressed header to bit_alignment with extra bits of # MSN - use zeros if more space than bits of MSN bit = bit_alignment n = (bit - (stack-size (compressed_data) mod bit)) mod bit temp = value (MSN) - value (lsb (MSN, msn_bits)) temp = temp / (2^msn_bits) extra_bits = lsb (temp, n) push (unc_fields, extra_bits) # add the uncompressed fields after the compressed header add (compressed_data, unc_fields) # add the payload after the uncompressed fields Price, et al. Expires August 2, 2002 [Page 52] Internet-Draft Framework for EPIC-LITE February 2002 add (compressed_data, uncompressed_data) end INDICATOR-FLAGS A.1.5 Step 5: Encapsulating in ROHC packet The last step is to encapsulate the EPIC-LITE compressed packet within a ROHC packet. Note that this includes adding the CID and any other ROHC framework headers (segmentation, padding etc.) as described in ROHC [1]. The ROHC packet is then ready to be transmitted. A.2 Decompressor This section describes the EPIC-LITE header decompressor. A.2.1 Step 1: Decapsulating from ROHC packet The input to the EPIC-LITE decompressor is a compressed ROHC packet. The first step is to read the CID of the packet and to extract the EPIC-LITE packet for parsing by the appropriate profile. If the ROHC packet is identified as containing an EPIC-LITE compressed packet then the decompression process continues as indicated below. A.2.2 Step 2: Running the state machine The decompressor state machine determines whether the received packet should be decompressed or discarded (based on whether the decompressor believes its stored context to be valid or invalid). Since the compressor and decompressor state machines do not have to be synchronized, this is left as an implementation decision. A.2.3 Step 3: Reading the indicator flags The input to Step 3 is an EPIC-LITE compressed packet. Note that the overall length of the packet is known from the link layer, but the length of the compressed header itself is NOT known. The first step is to determine the compressed header format and split the packet into compressed header and uncompressed data. This is accomplished by reading the indicator flags as per the following procedure: Price, et al. Expires August 2, 2002 [Page 53] Internet-Draft Framework for EPIC-LITE February 2002 procedure decode-indicator-flags (received_data, method_chosen, flags, bit_chunks, Mvalue) var main_list_item, ml var last_N_before_item, length, length_item, next_length, num var last_N_of_smaller_length var found_length var fl found_length = 0 fl = head-of (flag_list) while (found_length = 0 and fl <> NULL) if (top (received_data, fl.length*bit_chunks) <= fl.flags) then found_length = 1 else fl = next-item (fl) endif end loop if fl <> NULL then fl = previous=item (fl) else fl = tail-of (flag_list) endif length = fl.length flags = top (received_data, length*bit_chunks) # Find the last cumulative N which has flags of smaller length # than fl found_length = 0 ml = tail-of (main_list) while (found_length = 0) if (head-of (ml.length_list) < length) then ml = previous-item (ml) else found_length = 1 ml = next-item (ml) endif end loop length_item = head-of (ml.length_list) num = head-of (ml.cum_N_list) next_length = next-item (length_item) Price, et al. Expires August 2, 2002 [Page 54] Internet-Draft Framework for EPIC-LITE February 2002 found_length = 0 while (next_length <> NULL and found_length = 0) if next_length <> length then length_item = next-item (length_item) next_length = next-item (next_length) num = next-item (num) else found_length = 1 endif end loop last_N_of_smaller_length = num Mvalue = flags - fl.flags num = tail-of (ml.cum_N_list) while ((num - last_N_of_smaller_length) < Mvalue) ml = previous-item (ml) num = tail-of (ml.cum_N_list) end loop main_list_elt = ml ml = next-item (ml) last_N_before_item = tail-of (ml.cum_N_list) Mvalue = Mvalue + last_N_of_smaller_length - last_N_before_item # How this mapping is done is decompressor specific get-method-list (main_list_item, method_chosen) end decode-indicator-flags procedure READ-FLAGS var found, n, size, bit, k, len, Mvalue var temp, flags, flags_temp # Take account of the currently selected FORMAT set choose (main_list or formats and associated flag_list according to the value of current_set) decode-indicator-flags (received_data, method_chosen, flags, 1, Mvalue) len = length (flags) Price, et al. Expires August 2, 2002 [Page 55] Internet-Draft Framework for EPIC-LITE February 2002 pop (received_data, len, flags_temp) n = get-header-length (method_chosen) # put the compressed header on the compressed data stack pop (received_data, n, temp) push (compressed_data, temp) # store any extra lsbs of MSN sent bit = bit_alignment k = (bit - (n + len) mod bit) mod bit pop (received_data, k, msn_lsbs) # put the rest of the received packet on the unc_fields stack size = stack-size (received_data) pop (received_data, size, temp) push (unc_fields, temp) end READ-FLAGS A.2.4 Step 4: Decompressing the fields Now that the format of the compressed header has been determined, the next step is to decompress each field in turn. The decompressor calls the procedure DECOMPRESS to calculate the uncompressed value of the fields. The only input to the procedure is the name of a method. Unlike the COMPRESS function there are no outputs since decompression always succeeds (although if the packet is corrupted, the correct answer may not be obtained). Initially, the DECOMPRESS procedure is called for the method specified in CO_packet (or IR_DYN_packet or IR_packet depending on the ROHC packet type received). Note that as for COMPRESS the procedure may call itself recursively with different inputs. The global variable enc_index is initially 1. Price, et al. Expires August 2, 2002 [Page 56] Internet-Draft Framework for EPIC-LITE February 2002 procedure DECOMPRESS (method_name) var enc, method var decompress_function enc = last-field (method_name) while (enc <> NULL_ENCODING) method = get-method (method_chosen, enc) # decompress_function will be for the method if it is a # library method or a recursive call to this function for # composite method... decompress_function = lookup-decompress-function (extract-name (method)) call decompress_function (extract-name (method)) enc = prev-field (method_name) end while end DECOMPRESS Observe that the DECOMPRESS procedure reads the input code in the opposite order to the COMPRESS procedure. This is because decompression is the exact mirror-image of compression: if fields are parsed in reverse order then it will never be the case that a field can only be decompressed relative to a field that has not yet been reached. When the entire header has been decompressed it is on the stack uncompressed data and the payload is still on the stack unc_fields. These should be combined to make the original packet. A.2.5 Step 5: Verifying correct decompression By this stage the decompressor has calculated the value uncompressed_data that contains the entire uncompressed header as well as the payload. The final step is to verify that successful decompression has occurred by applying the checksum to the uncompressed header. The CRC method makes available the variables checksum_value (containing the checksum from the compressed header) and crc_static + crc_dynamic Price, et al. Expires August 2, 2002 [Page 57] Internet-Draft Framework for EPIC-LITE February 2002 (containing all of the fields in the uncompressed header). The CRC should be evaluated over crc_static + crc_dynamic and compared with the CRC stored in checksum_value. If the uncompressed header fails the checksum then it should be discarded. If it passes then it can be forwarded by the decompressor. Furthermore, if decompression is successful then the values contained within context can be replaced by the values contained in storage. A.3 Offline processing This section describes how the profile is converted into one or more sets of compressed header formats. Note that the following algorithms are run once offline and the results stored at the compressor and decompressor. A.3.1 Step 1: Building the header formats The first step is to build up a list of the max_formats different compressed header formats that occur with the highest probability (based on the probability values given in the input code). To generate the max_sets + 2 different sets of compressed header formats, the BUILD procedure is called max_sets times with the global variable compressor_state set to "CO" and current_set taking values from 0 to max_sets - 1 inclusive. Additionally it is called once with compressor_state = "IR" and once with compressor_state = "IR- DYN". The output in each case is a list describing the top max_formats different compressed header formats. The list has the following attributes: The output from the BUILD procedure is a list describing the top max_formats different compressed header formats in the following way. Each list_item has several parts: Price, et al. Expires August 2, 2002 [Page 58] Internet-Draft Framework for EPIC-LITE February 2002 list_item.P Overall percentage probability that the header format identified in this list item will be used list_item.N Total size of the header format identified in this list item in bits, excluding indicator flags list_item.id A list of integers uniquely identifying the header format associated with this list item (id is itself a list on which the list functions defined earlier can be performed) Note that all percentages are stored to exactly 2 decimal places (or by scaling they can be stored as a 2-octet integer from 0 to 10000 inclusive). When two percentages are multiplied, the result MUST be calculated exactly (i.e. to 4 decimal places, or equivalently a 4- octet integer) and then truncated to 2 decimal places. For example, 15.8% is represented as 1580, 89.2% is represented as 8920. The result of multiplying these two values together is: 1580 x 8920 = 14093600 (interim result, accurate to 4 DP) 14093600 / 10000 = 1409 (any remainder is discarded) 1409 = 14.09% For interoperability the top max_formats entries MUST NOT be reordered when the discarding process is carried out. In the event of a tie, the list entries with the lowest indices are kept. Note that the procedure may call itself recursively using a different input. Some functions used in the BUILD procedure are defined first: # # compare two items by probability # function COMPARE (a, b) if a.P > b.P then return 1 else if a.P < b.P then return -1 else return 0 endif end COMPARE Price, et al. Expires August 2, 2002 [Page 59] Internet-Draft Framework for EPIC-LITE February 2002 # # discard items from list such that: # list is sorted # if list contains less than max_formats entries then # the sorted list is returned # else if list contains more than max_formats then # keep the max_formats most probably entries # if any other entries have the same probability as # the least probable entry, keep those # discard the rest # procedure DISCARD (list, max_formats) var result_list var count var last_item empty (result_list) sort-natural (list, COMPARE) count = 0 last_item = tail-of (list) foreach item in reverse list if ((count >= max_formats) and ((last_item.P <> item.P) or (item.P = 0)) then break endif prepend (result_list, item) last_item = item count = count + 1 end loop copy (list, result_list) end DISCARD Price, et al. Expires August 2, 2002 [Page 60] Internet-Draft Framework for EPIC-LITE February 2002 # # combine two lists by creating their # product. This sums the N values and # multiplies the P values # procedure COMBINE (final, temp) empty (new_list) foreach dst in temp foreach src in final item.P = dst.P * src.P item.P = dst.N + src.N copy (item.id, dst.id) concatenate (item.id, src.id) append (new_list, item) end loop DISCARD (new_list, max_formats) end loop copy (final, new_list) end COMBINE # # build the list for the method given # procedure BUILD (method_name, probability, build_list) var enc, method var item var final_list, build_output, temp_list var build_function enc = first-field (method_name) item.P = convert-percentage (100%) item.N = 0 Price, et al. Expires August 2, 2002 [Page 61] Internet-Draft Framework for EPIC-LITE February 2002 empty (item.id) empty (final_list) append (final_list, item) while (enc <> NULL_ENCODING) empty (temp_list) method = first-method (enc) do # build_function will be for the method if it is a library # method or a recursive call to this function for a composite # method... empty (build_output) build_function = lookup-build-function (method) call build_function (extract-name (method), extract-probability (method), build_output) foreach item in build_output append (item.id, method) append (temp_list, item) end loop DISCARD (temp_list) method = next-method (enc) loop until method = NULL_METHOD # combine lists - result in final_list COMBINE (final_list, temp_list) enc = next-field (method_name) end while foreach item in final_list item.P *= probability Price, et al. Expires August 2, 2002 [Page 62] Internet-Draft Framework for EPIC-LITE February 2002 end loop copy (build_list, final_list) end BUILD procedure BUILD-TABLE (base_method, result) BUILD (base_method, convert-percentage (100%), result) end BUILD-TABLE The final output of BUILD is a list describing max_formats different compressed header formats. A.3.2 Step 2: Generating the indicator flags The final step of generating a new set of compressed header formats is to convert the list of probabilities into a set of indicator flags. Each header format begins with a unique pattern of indicator flags that serve to distinguish it from all other header formats in the set. EPIC-LITE generates the indicator flags using ordinary Huffman compression. For each of the cases in Section A.3.1 where the BUILD algorithm is run the following algorithm should be applied to the output of BUILD: # # build the flags associated with the list given, reserving the # bit pattern '111' if do_reserve is set # procedure BUILD-FLAGS (main_list, do_reserve) var work_list, reserve var u, v, w, z var i, flag, value, prev_length, num_formats sort-natural (main_list, COMPARE) DISCARD (main_list, max_formats) empty (work_list) Price, et al. Expires August 2, 2002 [Page 63] Internet-Draft Framework for EPIC-LITE February 2002 u = head-of (main_list) v = head-of (work_list) # which will be null # the work_list starts empty, so v is 'null'. However, as soon as # the first item is added to the work list, v references this item, # which is why there is a condition & re-initialisation of v at the # bottom of the loop item.P = u.P u.parent = item num_formats = size-of (main_list) for i = 0 to (num_formats - 2) if (i = (num_formats - 4) and do_reserve) then RESERVE (u, v, reserve, flag) endif u_next = next-item (u) v_next = next-item (v) if (at-end (v) or ( not at-end (u_next) and (u_next.P <= v.P)) then item.P = u.P + u_next.P append (work_list, item) u.parent = item u_next.parent = item u = next-item (u_next) else if (at-end (u) or ( not at-end (v_next) and v_next.P <= u.P)) then item.P = v.P + v_next.P append (work_list, item) v.parent = item v_next.parent = item v = next-item (v_next) else item.P = u.P + v.P append (work_list, item) u.parent = item v.parent = item u = u_next Price, et al. Expires August 2, 2002 [Page 64] Internet-Draft Framework for EPIC-LITE February 2002 v = next-item (v) endif if (i = 0) then v = head-of (work_list) endif end loop item.parent = NULL_ITEM cumulative_N = 0 empty (flag_list) w = tail-of (main_list) for i = 0 to (num_formats - 1) z = w length = 0 do if do_reserve then if (type = 0 and (z = reserve [0])) then length = length + 1 else if (type = 1 and (z = reserve [0] or z = reserve [1])) then length = length + 1 else if (type = 2 and z = reserve [3]) then length = length + 1 else if (type = 2 and z = reserve [1]) then length = length - 1 else if (type = 3 and z = reserve [2]) then length = length + 1 endif endif length = length + 1 z = z.parent loop until z.parent = NULL_ITEM cumulative_N = cumulative_N + 1 Price, et al. Expires August 2, 2002 [Page 65] Internet-Draft Framework for EPIC-LITE February 2002 append (w.length_list, length) append (w.cum_N_list, cumulative_N) # Add this length into the flag_list - either by adding # 1 to the element with correct length or by adding a # new element. Flag_list should be in ascending order of # lengths. found_same_length = 0 fl_elt = head-of (flag_list) while (fl_elt <> NULL and found_same_length = 0) if fl_elt.length = length then found_same_length = 1 endif end while if found_same_length = 0 then fl_elt.N = cumulative_N fl_elt.length = length append (flag_list, fl_elt) else fl_elt.N = fl_elt.N + 1 endif w = previous-item (w) end loop # Generate the Huffman flags flag_item.N = 0 flag_item.length = 0 flag_item.flags = 0 prepend(flag_list,flag_item) fl_3 = head-of (flag_list) fl_2 = next-item (fl_3) fl_2.flags = str(fl_2.length,0) fl_1 = next-item(fl_2) while (fl_1 <> NULL) fl_1.flags = str(fl_1.length,(fl_2.flags + (fl_2.N - fl_3.N)) * 2 ^ (fl_1.length - fl_2.length)) fl_1 = next-item (fl_1) Price, et al. Expires August 2, 2002 [Page 66] Internet-Draft Framework for EPIC-LITE February 2002 fl_2 = next-item (fl_2) fl_3 = next-item (fl_3) end while end BUILD_FLAGS # # procedure to work out whether to use one or two list # items to reserve the bits '111' # procedure RESERVE (u, v, reserve, flag) var temp_u, temp_v var t var prob temp_u = u temp_v = v flag = 0 # This section works out which order the 4 remaining nodes # will be formed into tree for t = 0 to 3 if (at-end (temp_v) or ( not at-end (temp_u) and temp_u.P <= temp_v.P) then reserve [t] = temp_u prob [t] = temp_u.P temp_u = next-item (temp_u) else reserve [t] = temp_v prob [t] = temp_v.P temp_v = next-item (temp_v) endif end loop # prob[0] = A ... prob [3] = D Price, et al. Expires August 2, 2002 [Page 67] Internet-Draft Framework for EPIC-LITE February 2002 # This function is pretending to create a node which will # have the same probability as B and will take up the bit # pattern '111'. If the new node were to be created then # check whether a + 2*B >= D to decide whether or not the # node comes before or after B. This part looks at the # probabilities to work out which nodes would have their # lengths changed by inserting this node so they can be # changed accordingly in the length counting (rather than # actually trying to add the new node) if ((prob [0] + prob [1]) >= prob [3]) then flag = 0 else if ((prob [0] + prob [1]) < prob [2]) then if ((prob [0] + (2 * prob [1])) < prob [3]) then flag = 1 else flag = 2 endif else if ((prob [1] + prob[2] < prob [3])) then flag = 3 else flag = 2 endif endif endif end RESERVE The procedure RESERVE is called at most once by BUILD-FLAGS to reserve the bit pattern "111" in the first octet of each compressed header (for compatibility with the ROHC framework). The output of BUILD-FLAGS is the main_list each item of which has three key parts: Price, et al. Expires August 2, 2002 [Page 68] Internet-Draft Framework for EPIC-LITE February 2002 list_item.length_list List of lengths of numbers of flags (for EPIC-LITE this will only have one element). The lengths should (automatically) be in ascending order. list_item.cum_N_list A list of numbers - corresponding to the number of headers with each flag length in the length_list (again for EPIC-LITE there will only be one element). The numbers should (automatically) be in ascending order. list_item.identifier Some unique identifier which can be used to perform mapping between these flags and the header format used to generate a compressed header requiring these flags. and a flag_list each item of which has the following elements: flag_list_item.length The length of the Huffman flags. flag_list_item.N The cumulative number of headers with Huffman flags up to this length. flag_list_item.flags The flags for the first header with flags of this length (the rest can be worked out from this information). Note that the compressor assigns bit patterns to the indicator flags using the following rules: 1. The most probable headers have all "0" indicator flags 2. The indicator flags for the next header format are calculated by adding 1 to the previous flags (treated as an integer) and padding with enough 0s to reach the correct length As an example, the indicator flags for a set of compressed header formats are given below: Price, et al. Expires August 2, 2002 [Page 69] Internet-Draft Framework for EPIC-LITE February 2002 main_list Compressed header format No. of flags Cumulative_N 1 2 1 2 2 2 3 3 3 4 4 4 5 4 5 6 4 6 7 5 7 8 6 8 9 6 9 flag_list No. of flags N Bit pattern of flags 2 1 00 3 3 100 4 4 1010 5 7 11010 6 8 110110 Note that the most probable compressed header format will have all "0" indicator flags, whilst the least probable header format will have all "1" indicator flags (except for the bit pattern "111" if this is reserved for the ROHC [1] framework). A.4 Library of methods This section gives pseudocode for each of the methods in the library. Note that for each method three pieces of pseudocode are given: corresponding to the function COMPRESS, and procedures DECOMPRESS and BUILD described previously. Note that all of the global variables required for these procedures are defined at the beginning of Appendix A. It is assumed that as soon as the 'return' command is encountered, the procedure stops. For COMPRESS functions which check through the r values stored in the context, the value of r is implementation-specific. Note that if any of the r context values is empty, any method attempting to compress relative to the context will automatically fail. A.4.1 STATIC STATIC (P%) Price, et al. Expires August 2, 2002 [Page 70] Internet-Draft Framework for EPIC-LITE February 2002 COMPRESS (STATIC) var context_val, item var n, i context (enc_index, 1, context_val) n = length (context_val) # check that the value to be compressed matches each of the r # values stored in context for this encoding - if not then # STATIC can't be used to compress this encoding for i = 1 to r context (enc_index, i, context_val) if (context_val <> top (uncompressed_data, n)) then return false endif end loop pop (uncompressed_data, n, item) save (enc_index, item, storage) enc_index = enc_index + 1 return true end COMPRESS DECOMPRESS (STATIC) var context_val context (enc_index, 1, context_val) push (uncompressed_data, context_val) save (enc_index, context_val, storage) enc_index = enc_index + 1 end DECOMPRESS BUILD (STATIC, P, format) var item item.P = P item.N = 0 empty (item.id) append (format, item) end BUILD A.4.2 IRREGULAR Price, et al. Expires August 2, 2002 [Page 71] Internet-Draft Framework for EPIC-LITE February 2002 IRREGULAR(n,P%) COMPRESS (IRREGULAR) var item pop (uncompressed_data, n, item) push (compression_stack, item) save (enc_index, item, storage) enc_index = enc_index + 1 return true end COMPRESS DECOMPRESS (IRREGULAR) var item pop (compression_stack, n, item) push (uncompressed_data, item) save (enc_index, item, storage) enc_index = enc_index + 1 end DECOMPRESS BUILD (IRREGULAR, P, format) var item item.P = P item.N = n empty (item.id) append (format, item) end BUILD A.4.2.1 IRREGULAR-PADDED IRREGULAR-PADDED(n,k,P%) COMPRESS (IRREGULAR-PADDED) var item, temp if (value (top (uncompressed_data, n - k)) <> 0) then return false else pop (uncompressed_data, n, item) temp = lsb (item, k) push (compression_stack, temp) Price, et al. Expires August 2, 2002 [Page 72] Internet-Draft Framework for EPIC-LITE February 2002 save (enc_index, item, storage) enc_index = enc_index + 1 return true endif end COMPRESS DECOMPRESS (IRREGULAR-PADDED) var item, temp var full full = 0 pop (compression_stack, k, temp) full = full + value (temp) item = str (n, full) push (uncompressed_data, item) save (enc_index, item, storage) enc_index = enc_index + 1 end DECOMPRESS BUILD (IRREGULAR-PADDED, P, format) var item item.P = P item.N = k empty (item.id) append (format, item) end BUILD A.4.3 VALUE Price, et al. Expires August 2, 2002 [Page 73] Internet-Draft Framework for EPIC-LITE February 2002 VALUE(n,v,P%) COMPRESS (VALUE) var value if (top (uncompressed_data, n) <> v) then return false else pop (uncompressed_data, n, value) save (enc_index, value, storage) enc_index = enc_index + 1 return true endif end COMPRESS DECOMPRESS (VALUE) var item item = str (n, v) push (uncompressed_data, n, v) save (enc_index, item, storage) enc_index = enc_index + 1 end DECOMPRESS BUILD (VALUE, P, format) var item item.P = P item.N = 0 empty (item.id) append (format, item) end BUILD A.4.4 LSB LSB(k,p,P%) COMPRESS (LSB) var context_val, item, temp, new_item, lsb_val, p_item var n, i context (enc_index, 1, context_val) n = length (context_val) Price, et al. Expires August 2, 2002 [Page 74] Internet-Draft Framework for EPIC-LITE February 2002 p_item = str (n, p) new_item = top (uncompressed_data, n) for i = 1 to r context (enc_index, i, context_val) # check new_item in interval # [value (context_val)-p, value (context_val)-p+2^k] temp = (new_item - context_val + p_item) if (value (temp) < 0) or (value (temp) >= 2^k) then return false endif end loop pop (uncompressed_data, n, item) lsb_val = lsb (item, k) push (compression_stack, lsb_val) save (enc_index, item, storage) enc_index = enc_index + 1 return true end COMPRESS DECOMPRESS (LSB) var context_val, interval_start, interval_end, recd, p_item var new_item, twok_item var n, new, start, end context (enc_index, 1, context_val) n = length (context_val) p_item = str (n, p) twok_item = str (n, 2^k) pop (compression_stack, k, recd) interval_start = context_val - p interval_end = interval_start + twok_item new_item = concat (msb (interval_start, (n-k)), recd) # check whether value (new_item) is in interval # [value (interval_start), value (interval_end)] # allowing for the interval to wrap over zero. If not then # recalculate new_item start = value (interval_start) end = value (interval_end) new = value (new_item) if (((start < end) and ((new < start) or (new > end))) or Price, et al. Expires August 2, 2002 [Page 75] Internet-Draft Framework for EPIC-LITE February 2002 ((start > end) and ((new > start) or (new < end)))) then new_item = concat (msb (interval_end, (n-k)), recd) endif push (uncompressed_data, new_item) save (enc_index, new_item, storage) enc_index = enc_index + 1 end DECOMPRESS BUILD (LSB, P, format) var item item.P = P item.N = k empty (item.id) append (format, item) end BUILD A.4.5 UNCOMPRESSED UNCOMPRESSED(n,d,m,p) COMPRESS (UNCOMPRESSED) var scale_len var unc, len_item scale_len = floor( value((top(control_data)) / d) * m + p) if (stack-size (uncompressed_data) < scale_len) then return false else pop (uncompressed_data, scale_len, unc) push (unc_fields, unc) pop (control_data, len_item) if (length (len_item) <> n) then return false endif push (uncompressed_data, len_item) return true endif end COMPRESS Price, et al. Expires August 2, 2002 [Page 76] Internet-Draft Framework for EPIC-LITE February 2002 DECOMPRESS (UNCOMPRESSED) var scale_len var unc, len_item pop (uncompressed_data, n, len_item) scale_len = floor( (value (len_item) / d) * m + p) push (control_data, len_item) pop (unc_fields, scale_len, unc) push (uncompressed_data, unc) end DECOMPRESS BUILD end BUILD A.4.6 STACK encoding methods A.4.6.1 STACK-TO-CONTROL STACK-TO-CONTROL(n) COMPRESS (STACK-TO-CONTROL) var item pop (uncompressed_data, n, item) push (control_data, item) return true end COMPRESS DECOMPRESS (STACK-TO-CONTROL) var item pop (control_data, item) push (uncompressed_data, item) end DECOMPRESS BUILD (STACK-TO-CONTROL, 100%, format) end BUILD Price, et al. Expires August 2, 2002 [Page 77] Internet-Draft Framework for EPIC-LITE February 2002 A.4.6.2 STACK-FROM-CONTROL STACK-FROM-CONTROL(n) COMPRESS (STACK-FROM-CONTROL) var item pop (control_data, item) if (length (item) <> n) then return false endif push (uncompressed_data, item) return true end COMPRESS DECOMPRESS (STACK-TO-CONTROL) var item pop (uncompressed_data, n, item) push (control_data, item) end DECOMPRESS BUILD (STACK-TO-CONTROL, 100%, format) end BUILD Price, et al. Expires August 2, 2002 [Page 78] Internet-Draft Framework for EPIC-LITE February 2002 A.4.6.3 STACK-PUSH-MSN STACK-PUSH-MSN(n) COMPRESS (STACK-PUSH-MSN) var temp temp = str (n, value (MSN) mod 2^n) push (control_data, temp) return true end COMPRESS DECOMPRESS (STACK-PUSH-MSN) var item pop (control_data, item) end DECOMPRESS BUILD (STACK-PUSH-MSN, 100%, format) end BUILD Price, et al. Expires August 2, 2002 [Page 79] Internet-Draft Framework for EPIC-LITE February 2002 A.4.6.4 STACK-POP-MSN STACK-POP-MSN(n) COMPRESS (STACK-POP-MSN) var item, temp pop (uncompressed_data, n, item) temp = str (n, value (MSN) mod 2^n) if (item <> temp) #value on stack wasn't MSN return false endif return true end COMPRESS DECOMPRESS (STACK-POP-MSN) var temp temp = str (n, value (MSN) mod 2^n) push (uncompressed_data, temp) end DECOMPRESS BUILD (STACK-POP-MSN, 100%, format) end BUILD Price, et al. Expires August 2, 2002 [Page 80] Internet-Draft Framework for EPIC-LITE February 2002 A.4.6.5 STACK-ROTATE STACK-ROTATE(n,m) COMPRESS (STACK-ROTATE) rotate (control_data, n, m) return true end COMPRESS DECOMPRESS (STACK-ROTATE) rotate (control_data, n, (n - m)) end DECOMPRESS BUILD (STACK-ROTATE, 100%, format) end BUILD A.4.7 INFERRED encoding methods A.4.7.1 INFERRED-TRANSLATE INFERRED-TRANSLATE(n,m,a(0),b(0),a(1),b(1)...,a(k-1),b(k-1)) COMPRESS (INFERRED-TRANSLATE) var item, trans_item var found, i found = 0 i = 0 while ((i < k) and (found = 0)) if (value (top (uncompressed_data, m)) = b(i)) pop (uncompressed_data, m, item) trans_item = str (n, a(i)) push (control_data, trans_item) found = 1 else i = i + 1 endif end while return found end COMPRESS Price, et al. Expires August 2, 2002 [Page 81] Internet-Draft Framework for EPIC-LITE February 2002 DECOMPRESS (INFERRED-TRANSLATE) var trans_item var i, found found = 0 i = 0 pop (control_data, trans_item) while ((i < k) and (found = 0)) if (value (trans_item) = a(i)) push (uncompressed_data, m, b(i)) found = 1 else i = i + 1 endif end while end DECOMPRESS BUILD (INFERRED-TRANSLATE, 100%, format) end BUILD Price, et al. Expires August 2, 2002 [Page 82] Internet-Draft Framework for EPIC-LITE February 2002 A.4.7.2 INFERRED-SIZE INFERRED-SIZE(n,p) COMPRESS (INFERRED-SIZE) var item var bits_in_byte # usually 8! if ((bits_in_byte * value (top (uncompressed_data, n))) + p) <> stack-size (uncompressed_data) then return false else pop (uncompressed_data, n, item) return true endif end COMPRESS DECOMPRESS (INFERRED-SIZE) var size var bits_in_byte # usually 8! size = (stack-size (uncompressed_data) + n - p) / bits_in_byte) push (uncompressed_data, n, size) end DECOMPRESS BUILD (INFERRED-SIZE, 100%, format) end BUILD A.4.7.3 INFERRED-OFFSET Price, et al. Expires August 2, 2002 [Page 83] Internet-Draft Framework for EPIC-LITE February 2002 INFERRED-OFFSET(n) COMPRESS (INFERRED-OFFSET) var item, base, offset pop (uncompressed_data, n, item) pop (control_data, base) if (length (base) <> n) then return false endif offset = item - base push (uncompressed_data, offset) push (uncompressed_data, base) return true end COMPRESS DECOMPRESS (INFERRED-OFFSET) var item, base, offset pop (uncompressed_data, n, base) push (control_data, base) pop (uncompressed_data, n, offset) item = offset + base push (uncompressed_data, item) end DECOMPRESS BUILD (INFERRED-OFFSET, 100%, format) end BUILD A.4.7.4 INFERRED-IP-CHECKSUM INFERRED-IP-CHECKSUM(new_method) COMPRESS (INFERRED-IP-CHECKSUM) var compress_function var can_compress var item, ip_sum # zero the ip checksum bits in the header pop (uncompressed_data, 80, item) pop (uncompressed_data, 16, ip_sum) push (uncompressed_data, 16, 0) Price, et al. Expires August 2, 2002 [Page 84] Internet-Draft Framework for EPIC-LITE February 2002 push (uncompressed_data, item) compress_function = lookup-compress-function (extract-name (new_method)) can_compress = call compress_function (extract-name (new_method)) return can_compress end COMPRESS DECOMPRESS (INFERRED-IP-CHECKSUM) var decompress_function var item, temp var init_len, final_len, decomp_len, ip_sum init_len = stack-size (uncompressed_data) decompress_function = lookup-decompress-function (extract-name (new_method)) call decompress_function (extract-name (new_method)) final_len = stack-size (uncompressed_data) decomp_len = final_len - init_len ip_sum = compute-16-checksum (uncompressed_data, decomp_len) pop (uncompressed_data, 80, item) pop (uncompressed_data, 16, temp) push (uncompressed_data, 16, ip_sum) push (uncompressed_data, item) end DECOMPRESS BUILD (INFERRED-IP-CHECKSUM, 100%, format) var build_function build_function = lookup-build-function (extract-name (new_method)) call build_function (extract-name (new_method), 100%, format) end BUILD A.4.8 NBO Price, et al. Expires August 2, 2002 [Page 85] Internet-Draft Framework for EPIC-LITE February 2002 NBO(n) COMPRESS (NBO) var original, swapped var nbo_flag pop (uncompressed_data, n, original) choose (nbo_flag of zero or one) # according to whether original is in network byte order or not # (1 implies it is, 0 implies it isn't) # this decision can be made based on the context history push (uncompressed_data, 1, nbo_flag) if (nbo_flag = 0) then swapped = byte-swap (original) push (uncompressed_data, swapped) else push (uncompressed_data, original) endif # store the original value or other implementation specific # information for making decision about flag value save (enc_index, original, storage) enc_index = enc_index + 1 return true end COMPRESS DECOMPRESS (NBO) var original, decomped, nbo_flag pop (uncompressed_data, n, decomped) pop (uncompressed_data, 1, nbo_flag) if (value (nbo_flag) = 1 then original = decomped else original = byte-swap (decomped) endif push (uncompressed_data, original) enc_index = enc_index + 1 end DECOMPRESS BUILD (NBO, 100%, format) end BUILD Price, et al. Expires August 2, 2002 [Page 86] Internet-Draft Framework for EPIC-LITE February 2002 A.4.9 SCALE SCALE(n) COMPRESS (SCALE) var original var scale_f, scaled_val, remainder pop (uncompressed_data, n, original) choose (scale_f) # such that original is changing by a multile # of scale_f each header. This decision can # be based on context history scaled_val = value (original) / scale_f remainder = value (original) mod scale_f push (uncompressed_data, n, scaled_val) push (uncompressed_data, n, remainder) push (uncompressed_data, n, scale_f) # store the original value or other implementation specific # information for making decision about scale_f save (enc_index, original, storage) enc_index = enc_index + 1 return true end COMPRESS DECOMPRESS (SCALE) var scaled_val, scale_f, remainder var original pop (uncompressed_data, n, scale_f) pop (uncompressed_data, n, remainder) pop (uncompressed_data, n, scaled_val) original = ((scaled_val * scale_f) + remainder) mod 2^n push (uncompressed_data, n, original) enc_index = enc_index + 1 end DECOMPRESS BUILD (SCALE, 100%, format) end BUILD Price, et al. Expires August 2, 2002 [Page 87] Internet-Draft Framework for EPIC-LITE February 2002 A.4.10 OPTIONAL OPTIONAL(new_method) COMPRESS (OPTIONAL) var flag var compress_function var can_compress, n var enc pop (control_data, flag) if (value (flag) = 1) then compress_function = lookup-compress-function (extract-name (new_method)) can_compress = call compress_function (extract-name (new_method)) else choose (format to encode new_method) # compressor choice of format for new_method, where enc is the # format chosen if u_flag = 0 then # not under U method then pad with bits of zero n = count-bits (new_method, enc) push (compression_stack, n, 0) else # don't need to pad as under U method endif store (method_chosen, OPTIONAL, enc) can_compress = 1 endif push (control_data, flag) return can_compress end COMPRESS DECOMPRESS (OPTIONAL) var flag, item var decompress_function var n var enc pop (control_data, flag) if (value (flag = 1)) then Price, et al. Expires August 2, 2002 [Page 88] Internet-Draft Framework for EPIC-LITE February 2002 decompress_function = lookup-decompress-function (extract-name (new_method)) call decompress_function (extract-name (new_method)) else # enc is the format sent for new_method (obtained from the # indicator flags) if u_flag = 0 then # not under U method so need to remove bits of padding n = count-bits (new_method, enc) pop (compression_stack, n, item) else # don't need to remove padding as under U method endif endif push (control_data, flag) end DECOMPRESS BUILD (OPTIONAL, 100%, format) var build_function build_function = lookup-build-function (extract-name (new_method)) call build_function (extract-name (new_method), P, format) end BUILD A.4.11 MANDATORY MANDATORY(new_method) COMPRESS (MANDATORY) var flag var compress_function var can_compress pop (control_data, flag) if (value (flag) <> 1) then return false else compress_function = lookup-compress-function Price, et al. Expires August 2, 2002 [Page 89] Internet-Draft Framework for EPIC-LITE February 2002 (extract-name (new_method)) can_compress = call compress_function (extract-name (new_method)) endif push (control_data, flag) return can_compress end COMPRESS DECOMPRESS (MANDATORY) var decompress_function var flag pop (control_data, flag) decompress_function = lookup-decompress-function (extract-name (new_method)) call decompress_function (extract-name (new_method)) push (control_data, flag) end DECOMPRESS BUILD (MANDATORY, 100%, format) var build_function build_function = lookup-build-function (extract-name (new_method)) call build_function (extract-name (new_method), 100%, format) end BUILD A.4.12 CONTEXT CONTEXT(new_method,k) COMPRESS (CONTEXT) var n, j, m var compress_function var can_compress n = ceiling (log2(k-1)) choose (j < k) # compressor choice m = context-size (new_method) Price, et al. Expires August 2, 2002 [Page 90] Internet-Draft Framework for EPIC-LITE February 2002 enc_index = enc_index + j * m compress_function = lookup-compress-function (extract-name (new_method)) can_compress = call compress_function (extract-name (new_method)) push (uncompressed_data, n, j) enc_index = enc_index + (k - j - 1) * m return can_compress end COMPRESS DECOMPRESS (CONTEXT) var n, j, m var decompress_function var index n = ceiling (log2(k-1)) pop (uncompressed_data, n, index) j = value (index) m = context-size (new_method) enc_index = enc_index + j * m decompress_function = lookup-decompress-function (extract-name (new_method)) call decompress_function (extract-name (new_method)) enc_index = enc_index + (k - j - 1) * m end DECOMPRESS BUILD (CONTEXT, 100%, format) var build_function build_function = lookup-build-function (new_method) call build_function (extract-name (new_method), 100%, format) end BUILD A.4.13 LIST LIST(n,d,m,p,z,new_method(0),new_method(1),..., new_method(k-1),v(0),v(1),...,v(j)) COMPRESS (LIST) Price, et al. Expires August 2, 2002 [Page 91] Internet-Draft Framework for EPIC-LITE February 2002 var scale_len, i, can_compress, stack_len, bits var comp_len, order, presence var present [0..(k-1)], unc_length var compress_function top(control_data, unc_length) scale_len = floor( value(unc_length) / d) * m + p) for i = 0 to (k - 1) present [i] = str (1,0) end loop order = 0 bits = ceiling (log2(k-1)) i = 0 list_start_enc_index = enc_index while (scale_len > 0) # basically loop through the methods until all scale_len bits # are compressed and any of the methods which aren't used are # marked as not used. The order in which methods are checked # is implementation specific but some ways will require # changing the order more frequently (reducing efficiency) than # others. stack_len = stack-size (uncompressed_data) can_compress = false i = 0 while (i < k) and (can_compress = false) if (value (present [i]) = 0) and ((i >= j) or ((i < j) and (value (top (uncompressed_data, z)) = v(i)))) then present [i] = str (1,1) order = order * 2^bits + i push (control_data, present [i]) for x = 0 to i enc_index = enc_index + context-size (new_methods(x)) compress_function = lookup-compress-function (extract-name (new_method(i))) can_compress = call compress_function (extract-name (new_method(i))) if can_compress = false then return false endif Price, et al. Expires August 2, 2002 [Page 92] Internet-Draft Framework for EPIC-LITE February 2002 comp_len = stack_len - stack-size (uncompressed_data) scale_len = scale_len - comp_len pop (control_data, present [i]) enc_index = list_start_enc_index if (length (present[i]) <> 1) then return false endif else i = i + 1 endif end while end while # process remaining LIST entries that have not been used # (i.e. are not present in the header) for i = 0 to (k - 1) if (value (present [i]) = 0) then push (control_data, present [i]) for x = 0 to i enc_index = enc_index + context-size (new_methods(x)) order = order * 2^bits + i compress_function = lookup-compress-function (extract-name (new_method(i))) can_compress = call compress_function (extract-name (new_method(i))) if can_compress = false then return false endif pop (control_data, present [i]) enc_index = list_start_enc_index if (length (present[i]) <> 1) then return false endif endif end loop presence = 0 for i = 0 to (k - 1) presence = presence * 2 + value (present[i]) end loop push (uncompressed_data, k, presence) push (uncompressed_data, bits*k, order) Price, et al. Expires August 2, 2002 [Page 93] Internet-Draft Framework for EPIC-LITE February 2002 return true end COMPRESS DECOMPRESS (LIST) var decompress_function var presence, order, i, j, bits, uncomp_len, old_len, var original_len var present [0..(k - 1)] var presence_item, order_item bits = ceiling (log2(k-1)) list_start_enc_index = enc_index pop (uncompressed_data, bits*k, order_item) pop (uncompressed_data, k, presence_item) presence = value (presence_item) order = value (order_item) for i = 0 to (k - 1) present [(k - 1) - i] = lsb (presence, 1) presence = (presence - value (present [(k - 1) - i])) / 2 end loop for j = 0 to (k - 1) i = value (lsb (order, bits)) order = (order û i )/ 2^bits push (control_data, present [i]) old_len = stack-size (uncompressed_data) for x = 0 to i enc_index = enc_index + context-size (new_methods(x)) decompress_function = lookup-decompress-function (extract-name (new_method(i))) call decompress_function (extract-name (new_method(i))) enc_index = list_start_enc_index uncomp_len = uncomp_len + (stack-size (uncompressed_data) - old_len) pop (control_data, present[i]) original_len = ((uncomp_len - p) * d) / m push (control_data, n, original_len) end loop end DECOMPRESS Price, et al. Expires August 2, 2002 [Page 94] Internet-Draft Framework for EPIC-LITE February 2002 BUILD (LIST, 100%, format) var i var build_function var temp_format item.P = convert-percentage (100%) item.N = 0 empty (item.id) append (format, item) for i = 0 to (k - 1) empty (temp_format) build_function = lookup-build-function ( extract-name (new_method(i))) call build_function (extract-name (new_method(i), 100%, temp_format)) DISCARD (temp_format) COMBINE (format, temp_format) end loop end BUILD A.4.13.1 LIST-NEXT LIST-NEXT (n,new_method(0),new_method(1),..., new_method(k-1),v(0),v(1),...,v(j)) # This pseudocode is very similar to LIST, the differences being # from where the information about which method to use next comes # from and how to tell when there is no more data to compress using # this method COMPRESS (LIST) var i, can_compress, bits, order, presence, p var present [0..(k-1)], v, null var compress_function for i = 0 to (k - 1) present [i] = str (1,0) end loop order = 0 bits = ceiling (log2(k-1)) i = 0 Price, et al. Expires August 2, 2002 [Page 95] Internet-Draft Framework for EPIC-LITE February 2002 pop (control_data, v) if (length (v) <> n) then return false endif null = str (0, 0) while (v <> null) # basically loop through the methods until no more information # has been put on the control_data stack by the previous method # (i.e. the end of the list has been reached). The order in # which methods are checked is implementation specific but some # ways will require changing the order more frequently # (reducing efficiency) than others. can_compress = false i = 0 while (i < k) and (can_compress = false) if (value (present [i]) = 0) and ((i >= j) or ((i < j) and (v = v(i)))) then present [i] = str (1,1) order = order * 2^bits + i push (control_data, present [i]) p = stack-pointer (control_data) compress_function = lookup-compress-function (extract-name (new_method(i))) can_compress = call compress_function (extract-name (new_method(i))) if can_compress = false then return false endif # find out whether there is more to compress by checking # the position of the stack pointer if (p <> stack-pointer (control_data)) then pop (control_data, v) if (length (v) <> n) then return false endif pop (control_data, present [i]) else pop (control_data, present [i]) v = null endif Price, et al. Expires August 2, 2002 [Page 96] Internet-Draft Framework for EPIC-LITE February 2002 if (length (present[i]) <> 1) then return false endif else i = i + 1 endif end while end while # process remaining LIST-NEXT entries that have not been used # (i.e. are not present in the header) for i = 0 to (k - 1) if (value (present [i]) = 0) then push (control_data, present [i]) order = order * 2^bits + i compress_function = lookup-compress-function (extract-name (new_method(i))) can_compress = call compress_function (extract-name (new_method(i))) if can_compress = false then return false endif pop (control_data, present [i]) if (length (present[i]) <> 1) then return false endif endif end loop presence = 0 for i = 0 to (k - 1) presence = presence * 2 + value (present[i]) end loop push (uncompressed_data, k, presence) push (uncompressed_data, bits*k, order) return true end COMPRESS DECOMPRESS is almost the same as for LIST - the only difference being that there is no need to keep track of length and push it onto the Price, et al. Expires August 2, 2002 [Page 97] Internet-Draft Framework for EPIC-LITE February 2002 control stack at the end as this is implicit in the choice of methods. BUILD is the same as for LIST A.4.14 FLAG encoding methods A.4.14.1 N N(new_method) COMPRESS (N) var compress_function var can_compress, temp temp = enc_index compress_function = lookup-compress-function (extract-name (new_method)) can_compress = call compress_function (extract-name (new_method)) if (enc_index <> temp) then clear (temp, storage) endif return can_compress end COMPRESS DECOMPRESS (N) var decompress_function var temp temp = enc_index decompress_function = lookup-decompress-function (extract-name (new_method)) call decompress_function (extract-name (new_method)) if (enc_index <> temp) then clear (temp, storage) endif end DECOMPRESS BUILD (N, (P = extract-probability (new_method)), format) var build_function Price, et al. Expires August 2, 2002 [Page 98] Internet-Draft Framework for EPIC-LITE February 2002 build_function = lookup-build-function (method) call build_function (extract-name (new_method), P, format) end BUILD A.4.14.2 U U(new_method) COMPRESS (U) var compress_function var can_compress if u_flag = 0 then compression_stack = unc_fields endif u_flag = u_flag + 1 compress_function = lookup-compress-function (extract-name (new_method)) can_compress = call compress_function (extract-name (new_method)) u_flag = u_flag - 1 if u_flag = 0 then compression_stack = compressed_data endif return can_compress end COMPRESS DECOMPRESS (U) var decompress_function if u_flag = 0 then compression_stack = unc_fields endif u_flag = u_flag + 1 decompress_function = lookup-decompress-function (extract-name (new_method)) call decompress_function (extract-name (new_method)) u_flag = u_flag - 1 Price, et al. Expires August 2, 2002 [Page 99] Internet-Draft Framework for EPIC-LITE February 2002 if u_flag = 0 then compression_stack = compressed_data endif end DECOMPRESS BUILD (U, (P = extract-probability (new_method)), format) var build_function build_function = lookup-build-function (method) call build_function (extract-name (new_method), P, format) foreach el in format el.N = 0 end loop end BUILD A.4.15 FORMAT FORMAT(new_method(0), ..., new_method(k - 1)) COMPRESS (FORMAT) var n, can_compress, index_val var compress_function n = ceiling(log2(k-1)) choose (index_val < k) # The compressor needs to make a choice on which FORMAT # to use. The algorithm for making this choice is entirely # up to the compressor. It may wish to take into account # compression performance (of compressed packets) and # flexibility of compression. The selection processing # should allow a successful match to be made (if possible), # but must also terminate in the case where the packet is # incompressible. It may be that a choice is made based on # "CO" state processing, which should be carried forward # into IR(-DYN) state packet generation. compress_function = lookup-compress-function ( extract-name(new_method(index_val))) can_compress = call compress_function ( extract-name (new_method(index_val))) Price, et al. Expires August 2, 2002 [Page 100] Internet-Draft Framework for EPIC-LITE February 2002 if (can_compress <> false) then current_set = current_set * k + index_val endif if can_compress = false then return false else push (uncompressed_data, n, index_val) endif return true end COMPRESS DECOMPRESS (FORMAT) var decompress_function var n, index n = ceiling(log2(k-1)) pop (uncompressed_data, n, index) if (compressor_state <> "CO") then # get-method-list in decode-indicator-flags has to assume # one of the methods from FORMAT to get a list of methods # used. This may not be the one actually used according to # the index so the list of methods (ie method_chosen) must # be reparsed from the original main_list_elt in light of # the updated information. format-get-method-list (main_list_elt, method_chosen, new_method (value (index))) current_set = current_set * k + value (index) endif decompress_function = lookup-decompress-function ( extract-name (new_method(value (index)))) call decompress_function ( extract-name (new_method(value (index)))) end DECOMPRESS BUILD (FORMAT, 100%, format) var j, i var build_function var temp_format Price, et al. Expires August 2, 2002 [Page 101] Internet-Draft Framework for EPIC-LITE February 2002 if (compressor_state = "CO") then j = current_set mod k current_set = current_set / k build_function = lookup-build-function ( extract-name (new_method(j))) call build_function (extract-name (new_method(j)), 100%, format) else for i = 0 to (k - 1) empty (temp_format) build_function = lookup-build-function ( extract-name (new_method(i))) call build_function (extract-name (new_method(i), 100%, temp_format) foreach item in temp_format append (item.id, new_method(i)) append (format, item) end loop end loop DISCARD (format) endif end BUILD Price, et al. Expires August 2, 2002 [Page 102] Internet-Draft Framework for EPIC-LITE February 2002 A.4.16 CRC CRC(n,P%) COMPRESS (CRC) var crc_function crc_function = lookup-crc-function (n) call crc_function (n, crc_static + crc_dynamic, crc) push (compression_stack, crc) return true end COMPRESS DECOMPRESS (CRC) pop (compression_stack, n, crc) end DECOMPRESS BUILD (CRC, P%, format) var item item.P = P item.N = n empty (item.id) append (format, item) end BUILD A.4.16.1 MSN-LSB MSN-LSB(k,p,P%) COMPRESS (MSN-LSB) var context_val, item, temp, lsb_val, p_item var n, i context (enc_index, 1, context_val) n = length (context_val) p_item = str (n, p) for i = 1 to r context (enc_index, i, context_val) Price, et al. Expires August 2, 2002 [Page 103] Internet-Draft Framework for EPIC-LITE February 2002 # check MSN in interval # [value (context_val)-p, value (context_val)-p+2^k] temp = MSN - context_val + p_item if ((value (temp) < 0) or (value (temp) >= 2^k)) then return false endif end loop lsb_val = lsb (MSN, k) push (compression_stack, lsb_val) save (enc_index, MSN, storage) enc_index = enc_index + 1 msn_bits = k return true end COMPRESS DECOMPRESS (MSN-LSB) var context_val, interval_start, interval_end, recd, p_item var new_item, twok_item, temp, lsbs, twok_extra var n, m, new, start, end context (enc_index, 1, context_val) n = length (context_val) p_item = str (n, p) twok_item = str (n, 2^k) twok_extra = str (n, 2^(k + length (msn_lsbs))) pop (compression_stack, k, temp) recd = concat (msn_lsbs, temp) interval_start = context_val - p_item interval_end = interval_start + twok_extra new_item = concat (msb (interval_start, (n-k-length (msn_lsbs))), recd) # check whether value (new_item) is in interval # [value (interval_start), value (interval_end)] # allowing for the interval to wrap over zero. If not then # recalculate new_item start = value (interval_start) end = value (interval_end) new = value (new_item) if (((start < end) and ((new < start) or (new > end))) or Price, et al. Expires August 2, 2002 [Page 104] Internet-Draft Framework for EPIC-LITE February 2002 ((start > end) and ((new > start) or (new < end)))) then new_item = concat (msb (interval_end, (n-k-length (msn_lsbs))), recd) endif MSN = new_item save (enc_index, new_item, storage) enc_index = enc_index + 1 end DECOMPRESS BUILD (MSN-LSB, P, format) var item item.P = P item.N = k empty (item.id) append (format, item) end BUILD Price, et al. Expires August 2, 2002 [Page 105] Internet-Draft Framework for EPIC-LITE February 2002 A.4.16.2 MSN-IRREGULAR MSN-IRREGULAR(n,P%) COMPRESS (MSN-IRREGULAR) push (compression_stack, MSN) save (enc_index, MSN, storage) enc_index = enc_index + 1 msn_bits = n return true end COMPRESS DECOMPRESS (MSN-IRREGULAR) pop (compression_stack, n, MSN) save (enc_index, MSN, storage) enc_index = enc_index + 1 end DECOMPRESS BUILD (MSN-IRREGULAR, P, format) var item item.P = P item.N = n empty (item.id) append (format, item) end BUILD Price, et al. Expires August 2, 2002 [Page 106] Internet-Draft Framework for EPIC-LITE February 2002 A.4.16.3 SET-MSN SET-MSN(n) COMPRESS (SET-MSN) var item pop (uncompressed_data, n, item) MSN = item return true end COMPRESS DECOMPRESS (SET-MSN) push (uncompressed_data, MSN) end DECOMPRESS BUILD (SET-MSN, 100%, format) end BUILD A.5 ABNF description of the input language The following is an ABNF description of a ROHC [1] profile generated using EPIC-LITE: = [ ] [ ] = 1*(%x09 | %x0A | %x0D | %x20) ; white space used as ; delimiters = "profile_identifier" Price, et al. Expires August 2, 2002 [Page 107] Internet-Draft Framework for EPIC-LITE February 2002 = "max_formats" = "max_sets" = "bit_alignment" = "npatterns" = "CO packet" = "IR-DYN packet" = "IR packet" = 1*() = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" = "0x" *() = | "a" | "b" | "c" | "d" | "e" | "f" | "A" | "B" | "C" | "D" | "E" | "F" The following is an ABNF description of a new encoding method written using the input language (note that the previous ABNF rules still apply). Comments are contained between a ";" symbol and the end of the line, and are ignored in the input language. = "=" 1*( ) Price, et al. Expires August 2, 2002 [Page 108] Internet-Draft Framework for EPIC-LITE February 2002 = *( "|" ) = ["(" *("," ) ")"] = *( | | "_" | "-" | "/" | ".") = "A" | "B" | "C" | ... | "X" | "Y" | "Z" | "a" | ... | "z" = | | | | = [] [] ["." []] "%" = | | = "0b" *() = "0" | "1" = = ["-"] Price, et al. Expires August 2, 2002 [Page 109] Internet-Draft Framework for EPIC-LITE February 2002 Full Copyright Statement Copyright (C) The Internet Society (2002). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society. Price, et al. Expires August 2, 2002 [Page 110]