Bandwidth sensitive data compression and decompression

• US 7,386,046 B2
• Filed: 02/13/2002
• Issued: 06/10/2008
• Est. Priority Date: 02/13/2001
• Status: Expired due to Fees

• Current Assignee: Realtime Adaptive Streaming LLC (Realtime Data Compression Systems, Inc.)
• Original Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Inventors: Fallon, James J., McErlain, Stephen J.
• Primary Examiner(s): Bocure, Tesfaldet
• Application Number:
  US10/076,013
• Publication Number:
  US 20020191692A1
• Time in Patent Office: 2,309 Days
• Field of Search: 375/240, 375/222, 375/372, 375/377, 348/384, 704/501, 704/502
• US Class Current: 375/240
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/6094 according to reasons other than compression rate or data type
• CPC Class Codes: H04N 19/103 Selection of coding mode or of prediction mode
• CPC Class Codes: H04N 19/164 Feedback from the receiver or from the transmission channel
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock

Abstract

Data compression and decompression methods for compressing and decompressing data based on an actual or expected throughput (bandwidth) of a system. In one embodiment, a controller tracks and monitors the throughput (data storage and retrieval) of a data compression system and generates control signals to enable/disable different compression algorithms when, e.g., a bottleneck occurs so as to increase the throughput and eliminate the bottleneck.

Claims

1. A method comprising:

compressing data using a first compression routine providing a first compression rate, wherein the first compression routine comprises a first compression algorithm;

tracking the throughput of a data processing system to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold, wherein said tracking throughput comprises tracking a number of pending requests for data transmission; and

when the tracked throughput does not meet the predetermined throughput threshold, compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, to increase the throughput of the data processing system to at least the predetermined throughput level, wherein the second compression routine comprises a second compression algorithm.

2. The method of claim 1, wherein the second compression routine comprises a symmetric routine.

3. The method of claim 1, wherein said data compressed using said first compression routine comprises a website.

4. The method of claim 1, wherein said data compressed using said first compression routine comprises a music and video.

5. A method comprising:

compressing data using a first compression routine providing a first compression rate;

tracking the throughput of a data processing system to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold; and

when the tracked throughput does not meet the predetermined throughput threshold, compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, to increase the throughput of the data processing system to at least the predetermined throughput level, wherein the first compression routine comprises an asymmetric routine and wherein the second compression routine comprises a symmetric routine.

6. The method of claim 5, wherein said data compressed using said first compression routine comprises a website.

7. The method of claim 5, wherein said data compressed using said first compression routine comprises a music and video.

8. A method comprising:

compressing data using a first compression routine providing a first compression rate;

tracking the throughput of a data processing system to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold, wherein said tracking throughput comprises tracking a number of pending requests for data transmission; and

when the tracked throughput does not meet the predetermined throughput threshold, compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, to increase the throughput of the data processing system to at least the predetermined throughput level; and

utilizing the second routine to perform compression until the throughput of the data processing system is determined to meet the predetermined throughput threshold, and then reusing the first compression routine.

9. The method of claim 8, wherein said data compressed using said first compression routine comprises a website.

10. The method of claim 8, wherein said data compressed using said first compression routine comprises a music and video.

11. A method comprising:

compressing data using a first compression routine providing a first compression rate;

tracking the throughput of a data processing system to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold; and

when the tracked throughput does not meet the predetermined throughput threshold, compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, to increase the throughput of the data processing system to at least the predetermined throughput level; and

utilizing the second routine to perform compression until the throughput of the data processing system is determined to meet the predetermined throughput threshold, and then reusing the first compression routine, wherein the first compression routine comprises a default asymmetrical algorithm.

12. The method of claim 11, wherein said data compressed using said first compression routine comprises a website.

13. The method of claim 11, wherein said data compressed using said first compression routine comprises a music and video.

14. A method comprising:

compressing data using a first compression routine providing a first compression rate;

tracking the throughput of a data processing system to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold; and

when the tracked throughput does not meet the predetermined throughput threshold, compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, to increase the throughput of the data processing system to at least the predetermined throughput level; and

processing a user command to load a user-selected compression routine for compressing data.

15. The method of claim 14, wherein said data compressed using said first compression routine comprises a website.

16. The method of claim 14, wherein said data compressed using said first compression routine comprises a music and video.

17. A method comprising:

compressing data using a first compression routine providing a first compression rate;

tracking the throughput of a data processing system to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold; and

when the tracked throughput does not meet the predetermined throughput threshold, compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, to increase the throughput of the data processing system to at least the predetermined throughput level;

processing a user command to compress user-provided data; and

automatically selecting a compression routine associated with a data type of the user-provided data.

18. A method comprising:

compressing data using a first compression routine providing a first compression rate;

tracking the throughput of a data processing system to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold; and

when the tracked throughput does not meet the predetermined throughput threshold, compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, to increase the throughput of the data processing system to at least the predetermined throughput level, wherein said tracking throughput comprises tracking a number of pending access requests to a storage device.

19. A method comprising:

