Note: Descriptions are shown in the official language in which they were submitted.
CA 02388006 2005-08-29
VARIABLE LENGTH ENCODING OF COMPRESSED DATA
TECHNICAL FIELD
The invention relates to high efficiency data compression including
packet header compression.
Description of the Prior Art
There are many areas where it is critical to be able to compress a
sequence of values, in a manner that is efficient and robust to errors. An
example is IP/UDP/RTP header compression to carry real-time IP-based
multi-media traffic over cellular networks.
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
Due to the large size of the IP/UDP/RTP header and the bandwidth limitations
of cellular
systems, compression efficiency is a must. Error robustness is also required
due to the
error-prone characteristics of the cellular link.
The RTP header compression described in Internet Engineering Task Force (IETF)
RFC 2508, February 1999, achieves high compression efficiency on a lossless
compressor-decompressor link. It can compress most of the headers to as low as
two
bytes. However, this scheme is not robust to errors. The problems encountered
are error
propagation and increased compressed header sizes. Error propagation refers
here to the
fact that if a compressed header is hit by an error, not only is this
compressed header not
decodable but the following compressed headers will likely not be decodable
even though
they are error free. Increased compressed header size refers here to the fact
that
because of the error recovery procedure, compressed headers on a lossy link
are larger
than the optimal 2 bytes achieved on a lossless link. Limitations of RFC 2508
are
hereinafter discussed.
Header compression schemes take advantage of the fact that certain information
fields carried in the headers either 1.) do not change (called here 'Type 1'
header fields)
or 2.) change in a fairly predictable way (called here 'Type 2' header
fields). Other fields,
referred to as 'Type 3' header fields, vary in such a way that they cannot be
truly predicted.
Examples of Type 1 header fields are the IP address, UDP port number, RTP SSRC
(synchronization source), etc. These fields need only be transmitted to the
receiver/decompressor once during the course of a session (as part of the
packets)
transferred at session establishment, for example).
Examples of Type 2 header fields are the RTP time stamp, RTP sequence number,
and IP ID fields. All have a tendency to increment by some constant amount
from packet to
packet. Thus, there is no need for these values to be transmitted within every
header. It is
2
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
only required that the decompressor be made aware of the constant increment
(differential)
value, called delta in RFC 2508. The decompressor utilizes these deltas to
regenerate up-
to-date Type 2 field values when reconstructing the original header. In other
words,
differential encoding is used to compress type 2 header fields.
The IP-ID field for most of IP stack implementations increments by a fixed
amount
for every packet sent by the source. Therefore as long as an RTP stream
packets are not
interleaved with other packets from the same source on the compressor-
decompressor
(CD)-channel, the IP-ID delta is constant and does not need to be transmitted.
An Example of a Type 3 header field is the RTP M-bit (Marker), which indicates
the
occurrence of some boundary in the media (e.g., end of a video frame). Because
the
media normally varies in unpredictable ways, this information cannot be truly
predicted.
The above mentioned limitations of header compression schemes stem from the
delta encoding used for type 2 fields. Because of differential encoding, if a
single
compressed header is lost, all the following compressed headers are not
decodable
because they are recursively predicted from a compressed header which is not
decodable.
This is what we called error propagation.
An algorithm used to recover from error propagation is known as the "twice"
algorithm which can be used if the packet UDP checksum is transmitted in the
compressed
packet. Compressed packets on the CD-link carry a 4-bit sequence number which
is
incremented by one for each compressed packet sent by the compressor. The
decompressor uses this sequence number to detect compressed packet loss on the
link. If
the sequence number increases by more than one, the decompressor hopes that
all the
compressed packet deltas have not changed since the last compressed packet
delta and
add one delta for each lost packet. The decompressor checks then that the
assumption
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
was valid by computing the decompressed packet UDP checksum and checking if it
matches the transmitted UDP checksum.
The twice algorithm is too limiting. First, it requires transmission of the
checksum (2
bytes) in every compressed packet and thus significantly reduces the
compression
efficiency. Second, for a typical audio stream, the twice algorithm works only
if there has
not been any TS or IP-ID jumps since the last decompressed packet.
When the decompressor is not able to decompress a packet, it sends an negative
acknowledgment Nack to the compressor. Upon reception of Nack, the compressor
has to
send uncompressed header fields. The Nack mechanism thus incurs audio or video
outages of a duration of at least one round-trip delay and decreased
compression
efficiency, since fields have to be sent uncompressed.
In order to limit error propagation, the compressor may use a refresh
mechanism
whereby it sends periodically uncompressed field values even though this is
not requested
by the decompressor. However such a mechanism further decreases compression
efficiency.
Another limitation of RFC 2508 is the compressed header short sequence number.
When the decompressor receives a header with a sequence number that is not
consecutive
from the previous one, packet loss is detected and a recovery scheme is
employed to
resynchronize the compressor and decompressor. Just using a short sequence
number to
detect packet loss is not robust to an error-prone link, such as wireless
where 'long loss'
may happen frequently. Long loss is defined as the loss of 'sequence cycle' or
more
packets in a row. When long loss occurs, the sequence number in the packet
received by
decompressor'wraps around'. For example, assume the sequence number consists
of k
bits, hence the sequence cycle equals to 2k. If 2k packets
4
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
are lost in a row, the decompressor fails to detect the packet losses since it
still sees a
consecutive sequence number in the incoming packets.
DISCLOSURE OF THE INVENTION
The invention is a robust and efficient encoding scheme which in one
embodiment
is referred to as VLE (variable length encoding). VLE and other embodiments of
the
invention solve the error propagation and efficiency drop of the prior art.
The invention is based in part on the observation, that header type 2 fields
received
at the compression point shows an increasing trend. This implies that fields
from
consecutive headers tend to have the same MSBs (most significant bits) and
differ only by
their LSBs (least significant bits). Compression can thus be achieved by
transmitting only
the LSBs.
The invention allows the compressor to determine the minimum number of LSBs to
be sent such as this number be sufficient to allow correct decompression
whatever the loss
of previous compressed packets on the CD-link.
1 S The invention can be applied to any series of values. The more clustered
(i.e. close
to each other) the values, the higher the efficiency.
A method of compressing a current value into a minimum or reduced number of
bits
for transmission from a compressor to a decompressor in accordance with the
invention
includes maintaining a series of at least one previous value at the
compressor, each
previous value having different k least significant bits and which have been
transmitted to
the decompressor; determining a value of k representing a smallest or reduced
number of
bits which allows successful decompression of the current value at the
decompressor using
as a reference value any value in the series of previous values; and
transmitting the current
value from the compressor to the decompressor in compressed form with the k
least
5
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
significant bits of the current value. The value of k may be determined by
comparing the
current value with the previous values to determine a maximum difference r
between the
current value and the previous values with k being an integer chosen to be the
smallest
integer which is greater than log2<<~+1. The decompressor may transmit at
least one
acknowledgment to the compressor which indicates that the decompressor has
decompressed a value and the compressor may update the series of at least one
previous
value to discard an older at least one previous value. The decompressor may
decompress
the current value with a reference value of a last value of the series of at
least one previous
value to be decompressed as a value having k least significant bits identical
to the k least
significant bits of the received current value which is closest to the
reference value. The
decompressor may use a search interval which contains values which range from
less than
to greater than the reference value; and may choose from the values within the
search
interval the value having the identical k least significant bits. The values
may be produced
from mapping a reference value v_ref and the number of bits k to the series of
at least one
previous value and the current value; and the series of at least one previous
value may be
updated to have as an oldest value an oldest transmitted value which has been
acknowledged to have been decompressed by the decompressor. The values may be
a
function of a reference value and the number of bits k. The function may be
]v_ref-2k-',
v_ref+2k-']. The function may be ]v_ref, v ref+2k]. The at least one
acknowledgment may
be the received uncompressed or compressed value. The at least one
acknowledgment
may be the received compressed value including information used in coding a
portion of the
compressed value. The at least one acknowledgment may contain an oldest value
in the
series of the at least one previous value. The series of at least one previous
value may be
updated to discard older previous values based upon an estimated maximum
number of
values which can be lost during transmission in a sequence of values between
the
6
CA 02388006 2002-04-12
WO 01/35534 PCT/CTS00/41773
compressor and the decompressor. The compressed current value may encode the
number k which is transmitted with the current value. The encoding may be
Huffman
encoding. The values may comprise RTP headers. The at least one acknowledgment
may
be an acknowledgment of an RTP SN header representing an acknowledgment of TS
and
IP-ID in the RTP header.
A system for compressing a current value into a minimum or reduced
number of bits in accordance with the invention includes a compressor which
maintains a
series of at least one previous value, each previous value having different k
least significant
bits; a decompressor which receives the current value compressed into a
minimum or
reduced number of k least significant bits from the compressor; and wherein
the
compressor determines a value of k representing a smallest number of bits
which allows
successful decompression of the current value at the decompressor using as a
reference
any value in the series of at least one previous value. The value of k may be
determined by
comparing the current value with the at least one previous value to determine
a maximum
difference r between the current value and the at least one previous value
with k being an
integer chosen to be the smallest integer which is greater than Iog2<<~+1. The
decompressor
may transmit at least one acknowledgment to the compressor which indicates
that the
decompressor has decompressed a value and the compressor may update the series
of at
least one previous value to discard an older at least one previous value. The
decompressor may decompress the current value at the decompressor with a
reference
value of a last value of the series of at least one previous value to be
decompressed as a
value having k least significant bits identical to the k least significant
bits of the received
current value which is closest to the reference value. The decompressor may
use a search
interval which contains values which range from less than to greater than the
reference
value; and may choose from the values within the search interval the value
having the
7
CA 02388006 2005-08-29
identical k least significant bits. The compressor may produce the values from
mapping a reference value v ref and the number of bits k to the series of at
least one previous value and the current value; and the series of at least one
previous value may be updated to have as an oldest value an oldest
transmitted value which has been acknowledged to have been decompressed
by the decompressor. The function is ]v_ref-2k-~, v_ref+2k-~]. The function
may
be ]v_ref, v_ref+2k]. The acknowledgments may be the received
uncompressed value. The at least one acknowledgment may be the received
compressed value. The at least one acknowledgment may be the received
compressed value including information used in coding a portion of the
compressed value. The series of at least one previous value may be updated
by the compressor to discard at least one older previous value based upon an
estimated maximum number of values which can be lost during transmission
in a sequence of values between the compressor and the decompressor. The
compressed current value may encode the number k which is transmitted with
the current value. The values may comprise RTP headers. The at least one
acknowledgment may be an acknowledgment of an RTP SN header
representing an acknowledgment of TS and IP-ID in the RTP header.
In accordance with another aspect of the present invention, there is
provided a method of compressing a current value into a reduced number of
bits for transmission from a compressor to a decompressor comprising:
maintaining a series of at least one previous value at the compressor,
each previous value having different k least significant bits and which have
been transmitted to the decompressor;
determining a value of k by comparing the current value with the at
least one previous value to determine a maximum difference r between the
current value and the at least one previous value, wherein the value of k
represents a reduced number of bits which allows successful decompression
of the current value at the decompressor using as a reference value any value
in the series of previous values; and
transmitting the current value from the compressor to the
decompressor in compressed form with the k least significant bits of the
current value.
8
CA 02388006 2003-O1-09
BRIEF DESCRIPTION OF THE DRAWINGS
Fig. 1 conceptually illustrates compression of information.
Fig. 2 conceptually illustrates decompression of information.
Fig. 3 illustrates the transition of a compressor from transmitting
headers having a higher number of bits to headers having a lower number of
bits using acknowledgments in accordance with the present invention.
8a
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
Fig. 4 illustrates the transition of a compressor from transmitting headers
with a first
order of compression to headers with a second order of compression in
accordance with
the present invention.
Figs. 5 and 6 illustrate examples of the selection of the minimum number of
bits k in
accordance with the invention.
Figs. 7A and 7B illustrate the use of a sliding window of values stored by the
compressor in accordance with the invention.
Fig. 8 illustrates an example of VLE encoding format using two encoding fields
for
transmitting the compressed value in accordance with the present invention.
BEST MODE FOR CARRYING OUT THE INVENTION
Basic Concepts and Rules
Fig. 1 illustrates conceptually compression information and examples thereof.
Compression context information is a set, subset or representative of a subset
of
information which may be without limitation any type of information including
a header used
by a compressor as illustrated in Figs. 3 and 4 as an input to the compression
algorithm to
produce compressed information which may be without limitation a compressed
header.
The other input is from the source of the information to be compressed which
is illustrated
without limitation in the example as headers to be compressed.
Fig. 2 illustrates conceptually decompression of information and examples
thereof.
Decompression context information is a set, subset or representation of a
subset of
information which may be without limitation of any type of information
including a header
used by a decompression as illustrated in Figs. 3 and 4 as an input to the
decompression
algorithm to produce decompressed information which may be without limitation
a
decompressed header. The other input is from the information to be
decompressed which
9
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
is illustrated without limitation in the example as headers to be
decompressed.
Both the compression and decompression context informations are dynamic, that
is,
they may be updated by the compressor and decompressor respectively. The
frequency of
updates depends on the header compression mechanism. Events that may result in
an
update of the compression context information at the compressor include the
compression
of an incoming header, or the receipt of feedback from the decompressor.
Events that may
result in an update of the decompression context information at the
decompressor include
the decompression of an incoming header.
The Compressor can be in one of 3 states:
~ FH (Full Header) state
~ FO (First Order) state
~ SO (Second Order) state
The compressor operates in the FH state in the initialization phase. In the FH
state,
the compressor sends a full RTP header. This state is normally just a
transient state which
only happens at the beginning of an RTP session or in the middle of a session
due to very
exceptional events, e.g., the compressor fails or loses memory.
The compressor operates in the FO state in the update phase. In the FO state,
the
transmitter sends a FO header, i.e. a packet whose header carries the fields
that have
changed compared to the reference header, appropriately encoded, along with
the
sequence number. The decompressor is expected to acknowledge as illustrated in
Figs. 3
and 4 a certain number of FOs, where the number depends on the pattern. For
example, if
the pattern is linear with constant parameters, only one acknowledgment is
needed to
transition to the extrapolation phase.
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
The compressor operates in the SO state in the extrapolation phase. In this
state,
the transmitter sends a SO packet, i.e. a packet whose header is essentially
just a
sequence number. The decompressor may or may not acknowledge a correctly
received
SO packet.
A type of mathematical function, which may be used with the invention but to
which
the invention is not limited, used in VLE is described as follows. Such a
function, denoted
as f(k,v_ref)=(v_1, v 2,....,v_2k), maps to an integer value v ref called
reference value and
a number of bits k to a k-tuple of integers which all have different k LSBs.
Although any such function could be appropriate, one preferred embodiment uses
only functions which return consecutive values v_1, v_2,....,v_2'', i.e. v_i =
v_1 + i-1. In
other words, the function has an interval of length 2k values. The interval
can be written as
]v_ref-C(k, v_ref), v_ref-C(k, v_ref)+2k] where C is an integer value which is
function of
k and v_ref. Here again, although any such interval could be of interest, one
preferred embodiment uses C(k, v_ref)=0 and C(k,v_ref)=2k-'. In other words,
the
embodiment uses the intervals ]v_ref-2k-', v_ref+2k-'] and ]v_ref, v_ref+2k].
A VLE embodiment based on the ]v_ref-2k~', v_ref+2k-'] interval is described
as
follows. The system is composed of a compressor, a decompressor and a CD-
channel as
illustrated in Fig. 3 and 4, i.e. the link between the compressor and the
decompressor. The
channel may be error-prone. The only assumptions made with this embodiment,
which are
not limiting, are that compressed values are not reordered by the channel and
the
compressed values which are given as inputs to the decompressor are not
corrupted (or in
other words corrupted headers are treated as lost headers). The channel may be
a simplex
link, i.e. carries only compressed values from the decompressor or duplex,
i.e. the channel
carries also feedback from the decompressor to the compressor as illustrated
in Figs. 3
and 4. In the preferred embodiment a duplex channel is used.
11
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
The first phase is the acquisition by the decompressor of an initial value.
This may
be performed by the compressor sending uncompressed values at the start of the
communication or any other suitable means. The decompressor may use a feedback
channel to acknowledge the received value as illustrated in Figs. 3 and 4. The
initialization is completed without limitation when the compressor has
received one
feedback acknowledgment and VLE encoding can then be used for compression. In
VLE,
values are compressed as a variable number of bits k. The operation of the
decompressor
in the VLE mode is first discussed.
Figs. 7A and 7B illustrate a window update process. The window is comprised of
previous values which are inputted to the compressor and may be compressed but
are not
required to be compressed. It is assumed that the window is v;, v;+,, , v~ at
a contain
point of time:
(1 ) When a new value V~+, is compressed, the window is enlarged in order to
include this new value as illustrated in Fig. 7A.
(2) The window is then reduced, as illustrated in Fig. 7B, by removing older
values)
(in that example, v; and v;+,) when the compressor knows that these values
cannot be used
by the decompressor anymore which, in this example, could be when the
reception of an
acknowledgment for the value v;+2 occurs.
Decompression:
The reference value is the last value decompressed by the decompressor. The
compressor may be signalled of decompression by the reception of an
acknowledgment as
illustrated in Figs. 3 and 4 or on the assumption that an actual value has
been received in
view of the transmission of a series of values over sufficient time duration
that at least one
value is statistically likely to be received and decompressed without use of
any feedback
from the decompressor. The decompressor decompresses an incoming compressed
value
by providing the only value in the interval ]v_ref-2k-', v ref+2k-'] whose k
LSBs are a match
12
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
of the k bits received. This search interval is a special instance of the
functions introduced
earlier. The decompressed value becomes the v-ref which will be in turn used
to
decompress the next incoming compressed value. In the preferred embodiment,
the
decompressor acknowledges at least some of the packets which have been
decompressed
such as illustrated in Figs. 3 and 4. The number of packets which have to be
acknowledged is totally flexible and is chosen to meet the specifications of
the desired
application. The more acknowledgments which are transmitted from the
decompressor to
the compressor, the higher the compression efficiency on the forward link as
will be shown
hereafter.
Compression:
Reference is now made to the compressor operations. The compressor maintains a
sliding window of values it has compressed and transmitted to the decompressor
which are
illustrated in Figs. 7A and 7B. In the one embodiment, the window holds the
latest value for
which it has received an acknowledgment from the decompressor and all the
following
transmitted values in the order they were transmitted to the decompressor. The
compressor also maintains the minimum and maximum values v-min and the v_max
respectively of the sliding window.
When a new uncompressed value v reaches the compressor, the compressor sends
k LSBs of v such that v be in the interval ]v-i-2k-', v_i+2k-'] for every v_i
of the sliding
window. This can be conveniently expressed by r<2k-1 where r = max(w - v_max~,
w - v mini). The compressor thus chooses k to be the smallest integer which is
more than
log2(r)+1. When the compressor receives an acknowledgment, it removes from its
window
all the values which have been sent prior the acknowledged value as discussed
above with
reference to Fig. 7B.
13
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
The following discussion demonstrates why VLE always provides correct
decompression and is a very flexible compression mechanism.
As long as the compressor and decompressor follow the above-described rules,
correct decompression occurs whatever the losses are on the CD-channel between
the
compressor and decompressor as illustrated in Figs. 3 and 4. In effect, the
reference value
v_ref used by the decompressor necessarily belongs to the compressor window,
as
illustrated for example in Figs. 5 and 6 between points v_min and v_max, and
therefore the
encoded value is known to be in the interval ]v_ref-2k-', v_ref+2k-'] which is
the search
interval used by the decompressor.
There is no error propagation with VLE. A compressed packet received by the
decompressor can always be decompressed. Packet losses translate into a
gradual
increase in the compressed packet size.
The more frequent the acknowledgments, the less values in the window and
therefore the less LSBs are likely to be sent. This holds especially in the
case of header
compression where the values to be compressed follow an increasing trend and
where
v-v min increases for each new value v until an acknowledgment is received.
The length of the compressed value must be known to the decompressor. In some
cases this length can be known without any additional signaling, for example
through the
framing information from lower layers of coding. If explicit signaling is
needed the
preferred embodiment defines a VLE format. The format may have two fields: the
length
field (i.e. k the number of LSB) and the compressed value field (i.e, k LSB of
the original
value v) as illustrated in Fig. 8.
In a preferred embodiment, the VLE length field, as illustrated in Fig. 8, is
itself
encoded using Huffman coding. Any other encoding methods (e.g. linear
encoding) may
be used. For different applications the likelihood of different lengths should
be accessed
14
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
and then a Huffman coding algorithm should be used to encode these data where
desirable. The likelihood of encountering a given length on a communication
link between
the compressor and decompressor can be assessed knowing the link properties
(loss and
delay) and the decompressor acknowledgment period, as well as the patterns of
the
original values to be compressed.
To further reduce the length of the length field itself, the compressor may be
constrained to choose the length of the field from a reduced set of values.
For instance,
assuming the uncompressed field is 32 bits and it is desired to encode with a
maximum 2-
bit length the following lengths which are in a decreasing order of likelihood
4 bits, 8 bits
and 32 bits, appropriate code words could be the single bit 0 for 4 bits, the
2-bit value 1 0
for 8 bits and the 2-bit value 1 1 for 32 bits.
Using appropriate coding minimizes the average size of the compressed values.
Furthermore, the length information may not require dedicated bits if the
length can
be derived from other packet fields. For example, in a typical header
compression
application a packet type field is transmitted in the compressed header. This
packet type
field can be used to imply a default length which is rarely exceeded. In the
case, where the
default length is exceeded, a separate packet type is used. Since this happens
only rarely
the overhead is overall decreased.
If there is no feedback channel, other (out-of-band) information or additional
assumptions are required to move the compressor window forward and keep the k
from
increasing forever. One way is to assume that at most L consecutive compressed
values
can be lost along the channel from the compressor to the decompressor. In
other words,
the compressor knows for sure that at least one out of (L + 1 ) consecutive
compressed
values arrives at the decompressor. Therefore, the compressor only needs to
store in the
window the last (L + 1 ) values that have been sent to the decompressor.
Therefore, the
range (v-max - v_min), and thus the value of k, depends only on the last (L +
1 ) values
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
sent.
VLE can be applied to RTP header compression. Conversely to RFC 2508, there is
no need to use a compressor- decompressor sequence number. Instead, the RTP
sequence number is encoded using VLE. The decompressor acknowledges packets
such
as illustrated in Figs. 3 and 4 as described in the VLE application by sending
to the
compressor the RTP SN it has received.
As discussed below regarding optimal acknowledgments, the decompressor does
not have to return the uncompressed RTP SN value.
The following example illustrates the working of the present invention for RTP
SN
compression as set forth in RFC 2508. A series of incoming packets are
provided to the
compressor whose SN (sequence number) are: 32, 33, 35, 36, 39, 40, 38, 41.
Assuming
that the decompressor has acknowledged the packet whose sequence number is 35,
the
compressor keeps a window of sequence numbers as discussed above transmitted
since
the last acknowledged packet. When the acknowledgment is received, the
compressor
window is thus: 35, 36, 39, 40, 38, 41. Now it is assumed that a new SN value
is coming to
the compressor having a SN value of 43. The compressor looks for its window
maximum
and finds 41. The compressor looks for is window minimum and finds 35. The
compressor computes the distance r of the incoming value to its upper (43-41 =
2) and
lower (43-35 = 8) bounds. The maximum distance is 8. The compressor has to
transmit a
number of bits k such that the integer is more than Iog2~+1 with 2k being
greater than 17 in
this example. This number is k=5. Since 43 is written in binary format as
101011, the
compressor sends the 5 LSB, i.e. 01011. The decompressor reference value is
the last
value decompressed by the decompressor and it is for sure one of the values in
the
compressor window. The decompressor decompresses the incoming value (01011 )
by
returning the value whose 5 LSBs are 01011 and which is the closest to the
reference
value. Whatever the reference value, this value will always be 43. For
example, if it is
16
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
assumed that the last value received by the decompressor is 40 when it
receives the
compressed value (i.e. 38 and 41 were lost on the link between the compressor
and the
decompressor), the search interval used by the decompressor is [25, 56J or in
binary format
[011001, 111000]. The only value in the interval whose last LSBs are 01011 is
101011, i.e.
43.
Another way for the decompressor to pick the value of k is to choose the
closest
value to 40 whose LSBs are 01011. The number 40 is 101000 in binary format.
The
closest value to 101000 whose last LSBs are 01011 is 01011, i.e. 43. This
illustrates that
whatever the losses on the compressor-decompressor link, the VLE allows
determination of
the minimum or reduced number of LSB bits to be sent which will provide
correct
decompression.
Figs. 5 and 6 illustrate the picking of k such that the current value to be
VLE
encoded is among the values having the same LSB and is closest to either a
maximum or a
minimum in the window. Fig. 5 illustrates the case where v is greater than
v_max and Fig.
6 illustrates the case where V is less than v_min.
In the packets where the RTP time stamp or the IP-ID field is sent, these
fields are
encoded using the same window of transmitted packets as used for SN encoding.
Therefore, the decompressor does not send back these fields on the
reverse/feedback
channel in order to acknowledge them. The window can also be seen as a window
of
vectors (SN, TS, IP-ID). A given vector can be acknowledged by returning only
the SN
field.
One embodiment performs header compression based on an acknowledgment
framework to transmit SN, TS and IP-ID when these fields have to be
transmitted. Other
encodings can be used for TS and IP-ID. This header compression scheme is
summarized
below.
17
CA 02388006 2005-08-29
WO 01/35534 PGT/US00/41773
Transition to FO and SO States Using Acknowledgments
When a new session starts, the compressor operates in FH state until receiving
an
acknowledgment (ACK) from the decompressor, indicating that at least one FH
packet has
been received. It is the responsibility of the decompressor to acknowledge an
FH packet as
soon as it receives it, so that the compressor can transit from FH state to FO
state.
Acknowledgments may contain either the compressed current value which is
decompressed by the decompressor or the uncompressed current value. Either
quantity
permits the compressor to update the state of compression and initiate
discarding of the old
values.
In the FO state, the compressor transmits FO packets and the decompressor is
supposed to acknowledge received FO packets (not necessarily every FO packet).
If the
compressor determines (based on the ACKs) that the decompressor has
established an
FOD, and that FOD is same as the FOD between the current header being
transmitted and
the last transmitted header, the compressor then advances to SO state and
starts sending
SO packets.
Due to the reasons discussed above, the compressor may have to fallback from
SO state to FO state. However, the compressor never transits back to FH state
unless
some exceptional events happen, such as decompressor loses its contexts
because of
system crash. Whenever the compressor is in FO state, it tries to advance to
SO state as
described above.
Two variations of VLE, referred to Fixed Length Encoding (FLE) and One Sided
Variable Length Encoding (OVLE) are described below.
18
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
Fixed Length Encoding (FLE)
Fixed length encoding may be used, if it is known for sure that, the range
r = (v_max - v_min) never exceeds an upper-bound. Every value is encoded with
the same
number of bits which is the smallest number of bits needed to cover this
range. The length
does not need to be transmitted in that case since it is assumed to be a known
constant.
One Sided Variable Length Encoding (OVLE)
The previously described VLE is based on a function which maps to a reference
value v ref and a number of bits k which returns the search interval ]v_ref-2k-
', v_ref+2k-'].
This is very general and flexible, as it can accommodate arbitrary changes
(positive,
negative) from one value to the next. However, this interval is not the most
efficient when
used for a field which is monotonic. In effect, the decompressor picks up a
decompressed
value only in the subset ]v_ref, v_ref+2k-'].
In the case of RTP header compression, the fields usually arrive to the
compressor
in increasing order. However, there are exceptions because of possible
misordering
upstream from the compressor or in the case of the timestamp, an encoder might
not
deliver the coded frames in the order they were sampled. In order to improve
efficiency, it
may be worth using a function which would return a search interval which is
not centered on
v ref, for instance the interval ]v_ref-2k-2, v_ref+3*2k~2].
When VLE is used as part of an adaptive header compression application, it is
possible to use the interval ]v_ref, v ref+2k] which is the most efficient for
a given k. This is
referred to as one sided variable length encoding (OVLE). VLE is used for FO
packets and
OVLE for SO packets as long as the compressor incoming values are increasing.
In the
case that a misordering of packets occurs before the compressor, the
compressor
19
CA 02388006 2002-04-12
WO 01/35534 PCT/LTS00/41773
always compresses the packet as an FO packet. Alternatively, the compressor
could
reorder and/or drop packets in order to stay in the SO state even if
misordering occurs.
An Optimal Acknowledgment Algorithm for the Variable Length
Encoding (VLE) and One-sided VLE (OVLE) of Compressed Data
To improve the overall compression efficiency, it is desirable to keep the
size of the
acknowledgment sent by the decompressor to the compressor to a minimum. In the
algorithm discussed herein, the decompressor only needs to send in an
acknowledgment
the same number of bits (or at most 2 more bits, as described later) as it has
received in
the compressed message.
As described in VLE and OVLE, the compressor maintains a sliding window of
values VSW and stores each of the original uncompressed values in VSW after
transmission to the decompressor.
VSW: y, v2, vz. ... y;.. ...v~ Note: y, is the oldest value, and V~ the
vounaest)
Case 1: Single Encoding Method
It is assumed that only one encoding method is used (either VLE or OVLE) and
both
the compressor and the decompressor know which one is being used. When the
decompressor successfully receives a compressed value and decides to
acknowledge it, it
simply copies the received compressed value into the acknowledgment and
transmits it
back to the compressor.
When the compressor receives an acknowledgment message, it processes the
acknowledgment in the following three steps:
1 ) Uses v, (the oldest value) in VSW as the reference value and decompresses
the
compressed value in the acknowledgment following the same rules as the
decompressor.
The decompressed value is identified as v acked.
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
2) Searches the VSW from head (oldest) to tail (youngest), for the first
(oldest)
occurrence of v acked.
3) Deletes all the values preceding (older than) v_acked.
It can be shown that the above algorithm works by observing the following
property
of the VSW:
~ If v; in HSW was sent by the compressor using k bits, it can be correctly
decompressed using the same k bits and using any v;(j__<i) as the reference
value.
Specifically, v, can be used as the reference value to decompress any value in
the
VSW. Combined with the fact that an acknowledgment always acknowledges one of
the
values in the VSW, it is concluded that v_acked derived in step 1 ) is indeed
the correct
original value that triggered the acknowledgment message.
Case 2: Multiple Encoding Methods
In this case, the decompressor dynamically switches encoding methods between
VLE and OVLE. It is only needed to change the aforementioned algorithm
slightly to
handle this case. Basically, in each acknowledgment message, the decompressor
must
add a flag to indicate which encoding method was used to compress the received
value.
Therefore, when the compressor receives an acknowledgment message, it can
choose the
correct decompression method based on the encoding flag in the acknowledgment.
As
long as the property of the VSW holds, the modified algorithm is correct,
based on the
same reasoning as in the previous section.
Also when VLE and/or OVLE are applied to header compression, the encoding flag
need not be carried explicitly in the compressed headers sent from the
compressor to the
decompressor, since decompressor can derive that information implicitly based
on header
type and other configuration information. However, on the reverse direction,
the flag has to
be carried explicitly in the acknowledgment message. In the worst case, 2 bits
are needed
21
CA 02388006 2002-04-12
WO 01/35534 PCT/US00/41773
to differentiate three possibilities: VLE, plus-sided OVLE, minus-side OVLE.
The encoding
flag could be reduced to one bit if the side information of OVLE is
predefined.
Duplicated values in VSW
There is one special case that has not been discussed above. It is possible
that the
same (original uncompressed) value may occur more than once in the compressor
sliding
window. This needs to be considered for the following two reasons: 1 ) in
theory, the
algorithm should be generic and work for any sequence of values; 2) in
practice, RTP
Timestamps for some video codes do have this behavior.
The problem is that, although the calculated value v_acked is still correct,
the
compressor cannot determine which occurrence (if it found multiple
occurrences) of the
v acked in VSW actually triggered the ACK.
However, it should be noted that the algorithm works, since the compressor
always
chooses the first (oldest) occurrence of v_acked in VSW. If it is not the
correct instance
that triggered the acknowledgment, the only side effect is that less values
were deleted
from the VSW than should have been. As a result, the new values arriving
thereafter may
be encoded using more bits than necessary.
If a duplication of values seldom occurs, no modification to the
aforementioned
algorithm is necessary, since the compressor is brought out of its less-than-
optimal state as
soon as another (unambiguous) acknowledgment arrives which acknowledges a
value that
occurs only once in the VSW.
If duplicated values are expected to happen frequently, extra information may
be
added to remove the ambiguity of an acknowledgment. One example is to assign a
generation number (GN) to each compressed value and require the decompressor
to put
the GN in the acknowledgment.
While the invention has been described with reference to its preferred
22
CA 02388006 2002-04-12
WO 01/35534 PCT/LTS00/41773
embodiments, it should be understood that numerous modifications may be made
thereto
without departing from the spirit and scope thereof. It is intended that all
such modifications
fall within the scope of the appended claims.
23
