Back to results
US 7,742,414 B1Granted
Lightweight indexing for fast retrieval of data from a flow-level compressed packet trace
AssigneeSprint Communications Company L.P.
InventorsGianluca Iannaccone, Tao Ye
Life of this patent
Estimating the term…
Abstract
The present invention describes methods, systems, and data structures to create and search index records within a trace of a packet-based communications link that has been compressed by organizing the data packets according to which flow they belong. Index points are inserted within the compressed flow trace file to create frames and index records are created and saved for each index point. Consequently, searching for a particular data packet does not require sequentially reading the compressed flow trace file, but rather locating the appropriate index record and its corresponding frame in the compressed flow trace file.
Claims22
A computer readable medium having stored thereon a data structure to describe the contents of frames of a compressed trace record file, the data structure comprising:
- an offset field containing data stored on the computer readable medium the data representing the offset of a first frame of the compressed trace record file from the beginning of the compressed trace record file;
- a number of packets field containing data stored on the computer readable medium representing the number of data packets recorded in a first frame of the compressed trace record file;
- a minimum time stamp field containing data stored on the computer readable medium representing the minimum time stamp of the data packets recorded in a first frame of the compressed trace record file;
- and
- a maximum time stamp field containing data stored on the computer readable medium representing the maximum time stamp of the data packets recorded in a first frame of the compressed trace record file.
2 more elements
A method for indexing a compressed trace record file;
- the method comprising:
- creating frames in the compressed trace record file stored on a computer by logically dividing the compressed trace record file into frames, delimited by logical index points, a frame being flow records and data packet records between the beginning of the compressed trace record file and the first index point and the flow records and data packet records between an index point and the next index point;
- and
- creating an index record for each index point, each index record comprising:
- an offset field containing data stored on a computer readable medium representing the offset of the corresponding index point from the beginning of the compressed trace record file;
- a number of packets field containing data stored on the computer readable medium representing the number of packets in the frame ending with the corresponding index point;
- a minimum time stamp field containing data stored on the computer readable medium representing the minimum time stamp of a packet in the frame ending with the corresponding index point;
- and
- a maximum time stamp field containing data stored on the computer readable medium representing the maximum time stamp of a packet in the frame ending with the corresponding index point.
6 more elements
A method for forming and indexing a trace record file, the method comprising:
- monitoring data packets received over a packet-based communications link;
- identifying a flow to which each data packet belongs;
- saving at least a portion of each data packet in a flow record, each flow record corresponding to a flow;
- creating frames in the trace record file stored on a computer by logically dividing the compressed trace record file into frames, delimited by index points, a frame being flow records and data packet records between the beginning of the trace record file and the first index point and the flow records and data packet records between an index point and the next index point;
- and
- creating an index record for each index point, each index record containing data describing the data packet records in the frame ending with the corresponding index point.
3 more elements
A method for searching a compressed trace record file, the method comprising:
- creating frames in the compressed trace record file stored on a computer by logically dividing the compressed trace record file into frames, delimited by index points, a frame being flow records and data packet records between the beginning of the trace record file and the first index point and the flow records and data packet records between an index point and the next index point;
- creating an index record for each index point, each index record comprising:
- an offset field containing data stored on a computer readable medium representing the offset of the corresponding index point from the beginning of the compressed trace record file;
- a number of packets field containing data stored on the computer readable medium representing the number of packets in the frame ending with the corresponding index point;
- a minimum time stamp field containing data stored on the computer readable medium representing the minimum time stamp of a packet in the frame ending with the corresponding index point;
- and
- a maximum time stamp field containing data stored on the computer readable medium representing the maximum time stamp of a packet in the frame ending with the corresponding index point;
- selecting a target data packet;
- sequentially reading the created index records until the index record that contains the target data packet is identified;
- locating the frame in the compressed trace file stored on the computer described by the offset in the identified index record;
- and
- sequentially reading the data packet records in the frame until the target data packet is located or the number of packets in the frame is read.
9 more elements
Dependencies are inferred from the claim text.