Pulse or digital communications – Bandwidth reduction or expansion
Reexamination Certificate
2000-03-28
2004-08-24
Corrielus, Jean B. (Department: 2631)
Pulse or digital communications
Bandwidth reduction or expansion
C341S067000
Reexamination Certificate
active
06782047
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to high efficiency data compression including packet header compression.
2. Description of the Prior Art
There are many areas where it is critical to be able to compress a sequence of values, in an 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. 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 packet(s) 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 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 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-rip 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 2
k
. If 2
k
packets 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.
SUMMARY 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 show 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 that this number is sufficient to allow correct decompression whenever the loss occurs of previous compressed packets on the CD-link.
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 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 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. The value of k may be determined by comparing the current value
Le Khiem
Leon David
Liu Zhigang
Antonelli Terry Stout & Kraus LLP
Corrielus Jean B.
Nokia Networks Oy
LandOfFree
Variable length encoding of compressed data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Variable length encoding of compressed data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variable length encoding of compressed data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3349307