compressing data using a first compression routine providing a first compression rate;

tracking the throughput of a data processing system to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold; and

when the tracked throughput does not meet the predetermined throughput threshold, compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, to increase the throughput of the data processing system to at least the predetermined throughput level, wherein said tracking throughput comprises tracking a number of pending requests for data transmission over a communication channel.

20. The method of claim 19, wherein said data compressed using said first compression routine comprises a website.

21. The method of claim 19, wherein said data compressed using said first compression routine comprises a music and video.

22. A method comprising:

receiving a digital data stream at an input data transmission rate that is greater than a data storage rate of a target storage device;

compressing the digital data stream at a compression rate that increases the effective data storage rate of the target storage device, wherein the compression rate is at least equal to the ratio of the input data transmission rate to the data storage rate so as to provide continuous storage of the input digital data stream at the input data transmission rate; and

storing the compressed digital data stream in the target storage device;

wherein said compressing comprises;

compressing data using a first compression routine providing a first compression rate, wherein the first compression routine comprises a first compression algorithm;

tracking an amount of pending access requests to the storage device to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold; and

compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, if the tracked throughput does not meet the predetermined throughput threshold, wherein the second compression routine comprises a second compression algorithm.

23. A system comprising:

a data compression system for compressing and decompressing data input;

a plurality of compression routines selectively utilized by the data compression system, wherein a first one of the plurality of compression routines includes a first compression algorithm and a second one of the plurality of compression routines includes a second compression algorithm; and

a controller for tracking throughput and generating a control signal to select a compression routine based on the throughput, wherein said tracking throughput comprises tracking a number of pending requests for data transmission; and

wherein when the controller determines that the throughput falls below a predetermined throughput threshold, the controller commands the data compression engine to use one of the plurality of compression routines to provide a faster rate of compression so as to increase the throughput.

24. A system comprising:

a data compression system for compressing and decompressing data input;

a plurality of compression routines selectively utilized by the data compression system;

a controller for tracking throughput and generating a control signal to select a compression routine based on the throughput,

wherein when the controller determines that the throughput falls below a predetermined throughput threshold, the controller commands the data compression engine to use one of the plurality of compression routines to provide a faster rate of compression so as to increase the throughput; and

a plurality of access profiles, operatively accessible by the controller, to determine a compression routine that is associated with a data type of data to be compressed.

25. A system comprising:

a data compression system for compressing and decompressing data input;

a plurality of compression routines selectively utilized by the data compression system;

a controller for tracking throughput and generating a control signal to select a compression routine based on the throughput,

wherein when the controller determines that the throughput falls below a predetermined throughput threshold, the controller commands the data compression engine to use one of the plurality of compression routines to provide a faster rate of compression so as to increase the throughput, wherein the system comprises a data storage controller, wherein the system throughput comprises a number of pending access requests to a storage device.

26. A system comprising:

a data compression system for compressing and decompressing data input;

a plurality of compression routines selectively utilized by the data compression system;

a controller for tracking throughput and generating a control signal to select a compression routine based on the throughput,

wherein when the controller determines that the throughput falls below a predetermined throughput threshold, the controller commands the data compression engine to use one of the plurality of compression routines to provide a faster rate of compression so as to increase the throughput, wherein the system comprises a data transmission controller, wherein the system throughput comprises a number of pending transmission requests over a communication channel.

27. A program storage device readable by a machine, tangibly embodying a program instructions executable by the machine to perform the method comprising:

compressing data using a first compression routine providing a first compression rate, wherein the first compression routine comprises a first compression algorithm;

tracking the throughput of a data processing system to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold, wherein said tracking throughput comprises tracking a number of pending request for data transmission; and

when the tracked throughput does not meet the predetermined throughput threshold, compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, to increase the throughput of the data processing system to at least the predetermined throughput level, wherein the second compression routine comprises a second compression algorithm.

28. A program storage device readable by a machine, tangibly embodying a program instructions executable by the machine to perform the method comprising:

receiving a digital data stream at an input data transmission rate that is greater than a data storage rate of a target storage device;

compressing the digital data stream at a compression rate that increases the effective data storage rate of the target storage device, wherein the compression rate is at least equal to the ratio of the input data transmission rate to the data storage rate so as to provide continuous storage of the input digital data stream at the input data transmission rate; and

storing the compressed digital data stream in the target storage device;

wherein said compressing comprises;

compressing data using a first compression routine providing a first compression rate, wherein the first compression routine comprises a first compression algorithm;

tracking an amount of pending access requests to the storage device to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold; and

compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, if the tracked throughput does not meet the predetermined throughput threshold, wherein the second compression routine comprises a second compression algorithm.

29. A method comprising:

using a first compression algorithm to compress data at a first compression rate to provide first compressed data to a communications channel;

tracking the throughput of the communications channel, wherein said tracking throughput comprises tracking a number of pending requests for data transmission over said communications channel;

determining if the first compression rate provides throughput that meets a predetermined throughput threshold; and

