Method and apparatus for data compression of network packets

• US 6,388,584 B1
• Filed: 03/16/2000
• Issued: 05/14/2002
• Est. Priority Date: 03/16/2000
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Dorward, Sean Matthew, Quinlan, Sean
• Primary Examiner(s): PHAN, TRONG Q
• Application Number:
  US09/527,315
• Time in Patent Office: 789 Days
• Field of Search: 341/51, 341/60, 341/65
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

A method and apparatus for compressing packets that enables inter-packet compression thereby achieving greater robustness and increased compression ratios without the deleterious effects, e.g., the effect of packet loss multiplying, of prior compression schemes. More particularly, a so-called acknowledgment scheme is employed in conjunction with the specific compression algorithm such that the transmitter, i.e., sender, can limit the history used by the compression algorithm to those packets that are correctly received. In particular, a vector identifying the packets used as the history is included in the compressed packet thereby enabling the receiver to reconstruct the packet history state necessary to decompress the packet. Advantageously, increased robustness and greater compression ratios are achieved independent of any particular one compression scheme.

Claims

1. A data communications method comprising:

dividing the input stream of data into a plurality of packets;

identifying a respective packet history state for particular ones of the packets as a function of at least one acknowledgement vector;

encoding the particular ones of the plurality of packets as a function of the respective packet history associated therewith; and

compressing the plurality of packets into a compressed data stream.

2. The method of claim 1 wherein the respective packet history state associated with the packet is identified as a function of a plurality of received packets.

3. The method of claim 2 wherein the plurality of received packets represent packets which have been previously received by a receiver without a transmission error.

4. The method of claim 2 wherein each packet has a respective packet header, the packet header including at least a history vector which identifies the respective packet history state of the packet.

5. The method of claim 3 wherein the acknowledgement vector is generated by the receiver.

6. The method of claim 3 wherein the acknowledgement vector includes a sequence number of the particular received packet which was last received.

7. The method of claim 4 wherein the packet header includes a sequence number identifying a particular received packet.

8. A method of transmitting a communications stream between a sending location and a receiving location across a communications channel, the method comprising:

dividing the communications stream into a plurality of packets;

identifying a respective packet history state for particular ones of the packets as a function of a first acknowledgement vector, the first acknowledgement vector being received by the sending location from the receiving location;

encoding the particular ones of the packets as a function of the respective packet history associated therewith, each such packet having a packet header associated therewith, the packet header including at least a history vector which identifies the respective packet history state of the packet;

compressing the plurality of packets into a compressed data stream; and

transmitting, across the communications channel, the compressed data stream from the sending location to the receiving location.

9. The method of claim 8 wherein the respective packet history state associated with the packet is identified as a function of a plurality of received packets at the receiver location.

10. The method of claim 9 wherein the first acknowledgement vector includes a sequence number of a particular received packet which was last received by the receiving location.

11. The method of claim 9 wherein Lempel-Ziv coding is employed in the compressing the packets.

12. The method of claim 8 further comprising:

receiving the compressed data stream at the receiving location,

extracting the respective history state associated with the particular ones of the packets; and

decompressing the compressed data stream to recover the plurality of packets, the particular ones of the encoded packets being decompressed as a function of the extracted packet history associated therewith.

13. The method of claim 12 further comprising:

updating a received packet state as a function of the decompressed packets.

14. The method of claim 13 further comprising:

constructing a second acknowledgment vector, the second acknowledgement vector confirming a receipt of the decompressed packets by the receiving location; and

transmitting the second acknowledgement vector from the receiver location to the sending location.

15. A method of recovering data from a compressed data stream, the method comprising:

receiving the compressed data stream, the compressed data stream including a plurality of encoded packets;

identifying a respective history state associated with particular ones of the encoded packets; and

decompressing the compressed data stream to recover the data;

the particular ones of the encoded packets being decompressed as a function of the respective packet history associated therewith.

16. The method of claim 15 further comprising:

updating a received packet state as a function of the packets being decompressed.

17. The method of claim 16 further comprising:

constructing an acknowledgment vector; and

