Compressing trace data

Patent metadata

Field	Value
Publication number	US-10326674-B2
Application number	US-201414470212-A
Country	US
Kind code	B2
Filing date	Aug 27, 2014
Priority date	Aug 27, 2013
Publication date	Jun 18, 2019
Grant date	Jun 18, 2019

Abstract

Trace data are compressed by storing a compression table in a memory. The table corresponds to results of processing a set of training trace data using a table-driven compression algorithm. The trace data are compressed using the table according to the algorithm. The stored compression table is accessed read-only. The table can be determined by automatically processing a set of training trace data using the algorithm and transforming the compression table produced thereby into a lookup-efficient form. A network device includes a network interface, memory, and a processor that stores the table in the memory, compresses the trace data using the stored compression table according to the table-driven compression algorithm, the stored table being accessed read-only during the compressing, and transmits the compressed trace data via the network interface.

First claim

The invention claimed is:

1. A method of compressing a dataset, the dataset comprising at least sensor data or other data representing the runtime behavior of a computing system, the method comprising performing the following steps using a processor of the computing system:
storing a compression table in a nonvolatile memory to provide a read-only compression table, wherein the compression table corresponds to results of processing a set of training data using a table-driven compression algorithm and the compression table is different from a compressed string output by the table-driven compression algorithm; and
after storing the compression table in the nonvolatile memory, compressing the dataset using the read-only compression table according to the table-driven compression algorithm to provide a compressed set of data, wherein:
the dataset differs from the set of training data;
the read-only compression table is accessed in a read-only manner during compression of the dataset;
the set of training data is not stored in the nonvolatile memory; and
compressing the dataset comprises:
determining a portion of the dataset;
reading, from the read-only compression table, a pattern corresponding to the portion of the dataset; and
determining a portion of the compressed set of data based at least in part on the pattern, wherein the portion of the compressed set of data represents the portion of the dataset; and

after compressing the dataset:
determining a second dataset comprising at least sensor data or other data representing the runtime behavior of the computing system; and
compressing the second dataset using the read-only compression table according to the table-driven compression algorithm to provide a second compressed set of data, wherein:
the read-only compression table is accessed in a read-only manner during compression of the second dataset; and
compressing the second dataset comprises:
determining a portion of the second dataset;
reading, from the read-only compression table, a second pattern, the second pattern corresponding to the portion of the second dataset; and
determining a portion of the second compressed set of data based at least in part on the second pattern, wherein the portion of the second compressed set of data represents the portion of the second dataset.

2. The method according to claim 1 , wherein the table-driven compression algorithm is a finite-context-method or Lempel-Ziv-Welch algorithm.

3. The method according to claim 1 , further comprising, before storing the compression table:
receiving a pre-table; and
transforming the pre-table to a lookup-efficient form to provide the compression table.

4. The method according to claim 3 , wherein the table-driven compression algorithm uses fixed-length sequences of input data and the transforming includes determining a hash table mapping values of the sequences to corresponding predictions.

5. The method according to claim 3 , wherein the table-driven compression algorithm uses a dictionary of patterns of values of input data and the transforming includes determining a trie of patterns in the dictionary, wherein nodes of the trie store entries in the dictionary and edges of the trie are labeled with corresponding ones of the values of the input data.

6. The method according to claim 1 , further comprising storing the compressed set of data in a processor-accessible memory.

7. The method according to claim 1 , further comprising transmitting the compressed set of data via a network interface.

8. The method according to claim 1 , further comprising repeating the storing and compressing steps in order with respect to a second compression table different from the compression table.

9. The method according to claim 1 , further comprising, after compressing the dataset, decompressing the compressed set of data using the read-only compression table.

10. The method according to claim 1 , further comprising determining the dataset including at least one control-flow trace data element and at least one network trace data element.

11. A network device, comprising:
a nonvolatile memory; and
a processor configured to:
store a compression table in the nonvolatile memory to provide a read-only compression table, wherein:
the compression table corresponds to results of processing a set of training data using a table-driven compression algorithm;
the compression table is different from a compressed string output by the table-driven compression algorithm; and
the processor does not store the set of training data in the memory;

subsequent to storing the compression table in the memory, compress a dataset using the read-only compression table according to the table-driven compression algorithm to provide a compressed set of data, wherein:
the dataset comprises at least sensor data or other data representing the runtime behavior of the network device;
the dataset differs from the training data;
the read-only compression table is accessed in a read-only manner during the compressing of the dataset; and
compressing the dataset comprises:
determining a portion of the dataset;
reading, from the read-only compression table, a pattern corresponding to the portion of the dataset; and
determining a portion of the compressed set of data based at least in part on the pattern, wherein the portion of the compressed set of data represents the portion of the dataset; and

after compressing the dataset:
determine a second dataset comprising at least sensor data or other data representing the runtime behavior of the computing system; and
compress the second dataset using the read-only compression table according to the table-driven compression algorithm to provide a second compressed set of data, wherein:
the read-only compression table is accessed in a read-only manner during compression of the second dataset; and
compressing the second dataset comprises:
 determining a portion of the second dataset;
 reading, from the read-only compression table, a second pattern, the second pattern corresponding to the portion of the second dataset; and
 determining a portion of the second compressed set of data based at least in part on the second pattern, wherein the portion of the second compressed set of data represents the portion of the second dataset.

12. The network device according to claim 11 , further comprising a sensor, wherein the processor is further configured to receive sensor data from the sensor and determine the dataset including the received sensor data.

13. The network device according to claim 11 , wherein the dataset includes an element selected from the group consisting of a control flow trace data element, an event trace data element, a power trace data element, and a function call trace data element.

14. The network device according to claim 11 , wherein the processor is further configured to determine the dataset including at least one control-flow trace data element and at least one network trace data element.

15. The method according to claim 1 , wherein the dataset comprises trace data and the training data comprises training trace data.

16. The network device according to claim 11 , wherein the training data is training trace data and the dataset comprises trace data.

17. The network device according to claim 11 , wherein:
the network device further comprises a network interface; and
the processor is further configured to transmit the compressed data via the network interface.

18. The network device according to claim 11 , wherein the p

Assignees

• Purdue Research Foundation

Inventors

• Sundaram Vinaitheerthan
• Eugster Patrick
• Zhang Xiangyu

Classifications

• G06F11/3636

  by tracing the execution of the program · CPC title

• H04L43/062 Primary

  related to network traffic · CPC title

• H04L69/04

  Protocols for data compression, e.g. ROHC · CPC title

• G06F16/1744

  using compression, e.g. sparse files · CPC title

• H04L45/74

  Address processing for routing · CPC title