when the tracked throughput does not meet the predetermined throughput threshold, using a second compression algorithm to compress data at a second compression rate to provide second compressed data to the communications channel, wherein the second compression rate is greater than the first compression rate and providing the second compressed data to the communications channel increases the throughput of the communications channel.

30. The method of claim 29, wherein the communications channel is a network communications channel.

31. The method of claim 29, wherein a receiving device receives the first and second compressed data, and the receiving device decompresses the first and second compressed data.

32. The method of claim 29, wherein the communications channel is a network communications channel, a receiving device receives the first and second compressed data, and the receiving device decompresses the first and second compressed data.

33. The method of claim 29, wherein the second compression algorithm comprises a symmetric algorithm.

34. A method comprising:

compressing data using a first compression routine providing a first compression rate, wherein the first compression routine comprises a first compression algorithm;

tracking the throughput of a data processing system to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold; and

when the tracked throughput does not meet the predetermined throughput threshold, compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, to increase the throughput of the data processing system to at least the predetermined throughput level, wherein the second compression routine comprises a second compression algorithm, wherein the first compression routine comprises an asymmetric routine.

35. A method comprising:

using a first compression algorithm to compress data at a first compression rate to provide first compressed data to a communications channel;

tracking the throughput of the communications channel;

determining if the first compression rate provides throughput that meets a predetermined throughput threshold; and

when the tracked throughput does not meet the predetermined throughput threshold, using a second compression algorithm to compress data at a second compression rate to provide second compressed data to the communications channel, wherein the second compression rate is greater than the first compression rate and providing the second compressed data to the communications channel increases the throughput of the communications channel, wherein the first compression algorithm comprises an asymmetric algorithm.

36. A method comprising:

using a first compression algorithm to compress data at a first compression rate to provide first compressed data to a communications channel;

tracking the throughput of the communications channel;

determining if the first compression rate provides throughput that meets a predetermined throughput threshold; and

when the tracked throughput does not meet the predetermined throughput threshold, using a second compression algorithm to compress data at a second compression rate to provide second compressed data to the communications channel, wherein the second compression rate is greater than the first compression rate and providing the second compressed data to the communications channel increases the throughput of the communications channel, wherein the first compression algorithm comprises an asymmetric algorithm and the second compression algorithm comprises a symmetric algorithm.

37. A method comprising:

receiving a digital data stream at an input data transmission rate that is greater than a data storage rate of a target storage device;

compressing the digital data stream at a compression rate that increases the effective data storage rate of the target storage device; and

storing the compressed digital data stream in the target storage device,

wherein said compressing comprises;

compressing data using a first compression routine providing a first compression rate, wherein the first compression routine comprises a first compression algorithm;

tracking an amount of pending access requests to the storage device to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold; and

compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, if the tracked throughput does not meet the predetermined throughput threshold, wherein the second compression routine comprises a second compression algorithm.

38. A method comprising:

compressing data using a first compression routine providing a first compression rate, wherein the first compression routine comprises a first compression algorithm;

tracking the throughput of a data processing system to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold, wherein said tracking throughput comprises tracking a number of pending access requests to a storage device; and

when the tracked throughput does not meet the predetermined throughput threshold, compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, to increase the throughput of the data processing system to at least the predetermined throughput level, wherein the second compression routine comprises a second compression algorithm.

39. A method comprising:

compressing data using a first compression routine providing a first compression rate;

tracking the throughput of a data processing system to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold, wherein said tracking throughput comprises tracking a number of pending access requests to a storage device; and

when the tracked throughput does not meet the predetermined throughput threshold, compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, to increase the throughput of the data processing system to at least the predetermined throughput level; and

utilizing the second routine to perform compression until the throughput of the data processing system is determined to meet the predetermined throughput threshold, and then reusing the first compression routine.

40. A system comprising:

a data compression system for compressing and decompressing data input;

a plurality of compression routines selectively utilized by the data compression system, wherein a first one of the plurality of compression routines includes a first compression algorithm and a second one of the plurality of compression routines includes a second compression algorithm; and

a controller for tracking throughput and generating a control signal to select a compression routine based on the throughput, wherein said tracking throughput comprises tracking a number of pending access requests to a storage device; and

wherein when the controller determines that the throughput falls below a predetermined throughput threshold, the controller commands the data compression engine to use one of the plurality of compression routines to provide a faster rate of compression so as to increase the throughput.

41. A program storage device readable by a machine, tangibly embodying a program instructions executable by the machine to perform the method comprising:

compressing data using a first compression routine providing a first compression rate, wherein the first compression routine comprises a first compression algorithm;

tracking the throughput of a data processing system to determine if the first compression rate provides a throughput that meets a predetermined throughput threshold, wherein said tracking throughput comprises tracking a number of pending access requests to a storage device; and

when the tracked throughput does not meet the predetermined throughput threshold, compressing data using a second compression routine providing a second compression rate that is greater than the first compression rate, to increase the throughput of the data processing system to at least the predetermined throughput level, wherein the second compression routine comprises a second compression algorithm.