Granted Patent B1

US 7,154,416 · App. 11/233,872 · Granted Dec 26, 2006

Abstract

Claims (56)

1. In a data compression mechanism, a method for controlling updates to a codebook used to compress data, the method comprising

receiving input data comprising at least one input symbol;

transforming at least a portion of the input data to compressed output data using a first codebook, the compressed output data having a length;

computing, according to a simulated codebook process, a simulated output length based on the input data;

maintaining an aggregate output length deviation between the length of the compressed output data and the simulated output length;

conditionally updating the first codebook based at least in part on the aggregate output length deviation.

2. The method of claim 1 further comprising

maintaining an input data history comprising a sliding window of the input symbols in the received input data.

3. The method of claim 2 wherein the simulated codebook process computes the simulated output length based at least in part on the input data history.

4. The method of claim 1 further comprising transmitting the compressed output data to a remote host.

5. The method of claim 1 wherein the input data comprises at least one packet transmitted from a destination host to a source host.

6. The method of claim 5 further comprising transmitting the compressed output data in at least one packet to a remote host.

7. In a data compression mechanism, a method for controlling updates to a codebook used to compress data, the method comprising

receiving an input symbol;

generating an output based on a first codebook and the input symbol, wherein the output has a length;

updating an input symbol history based on the received input symbol;

computing, according to a simulated codebook process, a simulated output length based on the input symbol and the input symbol history;

adjusting an aggregate deviation value based on the difference between the length of the generated output and the simulated output length;

conditionally updating the first codebook based at least in part on the deviation value.

8. The method of claim 7 wherein updating an input symbol history comprises

storing previously received input symbols in a queue of input symbols; and

popping, in response to the receiving step, a first input symbol in the queue; and

placing the received input symbol on the queue.

9. The method of claim 7 wherein computing the length of the simulated output comprises

determining, based on the input symbol history, an occurrence probability of the received input symbol;

computing the simulated length of the output symbol based on the occurrence probability of the received input symbol.

10. The method of claim 8 wherein the simulated length of the output symbol is computed according to the relation:

simulated_output_length=−1×log 2 (symbol_occurrence_probability).

11. An apparatus including compression functionality, comprising

a processor;

at least one network interface,

a memory;

a compression module, physically stored in the memory, comprising instructions operable to cause the processor and the apparatus to:

receive input data comprising at least one input symbol;

transform at least a portion of the input data to compressed output data using a first codebook, the compressed output data having a length;

compute, according to a simulated codebook process, a simulated output length based on the input data;

maintain an aggregate output length deviation between the length of the compressed output data and the simulated output length;

conditionally update the first codebook based at least in part on the aggregate output length deviation.

12. The apparatus of claim 11 wherein the compression module further comprises instructions operative to cause the processor and the apparatus to

maintain an input data history comprising a sliding window of the input symbols in the received input data.

13. The apparatus of claim 12 wherein the simulated codebook process computes the second simulated output length based at least in part on the input data history.

14. The apparatus of claim 11 wherein the compression module further comprises instructions operative to cause the processor and the apparatus to

transmit the compressed output data to a remote host.

15. The apparatus of claim 11 wherein the input data comprises at least one packet transmitted from a destination host to a source host.

16. The apparatus of claim 15 wherein the compression module further comprises instructions operative to cause the processor and the apparatus to

transmit the compressed output data in at least one packet to a remote host.

17. The apparatus of claim 11 wherein the compression module further comprises instructions operative to cause the processor and the apparatus to

establish compression tunnels with a remote network device in the communications path to one or more destination hosts; and

intercept outgoing data packets to the one or more destination hosts.

18. The apparatus of claim 11 further comprising

a tunnel probing module, physically stored in the memory, comprising instructions operable to cause the processor and the apparatus to:

dynamically probe a communications path to a destination host for at least one network device having compression capabilities; and

establish a compression tunnel with an identified network device in the communications path.

19. The apparatus of claim 18 wherein the tunnel probing module is operative to

transmit probe requests along the communications path to the destination host; and

receive probe responses from network devices in the communications path to the destination host.

Assignments (8)