Packet-based data compression method

• US 5,293,379 A
• Filed: 05/27/1993
• Issued: 03/08/1994
• Est. Priority Date: 04/22/1991
• Status: Expired due to Fees

• Current Assignee: Zarlink Semiconductor Inc. (Microchip Technology Incorporated)
• Original Assignee: Gandalf Technologies, Inc.
• Inventors: Carr, David W.
• Primary Examiner(s): Safourek, Benedict V.
• Assistant Examiner(s): Nguyen, Chau T.
• Application Number:
  US08/068,284
• Time in Patent Office: 285 Days
• Field of Search: 370/94.1, 370/94.2, 370/82, 370/83, 370/99, 370/109, 370/118, 375/122, 341/51, 341/65, 341/95, 358/426, 358/433, 358/432
• US Class Current: 370/474
• 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/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A data processing system is described that employs data packets which include at least static and dynamic fields, the static fields containing information that often remains constant during a multi-packet communication interval and the dynamic fields containing information that changes for each packet. Many packets also include a user-data fields. A compression method is described which comprises: reformatting each data packet by associating its static fields with a first packet region and its dynamic fields with a second packet region. The process then assembles a static table that includes static information from at least an initial data packet'"'"'s first packet region. It then identifies static field information in a subsequent data packet'"'"'s first packet region that is common to the information in the static table. Such common information is encoded so as to reduce its data length. The common static information is then replaced in the modified data packet with the encoded common static information and the modified data packet is then transmitted. A similar action occurs with respect to user-data information. A single dictionary table is created for all packet headers, while separate dictionary tables are created for each user-data portion of a packet-type experienced in the communication network thereby enabling better compression.

Claims

1. In a data processing system that employs packets, a packet including at least static fields and dynamic fields, said static fields including data which remains constant over plural packets, said dynamic fields including data which may change for each packet, some said packets also including user-data fields, a method for compressing said packets for transmission from one to another portion of the system, the method comprising:

a. reformatting each packet by associating its static fields with a first packet region, and its dynamic-fields with a second packet region;

b. assembling a static table that includes static field data from at least an initial data packet'"'"'s first packet region and assigning a code value thereto;

c. identifying static field data associated with a subsequent packet'"'"'s first packet region that is common to data in said static table, and selecting a code value assigned to said data that is common in said static table;

d. modifying said subsequent packet by replacing said common, static field data with said assigned code value; and

e. transmitting said modified subsequent packet.

2. The method of claim 1, wherein said reformatting step occurs with respect to data contained within header fields appearing in each packet and the method commences with the step of segregating header fields and user-data fields.

3. The method of claim 2 wherein said reformatting step further comprises rearranging each packet to place its static fields into said first packet region and its dynamic fields into said second packet region.

4. The method of claim 3 wherein said packets comprise semi-static data fields that contain semi-static data, a first portion of which can change with every packet and a second portion of which remains static over a plurality of packets, said method comprising the added step of:

a1. associating said first portion of said semi-static data with said first packet region so that it is compressed along with other static data.

5. The method of claim 4 wherein said method comprises the added step of:

e1. transmitting, uncompressed, said second portion of said semi-static data and data in said dynamic fields.

6. The method as recited in claim 1, comprising the additional steps of:

f. assembling a user-data table that includes data in a user-data field from at least an initial packet and assigning a determined code value thereto;

g. identifying data in a user-data field in a subsequent packet that is common to data in a user-data field entry in said user-data table and selecting said determined code value assigned to a said entry containing common data; and

h. modifying said subsequent packet by replacing said common data in said user-data field with said determined code value.

7. The method of claim 6, wherein said data processing system employs a plurality of protocols, each protocol employing a unique packet structure, said method comprising the added step of:

i. establishing for each one of a group of selected protocols, a user-data table, whereby user-data in a packet belonging to a selected protocol is compressed in relation to common user-data in a said user-data table specific for a selected protocol.

8. The method as recited in claim 7 further comprising the step of:

d1. appending a coded symbol to a packet which indicates whether it has been data compressed or not.

9. The method of claim 6, comprising the additional step of:

i. determining if said determined code value, in addition to remaining uncompressed user-data of a packet is greater in bit length than all uncompressed user-data in said packet, and if so, modifying step e by transmitting said uncompressed user-data from said packet in lieu of said determined code value and remaining uncompressed user-data.

10. The method as recited in claim 1, wherein information in a dynamic field of a packet is transmitted without modification.

