INTERNET-DRAFT J. Heath April 17, 2002 J. Border Expires: October 17, 2002 Hughes Network Systems PPP V.44/LZJH Compression Protocol draft-heath-ppp-v44-00.txt This document is an Internet-Draft and is subject to all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and it 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. Status of this Memo This memo is an Internet-Draft that provides information for the Internet community. Distribution of this memo is unlimited. Comments are invited and should be addressed to the authors whose contact information is in Section 9. This Internet-Draft expires on October 17, 2002. Abstract The Point-to-Point Protocol [PPP] provides a standard means for transporting multi-protocol datagrams over point-to-point links. The PPP Compression Control Protocol [CCP] provides a means to negotiate and utilize compression protocols over PPP encapsulated links. This memo describes a means for compressing PPP encapsulated datagrams by utilizing the data compression algorithm that is described in International Telecommunication Union (ITU-T) Recommendation V.44 [V44]. Recommendation V.44 is a modem standard but Annex B of the recommendation describes the implementation of V.44 in packet networks. This memo defines the application of V.44, with single or multiple compression dictionaries,to the PPP Compression Control Protocol (RFC 1962). Heath Internet-Draft [Page 1] PPP V.44/LZJH Compression Protocol April 2002 Table of Contents 1 Introduction................................................... 2 1.1 General................................................... 3 1.2 Background of LZJH Data Compression....................... 3 1.3 Intellectual Property Rights.............................. 4 1.4 Specification of Requirements............................. 4 2 V.44 Compression Operation..................................... 4 2.1 Datagram Mode............................................. 5 2.1.1 Attributes........................................... 5 2.1.2 Transmit Operation................................... 6 2.1.3 Receive Operation.................................... 6 2.1.4 Dictionary Synchronization........................... 6 2.1.5 V.44 Compressed Datagram Format...................... 6 2.1.6 Data Expansion....................................... 7 2.1.7 Configuration........................................ 7 2.2 Multi-Datagram Mode....................................... 7 2.2.1 Attributes........................................... 7 2.2.2 Transmit Operation................................... 7 2.2.3 Receive Operation.................................... 8 2.2.4 Dictionary Synchronization........................... 8 2.2.5 V.44 Compressed Datagram Format...................... 8 2.2.6 Data Expansion....................................... 9 2.2.7 Configuration........................................ 9 2.3 Individual Link Mode...................................... 9 2.3.1 Attributes........................................... 9 2.3.2 Transmit Operation................................... 9 2.3.3 Receive Operation.................................... 10 2.3.4 Dictionary Synchronization........................... 10 2.3.5 Individual Link Compressed Datagram Format........... 11 2.3.5.1 Number of Dictionaries is 128 or Less........... 11 2.3.5.2 Number of Dictionaries is More Than 128......... 12 2.3.6 Data Expansion....................................... 12 2.3.7 Configuration........................................ 13 3 V.44 Configuration Option...................................... 13 3.1 Negotiation Rules......................................... 14 4 V.44 Compressed Data........................................... 15 4.1 Padding................................................... 15 5 Datagram Integrity............................................. 15 6 Reliable and In-order Delivery of Datagrams.................... 15 7 Security Considerations........................................ 16 8 References..................................................... 16 9 Authors' Addresses............................................. 16 10 Full Copyright Statement...................................... 17 1 Introduction ITU-T Recommendation V.44 is based upon the LZJH data compression algorithm. Throughout the remainder of this memo the terms V.44 and LZJH are synonymous. Heath Internet-Draft [Page 2] PPP V.44/LZJH Compression Protocol April 2002 1.1 General This memo specifies the application of V.44 data compression, a lossless data compression algorithm, to PPP datagrams. V.44 data compression is to be used in conjunction with the Point-to-Point Protocol (PPP) [PPP] and the PPP Compression Control Protocol (CCP) [CCP]. This memo is written with the assumption that the reader has an understanding of the PPP and CCP protocols. For the PPP application, V.44 can operate using one of three compression modes defined as follows: 1. Datagram Mode: independent datagram compression using V.44 Packet Method where a single dictionary is utilized for all virtual links and the dictionary is re-initialized between each datagram. This mode uses a minimum amount of memory and does not require the reliable, in-order delivery of datagrams. However the compression obtained may be less than with the other modes. V.44 Packet Method is described in Annex B.1 of [V44]. 2. Multi-Datagram Mode: datagram compression using V.44 Multi-Packet Method where a single dictionary is utilized for all virtual links and several datagrams, from potentially different links, are processed as a continuation using a single history buffer. This mode requires the reliable, in-order delivery of datagrams. Multi-Datagram Mode generally requires somewhat more memory than Datagram Mode but should obtain better compression.V.44 Multi-Packet Method is described in Annex B.2 of [V44]. 3. Individual Link Mode: datagram compression using V.44 Multi-Packet Method where a separate dictionary is utilized for each virtual link and several datagrams on a link are processed as a continuation using a separate history buffer for each link. This mode requires dictionary and history buffer memory for each virtual link and requires the reliable, in-order delivery of datagrams on each link. However, this mode should obtain the best compression of the 3 modes. V.44 Multi-Packet Method is described in Annex B.2 of [V44]. 1.2 Background of LZJH Data Compression LZJH is similar to the algorithm described in [LZ78] although it also has aspects that are similar to the algorithm described in [LZ77]. As such, it provides the execution speed and low memory requirements of [LZ78] with compression ratios that are better than [LZ77]. Originally developed for the satellite industry to compress IP datagrams independently, it is ideal for the PPP data compression application. The LZJH algorithm was modified to compress a continuous stream of data for a modem environment and this modified version is the basis Heath Internet-Draft [Page 3] PPP V.44/LZJH Compression Protocol April 2002 for Recommendation V.44. LZJH is an adaptive, general purpose, lossless data compression algorithm. It was selected by the ITU as the basis for Recommendation V.44 based on its performance across a wide variety of data types, particularly web HTML's, and based on its compression ratio characteristics, per MIP and memory utilized (as compared to other candidate algorithms). Its encoder is extremely efficient and can encode a redundant string using just a few additional bits the second time that string is encountered in the data stream. While encoding a datagram, unmatched characters are encoded as ordinals and matched redundant strings of characters are encoded as codewords or string-extension lengths that represent the redundant strings. While decoding a compressed datagram, the ordinals, codewords, and string-extension lengths are interpreted to re-create exactly the original datagram. For V.44 Packet Method, where each datagram is processed independently and dictionaries are re-initialized between datagrams, the V.44 algorithm defaults to a dictionary of 1525 entries. This requires a total of only 16K of dictionary memory for the encoder and decoder. For V.44 Multi-Packet Method, where several datagrams are processed separately but as a continuation (i.e. no re-initialization between each datagram), the V.44 algorithm defaults to a dictionary of 2048 entries and a history of 10K bytes. This requires a total of about 40K of dictionary and history memory for the encoder and decoder. The details of LZJH data compression can be found in [V44]. 1.3 Intellectual Property Rights The IETF has been notified of intellectual property rights claimed in regard to some or all of the specifications contained in this memo. For more information, consult the online list of claimed rights. 1.4 Specification of Requirements The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this memo are to be interpreted as described in [KEY]. 2 V.44 Compression Operation Before any V.44 compressed datagrams may be communicated: 1. PPP MUST reach the Network-Layer Protocol phase. 2. V.44 MUST be negotiated as the primary compression algorithm. 3. The Compression Control Protocol (CCP) MUST reach the Opened state. Heath Internet-Draft [Page 4] PPP V.44/LZJH Compression Protocol April 2002 Only datagrams with PPP Protocol field numbers in the range 0x0000 to 0x3FFF and neither 0xFD nor 0xFB SHALL be passed to the V.44 encoder to be compressed. Datagrams with PPP Protocol field numbers of 0xFD or 0XFB MUST be discarded and not compressed or sent. Other PPP datagrams with PPP Protocol field numbers outside that range MUST NOT be passed to the V.44 encoder and MUST always be sent uncompressed. V.44 datagrams are created by the encoding/transmitting processes and are identified by either an 0xFD or 0xFB in the PPP Protocol ID Field (PPP Protocol field). The receiving peer of V.44 datagrams SHALL insure that the data has not been corrupted or packetized segments of the V.44 datagram were lost prior to passing the compressed information field to the V.44 decoder. Data integrity, reliable in-order delivery, and segmentation/re-assembly methods are beyond the scope of this memo. The maximum length of the V.44 datagram transmitted over a PPP link is the same as the maximum length of the Information field of a PPP encapsulated datagram. Prior to compression, the uncompressed data begins with the PPP Protocol ID Field. Protocol-Field-Compression MAY be used on this value, if it has been successfully negotiated for the link. The PPP Protocol ID Field is followed by the original Information field. The length of the uncompressed data field is limited only by the allowed size of the compressed data field and the higher protocol layers. PPP Link Control Protocol packets MUST NOT be sent within V.44 datagrams. PPP Network Control Protocol packets MUST NOT be sent within V.44 datagrams. The following 3 sub-sections describe the operation of the three V.44 operating modes for compressing datagrams in the PPP application. 2.1 Datagram Mode Datagram mode is used when each datagram is to be compressed independantly of other datagrams, i.e. dictionaries are re-initialized between each datagram, regardless of whether the stream of datagrams are from a single link or a multi-link bundle. 2.1.1 Attributes 1. Each datagram is compressed and transmitted separately within a single V.44 Compressed Datagram. 2. Conforms to V.44 Packet Method as described in [V44] section B.1. 3. Each peer requires just a single dictionary for each direction. 4. Does not require a history buffer. Heath Internet-Draft [Page 5] PPP V.44/LZJH Compression Protocol April 2002 5. Does not require the reliable, in-order delivery of datagrams between the compression peers. 6. Encoder and decoder dictionaries are re-initialized after processing each datagram. 2.1.2 Transmit Operation Datagrams with a PPP Protocol field value in the range 0x0000 to 0x3FFF MAY be passed to the V.44 encoder to be compressed. If compression is successful the entire compressed datagram is placed into the PPP information field and the PPP Protocol field value is set to 0xFD to indicate a V.44 compressed datagram. If compression is not successful, the original datagram is transmitted with its original value in the PPP Protocol field (uncompressed datagram). The V.44 algorithm, initialized for Packet Method, will re-initialize the encoder dictionary after processing each datagram. 2.1.3 Receive Operation The information field of all valid datagrams with a PPP Protocol field value of 0xFD MUST be passed to the V.44 decoder to be decompressed. The decompression process will yield a datagram with the original PPP Protocol field and information field. Datagrams with a PPP Protocol field value in the range 0x0000 to 0x3FFF, but not 0xFD, MUST NOT be passed to the decoder since they have not been compressed. The V.44 algorithm, initialized for Packet Method, will re-initialize the decoder dictionary after processing each V.44 datagram. 2.1.4 Dictionary Synchronization Both encoder and decoder re-initialize the dictionary between each datagram which insures dictionary synchronization under all circumstances including out of order delivery and lost datagrams. 2.1.5 V.44 Compressed Datagram Format Datagrams that are not successfully compressed are sent in their original form, refer to [PPP] for possible formats. The format of V.44 compressed datagrams of type 0xFD is shown below. The fields are transmitted from left to right. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PPP Protocol (0x00FD) | Compressed Data ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Heath Internet-Draft [Page 6] PPP V.44/LZJH Compression Protocol April 2002 The PPP Protocol field is a 2 octet field described in the Point-to-Point Protocol Encapsulation [PPP] that is set to 0x00FD to indicate a V.44 Compressed datagram. This value MAY be compressed when Protocol-Field-Compression is negotiated. The Compressed Data is contained in the PPP Information field and consists of the compressed original datagram. 2.1.6 Data Expansion Data expansion is not possible since those datagrams where compression does not result in a smaller datagram are transmitted in their original form. 2.1.7 Configuration Refer to section 3 for the negotiation of V.44 compression on a link and the configuration of Datagram Mode. 2.2 Multi-Datagram Mode Multi-datagram mode is used when several datagrams are compressed as a continuation, using information in earlier datagrams to compress later datagrams, regardless of whether the stream of datagrams are from a single link or a multi-link bundle. 2.2.1 Attributes 1. Each datagram is compressed and transmitted separately within a single V.44 Compressed Datagram even though two or more datagrams may be compressed before the dictionary is re-initialized. 2. Conforms to V.44 Multi-Packet Method as described in [V44] section B.2. 3. Each peer requires just a single dictionary and history for each direction. 4. Requires the reliable, in-order delivery of all original uncompressed and V.44 compressed datagrams. 2.2.2 Transmit Operation Datagrams with a PPP Protocol field value in the range 0x0000 to 0x3FFF MUST be passed to the V.44 encoder to be compressed. If compression is successful the entire compressed datagram is placed into the PPP information field and the PPP Protocol field value is set to 0xFD to indicate a V.44 compressed datagram. If compression is not successful, the original datagram is sent with its original value in the PPP Protocol field (uncompressed datagram). The encoder also MUST re-initialize its dictionary when compression is not successful. Heath Internet-Draft [Page 7] PPP V.44/LZJH Compression Protocol April 2002 2.2.3 Receive Operation The information field of all datagrams with a PPP Protocol field value of 0xFD MUST be passed to the V.44 decoder to be decompressed. The decompression process will yield a datagram with the original PPP Protocol field and information field. Datagrams with a PPP Protocol field value in the range 0x0000 to 0x3FFF, but not 0xFD, MUST NOT be passed to the decoder since they have not been compressed. The receiver MUST also re-initialize the V.44 decoder dictionary when an uncompressed datagram is received. 2.2.4 Dictionary Synchronization When either the encoder dictionary or history becomes filled the V.44 algorithm re-initializes the encoder dictionary (and history), and inserts a REINIT control code into the compressed data to indicate to the peer decoder that it MUST re-initialize its dictionary and history. When the encoder is unsuccessful in compressing a datagram, the transmitting entity MUST transmit the original datagram and MUST re-initialize the encoder dictionary and history. When the peer receiving entity receives a datagram that does not have a 0xFD value in its PPP Protocol field, i.e. it is an original uncompressed datagram, it MUST NOT pass that datagram to the V.44 decoder and it MUST re-initializes the decoder dictionary and history. 2.2.5 V.44 Compressed Datagram Format Datagrams that are not successfully compressed are sent in their original form, refer to [PPP] for possible formats. The format of V.44 compressed datagrams of type 0xFD is shown below The fields are transmitted from left to right. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PPP Protocol (0x00FD) | Compressed Data ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The PPP Protocol field is a 2 octet field described in the Point-to-Point Protocol Encapsulation [PPP] that is set to 0x00FD to indicate a V.44 compressed datagram. This value MAY be compressed when Protocol-Field-Compression is negotiated. The Compressed Data is contained in the PPP Information field that consists of the compressed original datagram. Heath Internet-Draft [Page 8] PPP V.44/LZJH Compression Protocol April 2002 2.2.6 Data Expansion Data expansion is not possible since those datagrams where compression does not result in a smaller datagram are transmitted in their original form. 2.2.7 Configuration Refer to section 3 for the negotiation of V.44 compression on a link and the configuration of Multi-Datagram Mode. 2.3 Individual Link Mode Individual link mode is used when each individual link of a multi-link bundle has a separate compression context for some or all links and several datagrams on a link are compressed as a continuation, using information in earlier datagrams to compress later datagrams. 2.3.1 Attributes 1. Each datagram is compressed and transmitted separately within a single V.44 Compressed Datagram even though two or more datagrams on a link may be compressed before the dictionary is re-initialized. 2. Conforms to V.44 Multi-Packet Method as described in [V44] section B.2. 3. Each peer requires a separate dictionary and history for each separate link for each direction. 4. Requires the reliable, in-order delivery on each link of all V.44 individual link compressed datagrams. 2.3.2 Transmit Operation All datagrams, for links where V.44 compression is active, with a PPP Protocol field value in the range 0x0000 to 0x3FFF MUST be passed to the V.44 encoder to be compressed. The transmitting entity MUST insure that the dictionary used by the encoder to compress the datagram corresponds to the correct link. An 0xFB is placed into the PPP Protocol field to indicate a V.44 individual link compressed datagram. The dictionary number is placed into the Dictionary ID sub-field of the V.44 Control field. If compression is successful the entire compressed datagram is placed into the PPP information field and the Compressed Bit in V.44 Control field is set to a 1. If compression is not successful, the original datagram, including PPP Protocol field, is placed into the PPP information field and the Compressed Bit in V.44 Control field is set to a 0. The transmitting Heath Internet-Draft [Page 9] PPP V.44/LZJH Compression Protocol April 2002 entity MUST also re-initialize the encoder dictionary and history corresponding to that datagrams link when compression is not successful. 2.3.3 Receive Operation Datagrams with a PPP Protocol field value of 0xFD are invalid and MUST be discarded. Datagrams with a PPP Protocol field value in the range 0x0000 to 0x3FFF, but not 0xFB, are assumed to correspond to links where V.44 compression is not active and MUST NOT be passed to the V.44 decoder by the receiving entity. Datagrams with a PPP Protocol field value of 0xFB are processed by the receiving entity depending upon the value of the Compressed Bit in the V.44 Control field as follows: - if the Compressed Bit is a 1, the receiving entity uses the Dictionary ID sub-field to access the corresponding dictionary and passes the PPP information field to the V.44 decoder for decompression. - if the Compressed Bit is a 0, the receiving entity forwards the datagram located in the PPP Information field without passing it to V.44 decoder. The receiver also MUST use the Dictionary ID sub-field to access and re-initialize the corresponding decoder dictionary and history. 2.3.4 Dictionary Synchronization When either the encoder dictionary or history, corresponding to the datagrams link, becomes filled the V.44 algorithm re-initializes that encoder dictionary (and history), and inserts a REINIT control code within the compressed data to indicate to the peer decoder that it MUST re-initialize the dictionary and history corresponding to the dictionary number in the Dictionary ID sub-field of the V.44 Control field. When the encoder is unsuccessful in compressing a datagram, the original datagram is placed into the PPP Information field of the V.44 Individual Link Compressed Datagram (PPP Protocol field of 0xFB) and the dictionary and history corresponding to the uncompressed datagrams link are re-initialized. Also a 0 value is placed into the Compressed Bit in the V.44 Control field. When the peer receiving entity receives a V.44 Individual Link Compressed Datagram (i.e. an 0xFB value in its PPP Protocol field) with a 0 bit in the Compressed Bit in the V.44 Control field it MUST NOT pass that datagram to the V.44 decoder. It MUST re-initializes the decoder dictionary and history corresponding to the value in the Heath Internet-Draft [Page 10] PPP V.44/LZJH Compression Protocol April 2002 Dictionary ID sub-field. 2.3.5 Individual Link Compressed Datagram Format Datagrams for links where V.44 compression not is active are transmitted in their original form, refer to [1] for possible formats. When using Individual Link Compression, all datagrams for a link where V.44 compression is active MUST be transmitted using the format of the Individual Link Compressed Datagram regardless of whether the PPP Information field contains a V.44 compressed datagram or an original datagram. The format of V.44 Individual Link Compressed Datagrams of type 0xFB depends upon the number of separate links, i.e. dictionaries, that are negotiated between the V.44 compression peers. 2.3.5.1 Number of Dictionaries is 128 or Less If the number of negotiated dictionaries is 128 or less then the V.44 Control field is one byte and the format is as shown below. The fields are transmitted from left to right. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PPP Protocol | V.44 | PPP | (0x00FB) | Control | Information.. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The PPP Protocol field is a 2 octet field described in the Point-to-Point Protocol Encapsulation [PPP] that is set to 0x00FB to indicate a V.44 Individual Link Compressed Datagram. This value MAY be compressed when Protocol-Field-Compression is negotiated. The format of the 8 bit V.44 Control field is: 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | Dictionary ID | C | +---+---+---+---+---+---+---+---+ where: - Dictionary ID (0 - 127) corresponds to a specific link and is used to insure the V.44 encoder and decoder are using the same dictionary. - C is the Compressed Bit indicating whether the PPP Information contains a compressed datagram (C = 1) or an original datagram (C = 0). Heath Internet-Draft [Page 11] PPP V.44/LZJH Compression Protocol April 2002 The PPP Information field contains either a compressed datagram or an original datagram depending upon the setting of the Compressed Bit in the V.44 Control field. 2.3.5.2 Number of Dictionaries is More Than 128 If the number of negotiated dictionaries is 129 through 32K then the V.44 Control field is two bytes and the format is as shown below. The fields are transmitted from left to right. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PPP Protocol (0x00FB) | V.44 Control | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PPP Information .............. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The PPP Protocol field is a 2 octet field described in the Point-to-Point Protocol Encapsulation [PPP] that is set to 0x00FB to indicate an V.44 Individual Link Compressed Datagram. This value MAY be compressed when Protocol-Field-Compression is negotiated. The format of the two octet V.44 Control field is: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | Dictionary ID | C | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ where: - Dictionary ID corresponds to a specific link and is used to insure the V.44 encoder and decoder are using the same dictionary. - C is the Compressed Bit indicating whether the PPP Information contains a compressed datagram (C = 1) or an original datagram (C = 0). The PPP Information field contains either a compressed datagram or an original datagram depending upon the setting of the Compressed Bit in the V.44 Control field. 2.3.6 Data Expansion The total length of datagrams that do not compress is expanded by up to 4 bytes by the addition of a PPP Protocol field and the V.44 Control field. In addition, the PPP Information field is expanded by up to 2 bytes by including both the original PPP Protocol field and original PPP Information field. Heath Internet-Draft [Page 12] PPP V.44/LZJH Compression Protocol April 2002 Thus, when using Individual Link Mode, both peers MUST negotiate a Maximum Receive Unit, on all links where V.44 compression is used, that is sufficiently larger than a normal maximum length datagram to account for this expansion. 2.3.7 Configuration Refer to Section 3 for the negotiation of V.44 compression on a link and the configuration of V.44 Individual Link Mode. 3 V.44 Configuration Option The V.44 Configuration Option of the CCP negotiates the use of V.44 compression between two peers. If a common compression algorithm can not be negotiated then no compression is used. All implementations MUST support the default values. A summary of the V.44 Configuration Option format is shown below. The fields are transmitted from left to right. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | Mode/Dictionary Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | *Dictionary Size | *History Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 27 (i.e. V.44/LZJH Compression) Length 4, 6, or 8 Mode/Dictionary Count The Mode/Dictionary Count field is two octets, most significant octet first, and specifies the V.44 Compression Mode and the number of individual link dictionaries proposed (Individual Link Mode only). Mode selection values are: 0 = Datagram Mode (one dictionary and no history) 1 = Multi-Datagram Mode (one dictionary with history) 2 or more = Individual Link Mode and proposed number of dictionaries each with a corresponding history Heath Internet-Draft [Page 13] PPP V.44/LZJH Compression Protocol April 2002 Dictionary Size The Dictionary Size field is optional. If it is not present then the History Length field MUST NOT be present either. If present, the Dictionary Size field is two octets and contains the number of proposed entries in the dictionary. The range is from 256 to 16,384 and the default depends upon the mode proposed as follows: - if Datagram Mode is proposed the default is 1525. - otherwise the default is 1024. A peer is not required to propose as large a dictionary size as an implementation indicates that it can accept. However, it should be noted that resources MUST be allocated in a peer to support the number of dictionary entries proposed by that peer in this field. History Length The History Length field is optional and, if present, MUST be ignored if Datagram Mode is proposed in the Mode/Dictionary Count field. The History Length field is two octets and contains the proposed length of the history. The range is from 512 to 65,535. The default is 3 times the Dictionary Size to be consistent with [V44] Annex B.2, however, for best compression it should be 4 or more times the Dictionary Size. The History Length MUST NOT be less than twice the Dictionary Size. 3.1 Negotiation Rules 1. If either peer proposes Datagram Mode, then Datagram Mode is used. 2. If neither peer proposes Datagram Mode, and either peer proposes Multi-Datagram Mode, then Multi-Datagram Mode is used. 3. If both peers propose Individual Link Mode, then Individual Link Mode is used. The number of dictionaries selected is the lower of the two numbers proposed by the peers. 4. If the Dictionary Size field is not present from either peer, then the default dictionary size is selected. 5. If the Dictionary Size field is present from both peers, then the dictionary size selected is the lower of the two numbers proposed by the peers. 6. If the History Length field is not present from either peer, then the default history length is selected (i.e. 4 times the dictionary size). 7. If the History Length field is present from both peers, then the history length selected is the lower of the two numbers proposed by the peers (but not less than 2 times the dictionary size). Heath Internet-Draft [Page 14] PPP V.44/LZJH Compression Protocol April 2002 4 V.44 Compressed Data The PPP information field MUST contain only one datagram in compressed form. The length of this field is always an integer number of octets. There MUST BE only one FLUSH control code per block of compressed data. The format of the PPP information field is one block of compressed data as defined in ITU-T Recommendation V.44 and its Annex B. ITU-T Recommendation V.44 defines the implementation of the core elements of the LZJH algorithm, its encoder and decoder. Annex B of the recommendation defines the implementation of the LZJH algorithm in packet networks or applications such as PPP. 4.1 Padding The PPP Information field of a V.44 compressed datagram always ends with a FLUSH control code that is inserted by the V.44 encoder and is used to signal the end of compressed data. The V.44 encoder also adds 1 to 7 additional bits to obtain octet alignment, if necessary. Thus, any full octets beyond the octet containing the remaining bits of the FLUSH control code are considered padding that is not created or used by the V.44 algorithm. 5 Datagram Integrity Due to the very nature of data compression, the V.44 decoder is not capable of determining that a datagram it has received for decompression is corrupt or has otherwise been changed since it was generated by its peer encoder. Thus, it is highly recommended that a mechanism, or mechanisms, be implemented at the PPP link layer to insure the integrity of datagrams that are received by a PPP peer. Mechanisms such as a two octet Cyclic Redundancy Check are commonly used for this purpose. However, the choice of mechanisms and their definition are beyond the scope of this memo. A PPP peer that detects that the integrity of a received datagram has been compromised MUST NOT pass the datagram (if a V.44 Compressed or Individual Link Compressed Datagram) to the V.44 decoder. Further, if either Multi-Datagram or Individual Link mode is being used, the peer SHALL assume that dictionary synchonization has been or will be lost and SHOULD terminate the link or use the mechanisms defined in [CCP] to indicate the loss of dictionary synchronization. 6 Reliable and In-order Delivery of Datagrams The Multi-Datagram and Individual Link modes of using V.44 compression in PPP require the reliable and in-order delivery of both original (uncompressed) and V.44 compressed datagrams. The mechanisms utilized by the PPP peers to insure the reliable and in-order delivery of datagrams are beyond the scope of this memo, however, a Heath Internet-Draft [Page 15] PPP V.44/LZJH Compression Protocol April 2002 reliable transport such as LAPB [PRT] MUST be used. A PPP peer that detects a lost or out-of-order datagram, while using Multi-Datagram or Individual Link mode, MUST NOT pass this or subsequent compressed datagrams to the V.44 decoder. Further, the peer SHALL assume that dictionary synchonization has been or will be lost and SHOULD terminate the link or use the mechanisms defined in [CCP] to indicate the loss of dictionary synchronization. 7 Security Considerations Security issues are not discussed in this memo. 8 References [PPP] Simpson, W., Editor, "The Point-to-Point Protocol (PPP)", STD 51, RFC 1661, Daydreamer, July 1994. [CCP] Rand, D., "The PPP Compression Control Protocol (CCP)", RFC 1962, July 1996. [V44] ITU Telecommunication Standardization Sector (ITU-T) Recommendation V.44 "Data Compression Procedures", November 2000. [LZ77] Lempel, A., and Ziv, J., "A Universal Algorithm for Sequential Data Compression", IEEE Transactions On Information Theory, Vol. IT-23, No. 3, May 1977. [LZ78] Lempel, A., and Ziv, J., "Compression of Individual Sequences via Variable Rate Coding", IEEE Transactions On Information Theory, Vol. IT-24, No. 5, Sep 1978. [KEY] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [PRT] Rand, D., "PPP Reliable Transmission", RFC 1663, Novell, July 1994. 9 Authors' Addresses Jeff Heath Hughes Network Systems 10450 Pacific Center Court San Diego, CA 92121 Phone: 858-452-4826 Fax: 858-597-8979 EMail: jheath@hns.com Heath Internet-Draft [Page 16] PPP V.44/LZJH Compression Protocol April 2002 John Border Hughes Network Systems 11717 Exploration Lane Germantown, MD 20876 Phone: 301-548-6819 Fax: 301-548-1196 EMail: border@hns.com 10 Full Copyright Statement Copyright (C) The Internet Society (2001). 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. This Internet-Draft expires on October 17, 2002. Heath Internet-Draft [Page 17]