System and methods for compressing data based on data link characteristics

• US 9,172,771 B1
• Filed: 12/18/2012
• Issued: 10/27/2015
• Est. Priority Date: 12/21/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gross, Dor, Naik, Uday Ramakrishna
• Primary Examiner(s): Chan, Wing F
• Assistant Examiner(s): MUNDUR, PADMAVATHI V
• Application Number:
  US13/718,908
• Time in Patent Office: 1,043 Days
• Field of Search: 709/247
• US Class Current: 1/1
• CPC Class Codes: H04L 41/0823 characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability for optimising operational conditions of wireless networks H04W24/02
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 51/066 Format adaptation, e.g. format conversion or compression
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC

Abstract

Systems and methods for compressing data in a network system communicated across a network are discussed. The network system may determine a data link characteristic for a data link between a source and a destination. A compression algorithm may be selected from among a plurality of compression algorithms based on the data link characteristic. A chunk of data may be compressed, using the selected compression algorithm, to be communicated over the data link. A compression ratio of the compressed chunk and the chunk uncompressed may be compared to a compression threshold. The compressed chunk may be provided, using the control circuitry, if the compression ratio is greater or equal to the compression threshold. The chunk uncompressed may be provided if the first compression ratio is less than to the first compression threshold.

Claims

1. A method for compressing data in a network system communicated across a data link comprising:

determining, using control circuitry, a monetary cost of transferring data over a first data link between a source and a destination, wherein the monetary cost is a first data link characteristic of the first data link;

selecting, using the control circuitry, a first compression algorithm among a plurality of compression algorithms based on the determined monetary cost and further based on a system resource utilization associated with usage of the first compression algorithm;

compressing, using the selected first compression algorithm, a first chunk of data to be communicated over the first data link;

identifying a first compression threshold based on the monetary cost of transferring data over the first data link;

comparing, using the control circuitry, a first compression ratio of the compressed first chunk and the first chunk uncompressed to the first compression threshold; and

providing, using the control circuitry, the compressed first chunk if the first compression ratio is greater or equal to the first compression threshold;

or

providing, using the control circuitry, the first chunk uncompressed if the first compression ratio is less than the first compression threshold.

2. The method of claim 1, wherein selecting the first compression algorithm is further based on a compression strength for each of the plurality of compression algorithms.

3. The method of claim 1, wherein selecting the first compression algorithm is based on a mapping between the first data link characteristic and a compression strength for each of the plurality of compression algorithms.

4. The method of claim 1, wherein selecting the first compression algorithm is based on a data type.

5. The method of claim 1, further comprising:

compressing, using the selected first compression algorithm, a second chunk of data to be communicated over the first data link;

providing, using the control circuitry, the compressed second chunk.

6. The method of claim 1, further comprising:

compressing, using the selected first compression algorithm, a second chunk of data to be communicated over the first data link;

comparing, using the control circuitry, a second compression ratio of the compressed second chunk and the second chunk uncompressed to the first compression threshold; and

selecting, using the control circuitry, a second compression algorithm among the plurality of compression algorithms based on the first data link characteristic and the second compression ratio if the second compression ratio is less than the first compression threshold.

7. The method of claim 6, further comprising:

compressing, using the selected second compression algorithm, the second chunk of data to be communicated over the first data link;

comparing, using the control circuitry, a third compression ratio of the second chunk compressed using the second compression algorithm and the second chunk uncompressed to the first compression threshold; and

providing, using the control circuitry, the compressed second chunk if the third compression ratio is greater or equal to the first compression threshold;

or

providing, using the control circuitry, the second chunk uncompressed if the third compression ratio is less than the first compression threshold.

30. The method of claim 1, the method further comprising selecting the first data link from among a plurality of data links between the source and the destination based on a respective compression ratio for each of the plurality of compression algorithms.

31. The method of claim 1, wherein selecting the first compression algorithm is further based on a second data link characteristic for the first data link.

32. The method of claim 1, wherein identifying the first compression threshold is further based on a second data link characteristic for the first data link.

8. A system for compressing data in a network system communicated across a data link, the system comprising control circuitry configured to:

determine a monetary cost of transferring data over a first data link between a source and a destination, wherein the monetary cost is a first data link characteristic of the first data link;

select a first compression algorithm among a plurality of compression algorithms based on the determined monetary cost of transferring data over the first data link and further based on a system resource utilization associated with usage of the first compression algorithm;

compress, using the selected first compression algorithm, a first chunk of data to be communicated over the first data link;

identify a first compression threshold based on the monetary cost of transferring data over the first data link;

compare a first compression ratio of the compressed first chunk and the first chunk uncompressed to the first compression threshold; and

provide the compressed first chunk if the first compression ratio is greater or equal to the first compression threshold;

or

provide the first chunk uncompressed if the first compression ratio is less than the first compression threshold.

9. The system of claim 8, wherein selecting the first compression algorithm is further based on a compression strength for each of the plurality of compression algorithms.

10. The system of claim 8, the system comprising control circuitry further configured to select the first compression algorithm based on a mapping for the first data link characteristic and the system resource utilization for each of the plurality of compression algorithms.

11. The system of claim 8, the system comprising control circuitry further configured to select the first compression algorithm based on a data type.

12. The system of claim 8, the system comprising control circuitry further configured to:

compress, using the selected first compression algorithm, a second chunk of data to be communicated over the first data link;

provide the compressed second chunk.

13. The system of claim 8, the system comprising control circuitry further configured to:

compress, using the selected first compression algorithm, a second chunk of data to be communicated over the first data link;

