Bit-aligned header compression for CCN messages using dictionary

• US 10,021,222 B2
• Filed: 11/04/2015
• Issued: 07/10/2018
• Est. Priority Date: 11/04/2015
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Mosko, Marc E.
• Primary Examiner(s): Baturay, Alicia
• Application Number:
  US14/932,588
• Publication Number:
  US 20170126854A1
• Time in Patent Office: 979 Days
• Field of Search: 709227
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

One embodiment provides a system in a first node that facilitates efficient packet forwarding. During operation, the system stores, in a storage device in a first node, a static dictionary comprising a mapping between a type and length (TL) string and a byte-aligned compressed replacement string. The system encodes the byte-aligned compressed replacement string based on an encoding technique to generate a bit-aligned encoded replacement string and stores a mapping between the encoded replacement string and the TL string in an encoded dictionary. If the system identifies the TL string in a packet, the system replaces the TL string with the encoded replacement string and transmits the packet to a second node storing the encoded dictionary in a local storage device, thereby facilitating bit-aligned compression of a TL string.

Claims

1. A computer-implemented method for efficient packet forwarding, the method comprising:

storing, in a storage device in a first node, a static dictionary comprising a mapping between a type and length (TL) string and a byte-aligned compressed replacement string;

encoding the byte-aligned compressed replacement string based on an encoding technique to generate a bit-aligned encoded replacement string that includes a variable length value encoded as a prefix indicating a start of a range of values and a number of bits;

storing a mapping between the encoded replacement string and the TL string in an encoded dictionary;

in response to identifying the TL string in a packet, replacing the TL string with the encoded replacement string; and

transmitting the packet to a second node storing the encoded dictionary in a local storage device, thereby facilitating bit-aligned compression of the TL string.

2. The method of claim 1, wherein the packet is a content-centric network (CCN) message, and wherein a name for the CCN message is a hierarchically structured variable length identifier (HSVLI) which comprises contiguous name components ordered from a most general level to a most specific level;

wherein the method further comprises replacing a fixed header of the CCN message with a compressed fixed header.

3. The method of claim 1, further comprising:

generating a compressed representation of a type, length, and value (TLV) string in response to identifying the TLV string in the packet;

storing the compressed representation for the TLV string in a learned dictionary in the storage device of the first node;

in response to identifying the TLV string in a subsequent second packet, compressing the TLV string in the second packet based on the compressed representation.

4. The method of claim 3, further comprising, in response to not matching a TL pair of the packet in the static, encoded, and learned dictionaries, compacting the TL pair using a shorter bit length representation of a type and length of the TL pair.

5. The method of claim 3, wherein an entry in the static, encoded, or learned dictionary includes an identifying pattern, wherein the pattern indicates to which dictionary the entry belongs.

6. The method of claim 1, wherein the encoding is based on Huffman encoding.

7. The method of claim 6, wherein a Huffman code represents one or more of:

a fixed type and a fixed length;

a series of TL pairs with no intermediate value;

a fixed type and a specified bit length, wherein the Huffman code is followed by a specified number of bits; and

a fixed type and a variable bit length, wherein the Huffman code is followed by the variable length value.

8. The method of claim 7, wherein the variable bit length is calculated as a summation of the start of the range and a value represented by the number of bits.

9. A computer system for facilitating forwarding of packets, the system comprising:

a processor; and

a storage device storing instructions that when executed by the processor cause the processor to perform a method, the method comprising;

storing, in a storage device in a first node, a static dictionary comprising a mapping between a type and length (TL) string and a byte-aligned compressed replacement string;

encoding the byte-aligned compressed replacement string based on an encoding technique to generate a bit-aligned encoded replacement string that includes a variable length value encoded as a prefix indicating a start of a range of values and a number of bits;

storing a mapping between the encoded replacement string and the TL string in an encoded dictionary;

in response to identifying the TL string in a packet, replacing the TL string with the encoded replacement string; and

transmitting the packet to a second node storing the encoded dictionary in a local storage device, thereby facilitating bit-aligned compression of the TL string.

10. The computer system of claim 9, wherein the packet is a content-centric network (CCN) message, and wherein a name for the CCN message is a hierarchically structured variable length identifier (HSVLI) which comprises contiguous name components ordered from a most general level to a most specific level;

wherein the method further comprises replacing a fixed header of the CCN message with a compressed fixed header.

11. The computer system of claim 9, wherein the method further comprises:

generating a compressed representation of a type, length, and value (TLV) string in response to identifying the TLV string in the packet;

storing the compressed representation for the TLV string in a learned dictionary in the storage device of the first node;

in response to identifying the TLV string in a subsequent second packet, compressing the TLV string in the second packet based on the compressed representation.

12. The computer system of claim 11, wherein the method further comprises, in response to not matching a TL pair of the packet in the static, encoded, and learned dictionaries, compacting the TL pair using a shorter bit length representation of a type and length of the TL pair.

13. The computer system of claim 11, wherein an entry in the static, encoded, or learned dictionary includes an identifying pattern, wherein the pattern indicates to which dictionary the entry belongs.

14. The computer system of claim 9, wherein the encoding is based on Huffman encoding.

15. The computer system of claim 14, wherein a Huffman code represents one or more of:

a fixed type and a fixed length;

a series of TL pairs with no intermediate value;

a fixed type and a specified bit length, wherein the Huffman code is followed by a specified number of bits; and

a fixed type and a variable bit length, wherein the Huffman code is followed by the variable length value.

16. The computer system of claim 15, wherein the variable bit length is calculated as a summation of the start of the range and a value represented by the number of bits.

17. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:

storing, in a storage device in a first node, a static dictionary comprising a mapping between a type and length (TL) string and a byte-aligned compressed replacement string;

encoding the byte-aligned compressed replacement string based on an encoding technique to generate a bit-aligned encoded replacement string that includes a variable length value encoded as a prefix indicating a start of a range of values and a number of bits;

storing a mapping between the encoded replacement string and the TL string in an encoded dictionary;

in response to identifying the TL string in a packet, replacing the TL string with the encoded replacement string; and

transmitting the packet to a second node storing the encoded dictionary in a local storage device, thereby facilitating bit-aligned compression of the TL string.

18. The storage medium of claim 17, wherein the packet is a content-centric network (CCN) message, and wherein a name for the CCN message is a hierarchically structured variable length identifier (HSVLI) which comprises contiguous name components ordered from a most general level to a most specific level;

wherein the method further comprises replacing a fixed header of the CCN message with a compressed fixed header.

19. The storage medium of claim 17, wherein the method further comprising:

generating a compressed representation of a type, length, and value (TLV) string in response to identifying the TLV string in the packet;

storing the compressed representation for the TLV string in a learned dictionary in the storage device of the first node;

in response to identifying the TLV string in a subsequent second packet, compressing the TLV string in the second packet based on the compressed representation.

20. The storage medium of claim 17, wherein the encoding is based on Huffman encoding.