transmitting the acknowledgement vector from a receiver to a transmitter, the receiver and the transmitter exchanging the compressed data stream across at least one communications channel.

18. A data communications apparatus comprising:

a receiver for receiving a data stream for transmission by the apparatus, the data stream comprising a plurality of packets;

a encoder for identifying a plurality of packet history states as a function of at least one acknowledgement vector, each packet history state being associated with a respective one of the packets, and for encoding the plurality packets as a function of the plurality of history states; and

a compressor for compressing the packets into a compressed data stream.

19. The data communications apparatus of claim 18 further comprising:

a transmitter for transmitting the compressed data stream across a communication channel.

20. The data communications apparatus of claim 19 wherein the communications channel is part of an Internet.

21. The data communications apparatus of claim 18 further comprising:

a decompressor for receiving an input data stream, the input data stream including a plurality of compressed packets, identifying a respective history state associated with particular ones of the compresses packets and decompressing the plurality of compressed packets, the particular ones of the compressed packets being decompressed as a function of the respective packet history associated therewith.

22. The data communications apparatus of claim 21 wherein the decompressor constructs at least one acknowledgement vector for transmission from the data communications apparatus.

23. The data communications apparatus of claim 22 wherein the acknowledgement vector confirms a receipt of the decompressed packets by the data communications apparatus.

24. The data communications apparatus of claim 18 wherein the compressor utilizes Lempel-Ziv coding for the compressing the packets into the compressed data stream.

25. An apparatus for processing a compressed digital signal, the compressed digital signal being produced by, dividing an input stream of digital data into a plurality of packets;

identifying a respective packet history state for particular ones of the packets as a function of at least one acknowledgement vector, encoding the particular ones of the packets as a function of the respective packet history associated therewith, each packet having a packet header associated therewith, the packet header including at least a history vector which identifies the respective packet history state of the packet, compressing the encoded packets into the compressed digital signal and applying the compressed digital signal to a communications channel, the apparatus comprising;

a receiver for receiving the compressed digital signal from the communications channel; and

a decompressor for decompressing the received compressed digital signal, and recovering the input stream of digital data from the decompressed digital signal.

26. The apparatus of claim 25 wherein the particular ones of the packets are decompressed from the compressed digital signal as a function of the respective packet history associated therewith.

27. The apparatus of claim 26 wherein the decompressor constructs an acknowledgment vector, and transmits the acknowledgement vector from a receiver to a transmitter, the receiver and the transmitter exchanging the compressed digital signal across the communications channel.

28. The apparatus of claim 27 wherein the compressing the packets operation utilizes Lempel-Ziv coding.

29. The apparatus of claim 27 wherein the decompressor updates the respective history state of the associated packet upon being decompressed.

30. A machine-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions that, when executed by a machine, cause the machine to perform of a method of transmitting a communications stream between a sending location and a receiving location across a communications channel by dividing the communications stream into a plurality of packets;

identifying a respective packet history state for particular ones of the packets as a function of a first acknowledgement vector, the first acknowledgement vector being received by the sending location from the receiving location;

encoding the particular ones of the packets as a function of the respective packet history associated therewith, each such packet having a packet header associated therewith, the packet header including at least a history vector which identifies the respective packet history state of the packet;

compressing the plurality of packets into a compressed data stream; and

transmitting, across the communications channel, the compressed data stream from the sending location to the receiving location.

31. The machine-readable medium of claim 30 wherein the respective packet history state associated with the packet is identified as a function of a plurality of received packets at the receiver location.

32. The machine-readable medium of claim 31 including further instructions such that the method further comprises the operations of:

receiving the compressed data stream at the receiving location,

extracting the respective history state associated with the particular ones of the packets; and

decompressing the compressed data stream to recover the plurality of packets, the particular ones of the encoded packets being decompressed as a function of the extracted packet history associated therewith.

33. The machine-readable medium of claim 31 including further instructions such that the method further comprises the operations of:

constructing a second acknowledgment vector, the second acknowledgement vector confirming a receipt of the decompressed packets by the receiving location; and

transmitting the second acknowledgement vector from the receiver location to the sending location.