Method and apparatus for data compression of network packets employing per-packet hash tables
First Claim
1. A data communications method comprising:
- dividing an 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;
generating a respective hash table for each packet of the particular ones of the packets; and
encoding the particular ones of the plurality of packets as a function of the respective packet history associated therewith, each encoded packet being encoded with the respective hash table associated therewith.
3 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for compressing packets that enables inter-packet compression thereby achieving greater robustness and increased compression ratios. More particularly, a variable-length coding is used in conjunction with maintaining a separate hash table for each packet. Further, the per-packet hash table indexes particular byte strings in the packet but does not index data in any other packet(s). That is, a respective separate hash table for each packet is employed wherein such hash table is constructed as the particular packet is compressed. As such, the respective hash table is encoded with the particular packet. Employing a per-packet hash table in combination with variable history state inter-packet compression provides for efficient and robust overall compression of the packets.
-
Citations
25 Claims
-
1. A data communications method comprising:
-
dividing an 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;
generating a respective hash table for each packet of the particular ones of the packets; and
encoding the particular ones of the plurality of packets as a function of the respective packet history associated therewith, each encoded packet being encoded with the respective hash table associated therewith. - View Dependent Claims (2, 3, 4, 5, 6, 7)
encoding a plurality of match lengths, a plurality of literals, and a plurality of match offsets as a function of the portion of the data within the packet.
-
-
5. The method of claim 3 wherein the encoding the packets further comprises:
identifying a particular string of the input stream of data by searching the respective hash tables associated with the packets.
-
6. The method of claim 5 wherein the searching is performed as a function of the respective packet history state of the packet.
-
7. The method of claim 6 wherein a number of searches made during the searching of the respective hash tables is determined using a compression level parameter.
-
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 series of packets;
identifying a respective packet history state for each one of the packets as a function of an acknowledgement vector;
encoding the packets as a function of the respective packet history associated therewith, each packet being encoded together with a respective hash table; and
transmitting, across the communications channel, the encoded data stream from the sending location to the receiving location. - View Dependent Claims (9, 10, 11, 12, 13, 14)
identifying a particular one of byte substrings by searching each respective hash table of the packets, the searching being performed as a function of the respective packet history state of the packet. -
12. The method of claim 11 wherein a maximum number of searches made during the searching of the respective hash tables is determined using a compression level parameter.
-
13. The method of claim 12 wherein the compression level parameter is defined as at least eight strings.
-
14. The method of claim 11 wherein the searching operation further comprises:
constructing an index as a function of the respective hash tables, and using the index during the searching to identify the particular one byte substring.
-
-
15. A method of encoding an input data stream, the input data stream including a plurality of bits, the method comprising:
-
arranging the plurality of bits into a plurality of packets, each packet including a particular series of bits of the plurality of bits;
generating a plurality of hash tables, each one of the hash tables being associated with a particular one packet of the plurality of packets; and
encoding each packet of the plurality of packets into an output data stream, each packet of the output data stream being encoded together with the respective one hash table associated therewith. - View Dependent Claims (16, 17)
-
-
18. An apparatus for processing a digital signal, the 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;
generating a respective one hash table for each one of the packets;
encoding each packet as a function of the respective packet history associated therewith to produce an encoded digital signal, each one of the encoded packets being encoded together with the packet'"'"'s respective hash table; and
applying the encoded digital signal to a communications channel, the apparatus comprising;a receiver for receiving the encoded digital signal from the communications channel; and
a decoder for decoding the received encoded digital signal, and recovering the input stream of digital data from the decoded digital signal. - View Dependent Claims (19, 20, 21, 22)
- identifying a respective packet history state for particular ones of the packets as a function of at least one acknowledgement vector;
-
23. 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 a signal encoding method by arranging a plurality of bits of the signal into a plurality of packets, each packet including a particular series of bits of the plurality of bits;
- generating a plurality of hash tables, each one of the hash tables being associated with a particular one packet of the plurality of packets; and
encoding each packet of the plurality of packets into an output data stream, each packet of the output data stream being encoded together with the respective one hash table associated therewith. - View Dependent Claims (24, 25)
- generating a plurality of hash tables, each one of the hash tables being associated with a particular one packet of the plurality of packets; and
Specification