11. The method as recited in claim 1, wherein static field data in said static table comprises all static field data in a packet, to thereby enable a matching with all data in a static field of a subsequent packet and a transmission of a single code value in lieu of all matching static data.

12. The method as recited in claim 1, wherein a packet includes a recalculatable data field including recalculatable data, the method further comprising the steps of:

calculating a value for said recalculatable data field based on data present in said packet;

subtracting said calculated value from a value in said recalculatable data field to derive a difference value;

inserting said difference value into said recalculatable data field of said packet; and

at a receiving data processing system that receives said packet containing said difference value, calculating a value of recalculatable data from data in said received packet, and adding said value of recalculatable data to said difference value.

13. The method of claim 1, wherein said data processing system is adapted to make a plurality of connections with other data processing systems, each connection manifesting different information in a packet structure, said method comprising the added step of:

f. establishing for a connection, a connection table specific for said connection, whereby information in a packet belonging to said connection is compressed in relation to common information in said connection table specific for said connection.

14. In a data processing system that employs packets, a packet having a header which includes at least static and dynamic fields, said static fields including data which is constant during a multi-packet communication interval, said dynamic fields including data which may change for each packet, a method for compressing the contents of said packets for transmission from one portion of the system of another portion of the system, the method comprising:

a. reformatting each packet by placing static fields first in order in each said packet;

b. assembling a table in said one portion of said system that includes all header static field data from at least an initial packet'"'"'s header and associating therewith a code value;

c. identifying header data in a subsequent packet that is common to the static field data in said table and compressing common static field data by selecting a code value associated therewith in said table;

d. if said header of said subsequent packet contains additional static field data not included in said static field data in said table, updating said table to include static field data identical to that contained in said subsequent packet; and

e. transmitting said subsequent packet to a receiving processor in said another portion of said system, the header of said subsequent packet including the code value selected in step a, in lieu of said common static field data.

15. A method for compressing packets in a data communication system, each said packet comprising header fields that include at least static data strings and dynamic data strings,

a. restructuring each header field to segregate static data strings from dynamic data strings,

b. assembling a compression table that includes static data strings from packet headers, and a code value assigned to each static data string;

c. examining a restructured static data string in a header of a new packet to determine if a matching static data string is included in said compression table, and if a match is found, selecting a code value assigned to the matching static data string in said compression table; and

d. substituting said code value selected in step c for said restructured static data string in the header of said new packet when said new packet is transmitted in said data communication system.

16. The method of claim 15, further comprising the added steps of:

e. assembling a connection table for conversations over said system, by entering therein selected dynamic data strings from packets in said conversations;

f. for a packet in a conversation, computing differences between dynamic data strings of said packet and selected dynamic data strings from said conversation in said connection table;

g. entering in said compression table, a static data string from said packets in said conversation and computed differences and assigning a code value thereto;

h. for subsequent packets, repeating step f, and updating said connection table each time, with each subsequent packet'"'"'s selected dynamic data string; and

i. for each subsequent packet, searching said compression table to find a match for a said subsequent packet'"'"'s static data string and said computed differences, and when a match is found, employing a code value, assigned thereto in step g, in lieu thereof, as recited in step (d).

17. The method of claim 16 wherein said selected dynamic data string includes data that is incremented by an integer in succeeding packets during a conversation.

18. The method of claim 15, wherein each said packet header contains a semistatic data field, a first portion thereof including data that changes with every packet and a second portion thereof containing data that remains static over a plurality of packets, said method comprising the added step of:

a1. segregating said second portion of each packet with said data that remains static.

19. The method of claim 15 wherein said data communications system accommodates a plurality of protocols each protocol employing a unique packet structure, wherein said method comprises the added steps of:

e. assembling for each unique packet structure, a user data table and entering therein user-data strings from each said unique packet structure and assigning a code value thereto; and

f. determining if a user data string from a subsequent packet structure matches a user data string in said user data table and if a match is found, substituting for said user data string in said subsequent packet structure, a code value that is assigned to the user data string in said user data table that is found to match.

20. The method of claim 19, including the further step of:

g. inhibiting the substitution of step f if said assigned code value and remaining non-matching user data exhibits a data length longer than all user-data in a said packet.

21. The method of claim 15, wherein said packet contains a checksum field, said method including the further step of:

c1. calculating a new checksum for said packet, subtracting said new checksum value from the value in said checksum field to obtain a difference value and replacing the value in said checksum field with said difference value.