Network Working Group Hans Hannu, Ericsson INTERNET-DRAFT Jan Christoffersson, Ericsson Expires: January 2002 Krister Svanbro, Ericsson Stefan Forsgren, Ericsson Sweden July 06, 2001 RObust GEneric message size Reduction (ROGER) 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 cite them other than as "work in progress". The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/lid-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This document is an individual submission to the IETF. Comments should be directed to the authors. Abstract Using existing ASCII based application signaling protocols over bandwidth limited channels, such as cellular access channels, create problems with e.g. long session setup times, long control times and waste scarce radio resources. This draft provides a robust and efficient compression scheme for ASCII based protocols, which reduces the mentioned problems. Hannu, Christoffersson, Svanbro, Forsgren [Page 1] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 0. Document History - February 23, 2001, version 00 - July 06, 2001, version 01 Improved header formats, with additional functionality. TABLE OF CONTENTS 1. Introduction..................................................4 2. General description...........................................5 3. Terminology...................................................6 4. Compression algorithm.........................................7 4.1. Dictionary build-up and maintenance.........................8 5. ROGER message header functionality............................9 5.1. ROGER header type..........................................10 5.1.1. Message IDentification number (MID)......................10 5.1.2. Code Point (CP)..........................................10 5.2. ROGER Acknowledgement......................................11 5.2.1. Cumulative Acknowledgement...............................11 5.2.2. Bit Mask Acknowledgement.................................11 5.2.3. List Acknowledgement.....................................12 5.3. CRCs.......................................................12 5.3.1. CRC for message..........................................13 5.3.2. CRC for Dynamic Dictionary...............................13 5.4. Code Point with flags......................................13 5.4.1. Forced acknowledgements..................................14 5.4.2. The usage of CP-FLUSH....................................14 5.5. ROGER header formats.......................................15 5.6. Reuse of Message IDentification number (MID)...............16 5.7. Dictionary memory space....................................17 5.7.1. Sliding window...........................................17 5.7.2. No deletion..............................................17 5.8. Avoiding deadlock..........................................18 5.9. User Semi-Static Dictionary.................................18 6. Modes of implementation......................................19 6.1. No contact mode............................................19 6.1.1. Compression..............................................20 6.1.2. Decompression............................................20 6.2. Limited contact mode.......................................20 6.2.1. Compression..............................................21 6.2.2. Decompression............................................21 6.3. Full contact mode..........................................21 6.3.1. Compression..............................................22 6.3.2. Decompression............................................22 Hannu, Christoffersson, Svanbro, Forsgren [Page 2] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 6.4. Move of table content......................................22 6.4.1. TRD to DD................................................23 6.4.2. TST to DD................................................23 7. ROGER requirements...........................................23 8. Implementation status........................................24 9. ROGER over ROHC - A new ROHC profile.........................24 9.1. ROGER profile in the ROHC framework........................25 9.1.1. Limited contact mode.....................................25 9.1.1.1. Packet types...........................................25 9.1.2. Full contact mode........................................26 9.1.2.1. Packet types...........................................26 10. Evaluation of compression scheme............................26 11. Conclusion..................................................27 12. Security considerations.....................................28 13. IANA considerations.........................................28 14. Acknowledgments.............................................28 15. Intellectual property considerations........................28 16. Authors addresses...........................................28 17. References..................................................29 Hannu, Christoffersson, Svanbro, Forsgren [Page 3] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 1. Introduction Two communication technologies have become commonly used by the general public in the recent years: cellular telephony and the Internet. Cellular telephony has provided its users with the freedom of mobility - the possibility of always being reachable with reasonable service quality no matter where they are. However, until now the main service provided has been speech. With the Internet, the conditions have been almost the opposite. While flexibility for all kinds of usage has been its strength, its focus has been on fixed connections and large terminals, and the experienced quality of some services (such as Internet telephony) has generally been low. Due to new enhanced technologies this is about to change. Internet and cellular technologies are beginning to merge. Future cellular "phones" will contain an IP-stack and support voice over IP in addition to web-browsing, e-mail, etc. One could say that the Internet is going mobile, or that cellular systems are becoming much more than telephony depending on one's point of view. Commonly used terms in this technical area are "all-IP" and "IP all the way". These terms all relate to the case where IP is used end to end, even if the path involves cellular links. This is done for all types of traffic, both the user data (e.g. voice or streaming) and control signaling data (e.g. SIP or RTSP). A great benefit of this is the service flexibility introduced by IP combined with the freedom provided by continuos mobility. A high cost, on the other hand, is the relative large overhead the IP protocol suite typically introduces, due to large headers and text-based signaling protocols. It is very important in cellular systems to use the scarce radio resources in an efficient way. It must be possible to support a sufficient number of users per cell, otherwise costs will be prohibitive [CELL]. The ROHC (RObust Header Compression) working group has successfully solved the problem of reducing bandwidth requirements for the header parts of e.g. RTP/UDP/IP packets [ROHC]. With this obstacle removed, new challenges of enhancing mobile Internet performance arise. One of these relates to application signaling protocols. Protocols such as SIP [SIP], SDP [SDP] and RTSP [RTSP] will typically be used to setup and control applications also in a mobile Internet. However, the generous size of the protocol messages combined with their request/response nature create delays and waste bandwidth. Compression of these messages should be considered in order to increase spectrum efficiency and reduce transmission delay [APP]. Hannu, Christoffersson, Svanbro, Forsgren [Page 4] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 2. General description This chapter describes compression of protocol data above IP/UDP or IP/TCP. The solution is a framework which is robust to packet loss and will give efficient compression of ASCII based protocol messages. Furthermore, the compression is transparent, i.e. a compressed message will after decompression be bitwise identical to the original message. The framework is especially suitable for SIP/SDP, RTSP and HTTP [HTTP], but could also be used for other ASCII based protocols. Three possible compression/decompression scenarios are identified. The scenarios differ from each other depending on to what extent the compressor and decompressor can communicate. In all three cases it is assumed that the messages are compressed when sent over a narrow band link, such as a cellular link. This means that one of the entities may reside in the terminal equipment (mobile phone, thin client etc.) and the other (somewhere)in the fixed part of a cellular system. The different cases and how to handle them are described in Chapter 6. The compression scheme enhances dictionary based compression of single messages by compressing messages from designated packet flow(s) in a sequential manner. Already transmitted messages are used when compressing new messages. The great gain in doing so stems from the fact that previous messages will contain much of the information or text strings that are found in later messages. In order to classify messages as belonging to a certain flow the messages must all pass through the points where the compressor/decompressor entities reside. That is, packets that go to different mobile terminals can not in general belong to the same compressed packet flow. The method takes advantage of the possibility to acknowledge received messages. The acknowledgements can either be sent with messages travelling in the opposite direction or using a dedicated backwards channel. All sent and received messages are temporarily stored. Once the messages are acknowledged, they are put in a dictionary which is used for compression/decompression of future messages. Details on where the messages are stored while waiting for acknowledgements is given in Chapter 3. The dictionary management and a more thorough description of the different scenarios are described in Chapter 6. The compression algorithm used for compression is based on the Lempel-Ziv algorithm which replaces strings in the message by references to previous occurrences in the message or dictionary. The use of a dictionary will greatly increase the compression efficiency. More information on the compression algorithm can be found in Chapter 4. Hannu, Christoffersson, Svanbro, Forsgren [Page 5] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 3. Terminology * Static Dictionary (SD) A dictionary which is static, i.e. does not change during or between compression of message flows. The dictionary contains, e.g. protocol-specific Header field names, Methods, Status-codes etc. The static dictionary is known by the compressor and decompressor prior to compression/decompression at both sides of the link. The SD is used for both compression and decompression. * Dynamic Dictionary (DD) Contains acknowledged messages (or parts of them), which have been transmitted during the session. The dynamic dictionary is known by both the compressor and the decompressor on the opposite side. The DD is empty when the compression begins and is updated according to some specific scheme during the message sequence. The DD is used for both compression and decompression. * Temporary Receiver Dictionary (TRD) Messages (or parts of them), which have traversed the link, are stored at the receiver side in the TRD. When a receiving entity is positive that the opposite side knows that the messages have been received, the messages are moved from the TRD to the DD. The TRD is used for compression only. * Temporary Sender Table (TST) Messages that have been sent over the link are stored in the TST at the sending side until it is positive that the messages have been received at the opposite side, then they are moved to the DD. Thus, messages in the TST are not used in the compression process. * Temporary Receiver Dictionary Table (TRDT) The TRDT is used to keep track of when to move a message from the TRD to the DD. The TRDT holds an association between the sent messages and the received messages that are being acknowledged by the sent messages from an entity. * Headers In order for the two entities to keep track of which messages have been sent from and received by the other entity the compressed messages are supplied with a header. The header holds the sequence number of the present message and the sequence numbers of all the received messages which have not yet been acknowledged, i.e. the contents of the TRD. * Context Contains the information necessary to perform compression and decompression, i.e. the dictionaries and the tables described above. Hannu, Christoffersson, Svanbro, Forsgren [Page 6] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 4. Compression algorithm The default compression algorithm used to compress messages is a slightly modified LZSS [LZSS], which is of Lempel-Ziv type. The algorithm works by scanning through the file from left to right and replace repeated strings by references to the last previous occurrence in the file. The reference is of the form (offset, length of match) and is typically represented using two bytes. The implementation of LZSS must be done so that it is possible to compress and decompress messages using dictionaries. A logical representation of how this can be achieved is as follows, see also Figure 4.1: Compression 1. Append the message to the dictionary and compress the extended file using LZSS. 2. Separate the part of the compressed file that corresponds to the dictionary from the part which corresponds to the message. This is possible since LZSS processes the file from left to right and the part which has already been compressed does not change as the compression proceeds. That is, compressing the dictionary by itself or compressing it with a message appended to it will produce the same output (apart from the compressed message) Decompression 1. Append the compressed message to the compressed dictionary and decompress the extended file. 2. Separate the message from the dictionary. It is of course of vital importance that the same dictionary is used by both the compressor and decompressor. +--------------+---------+ +--------+------+ | Dictionary | Message | ---> | CD | CM | +--------------+---------+ Compression +--------+------+ +--------------+ +--------+ | Dictionary | ---> | CD | +--------------+ Compression +--------+ Figure 4.1. Compression of the dictionary with a message appended and the dictionary by itself. CD is the compressed dictionary and CM is the compressed message. The LZSS implementation should be tailored to enable the split of the compressed file into these two parts in a simple fashion. To facilitate the splitting the implementation should not replace a Hannu, Christoffersson, Svanbro, Forsgren [Page 7] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 repeated string which runs from the dictionary and into the message with a single reference. The part of the string in the dictionary should be replaced with one reference and the part of the string in the message should be replaced by another reference. Compression with LZSS is valid for virtually all types of protocol data, not just ASCII based. However, compression would probably not be as efficient for other types of data. Note: LZSS is chosen as the default compression algorithm in this draft. However, it is left as an open issue how LZSS could be modified or if some other compression algorithm should be used, in order to enhance the performance of ROGER. 4.1. Dictionary build-up and maintenance The DD is part of the ROGER context, and the compressor DD must be kept consistent with the decompressor DD to avoid faulty decompressed packets. Each packet stream should have its own context, but it would of course be possible to share dictionaries between different flows as long as they pass the same compression and decompression points. However, this depends on where the scheme is placed and is therefore left for the implementation. The DD should at least be kept as long as packets belonging to the context keep arriving. Determining whether a packet flow is still active can be done using a timer. It could also be possible to identify the end of a packet flow from the semantics of the protocol, but this would complicate the compressor scheme by forcing the compressor to know the semantics of the compressed protocols and also to keep track of the type of the transmitted messages. There are several different strategies which could be used to determine what to update the dynamic dictionary with. The method should ensure a high compression efficiency while keeping the dictionary size and the complexity of the scheme at a reasonable level. Some possibilities on how to update the dictionary are given below: * Append all messages to the dictionary. This would give very large dictionaries in long sessions with many messages. * Only use the first (or last) n messages of the session. Typically, n would be small to ensure that the dictionary does not grow to an unreasonable size. Still, it would have to be large enough to make the compression efficient. * Append only new strings, short sub-strings or rows to the dictionary. This would also ensure a slower growth of the dictionary. However, it remains to be investigated how this will affect the compression efficiency. Hannu, Christoffersson, Svanbro, Forsgren [Page 8] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 * Messages, strings or rows could also be deleted from the dictionary to avoid having an unreasonably large dictionary. One strategy for this could be to delete from the beginning of the dictionary, i.e. deleting the oldest parts first, i.e. using a sliding window. See also section 5.7.1 and chapter 7. Note: It still remains to be investigated what is the most efficient way to update the dictionary. 5. ROGER message header functionality To achieve robustness and keep track of sent and received messages, a header is added to the compressed message. The ROGER header consist of the following parts, and the parts are also placed in this order in the header: * Header Type - Message ID (MID), or - Code Point (CP) * Acknowledgement - Cumulative Acknowledgement, or - Bit Mask Acknowledgement, or - List Acknowledgement * (CRC for Dynamic Dictionary) * CRC for message Not all of these parts have to be present in each ROGER message. ROGER can handle packet reordering, which has happened before the compressor, and also message reordering between compressor and decompressor. The interval of reordering ([MID-N,MID]) that ROGER must support, should be negotiated before compression starts. N must be chosen to be less than the number of MIDs used, (0<=N<12) see also section 5.1.1. Hannu, Christoffersson, Svanbro, Forsgren [Page 9] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 5.1. ROGER Header Type The basic header format is shown in Figure 5.1. 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | Header Type | Depends on | +---+---+---+---+ + : : / the value of Header Type / : : +---+---+---+---+---+---+---+---+ Figure 5.1. Basic ROGER header format The Header Type (HT) states either a Message IDentification number (MID) or a Code Point (CP). 5.1.1 Message IDentification number (MID) The MID is used by the receiving entity (decompressor) to determine, which message has been received and it is also acknowledged to the sending entity (compressor). If HT has one of the following values it indicates a MID: +---+---+---+---+ +---+---+---+---+ | 0 0 0 1 | to | 1 1 0 0 | +---+---+---+---+ +---+---+---+---+ The MID is increased with one for each message sent. As there is a maximum of twelve numbers for MID usage, they will be reused. How this is done is described in section 5.6. If there is a gap between MIDs, those missing MIDs messages must be considered to be lost if they are not within the interval of reordering that ROGER has been configured to handle. 5.1.2 Code Point (CP) Four values of the Header Type are used for CPs. The CPs indicates special events to be taken and also a slightly modified header format. Following values of HT is used for CPs: CP-FLUSH +---+---+---+---+ | 0 0 0 0 | : Flush everything in the DD, TRD and TST, +---+---+---+---+ and go into "FLUSH-STATE". The receiver of this CP, must respond with a CP described in section 5.4. Hannu, Christoffersson, Svanbro, Forsgren [Page 10] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 CP-DD +---+---+---+---+ | 1 1 0 1 | : The header contains a CRC for the DD, see +---+---+---+---+ section 5.3.2. CP-FLAG +---+---+---+---+ | 1 1 1 0 | : The next following four bits are used as flags, +---+---+---+---+ see section 5.4. CP-IGNORE +---+---+---+---+ | 1 1 1 1 | : Do not place any part of this message in the +---+---+---+---+ TRD of the receiving entity or in the TST of the sending entity. 5.2. ROGER Acknowledgement A sent or received message can not be used in the compression process by an entity until it is certain that the corresponding entity has knowledge about the specific message. For this purpose acknowledgments are used. A message indicated in the acknowledgments has been received at the entity generating the acknowledgment and is stored in its TRD. Once the message has been moved from the TRD it will not be further acknowledged, which means that an acknowledgement for a received message might be carried in several consecutive packets. Three types of acknowledgments can be used as described below. 5.2.1. Cumulative Acknowledgement The Cumulative Acknowledgement must only be used when there is no gap in the message sequence it is about to acknowledge, e.g. if the receiving entity has received all messages up to message m, then it sets the Cumulative Acknowledgement to m. The Cumulative Acknowledgement is four bits large to handle the sequence number space. This is the default acknowledgement to use. 5.2.2. Bit Mask Acknowledgement The Bit Mask Acknowledgement must be used when there is a gap in the message sequence it is about to acknowledge and only when the interval of reordering is set to zero. The bits, which corresponds to the messages to be acknowledged, are set in the mask. The Bit Mask is twelve bits large to handle the sequence number space. The MSB bit corresponds to message 12. Thus, to indicate messages with identification numbers 2, 4 and 9 the bit-mask is set to: Hannu, Christoffersson, Svanbro, Forsgren [Page 11] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | 0 0 0 1 0 0 0 0 | + +---+---+---+---+ | 1 0 1 0 | +---+---+---+---+ The use of this acknowledgement must be indicated by using CP-FLAG as described in section 5.4. 5.2.3. List Acknowledgement The Bit Mask Acknowledgement is replaced by a List Acknowledgement in the header formats, when the reordering interval is non-zero. The List Acknowledgement must be used when there is a gap in the received MID sequence. The List must contain the received MIDs in the order that they were received at the decompressing entity. The List Acknowledgement has the following format: 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | AC | RMID (1) | +---+---+---+---+---+---+---+---+ | RMID (2) | RMID (3) | +---+---+---+---+---+---+---+---+ : : / / : : +---+---+---+---+---+---+---+---+ | RMID (C) | +---+---+---+---+ AC: Number of MIDs being acknowledged (RMID), which are included in the List. If AC is an odd number the last RMID, RMID(C), is only padding, in order to get octet aligned. RMID: Received MID, which are being acknowledged. Must be placed in the List in the order that they were received at the decompressor entity and thus in the order the message is to be placed in the DD. The use of this acknowledgement must be indicated by using CP-FLAG as described in section 5.4. 5.3. CRCs Two types of CRCs can be carried in the ROGER header. An 8-bit CRC to discover residual bit errors in the messages. A 12-bit CRC to obtain robustness to errors in the Dynamic Dictionary. Hannu, Christoffersson, Svanbro, Forsgren [Page 12] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 5.3.1 CRC for message The 8-bit CRC is computed over the message before compression. Then it is transmitted in the header of ROGER messages. After decompression, a CRC is computed over the decompressed message and compared to the CRC in the header. If these CRCs do not match, an error has occurred. In this case the message is not placed in the TRD and not acknowledged, thus the message must be treated as it had never arrived at the decompressor. The CRC polynomial is given by, C(x) = 1 + x + x^2 + x^8. If this CRC is present in the message header it must always be placed right before the compressed message. 5.3.2 CRC for Dynamic Dictionary The CRC for Dynamic Dictionary is a 12-bit CRC. It is used to obtain robustness to errors in the Dynamic Dictionary which would cause the decompression of messages to fail. It is computed over a text string representation of the content in the dynamic dictionary. This CRC is compared to the CRC computed over the dynamic dictionary at the other entity. This can be useful when the decompressor has failed to decompress several consecutive messages. The 12-bit CRC computed over the dynamic dictionary is signaled using CP-DD. The CRC-polynomial is given by, C(x) = 1 + x^2 + x^3 + x^11 + X^12. If this CRC is present in the message header it must always be placed right before the 8-bit CRC or last if the 8-bit CRC is not present. 5.4. Code Point with flags 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | 1 1 1 0 | B R A F | +---+---+---+---+---+---+---+---+ The shown CP follows by four flags, which if set indicates: * B: The Bit Mask/List Acknowledgement is used in this message * R: This Bit is set to request acknowledgements, i.e. Forced Acknowledgements , from the receiver of this message. * A: This bit must only be set when this message carries Forced Acknowledgements * F: This must be set upon the reception of CP-FLUSH in every sent message, until the entity generating CP-FLUSH stops sending CP-FLUSH. Hannu, Christoffersson, Svanbro, Forsgren [Page 13] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 5.4.1. Forced Acknowledgements In some occasions it is useful to have the opposite entity to acknowledge the messages it has received (i.e. those stored in the TRD), e.g. when the MID numbers are running low. The request is done using CP-FLAGS with the R bit set. To avoid inconsistency between the DD of the compressor and decompressor, a request must only be sent with CP-IGNORE. The entity, which receives the request, must use CP- FLAGS with the A bit set when it responds with acknowledgements, i.e. Forced Acknowledgements, to the request. More specifically compressor A enters "REQUEST-STATE" and packets must be sent with CP-FLAGS/R-bit + CP-IGNORE, until a Forced Acknowledgement is received from decompressor B. The messages stored in the TST, which are not acknowledged by the Forced acknowledgement, and are not in the supported reordered interval must be regarded as lost by the compressor and discarded. When compressor A leaves "REQUEST-STATE", the next MID number it should use must be larger than the highest Forced acknowledged MID number plus the supported interval of reordering. Decompressor B enters a "FORCEDACK-STATE" upon the reception of a Request, and packets (acknowledgements) must be sent using CP-FLAG/A- bit and the same packets must be acknowledged, until decompressor B receives an "ordinary" MID packet from compressor A. Decompressor B then leaves the "FORCEDACK-STATE" and moves the messages that were in the Forced Acknowledgement to the DD. Decompressor B must also be able to decompress reordered messages from compressor A, which are in the reordered interval to handle, and these messages must not make decompressor B leave the "FORCEDACK-STATE". They are also stored as usual in the TRD. Reordered packets must remain in the TRD until an ordinary acknowledgement for an acknowledgement is received. 5.4.2. The usage of CP-FLUSH Sometimes there is a need to empty everything from the dictionaries and tables. e.g. when a CRC for the DD indicates that something is wrong with the DD. If an entity wants to restart the compression process, it must use CP-FLUSH. Thus, the entity enters a "FLUSH- STATE", and must continue sending CP-FLUSH until it receives an acknowledgment for a message, which carried a CP-FLUSH. The acknowledgement must carry CP-FLAGS with the F bit set, otherwise it must be ignored. The entity receiving CP-FLUSH also enters a "FLUSH- STATE, and must respond with CP-FLAGS and the F bit set within every message sent, until it receives a message, which does not carry a CP- FLUSH. This indicates that the compressor has left the "FLUSH-STATE" and that the decompressor must also leave the "FLUSH-STATE". Messages, which carries CP-FLUSH or CP-FLAGS/F must be saved as usually in the TRD or TST. Hannu, Christoffersson, Svanbro, Forsgren [Page 14] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 5.5. ROGER header formats These are the header formats of ROGER. Format-1: 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | Header Type | Cumulative ACK| HT = MID or CP: 1111 (CP-IGNORE) +---+---+---+---+---+---+---+---+ | CRC for Message | +---+---+---+---+---+---+---+---+ / Compressed message / +---+---+---+---+---+---+---+---+ Format-2: 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | Header Type |MID / CP-IGNORE| HT = CP: 1101 (CP-DD) +---+---+---+---+---+---+---+---+ |Cumulative ACK | CRC for | +---+---+---+---+ + | Dynamic Dictionary | +---+---+---+---+---------------+ | CRC for Message | +---+---+---+---+---+---+---+---+ / Compressed message / +---+---+---+---+---+---+---+---+ Format-3: 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | Header Type |MID / CP-IGNORE| HT = CP: 0000 (CP-FLUSH) +---+---+---+---+---+---+---+---+ | CRC for Message | +---+---+---+---+---+---+---+---+ / Compressed message / +---+---+---+---+---+---+---+---+ Hannu, Christoffersson, Svanbro, Forsgren [Page 15] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 Format-4: 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | Header TYPE | B | R | A | F | HT = CP: 1110 (CP-FLAG) +---+---+---+---+---+---+---+---+ :(1) HT or Padding, 4 or 8 bits : / / :(2) Cumulative or Bit Mask ACK : : 4 or 12 bits : / / :(3) CRC for DD, 12 bits : / / :(4) CRC for message, 8 bits : +---+---+---+---+---+---+---+---+ / Compressed message / +---+---+---+---+---+---+---+---+ Format-4, is used when the information described in section 5.4, has to be delivered. Format-4 is also used when the Bit Mask/List Acknowledgement is used (B-flag is set). Then the header has the same format as Format-1 and Format-2 except for the first octet and the Cumulative Acknowledgement is replaced in the header formats at place (2) with the Bit Mask/List Acknowledgement. The compressor and decompressor respectively can use Format-4, with the bits R or A set, without carrying any compressed message. If this is the case, the following first four bits after the first octet should be ignored as it is padding. 5.6. Reuse of Message IDentification number (MID) To avoid that wrong message is being acknowledged, which could happen if a MID is too early reused, there is a three way handshake that must be completed before a MID is reused. This handshake is described in the example of Figure 5.2. Entity A Entity B |------------ MID-1A -------------->| | | Step (1) |<----------- MID-1B, ACK-1A -------| | | Step (2) |------------ MID-2A, ACK-1B ------>| | | Step (3) |<----------- MID-2B, ACK-2A -------| | | Figure 5.2. Three way handshake for MID reuse Hannu, Christoffersson, Svanbro, Forsgren [Page 16] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 Step (1): The handshake starts with an acknowledgment that the message has been received, in this example, by Entity B Step (2): The acknowledgement from Entity B is then implicitly acknowledged by, in this example, Entity A. Step (3): At the reception of the acknowledgement from Entity B, the acknowledgement from Entity A is implicitly acknowledged, and MID-1A can be reused, i.e. a MID cannot be reused until it has stopped being acknowledged. Although, the example in Figure 5.2 shows a strict request/reply pattern, the design of ROGER is done so it can handle non-strict request/reply patterns. 5.7. Dictionary memory space There will be a limited physical memory space for the dynamic dictionary. This section describes two implementations. One with a sliding window for the DD and one were the DD is filled up to the physical limit, and is kept at that size. 5.7.1. Sliding window In the case when a sliding window is used for the DD, the parts of the DD that are shifted out must be saved so that reordered messages can be decompressed. Thus, when a compressed reordered message is in the interval, a temporary dictionary, which the message was compressed with, is reconstructed and the message is decompressed. It is then treated in an ordinary fashion (put into the TRD). If the reordered interval is set to zero, there is no need to save parts that are shifted out from the DD, because reordered packets is in this case regarded as lost. 5.7.2. No deletion When there is no deletion from the DD, there is a need to signal to the opposite entity when the DD is full. This is done to avoid unnecessary large message headers. CP-IGNORE and the Cumulative Acknowledgement set to number 13 is used to signal to the other entity that its DD is full. Thus, when an entity finds out that its DD will be full when it receives an acknowledgement for the packet it is about to send ("packet full"). Then the other entity's DD, will be full first and send CP-IGNORE with Cumulative Acknowledgement set to number 13, this CP- IGNORE/CUMACK-13 will serve as an acknowledgement for the acknowledgements in "packet full" and those message can be moved from Hannu, Christoffersson, Svanbro, Forsgren [Page 17] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 TRD to DD, which makes DD full. Both sides will hereafter send CP- IGNORE/CUMACK-13. 5.8. Avoiding deadlock If more than 12 consecutive messages in one direction are sent without any acknowledgement has been received, the compressor runs out of MIDs and a deadlock may occur if all 12 messages were lost. To avoid this, the following scheme will restart the compression. Messages sent within a prescribed time after the 12Æth message must be sent with CP-IGNORE or request an acknowledgement using CP-FLAGS with the R bit set. The compressor waits for acknowledgements for a prescribe time. After the prescribed time period and if no acknowledgment has been received, CP-FLUSH is sent. This signals that the DD, TRD and TST are emptied and the compression scheme restarts. If no acknowledgement is received for this message the procedure is repeated. Note: The prescribed time period and how to use the CP-FLAGS/R-bit is decided at implementation. 5.9. User Semi-Static Dictionary The Static Dictionary (SD) is the same for packets flows rendering from different users as it is predefined. However, the User Semi- Static Dictionary (USSD), is a dictionary containing user specific information, which could be useful to have already at the start of compression. The USSD would work in conjunction with the SD. Figure 5.3 shows the search order using the dictionaries, starting with the SD. +---------+---------+---------+ | SD | USSD | DD | +---------+---------+---------+ Figure 5.3. Search order for the compression algorithm The information in the USSD is not specified in this draft, but information, such as frequently connected addresses could be in USSD. The information in the USSD should be exchanged between the involved entities' compressor and decompressor during the negotiation phase for the usage of ROGER. How, the negotiation is done is out of the scope for this draft, but the USSD should then be transported in conjunction with other parameters for ROGER compression. Hannu, Christoffersson, Svanbro, Forsgren [Page 18] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 6. Modes of implementation In the following sections of this draft the compressor/decompressor entities will be referred to as entity-u (entity-uplink) and entity- d (entity-downlink), see Figure 6.1. Entity-uÆs compressor sends messages to entity-dÆs decompressor and entity-dÆs compressor sends messages to entity-uÆs decompressor. Depending on how the compressor and decompressor at one entity resides, or more specifically, to what extent they are able to communicate, different modes of implementation are possible. The compression efficiency will vary depending on the implemented mode. The following three sections describe the different scenarios for the implementations. Although Figure 6.1 shows a mobile communicating with a base station, the ROGER scheme could be applied to other types of systems and scenarios. Mobile, entity-d Fixed network, entity-u | ................ | | ++ / +--+ || ............> || ++ /\ / \ Figure 6.1. Placement of the compression entities An implementation of the Full contact mode can run on all of the identified scenarios described in this draft. The other two modes should be considered as optimizations for systems, were Full contact mode can not be fully utilized. 6.1. No contact mode The compressor and decompressor residing at the same entity are unable to communicate. Also, the decompressor at entity-u is unable to communicate with the compressor at entity-d and vice versa, making use of acknowledgements impossible. This precludes the use of ROGER headers. Thus, in this particular case no ROGER header is attached to the message. This also implies that the compressor at entity-d never can be positive that a sent message has been received at the decompressor of entity-u. Consequently, use of a dynamic dictionary would make decompression impossible if a previous packet had been lost. Only the static dictionary can be used without losing robustness against packet losses. Figure 6.2 shows this scenario. Hannu, Christoffersson, Svanbro, Forsgren [Page 19] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 Entity-d Entity-u +---------+ +---------+ | Comp. |---------------->| Decomp. | +---------+ +---------+ +---------+ +---------+ | Decomp. |<----------------| Comp. | +---------+ +---------+ Figure 6.2. No information about the arrival of sent messages reaches the compressor. 6.1.1. Compression Compression is carried out by using the static dictionary only. * Compression steps 1) Compress message using SD 2) Send message 6.1.2. Decompression Decompression is carried out by using the static dictionary only. * Decompression steps 1) Decompress message using SD 6.2. Limited contact mode The decompressor at e.g. entity-u can acknowledge messages to the compressor at entity-d. The decompressor at entity-u has a system provided link, which from ROGER's point of view looks like a direct link, to the compressor at entity-d, see Figure 6.3. Entity-d Entity-u +---------+ +---------+ | Comp. |---------------->| Decomp. | | |<-----ACK--------| | +---------+ +---------+ Figure 6.3. Acknowledgements generated by decompressor. From ROGERÆs point of view, the acknowledgements has the same format as the message headers described in Chapter 5, except for the CRC intended for the message. Hannu, Christoffersson, Svanbro, Forsgren [Page 20] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 6.2.1. Compression When the session starts, the dynamic dictionary and the TST are empty. The message is compressed using the static and the dynamic dictionary and is also stored in the TST. The message header indicates which message is sent and which acknowledgements that have been received. * Compression steps: 1) If necessary, move content of TST to DD 2) Compress using SD+DD 3) Put message in TST 4) Attached header 5) Send message 6.2.2. Decompression Decompression is done by first looking at the header attached to the compressed message. The header indicates which messages were in the DD when the message was compressed. That is, the header indicates which acknowledgements that have arrived to the compressor and the messages corresponding to the acknowledgements are used in the compression process. The decompressor makes sure that the same messages are used for decompression, i.e. moving the content of the TRD to the DD which is indicated in the header. The received message is put into the TRD and an acknowledgement is sent to the compressor. One could consider to use a sparse acknowledging scheme here. * Decompression steps: 1) If necessary move content of TRD to DD, see Section 6.4.1. 2) Decompress message using SD+DD 3) Put message in TRD 4) Send Acknowledgement 6.3. Full contact mode The compressor and decompressor on both sides reside together. Thus, both sent and received messages can be used in the compression process since the compressor and decompressor share dictionaries. The decompressor uses the compressor, which it resides together with, to inform the compressor on the other side that a message has been received. This is done by an indication in the sent message's header. See Figure 6.6 for scenario. Hannu, Christoffersson, Svanbro, Forsgren [Page 21] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 +---------+ +----------+ | Comp./ |---------------->| Decomp./ | | Decomp. |<----------------| Comp. | +---------+ +----------+ Figure 6.6. Compressor and decompressor reside together and are able to share the context. 6.3.1. Compression Compression is done using the SD, the DD and the TRD. The sent message is put into the TST. The message ID is put into the header together with the acknowledgement indicating which messages have been received and not yet been put into the DD. * Compression steps: 1) Compress using SD+DD+TRD 2) Put message in TST 3) Attach header 4) Send message An implementation of the Full contact mode can run on all of the identified scenarios described in this draft. The other two modes should be considered as optimizations for systems, were Full contact mode can not be fully utilized. 6.3.2. Decompression The decompression starts by reading the message header. If the acknowledgement indicates a previous sent message which acknowledged an earlier received message this earlier received message is moved from the TRD to the DD. If the acknowledgement indicates that a previously sent message has been received at the other entity this previously sent message is moved from the TST to the DD. * Decompression steps: 1) If necessary move content of TRD to DD, see Section 6.4.1. 2) If necessary move content of TST to DD, see Section 6.4.2. 3) Decompress message using SD+DD 4) Put message in TRD 5) Send acknowledgment if needed 6.4. Move of table content This section defines when to move contents from the TRD or TST to the DD. In general the order for movement is: Hannu, Christoffersson, Svanbro, Forsgren [Page 22] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 1) move contents from TRD to DD 2) move contents from TST to DD. The contents of the TRD and TST may be several messages. Only the messages that correspond to a certain acknowledgement are moved. 6.4.1. TRD to DD When a message is sent carrying indications of received messages in the TRD, a mapping between the message ID and the IDs of the messages stored in the TRDT is made. When a future message is received by this entity, the entity withdraws the acknowledged messages IDs from the received message header. The acknowledged messages IDs are compared with the IDs stored in the TRDT. If there is a match the corresponding contents in the TRD (given by the mapping) is moved to the DD and the mapping is removed from the TRDT. If the next received message carries the same acknowledgment it will not cause difficulties since the mapping has been removed from the TRDT. 6.4.2. TST to DD The contents of the TST is moved to the DD when an acknowledgement is received for the message stored in the TST. The TST must be constructed so that if the next following messages acknowledge the same message there is no move of content from the TST to the DD. 7. ROGER requirements For the three modes there are some requirements on the involved protocols/layers where ROGER compression is applied. 1. Negotiation 1a. There should be a mechanism for negotiating whether ROGER compression is to be used or not. 1b. Maximum physical memory dynamic dictionary size must also be negotiated. This could be done by a carrying a parameter in the negotiating message, stating "Max DD= A", the response from the other entity states its "Max DD= B", the size of the DD to use in the compression process is then chosen to be the minimum of A and B. 1c. The mode ROGER is to run is an implementation issue. However, note that an implementation of ROGER in the full contact mode also can run in the other two modes if needed. Hannu, Christoffersson, Svanbro, Forsgren [Page 23] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 1d. The interval of reordering ([MID-N,MID]) that ROGER must support, should be negotiated before compression starts. N must be chosen to be less than the number of MIDs used. This draft does not state how the negotiation should be done. 2. Context identification 2a. There must be means to identify the flow(s) that correspond to a certain context. How, this is done depends on the environment where ROGER is placed. Thus, this is an implementation issue. 3. Feedback 3a. As ROGER does not define any piggyback headers, it is up to the other layers/protocols to provide the feedback to the ROGER entities, e.g. by a dedicated feedback channel. 3b. Its up the implementation to associate flows, when shared contexts are in use for the full contact mode. 4. Dictionary maintenance 4a. The ROGER context at the compressor and the decompressor must be kept equally long to avoid that a compressed message can not be decompressed. How, this is done depends on the environment where ROGER is placed. Thus, this is an implementation issue. However, CP- FLUSH can of course always be used to flush the dictionaries. 4b. The dictionaries at compressor and decompressor must be updated according to the same procedure, otherwise it is impossible to decompress a compressed message. A ROHC profile for ROGER is described in chapter 9. 8. Implementation status ROGER as defined in this draft is implemented by Ericsson ///. The implementation work started with the 00-version, and has provided useful experience, which lead to the updates in this 01-version of the ROGER scheme. Compression tests, using the implementation of ROGER 01-version, also validate the results in chapter 10. 9. ROGER over ROHC - A new ROHC profile ROGER is suitable for compression of ASCII based protocol messages, The ASCII protocol messages mentioned in this draft are all carried Hannu, Christoffersson, Svanbro, Forsgren [Page 24] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 on top of UDP/IP or TCP/IP, [UDP],[TCP,[IP]. This chapter describes how ROGER could fit into the ROHC framework. Figure 9.1 shows a packet before and after compression with ROGER included in ROHC. CM is compressed information e.g. SIP/SDP, H is the ROGER header and R is the ROHC header handling the UDP/IP part of the packet. +--------+---------+ +---+---+----+ | IP/UDP | SIP/SDP |---- compression ---->| R | H | CM | +--------+---------+ +---+---+----+ Figure 9.1. Packet before and after compression. 9.1. ROGER profile in the ROHC framework The compression scheme ROGER could be made as a part of the ROHC framework. Profile 2 in ROHC is a UDP/IP compression profile. A new profile which has the same functions and packet types as profile 2 and includes ROGER could be defined. Thus, the new profile would also compress the UDP payload with ROGER. Another profile can also be defined in a similar manner using the future ROHC TCP profile. 9.1.1. Limited contact mode The limited contact mode implementation of ROGER, does not require any changes to the ROHC scheme or any additional features from the system that are not already required by ROHC. The next section describes the packet types to fit ROGER into the ROHC scheme. 9.1.1.1. Packet types The packet types of this combination of ROHC and ROGER have the same formats as defined in ROHC for profile 2 with the addition of the ROGER message header. The ROGER message header is placed at the end of the profile 2 ROHC header: 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ : : / ROHC profile 2 header / : : +---+---+---+---+---+---+---+---+ : : / ROGER HEADER / : : +---+---+---+---+---+---+---+---+ / Compressed message / +---+---+---+---+---+---+---+---+ Hannu, Christoffersson, Svanbro, Forsgren [Page 25] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 The feedback types are the same for ROHC profile 2, with the addition of this option: 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ | Opt Type = 5 | Opt Len = * | +---+---+---+---+---+---+---+---+ : : / ROGER HEADER / - ROGER feedback : : +---+---+---+---+---+---+---+---+ / / - Other types of feedback +---+---+---+---+---+---+---+---+ *If the "Opt Len" field has a value larger than the length of the ROGER header there are more feedback options in this packet, which starts after the ROGER feedback. 9.1.2. Full contact mode ROGER gains in compression efficiency if the dictionaries can be shared between the compressor and decompressor at the entities. How to share contexts is not defined in the ROHC scheme and is therefore regarded as an implementation issue. However, this feature must be implemented on both sides of the link. The use of shared dictionaries requires that it is possible to associate the entities inbound and outbound flows. The criteria for associating the flows could be the IP-addresses and possibly also the port numbers. It is necessary that both the uplink and downlink flows pass through the same point. 9.1.2.1. Packet types The packet types of this combination of ROHC and ROGER have the same formats as defined in ROHC for profile 2 with the addition of the ROGER message header. Thus, the packet types are the same as described in section 9.1.1.1. 10. Evaluation of compression scheme A small test in the limited contact and full contact mode situations was carried out to evaluate the performance of ROGER. The messages from a SIP trace of a call setup were compressed. The packet flow consisted of 13 messages sent between a client and a SIP proxy. Hannu, Christoffersson, Svanbro, Forsgren [Page 26] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 The compression was performed using an implementation of the LZSS algorithm as described in Section 4. To determine the size of the compressed file, the size of the compressed dictionary was compared to the size of the compressed extended file. The static dictionary used for the compression and decompression is built up by header field names e.g.; To:, From:, and Via: In the limited contact mode it was assumed that every message was acknowledged before the next message was sent, i.e. a dedicated channel was available. This gives a slightly better compression than if piggy-backing on SIP messages travelling in the opposite direction is used, since this gives a slower dictionary expansion. The results in terms of compression factors (size uncompressed/size compressed) are given in Table 1. The over all compression factors were 3.3 for the limited contact mode and 4.6 for the full contact mode. Message # Originating source Compression factor Limited Full 1 Client 1.5 1.5 2 Proxy 1.5 5.6 3 Proxy 1.9 3.1 4 Client 3.5 4.9 5 Proxy 5.2 6.4 6 Client 5.7 5.7 7 Proxy 6.8 8.1 8 Proxy 7.4 8.3 9 Proxy 6.9 7.0 10 Client 7.2 7.4 11 Proxy 7.1 7.8 12 Proxy 6.6 7.9 13 UAC 7.8 7.8 Table 1. As can be seen from the table, compression is more efficient in the full contact mode. This is due to the fact that the dictionaries grow faster since both sent and received messages are used. 11. Conclusions This draft has presented the compression scheme ROGER for application signaling protocols. The scheme is simple to implement and shows promising results for compression of the ASCII based protocols SIP/SDP, and can be expected to have a similar performance on other ASCII based protocols such as RTSP. Hannu, Christoffersson, Svanbro, Forsgren [Page 27] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 Three modes of implementation exists; No contact mode, Limited contact mode, and Full contact mode. The mode should be chosen at the time of implementation. It should be noted that Full contact mode can be used in all of the defined scenarios without any modifications. Requirements on the layers/protocols where to run ROGER are listed in the draft. This draft also presents a new profile in the ROHC framework. 12. Security considerations In general encryption and compression do not go very well. More specifically, messages that are encrypted are not possible to compress efficiently. It is of course possible to run a loss less compression algorithm like ROGER on an encrypted message, but the compression will most likely not decrease the size of the message. 13. IANA considerations An implementation of ROGER, might need some IANA involvement depending on the layers/protocols that ROGER is implemented with. E.g. if ROGER is to be a part of the ROHC framework some ROHC profile identifiers must be reserved by the IANA. 14. Acknowledgements Thanks to Arto Mahkonen, Ericsson LMF, Lars-Erik Jonsson and Mats Nordberg, Ericsson Erisoft, for their valuable input to this work. 15. Intellectual property rights considerations Ericsson has filed patent applications that might possibly have technical relations to this contribution. See further: http://www.ietf.org/ietf/IPR/ERICSSON-General 16. Author's Addresses Hans Hannu Tel: +46 920 20 21 84 Ericsson Erisoft AB Lulea, Sweden EMail: Hans.Hannu@epl.ericsson.se Jan Christoffersson Tel: +46 920 20 28 40 Ericsson Erisoft AB Lulea, Sweden EMail: Jan.Christoffersson@epl.ericsson.se Hannu, Christoffersson, Svanbro, Forsgren [Page 28] INTERNET-DRAFT RObust GEneric message size Reduction July 06, 2001 Krister Svanbro Tel: +46 920 20 20 77 Ericsson Erisoft AB Lulea, Sweden EMail: Krister.Svanbro@epl.ericsson.se Stefan Forsgren Tel: +46 920 20 23 39 Ericsson Erisoft AB Lulea, Sweden EMail: Stefan.Forsgren@epl.ericsson.se 16. References [APP] H. Hannu, J. Christoffersson and K. Svanbro, Application signaling over cellular links, Internet Draft (work in progress), March 2001. [CELL] L. Westberg and M. Lindqvist, Realtime traffic over cellular access networks, Internet Draft (work in progress), June 2001. [HTTP] R. Fielding, et. al., Hypertext Transfer Protocol û HTTP/1.1. RFC 2616, June 1999. [IP] J. Postel, Internet Protocol, RFC 791, September 1981. [LZSS] J.A. Storer and T.G. Szimanski, Data Compression via Textual Substitutions. Journal of the ACM 29, 1982. [ROHC] C. Bormann, Et. al., RObust Header Compression, Internet Draft (work in progress), February 2001. [RTSP] H. Schulzrinne, A. Rao and R. Lanphier, Real Time Streaming Protocol (RTSP). RFC 2326, April 1998. [SDP] M. Handley and V. Jacobson, SDP: Session Description Protocol. RFC 2327, April 1998. [SIP] M. Handley, H. Schulzrinne, E. Schooler and J. Rosenberg, SIP: Session Initiation Protocol. RFC 2543, August 2000. [TCP] J. Postel, Transmission Control Protocol, RFC 793, September 1981. [UDP] J. Postel, User Datagram Protocol, RFC 761, August 1980. This Internet-Draft expires in January 2002. Hannu, Christoffersson, Svanbro, Forsgren [Page 29]