Header compression for CCN messages using dictionary learning

• US 10,009,446 B2
• Filed: 11/02/2015
• Issued: 06/26/2018
• Est. Priority Date: 11/02/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): Hsu, Alpus H
• Assistant Examiner(s): Thai, Camquyen
• Application Number:
  US14/929,994
• Publication Number:
  US 20170126850A1
• Time in Patent Office: 967 Days
• Field of Search: None
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 5/0055 Physical resource allocation for ACK/NACK for physical mapping arrangements in ARQ protocols H04L1/1861
• 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 identifies a type, length, and value (TLV) string in a packet and, in response, generates a compressed representation of the TLV string. The system stores the compressed representation for the TLV string in an entry of a learned dictionary in a storage device of the first node. The system then sends the entry to a second node and, in response, receives an acknowledgement from the second node. If the system identifies the TLV string in a subsequent second packet of the acknowledgement, the system compresses the TLV string in the second packet based on the compressed representation.

Claims

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

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

storing the compressed representation for the TLV string in an entry of a learned dictionary in a storage device of a first node, wherein the compressed representation in the entry is a compressed counter comprising a compressor key, and wherein the compressor key is mapped to a type of the TLV string and a base value in the entry;

sending from the first node the entry to a second node;

receiving, by the first node, an acknowledgement from the second node; and

in response to identifying the TLV string in a subsequent second packet of the acknowledgement, compressing the TLV string in the second packet based on the compressed representation, wherein compressing the TLV string in the second packet further comprises;

calculating an offset based on a value in the TLV string and the base value; and

replacing the TLV string with the compressor key and the offset.

2. The method of claim 1, wherein the compressed representation in the entry is a compressed replacement string, wherein the compressed replacement string is mapped to the TLV string in the entry;

and

wherein compressing the TLV string in the second packet further comprises replacing the TLV string with the compressed replacement string.

3. The method of claim 2, wherein a length of the compressed replacement string is proportional to a length of the TLV string in the entry.

4. 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.

5. The method of claim 4, wherein the TLV string is one of:

a Key Identifier;

a Public Key;

a Certificate; and

a Name Prefix.

6. The method of claim 1, wherein the first and second nodes store a static dictionary, wherein the static dictionary maps a type and length (TL) string to a compressed replacement TL string, and wherein the acknowledgement from the second node includes one or more compressed replacement TL strings compressed based on the static dictionary.

7. The method of claim 1, wherein the entry is timed out in response to inactivity over a period of time.

8. The method of claim 1, wherein the TLV string in the packet is a concatenation of a plurality of TLV strings.

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;

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

storing the compressed representation for the TLV string in an entry of a learned dictionary in a storage device of a first node, wherein the compressed representation in the entry is a compressed counter comprising a compressor key, and wherein the compressor key is mapped to a type of the TLV string and a base value in the entry;

sending from the first node the entry to a second node;

receiving, by the first node, an acknowledgement from the second node; and

in response to identifying the TLV string in a subsequent second packet of the acknowledgement, compressing the TLV string in the second packet based on the compressed representation, wherein compressing the TLV string in the second packet further comprises;

calculating an offset based on a value in the TLV string and the base value; and

replacing the TLV string with the compressor key and the offset.

10. The computer system of claim 9, wherein the compressed representation in the entry is a compressed replacement string, wherein the compressed replacement string is mapped to the TLV string in the entry;

and

wherein compressing the TLV string in the second packet further comprises replacing the TLV string with the compressed replacement string.

11. The computer system of claim 10, wherein a length of the compressed replacement string is proportional to a length of the TLV string in the entry.

12. 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.

13. The computer system of claim 12, wherein the TLV string is one of:

a Key Identifier;

a Public Key;

a Certificate; and

a Name Prefix.

14. The computer system of claim 9, wherein the first and second nodes store a static dictionary, wherein the static dictionary maps a type and length (TL) string to a compressed replacement TL string, and wherein the acknowledgement from the second node includes one or more compressed replacement TL strings compressed based on the static dictionary.

15. The computer system of claim 9, wherein the entry is timed out in response to inactivity over a period of time.

16. The computer system of claim 9, wherein the TLV string in the packet is a concatenation of a plurality of TLV strings.

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:

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

storing the compressed representation for the TLV string in an entry of a learned dictionary in a storage device of a first node, wherein the compressed representation in the entry is a compressed counter comprising a compressor key, and wherein the compressor key is mapped to a type of the TLV string and a base value in the entry;

sending from the first node the entry to a second node;

receiving, by the first node, an acknowledgement from the second node; and

in response to identifying the TLV string in a subsequent second packet of the acknowledgement, compressing the TLV string in the second packet based on the compressed representation, wherein compressing the TLV string in the second packet further comprises;

calculating an offset based on a value in the TLV string and the base value; and

replacing the TLV string with the compressor key and the offset.

18. The non-transitory computer-readable 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 non-transitory computer-readable storage medium of claim 17, wherein the compressed representation in the entry is a compressed replacement string, wherein the compressed replacement string is mapped to the TLV string in the entry;

and

wherein compressing the TLV string in the second packet further comprises replacing the TLV string with the compressed replacement string.

20. The non-transitory computer-readable storage medium of claim 19, wherein a length of the compressed replacement string is proportional to a length of the TLV string in the entry.