Network Working Group Zhigang Liu INTERNET-DRAFT Khiem Le Date: 22 March 2001 Ka-Cheong Leung Expires: 22 September 2001 Christopher Clanton Nokia Research Center Scalable Robust Efficient Dictionary-Based Compression (SCRIBE) Status of This Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026 [RFC2026]. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This document is a submission of the IETF ROHC WG. Comments should be directed to its mailing list, rohc@cdt.luth.se. Abstract This document defines an efficient, robust, and scalable scheme for the use of dictionary-based compression algorithms when the transport between the compressor and decompressor is unreliable, i.e. prone to errors and losses. Dictionary-based compression algorithms are applicable in particular to compression of text-oriented protocol messages, such as signalling messages from SIP, RTSP, SDP, and HTTP. In particular, a major case of application is the compression of SIP protocol messages over bandwidth limited links, such as cellular Liu, Le, Leung, and Clanton [Page i] INTERNET-DRAFT SCRIBE 22 March 2001 links. Liu, Le, Leung, and Clanton [Page ii] INTERNET-DRAFT SCRIBE 22 March 2001 Table of Contents Status of This Memo . . . . . . . . . . . . . . . . . . . . . . . . i Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2. Basic Framework of SCRIBE . . . . . . . . . . . . . . . . . . . . 2 2.1. Assumptions . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2. Concepts and Terminology of SCRIBE . . . . . . . . . . . . . 3 2.2.1. Cross-Session Dictionary . . . . . . . . . . . . . . . . . 3 2.2.2. Checkpoint/Rollback . . . . . . . . . . . . . . . . . . . 3 2.2.3. Sliding Handshake . . . . . . . . . . . . . . . . . . . . 4 2.2.4. Dictionary Organization . . . . . . . . . . . . . . . . . 4 3. Protocol Definition . . . . . . . . . . . . . . . . . . . . . . . 5 3.1. Message Compression . . . . . . . . . . . . . . . . . . . . 5 3.2. Sliding Handshake . . . . . . . . . . . . . . . . . . . . . 7 3.3. Checkpoint Establishment Procedure . . . . . . . . . . . . . 9 3.4. Rollback Procedure . . . . . . . . . . . . . . . . . . . . . 12 3.5. Dictionary Management . . . . . . . . . . . . . . . . . . . 14 3.5.1. Cross-Session Dictionary . . . . . . . . . . . . . . . . . 15 3.5.1.1. State Verification and Downloading . . . . . . . . . . . 16 3.5.2. Profile specific Dictionary . . . . . . . . . . . . . . . 19 3.5.3. Implicit Dictionary Content Deletion . . . . . . . . . . . 21 4. Packet Formats . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.1. Normal Packet Formats . . . . . . . . . . . . . . . . . . . 22 4.1.1. Short Sequence Number . . . . . . . . . . . . . . . . . . 23 4.1.2. Long Sequence Number . . . . . . . . . . . . . . . . . . . 24 4.1.3. Acknowledgement . . . . . . . . . . . . . . . . . . . . . 24 4.1.4. Checkpoint . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2. Special Dictionary Management Packet Formats . . . . . . . . 29 5. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6. Intellectual Property Right Considerations . . . . . . . . . . . 34 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 8. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 36 Liu, Le, Leung, and Clanton [Page iii] INTERNET-DRAFT SCRIBE 22 March 2001 1. Introduction This document defines an efficient, robust, and scalable scheme for the use of dictionary-based compression algorithms when the transport between the compressor and decompressor is unreliable, i.e. prone to errors and losses. Dictionary-based compression algorithms are applicable in particular to compression of text-oriented protocol messages, such as signalling messages from SIP (Session Initiation Protocol) [SIP], RTSP (Real Time Streaming Protocol) [RFC2326], SDP (Session Description Protocol) [RFC2327], and HTTP (Hypertext Transfer Protocol) [RFC2616]. In particular, a major case of application is the compression of SIP protocol messages over bandwidth limited links, such as cellular links. The scheme proposed in this document includes some concepts which are similar to those in [ROGER]. However, compared to [ROGER], SCRIBE has additional concepts which provide significant improvements in terms of compression efficiency, robustness, scalability, and flexibility. SCRIBE improves on compression efficiency mainly by maintaining a dictionary from previous sessions that can be used at the very beginning of a subsequent session to jump start the compression of initial messages. Higher efficiency is also achieved because the scheme recovers from a detected dictionary desynchronization by rolling back to a checkpoint dictionary that is more populated than the static part of a dictionary, which contains protocol-specific entries only. SCRIBE is scalable as it provides mechanisms to accommodate memory size limitations at the compressor and/or decompressor. Memory size scalability is critically needed for mobile devices such as cellular terminals. SCRIBE is scalable also in the sense that it can be adjusted to a certain degree of packet loss experienced by the system. Finally, flexibility comes from the mechanisms to successfully manage the dictionary at various granularity levels, such as messages, strings, etc. The remainder of this document is structured as follows. Section 2 gives a conceptual framework of our proposed scheme, namely the basic assumptions, and concepts and terminology. Section 3 describes the protocol definition, which includes the message compression, sliding handshake, checkpoint establishment procedure, rollback procedure, and dictionary management. Section 4 introduces a set of message formats used by the proposed scheme. Finally, Section 5 concludes our work. Liu, Le, Leung, and Clanton [Page 1] INTERNET-DRAFT SCRIBE 22 March 2001 2. Basic Framework of SCRIBE 2.1. Assumptions Our proposed scheme is grounded on the following assumptions: - The entities to be compressed and decompressed are the protocol messages (e.g. SIP messages). The algorithm at a compressor endpoint takes as input a dictionary and a message to be compressed, and produces as output a compressed message. The reverse operation is performed by the algorithm at a decompressor endpoint, taking as input a dictionary and the compressed message, and producing as output a decompressed message. The dictionary used to decompress a message must be identical to the one used to compress (synchronized or coherent dictionary). - A larger dictionary leads to higher compression efficiency. That is, if Dictionary A is a superset of Dictionary B, usage of Dictionary A will result in higher compression efficiency than that of Dictionary B. - The dictionary is populated from the compressed protocol messages exchanged between the compressor and decompressor. - No assumption is made about the size of a protocol message. - Messages exchanged between the compressor and decompressor can be the compressed protocol messages, or signalling messages at the compressor/decompressor level. - The transport between the compressor and decompressor is such that the messages (protocol and signalling) are subject to losses and corruptions. - The memory storage at the compressor and decompressor can vary in size. The compressor and decompressor do not necessarily have the same storage capacity. This is true in particular in cellular systems, where the mobile terminal will likely have less memory capacity than its counterpart in the network. - There are two different ways to perform compression/decompression using a dictionary, namely split dictionary mode and shared dictionary mode. In split dictionary mode, a decompressor at one endpoint can only acknowledge received messages to a compressor at another endpoint. A compressor and a decompressor at the same endpoint use different dictionaries for compression and decompression respectively. However, in shared dictionary mode, a Liu, Le, Leung, and Clanton [Page 2] INTERNET-DRAFT SCRIBE 22 March 2001 compressor and a decompressor at an endpoint reside together such that a shared dictionary can be used for both compression and decompression. 2.2. Concepts and Terminology of SCRIBE SCRIBE is devised based on the following core concepts: cross-session dictionary, checkpoint and rollback, sliding handshake, and dictionary organization. These concepts are discussed as follows. 2.2.1. Cross-Session Dictionary This concept is based on the fact that text-based messages sent to or received by an user during different sessions (or calls) tend to share similar characteristics. This is particularly true for SIP messages. Therefore, for a given user, the dictionary built up during a session can be used to jump start the next subsequent session, i.e. compress the very first messages of that session. This leads to higher message compression efficiency and a shorter call set up time. In addition, in systems which steal bandwidth allocated to the media when there is an excessive bandwidth demand surge to carry the signalling protocol, the application of this approach results in higher media quality, since there is lesser or no need to steal or blank out media bits to carry signalling messages. However, the longer life span of a dictionary might result in a higher chance of losing synchronization on the dictionaries between a compressor and a decompressor. Therefore, there is a need to have additional mechanisms, namely checkpoint and rollback, to be used to assure the dictionary coherency. 2.2.2. Checkpoint/Rollback * Checkpoint: At a checkpoint establishment procedure, a compressor and a decompressor verify if they have a coherent dictionary and store it for future reference. Verification is done by using a strong CRC (Cyclic Redundant Code) calculation over the dictionary. The dictionary thus stored is referred to as a checkpoint dictionary. A version number is used to differentiate checkpoint dictionaries established at different points in time. * Rollback: At any point in time, a compressor and a decompressor can initiate a rollback procedure, where both ends rollback in a synchronized fashion to a checkpoint dictionary (CD) specified with its version number. Rollback can be triggered when a Liu, Le, Leung, and Clanton [Page 3] INTERNET-DRAFT SCRIBE 22 March 2001 dictionary error or desynchronization is detected. 2.2.3. Sliding Handshake This concept is similar to the one described in [ROGER]. Each message (protocol or signalling) carries a sequence number. A message can be acknowledged. Acknowledgements are cumulative and selective. An acknowledgement is cumulative and selective. An acknowledgement is cumulative in the sense that multiple messages, e.g. Messages 5, 6, 7, and 8, can be acknowledged at the same time. It is selective because one can specify Messages 5, 6, and 8 are acknowledged, but not Message 7. An acknowledgement only needs to carry the sequence number of Message m to mean acknowledging of a set of (m - n + 1) messages consecutively numbered from Message n to Message m, where Message (n - 1) is the last message whose acknowledgement is known to be received. A bit mask needs to be sent only when the messages to be acknowledged are not consecutively numbered. Most of the time, it is expected that messages are consecutively numbered, since non-consecutive numbering happens when messages are lost. Whenever a message, which is used to update the dynamic part of a dictionary (DD), is sent from an endpoint, a copy of the message is stored in a place called the temporary sender dictionary (TSD). When another endpoint receives the compressed message, it decompresses the message and the decompressed message will be stored in a repository called the temporary receiver dictionary (TRD). An acknowledgement with respect to the arrival of the compressed message will be sent to the sender, and a mapping between the sequence number of the acknowledgement and that of the compressed message will be maintained in the temporary receiver dictionary table (TRDT). When the sender receives the acknowledgement, the captioned message will be moved from the temporary sender dictionary to the dynamic part of the dictionary once an acknowledgement with respect to this message is received. An acknowledgement towards the reception of the acknowledgement of the message is then sent to the receiver. Once that acknowledgement is received, the receiver moves the stored message from the temporary receiver dictionary to the the dynamic part of the dictionary. The sliding handshake procedure for the captioned message is therefore completed. 2.2.4. Dictionary Organization To account for the fact that there are some strings specific to an user which has high probability to appear in messages involving that user, we define the concept of profile-specific part of a dictionary. Liu, Le, Leung, and Clanton [Page 4] INTERNET-DRAFT SCRIBE 22 March 2001 Generally, a dictionary consists of the static part, profile-specific part, and dynamic part. Unlike the static part, the profile-specific part and dynamic part of a dictionary may be empty at a given time. The static part of a dictionary is the part of the dictionary which can be populated simply from knowing what protocol is used. For example, if the protocol is SIP, the static part can include since the last costrings, such as "From:", "To:", etc. The static part is relevant for all users and sessions. It does not change over time. The profile-specific part of a dictionary is the part of the dictionary which can be populated from knowing information specific to an user. For example, if the protocol is SIP, the profile- specific part can include strings related to the SIP URL (Uniform Resource Locator), or the types of media capabilities, etc. The profile-specific part is relevant for all sessions involving an user. It may change over time, but not frequently. The dynamic part of a dictionary is the part of the dictionary which is neither static nor profile-specific. It is populated by making use of messages from/to an user. Thus, the dynamic part is updated more frequently than the profile-specific part, possibly on a message by message basis. Furthermore, each endpoint can decide to include or not include part or all of a message in the dictionary, even though the message was received. An acknowledgement to Message 1 means the message was received and the receiver decided to add it to the dictionary. If Message 1 is not acknowledged, it means the message was not received or, it was received but the receiver decided not to add it to the dictionary. 3. Protocol Definition This section describes the protocol definition, which includes the message compression, sliding handshake, checkpoint establishment procedure, rollback procedure, and dictionary management. 3.1. Message Compression The following text describes the idea by using SIP as a concrete example. However, it should be noted that the model is applicable to compressing any protocol messages. Liu, Le, Leung, and Clanton [Page 5] INTERNET-DRAFT SCRIBE 22 March 2001 SIP is a text-oriented application layer signalling protocol to set up, maintain, and terminate a call. Readers can refer to [SIP] for details. To set up a call, several (around five) messages, each of which is typically between 200 and 500 bytes in size, are required. SIP message compression is thus a must to bring down the bandwidth consumption and message latency in traversing a bandwidth constrained link, such as a cellular link. It is even more crucial when a third party tries to connect (by sending SIP messages) to a callee that is in the middle of a call. For some link technologies, if there is no SIP compression applied in this case, not only much longer message delay is inevitable, but also many more voice or media frames may have to be stolen or blanked to carry such signalling messages. This in turns substantially deteriorates voice or media quality. It is proposed in [ROGER] that a dictionary-based algorithm can be used to compress text-oriented messages, such as SIP messages. Figure 1 exhibits the basic idea. There are two endpoints on the SIP message travelling path. Each endpoint consists of a compressor or a decompressor or both. When a SIP message, say, going from left to right is received by the compressor in E-ms, it will be compressed using a dictionary stored in E-ms according to Lempel-Ziv or other similar compression algorithms. These algorithms work by scanning through a file containing the message from left to right and replacing repeated strings by pointers, each of which is the form of an offset and a length of match, to the last previous occurrence in the file. Provided that the dictionaries of a compressor at E-ms and a decompressor at E-net are coherent, E-net can reconstruct an original message from the compressed one by applying the same dictionary (or a superset) as the one it is used for compressing that particular message. Liu, Le, Leung, and Clanton [Page 6] INTERNET-DRAFT SCRIBE 22 March 2001 +------------------+ +--------------------+ | +--------------+ | | +----------------+ | | | Dictionary | | | | Dictionary | | | +--------------+ | | +----------------+ | | | | | | | | | original | | | | compressed | | | | message | +----------+ | | message | +------------+ | | --------------+>|Compressor|-) - + - - - - - -+>|Decompressor|-)---+----> | +----------+ | | | +------------+ | | | | | | | | decompressed | | | compressed | | | message | +--------------+ | message | +----------------+ | <-------------+-| Decompressor |<+- - - - - - +-| Compressor |<+----- | +--------------+ | | +----------------+ | +------------------+ +--------------------+ E-ms E-net Figure 1. Dictionary-Based Message Compression. Whenever a message is to be compressed, the dictionary for the compression is constructed in the manner that the static part goes first, the profile-specific part goes second, the the dynamic part goes third, and the temporary receiver dictionary goes last. Similarly, when a message is to be decompressed, the dictionary for the decompression is constructed in the manner that the static part goes first, the profile-specific part goes second, the dynamic part goes third, the relevant part of the temporary receiver dictionary (to be moved to the dynamic part of the dictionary, as indicated by the piggybacked acknowledgement) goes fourth, and the relevant part of the temporary sender dictionary (to be moved to the dynamic part of the dictionary, as indicated by the piggybacked acknowledgement) goes last. 3.2. Sliding Handshake As noted before, the same view in the dictionary on both endpoints is needed to allow a decompressor to recover a compressed message correctly. To ensure dictionary coherency, a three-way handshake mechanism, which is similar to the one proposed in [ROGER], is needed. The mechanism is exhibited in Figure 2. Liu, Le, Leung, and Clanton [Page 7] INTERNET-DRAFT SCRIBE 22 March 2001 | | (A) | CM | |------------------------------->| | | | ACK(CM) | (B) |<-------------------------------| | | (C) | ACK(ACK(CM)) | |------------------------------->| | | (D) | | Endpoint X Endpoint Y Figure 2. Sliding Handshake for Dictionary Maintenance. Suppose a message (called M), which is used to assist future compression/decompression, is sent from Endpoint X to Endpoint Y. Endpoint X will perform the following steps: A1) Compress M using the combined directory, as described in Section 3.1. The compressed message is denoted as CM, which is then transmitted to Endpoint Y. A2) A copy of M is stored in a place called the temporary sender dictionary. A3) Whenever allowed, piggyback acknowledgement, if any. When Endpoint Y receives CM, it will do the following steps: B1) Decompress CM using the combined directory, as described in Section 3.1. The decompressed message is denoted as M'. Note that M' should be the same as M for a successful decompression. B2) Perform a CRC check with M'. If it fails the CRC check, discard the message and stop. Otherwise, continue to do step B3. B3) If M' will be employed for subsequent compression/decompression (as indicated by Endpoint X), a copy of M' is then stored in a repository called the temporary receiver dictionary. B4) Perform dictionary management (as described below) if acknowledgements are piggybacked inside the message header. Move message(s) from the temporary sender dictionary and temporary receiver dictionary to the dynamic part of the dictionary respectively, whenever needed. Liu, Le, Leung, and Clanton [Page 8] INTERNET-DRAFT SCRIBE 22 March 2001 B5) Send an acknowledgement (possibly delayed), called ACK(CM), to Endpoint X about the reception of CM. A mapping between the sequence number of ACK(CM) and that of CM is stored in a location called the temporary receiver dictionary table. Note that ACK(CM) may be piggybacked to the header of a compressed message sent from Endpoint Y, and an acknowledgement can be used to acknowledge a set of received messages. When Endpoint X receives ACK(CM), it will do the following steps: C1) If ACK(CM) is piggybacked with a compressed message, perform tasks as described in steps B1 - B5. Steps B4 and B5 are further elaborated as steps C2 and C3. Otherwise (it contains no compressed messages), perform a CRC check with ACK(CM). If the CRC check is failed, discard the message and stop. C2) Move M from the temporary sender dictionary to the dynamic part of the dictionary. C3) Send an acknowledgement (possibly delayed), called ACK(ACK(CM)), to Endpoint Y about the reception of ACK(CM). Note that ACK(ACK(CM)) may be piggybacked to the header of a compressed message sent from Endpoint X, and an acknowledgement can be used to acknowledge a set of received messages. When Endpoint Y receives ACK(ACK(CM)), it will do the following steps: D1) If ACK(ACK(CM))) is piggybacked with a compressed message, perform tasks as described in steps B1 - B5. Step B4 is further elaborated as steps D2 and D3. Otherwise (it contains no compressed messages), perform a CRC check with ACK(ACK(CM)). If the CRC check is failed, discard the message and stop. D2) Retrieve a mapping between the acknowledged sequence number and a list of sequence numbers that correspond to some messages stored in the temporary receiver dictionary. D3) Move a set of messages (including M' in this example), of which the sequence numbers match with those in the list, from the temporary receiver dictionary to the dynamic part of the dictionary. 3.3. Checkpoint Establishment Procedure To ensure high compression efficiency maintained across sessions and to deal with a detected dictionary incoherency between a pair of Liu, Le, Leung, and Clanton [Page 9] INTERNET-DRAFT SCRIBE 22 March 2001 endpoints, a two-way handshake mechanism for creating a dictionary checkpoint is proposed, which is shown in Figure 3. | | DD = {1} | | DD = {1} TSD = {2} | | TSD = {101} TRD = {101} | | TRD = {2} CD = DD + TRD | | | | (E) | CHKPT_INIT | TO-1 starts |------------------------------->| | | DD = {1, 101} | | TSD = {} | | TRD = {2} | | CD = DD | | | CHKPT_ACK | (F) TO-1 stops |<-------------------------------| (G) | | | | DD = {1, 101} | | TSD = {2} | | TRD = {} | | CD = {1, 101} | | | | Endpoint X Endpoint Y Figure 3. Two-Way Handshake for Creating a Dictionary Checkpoint. The idea behind this is indeed similar to that described for the sliding handshake. Suppose Endpoint X initiates the creation for a dictionary checkpoint. It will perform the following steps: E1) Save a copy of the dynamic part of the dictionary and the temporary receiver dictionary, together with a version number, to a repository called a checkpoint dictionary. E2) Send a checkpoint initiation, called CHKPT_INIT, which includes a strong dictionary CRC and the version number, to Endpoint Y. This control message piggybacks with an acknowledgement to a list of received messages. E3) Store the mapping between the sequence number of CHKPT_INIT and those messages currently stored in the temporary receiver dictionary in the temporary receiver dictionary table. Liu, Le, Leung, and Clanton [Page 10] INTERNET-DRAFT SCRIBE 22 March 2001 E4) Start the checkpoint re-initiation timer (TO-1). E5) Delay all acknowledgements to packet receptions until the corresponding CHKPT_ACK arrives. When Endpoint Y receives CHKPT_INIT, it will do the following steps: F1) Perform dictionary management with respect to the piggybacked acknowledgement, as described in the sliding handshake. F2) Verify the dictionary CRC with that of the dynamic part of the dictionary. If it fails the CRC check, discard the request, initiate a rollback (to be discussed in the next section). Otherwise, continue to step F3. F3) Store a copy of the dynamic part of the dictionary, together than the version number carried in CHKPT_INIT, to a checkpoint dictionary. F4) Send a checkpoint acknowledgement, called CHKPT_ACK, to Endpoint X. When Endpoint X receives CHKPT_ACK, it will perform the following steps: G1) Stop the checkpoint re-initiation timer (TO-1). G2) Perform dictionary management with respect to the piggybacked acknowledgement, as described in the sliding handshake. When Endpoint X receives ROLL_INIT to signal the rejection of a checkpoint request, it will stop the checkpoint re-initiation timer and perform a rollback as instructed (to be detailed in the Section 3.4). Suppose at the beginning, as shown in Figure 3, Endpoint X has DD containing Message 1, TSD containing Message 2, and TRD containing Message 101; Endpoint Y has DD containing Message 1, TST containing Message 101, and TRD containing Message 2. When a checkpoint creation is initiated at Endpoint X, a CD is constructed such that it contains both the current contents of DD and TRD. A checkpoint initiation CHKPT_INIT, which is piggybacked with a strong dictionary CRC, and an acknowledgement to a received message, i.e. Message 101, is sent to Endpoint Y. The checkpoint re-initiation timer is started. Whenever Endpoint Y receives CHKPT_INIT, its TSD is updated such that the message is moved to DD. The dictionary CRC carried in CHKPT_INIT is verified against with that of its DD. If there is a match, a CD is then constructed by mirroring the current content of Liu, Le, Leung, and Clanton [Page 11] INTERNET-DRAFT SCRIBE 22 March 2001 DD. Once finished, a checkpoint acknowledgement CHKPT_ACK is sent to Endpoint X to indicate a successful completion of a checkpoint creation. The checkpoint re-initiation timer is stopped when Endpoint X receives CHKPT_ACK. When either CHKPT_INIT or CHKPT_ACK is lost during transmission, the checkpoint re-initiation timer (TO-1) will expire. CHKPT_INIT is then re-transmitted again by the initiator, i.e. Endpoint X. The whole process will repeat, where the timer initial value is doubled each time the timer is restarted under this way. When both endpoints initiate a checkpoint creation approximately the same time, one of such initiations will go through. This can be achieved by sending CHKPT_INIT with a random number, such as a time- seeded random number. The collision can be resolved by favouring the one with the larger random number. If ties happen, the initiation process has to be restarted again after waiting for a random amount of time, possibly with other mechanisms to adjust for the waiting time, whenever the timer is restarted under this situation. Furthermore, the dictionary collected at each checkpoint is stored in an identifiable manner (by means of a checkpoint version number) such that any previously stored dictionaries can be employed for a dictionary rollback whenever a dictionary desynchronization has detected. 3.4. Rollback Procedure Whenever a dictionary CRC mismatch is found by an endpoint, a two-way handshake mechanism is employed for a dictionary rollback, which is exhibited in Figure 4. | | (H) | ROLL_INIT | TO-2 starts |------------------------------->| | | (I) | ROLL_ACK / ROLL_REJ | TO-2 stops |<-------------------------------| (J) | | | | Endpoint X Endpoint Y Figure 4. Two-Way Handshake for Rollback Procedure. Liu, Le, Leung, and Clanton [Page 12] INTERNET-DRAFT SCRIBE 22 March 2001 Suppose Endpoint X finds a mismatch in the dictionary CRC, it initiates a dictionary rollback. It will perform the following steps: H1) Send a rollback initiation, called ROLL_INIT, to Endpoint Y. This control message carries a checkpoint version number to indicate which checkpoint is going to be used for dictionary re- synchronization, and a CRC for that particular checkpoint. H2) Start the rollback re-initiation timer (TO-2). When Endpoint Y receives ROLL_INIT, it will perform the following steps: I1) Verify the checkpoint CRC carried in ROLL_INIT with the one computed from the requested checkpoint. If the requested checkpoint is available and there is a match in the checkpoint CRC, continue to do step I2; otherwise, continue to do step I5. I2) Clear the dynamic part of the dictionary and all temporary dictionaries, tables, and related data structures. I3) Load the dictionary with the specified checkpoint dictionary. I4) Send a rollback acknowledgement, called ROLL_ACK, to Endpoint X, and done. Note that Endpoint Y does not perform any dictionary updates nor send any acknowledgements to received messages, of which the sequence numbers are smaller than that of ROLL_INIT. I5) Send a rollback rejection, called ROLL_REJ, to Endpoint X. When Endpoint X receives ROLL_ACK, it will perform the following step: J1) Stop the rollback re-initiation timer (TO-2). When Endpoint X receives ROLL_REJ, it will perform the following steps: J2) Stop the rollback re-initiation timer (TO-2). J3) Initiate a new rollback to Endpoint Y, with another checkpoint version number. Note that a specific checkpoint version number can be used to indicate a empty checkpoint, which is always available and coherent. When either ROLL_INIT or ROLL_ACK is lost during transmission, the rollback re-initiation timer (TO-2) will expire. ROLL_INIT is then Liu, Le, Leung, and Clanton [Page 13] INTERNET-DRAFT SCRIBE 22 March 2001 re-transmitted again by the initiator, i.e. Endpoint X. The whole process will then repeat. When both endpoints initiate a rollback approximately the same time, one of such initiations will go through. This can be achieved by sending ROLL_INIT with a random number, such as a time-seeded random number. The collision can be resolved by favouring the one with the larger random number. If ties happen, the initiation process has to be restarted again after waiting for a random amount of time, possibly with other mechanisms to adjust for the waiting time, whenever the timer is restarted under this situation. Rollback is also needed whenever a checkpoint initiation is rejected. An example is that a checkpoint CRC validation fails. Suppose Endpoint X sends a checkpoint initiation to Endpoint Y. However, the request is then rejected by Endpoint Y, which is shown in Figure 5. Endpoint Y simply sends a checkpoint initiation to signal the rejected request to Endpoint X. Whenever Endpoint X receives the initiation, it does a rollback as requested and a rollback acknowledgement is sent to Endpoint Y to acknowledge the completion of the rollback. | | | CHKPT_INIT | |------------------------------->| | | | ROLL_INIT | |<-------------------------------| | | | ROLL_ACK | |------------------------------->| | | Endpoint X Endpoint Y Figure 5. An Example Showing How the Rollback Procedure is Used to Reject a Checkpoint Initiation. 3.5. Dictionary Management In Sections 3.1 - 3.4, we have discussed several mechanisms that ensure compression and decompression of messages be done correctly. In this section, we investigate how to manage a pair of dictionaries such that a higher compression efficiency can be achieved. There are Liu, Le, Leung, and Clanton [Page 14] INTERNET-DRAFT SCRIBE 22 March 2001 three weapons to unfold this problem, namely the cross-session dictionary, profile-specific dictionary, and implicit dictionary content deletion. 3.5.1. Cross-Session Dictionary In [ROGER], it proposes to compress the messages sequentially using the previous messages from the same session. In other words, the dynamic part of the dictionary is built starting from scratch since a session begins and then discarded once the session terminates. This means, as pointed out in [ROGER], the first message sent in each session can be compressed using only the static part (and the profile-specific part) of the dictionary, whereas the dynamic part of the dictionary is empty at that moment. Compression of these messages is thus not as efficient as the dynamic part of the dictionary is well-populated, that has been verified as [ROGER] reported that the compression factor for the first message is 1.5 whereas that for the whole session of 13 messages is at least 3.3. This indicates that there is a room for improvement. To solve the aforementioned problem, the life span of the dynamic part of a dictionary is needed to be extended beyond to that of a session. One key observation is that certain messages, like SIP messages, belonging to different sessions (or calls) also share many similar characteristics. This naturally leads us to the concept of cross-session dictionary. Instead of limiting the scope of a dictionary to only a single session, we can simply keep the dynamic part of the dictionary to appear in the next subsequent session. One of the obvious results from cross session dictionary is that a higher compression efficiency for the initial messages of a session can be attained, since some strings in these messages can be referred from those stored in the dictionary. In the case of SIP, the initial messages of a session are usually the largest. A higher compression ratio of those messages will proportionally result in higher overall compression factor. In addition, a reasonable compression efficiency can still be maintained even if one round of dictionary synchronization procedure cannot be completed within a short time period, such as within an inter-message time. Specifically, there is no longer a need to re- synchronize the dictionaries quickly every time a new session starts, since the two endpoints can at least use the dictionaries that have been synchronized during the previous session. Nevertheless, a fast (i.e. within an inter-message time) re-synchronization mechanism would further improve compression efficiency whenever there exists some strings in the initial messages that are specific to a session, Liu, Le, Leung, and Clanton [Page 15] INTERNET-DRAFT SCRIBE 22 March 2001 such as call identifier. 3.5.1.1. State Verification and Downloading Since the dictionaries are maintained across sessions, it needs to have a mechanism for the two entities, i.e. E-ms and E-net, to verify that they have the same compression context or dictionary before or when a session begins. Such mechanism is known as the state verification. In addition, another mechanism, known as the state downloading, is needed to enable E-net to download the compression context from a dictionary server (denoted as D-server) if it does not have one for E-ms. This could happen, for example, when E-ms roams to an area covered by a new E-net. The procedure to perform these two mechanisms is called the state verification and downloading procedure. Of course, as the last resort, E-ms and E-net can always re- synchronize their contexts via the bandwidth limited link connecting them. All this is done preferably before a call is set up, but this is not a mandatory requirement. The following description of the state verification and downloading procedure assumes SIP message compression. Specifically, the first step, i.e. step K, can be piggybacked on a SIP registration message. However, nothing prevents the same mechanism being applied to the compression of any other text-oriented protocol messages. Note that the procedure can run on any unreliable channel. Figure 6 shows the concepts and message flows involved during the procedure. It is assumed that D-server maintains a dictionary and/or state associated with each E-ms. The procedure starts when a MS (mobile station) powers on or it detects that it has roamed to an area that is covered by a new E-net. K) E-ms sends a state advertisement, called STATE_ADV, to the current E-net to advertise what type of dictionary it has in its compression context. The message contains a menu of available items, such as checkpoint dictionary (Item 1), profile-specific dictionary (Item 2), static part of the dictionary (Item 3), etc. It also contains strong CRCs calculated over each of the items appeared in the menu. For example, STATE_ADV containing {1, 2, CRC1, CRC2} means E-ms has both Item 1 and Item 2. After sending STATE_ADV, E-ms starts a timer (TO-3) associated with the message. After timeout, E-ms can repeat step K up to a certain limit. The timer will be stopped when E-ms receives STATE_ADV_ACK from E-net (see step O below). Liu, Le, Leung, and Clanton [Page 16] INTERNET-DRAFT SCRIBE 22 March 2001 L) Upon receiving STATE_ADV, E-net scans the menu sent by E-ms. The item that matches with the one stored in E-net is available and selected as a part of the common dictionary. An items is deemed to be available only if the CRC check succeeds. If there exists an available item, it can choose to go to step N. Note that alternatively, E-net can decide to go to step N only if it finds a match for some item(s) (i.e. Item 1 or Item 2). If no match is found (or no match for any desired item is found) or there exists an item that is not available in E-net, E-net can send a download request, called DOWNLOAD_REQ, to D-server to request for the items listed in STATE_ADV that it does not have any locally. The corresponding CRC (originally stored in STATE_ADV) for each item is also included in DOWNLOAD_REQ. A globally unique user identifier is also included in the message to tell D-server whose information is being requested. It is assumed that E-net can derive the user identifier itself, such as based on the mapping from the device identifier of E-ms. Otherwise, E-ms can send explicitly its user identifier in STATE_ADV. After sending DOWNLOAD_REQ, E-net starts a timer (TO-4) for the message. If the timer expires, it can either go directly to step N or repeat this step to resend DOWNLOAD_REQ. The timer will be stopped when E-net receives a download response, called DOWNLOAD_REP, from D-server (see step M below). M) After receiving DOWNLOAD_REQ, D-server searches for its context associated with the user identifier for the items listed in the message. For each item found, it will check the CRC in the message against the one maintained locally. If the CRC check succeeds, it will include the item in DOWNLOAD_REP sent back to E-net. On the receiver side, E-net will store each item received in DOWNLOAD_REP. It also stops TO-4. To handle possible residual errors on the channel between E-net and D-server, E-net can optionally calculate the CRC for each data item received and check it against the corresponding CRC received from E-ms. Any item, of which the CRC check fails, will be discarded. N) E-net may come to this step in three possible scenarios: from step L without timeout, from step L after timeout, and from step M. Either case, it sends a state advertisement acknowledgement back to E-ms. The message contains the CRC corresponding to those selected as parts of the common dictionary (stored in STATE_ADV Liu, Le, Leung, and Clanton [Page 17] INTERNET-DRAFT SCRIBE 22 March 2001 during step K). E-net also starts a timer (TO-5) after sending STATE_ADV_ACK. If timeout occurs, E-net can repeat the message up to certain number of retransmissions. The timer will be stopped when it receives the state advertisement completion, called STATE_ADV_DONE (see step O). 0) Upon receiving STATE_ADV_ACK from E-net, E-ms will stop TO-3. It then searches for its context for the item whose CRC matches with the one carried in the message. If a match is found, that item will be used in place of the current contents of the dictionary and to compress messages in the new session. STATE_ADV_DONE is then sent to E-net to finish the three-way handshake. If no match is found, E-ms may go back to step K and repeat the whole procedure. Note that in the worst case, the static part of the dictionary can always be used to commit the procedure. After the procedure has finished, the result could be that E-net does not have the most preferred item by the E-ms. As an option (if E-ms wants and the bandwidth of the channel between E-ms and E-net allows), E-ms can resynchronize its compression context completely with E-net. Steps P, Q, and R in Figure 6 shows this procedure. It is basically a three-way handshake the same as described for the steps K, N, and O. The item carried in a state refresh, called STATE_REFRESH, is to identify which of the three items, namely checkpoint dictionary, profile-specific part of the dictionary, and static part of the dictionary, is being synchronized. Note that E- net can also initiate this state refresh procedure as well. For simplicity, it is not shown in Figure 6 since the procedure will be exactly the same. However, to avoid race condition, the initiating party has to make sure that there is no on-going state refresh taken place before it starts a new procedure. When this scheme is used in cellular systems, the downloading mechanism is a straightforward extension of the existing mechanisms to download profiles for cellular users. It is assumed that strong CRCs calculated over different parts of the dictionary having different values. In the extremely unlikely cases where this assumption is not true, an item identifier field should be inserted to STATE_ADV_ACK, STATE_ADV_DONE, STATE_REFRESH_ACK, and STATE_REFRESH_DONE, as shown in Figure 6, to avoid ambiguity. Liu, Le, Leung, and Clanton [Page 18] INTERNET-DRAFT SCRIBE 22 March 2001 | | | (K) | STATE_ADV | | TO-3 starts |----------------------->| | | | | | (L) | DOWNLOAD_REQ | | TO-4 starts |----------------------->| | | | | | DOWNLOAD_REP | (M) | TO-4 stops |<-----------------------| | | | | STATE_ADV_ACK | (N) | TO-3 stops |<-----------------------| TO-5 starts | | | | (O) | STATE_ADV_DONE | | |----------------------->| TO-5 stops | | | | | | | | | | (P) | STATE_REFRESH | | TO-6 starts |----------------------->| | | | | | STATE_REFRESH_ACK | (Q) | |<-----------------------| TO-7 starts | | | | (R) | STATE_REFRESH_DONE | | |----------------------->| TO-7 stops | | | | E-ms E-net D-server Figure 6. The Interaction Between State Verification and Downloading Procedure, and State Refresh Procedure. 3.5.2. Profile Specific Dictionary The profile-specific concept is based on the following observation. For protocols such as SIP, for a given user/device combination, it is common to have some fields always to be populated in a certain way, in particular, those fields dependent on the user and device/terminal capabilities. This kind of information can be inferred from a profile. Therefore, it makes sense to identify a profile-specific part of the dictionary that contains information Liu, Le, Leung, and Clanton [Page 19] INTERNET-DRAFT SCRIBE 22 March 2001 1) associated directly with the device (e.g. a cellular phone); and 2) associated with the user. An example of information specific to a device is the device's hardware capability; for example, a low-price device may have only the capability to send/receive audio and perform simple e-mail/SMS (non-real-time) functions. Capabilities specified in this case would include, not but limited to, voice codec type (e.g. AMR, EFR, G.721), mode (such as bit rate), and perhaps maximum bit rate supported for the non-real-time functions. High-end devices might be capable of these plus some more advanced services, such as audio/video streaming, video conferencing, or image capture capabilities in that case might include video codec type (e.g. MPEG4, H.263), codec bit rate, video codec picture size, image compression used (e.g JPEG), etc. The list can be quite long. Examples of user-specific information are the user URL, the user's name, e-mail address, and other identification data. Such data might be available in an identity module or removable "smartcard" device, enabling an user to access the same set of services from different devices by inserting an identity module. The profile-specific part can be derived from an user profile before a session starts. In the case of cellular communication, where one end for the message exchange is a mobile station endpoint, and the other is a network infrastructure endpoint, the profile is typically stored in the mobile station on a semi-permanent basis. The network infrastructure endpoint can download a profile, by using a relatively straightforward extension of the existing mechanisms to download profiles for cellular users (see Section 3.5.1.1). Downloading is necessary only when the mobile station moves to a new network endpoint. With the downloading, the profile specific dictionary can be used to compress/decompress the initial messages of a session, thus improving the compression ratio of the initial messages. Since the initial messages are the ones which are usually the largest (especially true in the case of SIP), a higher compression ratio for these messages will proportionately contribute more to the overall compression efficiency. Clearly, significant efficiency gains can be obtained by using a profile-specific dictionary. Liu, Le, Leung, and Clanton [Page 20] INTERNET-DRAFT SCRIBE 22 March 2001 3.5.3. Implicit Dictionary Content Deletion [ROGER] focuses on the procedures of adding messages to the dictionary. However, no procedures are provided for a compressor/decompressor to delete partial content of the dictionary. Although [ROGER] allows the compressor/decompressor to stop adding new content to the dictionary, it does not allow existing parts of the dictionary to be deleted. This lacks of capability of deleting dictionary content will lead to lower compression efficiency. For example, to achieve maximum compression efficiency, the compressor may want to delete part of the dictionary to make room for new content. This is especially important if the compressor/decompressor has limited memory to store the dictionary (as in the case of a mobile terminal), and/or the messages are large. With the implicit deletion, dictionary part(s) to be deleted are chosen according to a well defined algorithm that is known and applied in the same way at both endpoints. As input into the algorithm, one provides the total size to be deleted (e.g. number of bytes), and the algorithm specifies which part(s) are to be deleted. The freed room can then allow new content to be added to the dictionary. Since the same algorithm is applied at both endpoints, there is no need to explicitly signal which part(s) have been deleted. In particular, when the maximum memory size has been filled up, each endpoint, when it wants to add items of combined size S, will implicitly delete part(s) of combined size S. Since there is no need for signaling, the scheme is more efficient (lower signaling overhead) and more robust (less prone to errors or losses affecting the signaling information). It is assumed that the two endpoints agree on the maximum size of the dictionaries, either by a predefined constant or through memory usage negotiation before or at the beginning of a session. Memory size can also be renegotiated during a session. The scheme is simple. If the unused memory size is smaller than the size of the new message(s) and/or string(s) to be added, some part(s) of the current dictionary will be deleted to make room for the new message(s) and/or string(s). The deleted part(s) are chosen according to some algorithm that is known and applied in the same fashion at both endpoints. The size of the deleted part equals to the difference between the size of the added message and/or string(s), and the size of the unused memory. Thus, both endpoints perform the same operation on their dictionaries. Figure 7 illustrates the procedure for the case where the oldest part is chosen by the algorithm. Essentially, this is a sliding window dictionary mechanism following FIFO (First In First Out) policy. In Liu, Le, Leung, and Clanton [Page 21] INTERNET-DRAFT SCRIBE 22 March 2001 most cases, keeping the most recent content in the dictionary will improve compression efficiency. least | +---------------+ / +---------------+ recent | |Occupied Memory| | | | | | (part to be | | |Occupied Memory| | | deleted) | /--> | (kept during | | +---------------+ \ / | | addition) | | | | | / | | | | |Occupied Memory| | / \ +---------------+ \ | | (part to be | >- | | | | | kept) | | + - - - - - - - + | New message | | | | | Extra | > to be added | +---------------+ / | space | | most | | Unused Memory | | needed | | recent V +---------------+ +---------------+ / Dictionary before Dictionary after adding a new adding a new message message Figure 7. An Example For Implicit Dictionary Content Deletion. 4. Packet Formats 4.1. Normal Packet Formats Each normal packet is assigned with a sequence number by the sender. The sender maintains locally a two-byte counter for the purpose of the assignment. The counter is incremented by 1 after each assignment. In the packet header, only least significant bits (LSB) are carried. The W-LSB encoding, as described in Section 4.5.2 of [ROHC], is used here. To tolerate packet misordering, p value is set to 2^(k-2) - 1. The encoding rules determine which packet formats (see below) should be used by the sender. The convention of ROHC-09 packet formats will be used: Liu, Le, Leung, and Clanton [Page 22] INTERNET-DRAFT SCRIBE 22 March 2001 - colons ":" indicate that the part is optional - slashes "/" indicate variable length 4.1.1. Short Sequence Number +---+---+---+---+---+---+---+---+ | 0 | seq | A | C | N | +---+---+---+---+---+---+---+---+ | CRC | +---+---+---+---+---+---+---+---+ : : if A = 1 / ACK_info / variable length : : +---+---+---+---+---+---+---+---+ : : if C = 1 / CHKPT_info / variable length : : +---+---+---+---+---+---+---+---+ : : / compressed message / variable length : : (could be zero) +---+---+---+---+---+---+---+---+ seq - The 4 LSBs of the sequence number of this message. A - ACK bit, indicating the presence of ACK information element (ACK_info). if A = 1, ACK_info is present = 0, not present C - Checkpoint bit, indicating the presence of Dictionary Checkpoint information element (CHKPT_info). if C = 1, CHKPT_info is present = 0, not present N - Do-Not-Add bit. If N = 1, this message should not be added to the dictionary. CRC - calculated over concatenation of the packet and the original message (if this packet contains compressed message) Note: it is assumed that the total packet length is provided by the lower layer (be it UDP or TCP or link layer). Since the length of the header part is self-contained, the length of the compressed message Liu, Le, Leung, and Clanton [Page 23] INTERNET-DRAFT SCRIBE 22 March 2001 can be derived by subtracting the header length from the total packet length. The compressed message length could be zero (i.e. a stand alone packet for dictionary management only). 4.1.2. Long Sequence Number +---+---+---+---+---+---+---+---+ | 1 | 0 | seq | +---+---+---+---+---+---+---+---+ | seq | A | C | N | +---+---+---+---+---+---+---+---+ | CRC | +---+---+---+---+---+---+---+---+ : : if A = 1 / ACK_info / variable length : : +---+---+---+---+---+---+---+---+ : : if C = 1 / CHKPT_info / variable length : : +---+---+---+---+---+---+---+---+ : : / compressed message / variable length : : (could be zero) +---+---+---+---+---+---+---+---+ Same as the above format except the seq field is longer. 4.1.3. Acknowledgement The first 2 bits indicate the type of ACK_INFO. 1) Cumulative acknowledgement (ACCUM_ACK) +---+---+---+---+---+---+---+---+ | 0 | 0 | ack_seq | +---+---+---+---+---+---+---+---+ ack_seq - the 6 LSBs of the sequence number of the packet to be acknowledged. This format is used only if the receiver has received all the packets with sequence number equal and less than ack_seq. Liu, Le, Leung, and Clanton [Page 24] INTERNET-DRAFT SCRIBE 22 March 2001 2) ACK with short negative bit mask (ACK_SNBM) +---+---+---+---+---+---+---+---+ | 0 | 1 | ack_seq | +---+---+---+---+---+---+---+---+ | negative bit mask | +---+---+---+---+---+---+---+---+ ack_seq - same as above This format can be used when some packets with sequence number smaller than ack_seq have not been received. The bit mask indicates which packet is missing. First, the bit is indexed from the least significant bit (bit 0) to the most significant bit (bit 7). If the bit i is set to 1, the packet with sequence number of (ack_seq - i - 1) is missing. 3) ACK with long negative bit mask (ACK_LNBM) +---+---+---+---+---+---+---+---+ | 1 | 0 | ack_seq | +---+---+---+---+---+---+---+---+ | | + negative bit mask + 2 octets | | +---+---+---+---+---+---+---+---+ Same as above, except the bit mask is two-octet long, which can cover 16 missing packets instead of 8. As to the bit indexing, the bits in the least significant byte have lower index numbers than those in the most significant byte. Liu, Le, Leung, and Clanton [Page 25] INTERNET-DRAFT SCRIBE 22 March 2001 4) Negative list (NACK) +---+---+---+---+---+---+---+---+ | 1 | 1 | ack_seq | +---+---+---+---+---+---+---+---+ |E=0| missing_seq | +---+---+---+---+---+---+---+---+ :E=0| missing_seq : +---+---+---+---+---+---+---+---+ |E=1| missing_seq (last) | +---+---+---+---+---+---+---+---+ ack_seq - same as above. missing_seq - the 7 LSBs of the missing sequence number E - E bit. Indicating the end of the list. It MUST be set to 1 if and only if this is the last sequence number of the list. The missing list of sequence numbers has the similar function as the bit masks shown above. The shortest format that can convey the same information should be used. That depends on the packet missing pattern. 4.1.4. Checkpoint Each checkpoint dictionary is assigned with a five-bit version number, which gives a range from 0 to 31. In addition, version 0 is reserved to indicate the empty checkpoint dictionary. The version number of the new checkpoint dictionary is always the current version number plus one, except that Version 0 is skipped. Liu, Le, Leung, and Clanton [Page 26] INTERNET-DRAFT SCRIBE 22 March 2001 1) CHKPT_INIT +---+---+---+---+---+---+---+---+ | 0 | 0 | 0 | dict_ver | +---+---+---+---+---+---+---+---+ | Random Number | +---+---+---+---+---+---+---+---+ / ACK_info / +---+---+---+---+---+---+---+---+ | | + CRC + 2 octets | | +---+---+---+---+---+---+---+---+ dict_ver - the version number assigned to this checkpoint dictionary. CRC - calculated over the checkpoint dictionary. Liu, Le, Leung, and Clanton [Page 27] INTERNET-DRAFT SCRIBE 22 March 2001 2) CHKPT_ACK +---+---+---+---+---+---+---+---+ | 0 | 0 | 1 | dict_ver | +---+---+---+---+---+---+---+---+ dict_ver - copied from the CHKPT_INT information element 3) ROLL_INIT +---+---+---+---+---+---+---+---+ | 0 | 1 | 0 | dict_ver | +---+---+---+---+---+---+---+---+ | Random Number | +---+---+---+---+---+---+---+---+ | | + CRC + 2 octets | | +---+---+---+---+---+---+---+---+ dict_ver - the version number of the checkpoint dictionary that the sender wants to roll back to. CRC - calculated over the target checkpoint dictionary. 4) ROLL_ACK +---+---+---+---+---+---+---+---+ | 0 | 1 | 1 | dict_ver | +---+---+---+---+---+---+---+---+ dict_ver - copied from the ROLL_INT information element 5) ROLL_REJ +---+---+---+---+---+---+---+---+ | 1 | 0 | 0 | reserved | +---+---+---+---+---+---+---+---+ reserved - MUST be set to 0 (zero) Note: Bit patterns of the first 3 bits other than shown above are reserved. The receiver MUST discard a packet containing unknown bit patterns. Liu, Le, Leung, and Clanton [Page 28] INTERNET-DRAFT SCRIBE 22 March 2001 4.2. Special Dictionary Management Packet Formats Liu, Le, Leung, and Clanton [Page 29] INTERNET-DRAFT SCRIBE 22 March 2001 1) State Advertisement (STATE_ADV) +---+---+---+---+---+---+---+---+ | 1 | 1 | 0 | sub-type = 0 | +---+---+---+---+---+---+---+---+ | RES | P | dict_ver | +---+---+---+---+---+---+---+---+ | CRC-packet | +---+---+---+---+---+---+---+---+ : : + CRC-profile + if P = 1 : : (2 octets) +---+---+---+---+---+---+---+---+ : : + CRC-dynamic + if dict_ver != 0 : : (2 octets) +---+---+---+---+---+---+---+---+ P - when set to 1, indicates the sender has profile specific dictionary dict_ver - indicates the version number of the checkpoint dictionary. CRC-packet - calculated over the packet itself to detect transmission errors. CRC-profile - calculated over the profile specific dictionary CRC-dynamic - calculated over the checkpoint dictionary RES - reserved bit. MUST be set to 0 (zero). 2) State Advertisement Acknowledgement (STATE_ADV_ACK) +---+---+---+---+---+---+---+---+ | 1 | 1 | 0 | sub-type = 1 | +---+---+---+---+---+---+---+---+ | RES | P | dict_ver | +---+---+---+---+---+---+---+---+ | CRC-packet | +---+---+---+---+---+---+---+---+ RES - reserved bit. MUST be set to 0 (zero). P and dict_ver must be copied from the corresponding STATE_ADV packet. 3) State Advertisement Done (STATE_ADV_DONE) +---+---+---+---+---+---+---+---+ | 1 | 1 | 0 | sub-type = 2 | Liu, Le, Leung, and Clanton [Page 30] INTERNET-DRAFT SCRIBE 22 March 2001 +---+---+---+---+---+---+---+---+ | RES | P | dict_ver | +---+---+---+---+---+---+---+---+ | CRC-packet | +---+---+---+---+---+---+---+---+ RES - reserved bit. MUST be set to 0 (zero). P and dict_ver must be copied from the corresponding STATE_ADV_ACK packet. 4) State Refresh Request (STATE_REFRESH) +---+---+---+---+---+---+---+---+ | 1 | 1 | 0 | sub-type = 3 | +---+---+---+---+---+---+---+---+ | RES | P | dict_ver | +---+---+---+---+---+---+---+---+ | | + CRC + 2 octets | | +---+---+---+---+---+---+---+---+ : : / profile specific dictionary / if P = 1 : : (variable length) +---+---+---+---+---+---+---+---+ : : / dynamic dictionary / if dict_ver != 0 : : (variable length) +---+---+---+---+---+---+---+---+ RES - reserved bit. MUST be set to 0 (zero). CRC - calculated over the packet itself 5) STATE_REFRESH_ACK +---+---+---+---+---+---+---+---+ | 1 | 1 | 0 | sub-type = 4 | +---+---+---+---+---+---+---+---+ | RES | P | dict_ver | +---+---+---+---+---+---+---+---+ | CRC-packet | +---+---+---+---+---+---+---+---+ RES - reserved bit. MUST be set to 0 (zero). Liu, Le, Leung, and Clanton [Page 31] INTERNET-DRAFT SCRIBE 22 March 2001 P and dict_ver must be copied from the corresponding STATE_REFRESH packet. 6) STATE_REFRESH_DONE +---+---+---+---+---+---+---+---+ | 1 | 1 | 0 | sub-type = 5 | +---+---+---+---+---+---+---+---+ | RES | P | dict_ver | +---+---+---+---+---+---+---+---+ | CRC-packet | +---+---+---+---+---+---+---+---+ RES - reserved bit. MUST be set to 0 (zero). P and dict_ver must be copied from the corresponding STATE_REFRESH_ACK packet. 7) DOWNLOAD_REQ +---+---+---+---+---+---+---+---+ | 1 | 1 | 0 | sub-type = 6 | +---+---+---+---+---+---+---+---+ |RES| P | D | dict_ver | +---+---+---+---+---+---+---+---+ | CRC-packet | +---+---+---+---+---+---+---+---+ : : + CRC-profile + if P = 1 : : (2 octets) +---+---+---+---+---+---+---+---+ / user-ID / variable length +---+---+---+---+---+---+---+---+ P - when set to 1, indicates the sender wants to download the profile specific dictionary for the user D - when set to 1, indicates the sender wants to download the checkpoint dictionary with version specified by the dict_ver field user-ID - to identify the user, encoded according to section 4.5.6 in ROHC-09 RES - reserved bit. MUST be set to 0 (zero). Note: if D = 1 and dict_ver = 0, that means the sender wants to download the latest checkpoint regardless its version number. Liu, Le, Leung, and Clanton [Page 32] INTERNET-DRAFT SCRIBE 22 March 2001 8) DOWNLOAD_REP +---+---+---+---+---+---+---+---+ | 1 | 1 | 0 | sub-type = 7 | +---+---+---+---+---+---+---+---+ |RES| P | D | dict_ver | +---+---+---+---+---+---+---+---+ | | + CRC + 2 octets | | +---+---+---+---+---+---+---+---+ / user-ID / variable length +---+---+---+---+---+---+---+---+ : : / profile specific dictionary / if P = 1 : : (variable length) +---+---+---+---+---+---+---+---+ : : / dynamic dictionary / if D = 1 : : (variable length) +---+---+---+---+---+---+---+---+ RES - reserved bit. MUST be set to 0 (zero). CRC - calculated over the packet itself user-ID - must be copied from the corresponding DOWNLOAD_REQ packet. 5. Conclusions The draft defines a scheme that is generically applicable to dictionary-based compression algorithm when the transport between compressor and decompressor is unreliable. With the key concept of cross-section dictionary, the scheme achieves high compression efficiency even for the initial messages in a session. Good Liu, Le, Leung, and Clanton [Page 33] INTERNET-DRAFT SCRIBE 22 March 2001 compression of initial messages, when they are large (which is especially true for protocols like SIP), yields proportionately higher overall compression ratio. Other concepts and mechanisms, including the checkpoint, profile-specific dictionary, and sliding handshake provide additional robustness and efficiency. Delete mechanisms allow to accommodate limited memory devices, which makes it particularly suitable for mobile terminals. 6. Intellectual Property Right Considerations Nokia Inc. has filed patent applications that might possibly have technical relations to this contribution. 7. References [RFC2326] H. Schulzrinne, A. Rao, and R. Lanphier, "Real Time Streaming Protocol (RTSP)", RFC 2326, Network Working Group, Internet Engineering Task Force, April 1998. [RFC2327] M. Handley and V. Jacobson, "SDP: Session Description Protocol", RFC 2327, Network Working Group, Internet Engineering Task Force, March 1999. [RFC2616] R. Fielding, J. Gettys, J. Mogul, H. Frystyk, L. Masinter, P. Leach, and T. Berners-Lee, "Hypertext Transfer Protocol -- HTTP/1.1", RFC 2616, Network Working Group, Internet Engineering Task Force, June 1999. [ROHC] C. Burmeister, M. Degermark, H. Fukushima, H. Hannu, L.-E. Jonsson, R. Hakenberg, T. Koren, K. Le, Z. Liu, A. Martensson, A. Miyazaki, K. Svanbro, T. Wiebke, T. Yoshimura, and H. Zheng, "Robust Header Compression (ROHC): Framework and Four Profiles: RTP, UDP, ESP, and Uncompressed", draft-ietf-rohc-rtp-09.txt, Internet Draft, Network Working Group, Internet Engineering Task Force, 26 February 2001. [ROGER] H. Hannu, J. Christoffersson, and K. Svanbro, "Robust Generic Message Size Reduction (ROGER)", draft-hannu-rohc- roger-00.txt, Internet Draft, Network Networking Group, Liu, Le, Leung, and Clanton [Page 34] INTERNET-DRAFT SCRIBE 22 March 2001 Internet Engineering Task Force, 23 February 2001. [SIGNAL] H. Hannu, J. Christoffersson, and K. Svanbro, "Application Signaling Over Cellular Links", draft-hannu-rohc-signaling- cellular-01.txt, Internet Draft, Network Networking Group, Internet Engineering Task Force, 2 March 2001. [SIP] M. Handley, H. Schulzrinne, E. Schooler, and J. Rosenberg, "SIP: Session Initiation Protocol", draft-ietf-sip- rfc2543bis-02.txt, Internet Draft, Internet Engineering Task Force, 24 November 2000. Liu, Le, Leung, and Clanton [Page 35] INTERNET-DRAFT SCRIBE 22 March 2001 8. Authors' Addresses Zhigang Liu Nokia Research Center 6000 Connection Drive Irving, TX 75039 USA Phone: +1 972 894-5935 Fax: +1 972 894-4589 E-mail: zhigang.liu@nokia.com Khiem Le Nokia Research Center 6000 Connection Drive Irving, TX 75039 USA Phone: +1 972 894-4882 Fax: +1 972 894-4589 E-mail: khiem.le@nokia.com Ka-Cheong Leung Nokia Research Center 6000 Connection Drive Irving, TX 75039 USA Phone: +1 972 374-0630 Fax: +1 972 894-4589 E-mail: kacheong.leung@nokia.com Christopher Clanton Nokia Research Center 6000 Connection Drive Irving, TX 75039 USA Phone: +1 972 894-4886 Fax: +1 972 894-4589 E-mail: christopher.clanton@nokia.com Liu, Le, Leung, and Clanton [Page 36] INTERNET-DRAFT SCRIBE 22 March 2001 Liu, Le, Leung, and Clanton [Page 37]