compare a second compression ratio of the compressed second chunk and the second chunk uncompressed to the first compression threshold; and

select a second compression algorithm among the plurality of compression algorithms based on the first data link characteristic and the second compression ratio if the second compression ratio is less than the first compression threshold.

14. The system of claim 13, the system comprising control circuitry further configured to:

compress, using the selected second compression algorithm, the second chunk of data to be communicated over the first data link;

compare a third compression ratio of the second chunk compressed using the second compression algorithm and the second chunk uncompressed to the first compression threshold; and

provide the compressed second chunk if the third compression ratio is greater or equal to the first compression threshold;

or

provide the second chunk uncompressed if the third compression ratio is less than the first compression threshold.

33. The system of claim 8, the system comprising control circuitry configured to:

select the first data link from among a plurality of data links between the source and the destination based on a respective compression ratio for each of the plurality of compression algorithms.

34. The system of claim 8, the system comprising control circuitry configured to select the first compression algorithm further based on a second data link characteristic for the first data link.

35. The system of claim 8, the system comprising control circuitry configured to identify the first compression threshold further based on a second data link characteristic for the first data link.

15. A method for compressing data in a network system communicated across a data link comprising:

for each of a plurality of data links, determining a respective monetary cost of transferring data over the respective data link;

for each of a plurality of compression algorithms, compressing, by control circuitry at a first network system, a first chunk of data to be communicated, and determining a respective compression ratio for the respective compression algorithm based on compression of the first chunk of data;

selecting, using the control circuitry, a first data link from the plurality of data links and a first compression algorithm from the plurality of compression algorithms based on a function of;

(a) each of the determined monetary costs of transferring data over the respective data links, and

(b) for each of the plurality of compression algorithms,

(i) the respective compression ratio and

(ii) a respective system resource utilization associated with usage of the respective compression algorithm; and

providing, using the control circuitry, the first chunk of data compressed using the selected first compression algorithm over the selected first data link.

16. The method of claim 15, wherein the system resource utilization associated with usage of each of the plurality of compression algorithms includes utilization of a processor, memory, or storage resource.

17. The method of claim 15, wherein selecting the first data link is based on a mapping between the respective monetary cost of transferring data over each data link among the plurality of data links and the respective compression ratio for each of the plurality of compression algorithms.

18. The method of claim 15, wherein selecting the first compression algorithm is based on a mapping between the respective monetary cost of transferring data over each data link among the plurality of data links and the respective compression ratio for each of the plurality of compression algorithms.

19. The method of claim 15, wherein selecting the first compression algorithm is based on a data type.

20. The method of claim 19, wherein selecting the first compression algorithm is based on a pre-determined compression algorithm among the plurality of compression algorithms for the data type.

36. The method of claim 15, wherein the function optimizes tradeoffs between the determined respective monetary costs, the respective compression ratio, and the respective system utilization.

37. The method of claim 15, wherein the function selects an optimal compression algorithm that results in a highest compression ratio without exceeding a threshold system resource utilization pre-determined based on the monetary cost of transferring data over the respective data link.

21. A system for compressing data communicated from a first computer system to a second computer system, the system comprising:

a first computer system, the first computer system comprising control circuitry configured to;

determine a value for a first data link characteristic of a first data link between the first computer system and a second computer system, wherein the first data link characteristic is a monetary cost of transferring data over the first data link;

select a first compression algorithm among a plurality of compression algorithms based on the value for the first data link characteristic and further based on a system resource utilization of a processor, memory, or storage resource used by the first compression algorithm;

compress a first chunk of data to be communicated over the first data link based on the selected first compression algorithm;

identify a first compression threshold based on the value for the first data link characteristic;

determine whether a first compression ratio based on the compressed first chunk is greater or equal to the first compression threshold; and

provide the compressed first chunk to be communicated to the second computer system based on determining that the compression ratio based on the compressed first chunk is greater or equal to the first compression threshold; and

the second computer system, the second computer system comprising control circuitry configured to decompress the first chunk of data compressed by the first computer system.

22. The system of claim 21, further including a third computer system,

the second computer system comprising control circuitry further configured to:

store the received first chunk of data compressed by the first computer system; and

provide the stored compressed first chunk of data; and

the third computer system comprising control circuitry configured to;

decompress the first chunk of data compressed by the first computer system provided by the second computer system.

23. The system of claim 21, wherein the first computer system control circuitry is further configured to select the first compression algorithm based on a compression strength for each of the plurality of compression algorithms.

24. The system of claim 23, wherein the first computer system control circuitry is further configured to select the first compression algorithm based on a mapping between the first characteristic of the first data link and the compression strength for each of the plurality of compression algorithms.

25. The system of claim 21, wherein the first computer system control circuitry is further configured to select the first compression algorithm based on a data type.

26. The system of claim 21, wherein the first computer system is configured to select the first compression algorithm further based on a second data link characteristic for the first data link.

27. The system of claim 21, wherein the first computer system is configured to identify the first compression threshold further based on a second data link characteristic for the first data link.

28. The system of claim 21, wherein the first computer system control circuitry is further configured to:

compress, using the selected first compression algorithm, a second chunk of data to be communicated over the first data link;

determine whether a second compression ratio of the compressed second chunk and the second chunk uncompressed is greater or equal to the first compression threshold; and

select, a second compression algorithm among the plurality of compression algorithms based on the first data link characteristic and the second compression ratio based on determining that the second compression ratio is less than the first compression threshold.

29. The system of claim 21, wherein the first computer system control circuitry is further configured to:

select the first data link from among a plurality of data links between the first computer system and a second computer system based on a respective compression ratio for each of the plurality of compression algorithms.