CCN routing using hardware-assisted hash tables

• US 9,590,948 B2
• Filed: 12/15/2014
• Issued: 03/07/2017
• Est. Priority Date: 12/15/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Systems, Inc.
• Inventors: Mosko, Marc E., Solis, Ignacio
• Primary Examiner(s): Anwar, Mohammad
• Assistant Examiner(s): Detse, Kokou R
• Application Number:
  US14/570,144
• Publication Number:
  US 20160173445A1
• Time in Patent Office: 813 Days
• Field of Search: 370/392
• US Class Current: 1/1
• CPC Class Codes: H04L 2101/30 Types of network names
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 45/748 using longest matching prefix
• CPC Class Codes: H04L 61/3005 Mechanisms for avoiding name conflicts
• CPC Class Codes: H04L 61/4552 Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

One embodiment provides a system that facilitates forwarding of packets with variable length names. During operation, the system receives a packet with a hierarchically structured variable length identifier (HSVLI) which comprises contiguous name components ordered from a most general level to a most specific level. The system performs a longest prefix match lookup by selecting an entry from a first data structure of entries. The entries indicate a name component, forwarding information for the name component, and a plurality of entry identifiers that chain an entry to another entry. If a size of the name component is less than or equal to a predetermined threshold, the system selects an entry based on the name component. If the size is greater, the system selects an entry based on a compressed key which can be a hash of the name component. The system also resolves collisions associated with the selected entry.

Claims

1. A computer-implemented method forforwarding packets, comprising:

receiving, by a computer, a packet with a hierarchically structured variable length identifier (HSVLI) which comprises contiguous name components ordered from a most general level to a most specific level; and

performing a longest prefix match lookup for forwarding the packet by selecting an entry from a first data structure of entries, wherein a respective entry indicates a name component, forwarding information for the name component, and a plurality of entry identifiers that chain the respective entry to another entry, wherein performing the longest prefix match lookup further comprises;

determining a size of a name component;

if the size of the name component is less than or equal to a predetermined threshold, selecting a first entry based on the name component;

if the size of the name component is greater than the predetermined threshold;

compressing the name component to obtain a compressed key;

selecting a second entry based on the compressed key; and

in response to determining a lookup collision associated with the selected second entry, wherein the lookup collision indicates that the compressed key and another compressed key both return a same entry when performing the lookup in the first data structure of entries, resolving the lookup collision based on a new lookup key, thereby facilitating forwarding of packets with variable length names.

2. The method of claim 1,

wherein if the size of the name component is less than or equal to the predetermined threshold, the method further comprises creating the first entry in the first data structure based on the name component;

and

wherein if the size of the name component is greater than the predetermined threshold, the method further comprises;

performing a first compression function on the name component to obtain the compressed key;

creating the second entry in the first data structure based on the compressed key; and

in response to determining an insertion collision based on the created second entry, wherein the insertion collision indicates that the compressed key and another compressed key both return a same entry when creating the second entry in the first data structure of entries, resolving the insertion collision based on the new lookup key.

3. The method of claim 2, wherein if the size of the name component is greater than the predetermined threshold, the method further comprises:

creating a third entry in a second data structure based on the name component, wherein the second data structure indicates the name component and a corresponding index; and

setting a string identifier in the created second entry for the name component in the first data structure to the corresponding index for the created third entry in the second data structure.

4. The method of claim 2, wherein resolving the insertion collision further comprises:

including a collision indicator in the created second entry in the first data structure;

performing a second compression function on the name component to obtain the new lookup key; and

creating a fourth entry in a third data structure based on the new lookup key, wherein the third data structure indicates the new lookup key and forwarding information for the name component.

5. The method of claim 4, wherein resolving the lookup collision further comprises:

determining that the selected second entry includes the collision indicator;

performing the second compression function on the name component to obtain the new lookup key; and

selecting a fifth entry in the third data structure based on the new lookup key.

6. The method of claim 3, further comprising:

in response to selecting the second entry in the first data structure based on the compressed key, determining a string identifier for the selected second entry;

retrieving, from the second data structure, the name component based on the determined string identifier; and

comparing the name component of the HSVLI with the retrieved name component from the second data structure.

7. The method of claim 1, wherein the plurality of entry identifiers includes a parent identifier and an entry identifier, wherein the entry identifier is unique for each entry in the first data structure, and wherein selecting the entry further comprises:

for each name component, beginning with a name component at the most general level, selecting the entry from the first data structure of entries based on the parent identifier, wherein;

for the most general level name component, the parent identifier of the selected entry corresponds to a predetermined initial value; and

for each subsequent name component, the parent identifier of the selected entry corresponds to the entry identifier of an entry corresponding to the name component of a previous most general level.

8. The method of claim 1, wherein the first data structure is a hash table of entries comprised of a key and a result, wherein:

if the size is less than or equal to the predetermined threshold, the key is based on the name component directly; and

if the size is greater than the predetermined threshold, the key is based on the compressed key.

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

receiving, by the computer, a packet with a hierarchically structured variable length identifier (HSVLI) which comprises contiguous name components ordered from a most general level to a most specific level; and

performing a longest prefix match lookup for forwarding the packet by selecting an entry from a first data structure of entries, wherein a respective entry indicates a name component, forwarding information for the name component, and a plurality of entry identifiers that chain the respective entry to another entry, wherein performing the longest prefix match lookup further comprises;

determining a size of a name component;

if the size of the name component is less than or equal to a predetermined threshold, selecting a first entry based on the name component;

if the size of the name component is greater than the predetermined threshold;

compressing the name component to obtain a compressed key;

selecting a second entry based on the compressed key; and

in response to determining a lookup collision associated with the selected second entry, wherein the lookup collision indicates that the compressed key and another compressed key both return a same entry when performing the lookup in the first data structure of entries, resolving the lookup collision based on a new lookup key, thereby facilitating forwarding of packets with variable length names.

10. The storage medium of claim 9,

wherein if the size of the name component is less than or equal to the predetermined threshold, the method further comprises creating the first entry in the first data structure based on the name component;

and

wherein if the size of the name component is greater than the predetermined threshold, the method further comprises;

performing a first compression function on the name component to obtain the compressed key;

creating the second entry in the first data structure based on the compressed key; and

in response to determining an insertion collision based on the created second entry, wherein the insertion collision indicates that the compressed key and another compressed key both return a same entry when creating the second entry in the first data structure of entries, resolving the insertion collision based on the new lookup key.

11. The storage medium of claim 10, wherein if the size of the name component is greater than the predetermined threshold, the method further comprises:

creating a third entry in a second data structure based on the name component, wherein the second data structure indicates the name component and a corresponding index; and

setting a string identifier in the created second entry for the name component in the first data structure to the corresponding index for the created third entry in the second data structure.

12. The storage medium of claim 10, wherein resolving the insertion collision further comprises:

including a collision indicator in the created second entry in the first data structure;

performing a second compression function on the name component to obtain the new lookup key; and

creating a fourth entry in a third data structure based on the new lookup key, wherein the third data structure indicates the new lookup key and forwarding information for the name component.

13. The storage medium of claim 12, wherein resolving the lookup collision further comprises:

determining that the selected second entry includes the collision indicator;

performing the second compression function on the name component to obtain the new lookup key; and

selecting a fifth entry in the third data structure based on the new lookup key.

14. The storage medium of claim 11, wherein the method further comprises:

in response to selecting the second entry in the first data structure based on the compressed key, determining a string identifier for the selected second entry;

retrieving, from the second data structure, the name component based on the determined string identifier; and

comparing the name component of the HSVLI with the retrieved name component from the second data structure.

15. The storage medium of claim 9, wherein the plurality of entry identifiers includes a parent identifier and an entry identifier, wherein the entry identifier is unique for each entry in the first data structure, and wherein selecting the entry further comprises:

for each name component, beginning with a name component at the most general level, selecting the entry from the first data structure of entries based on the parent identifier, wherein;

for the most general level name component, the parent identifier of the selected entry corresponds to a predetermined initial value; and

for each subsequent name component, the parent identifier of the selected entry corresponds to the entry identifier of an entry corresponding to the name component of a previous most general level.

16. The storage medium of claim 9, wherein the first data structure is a hash table of entries comprised of a key and a result, wherein:

if the size is less than or equal to the predetermined threshold, the key is based on the name component directly; and

if the size is greater than the predetermined threshold, the key is based on the compressed key.

17. A computer system for forwarding content, the system comprising:

a processor;

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

receiving, by the computer, a packet with a hierarchically structured variable length identifier (HSVLI) which comprises contiguous name components ordered from a most general level to a most specific level; and

performing a longest prefix match lookup for forwarding the packet by selecting an entry from a first data structure of entries, wherein a respective entry indicates a name component, forwarding information for the name component, and a plurality of entry identifiers that chain the respective entry to another entry, wherein performing the longest prefix match lookup further comprises;

determining a size of a name component;

if the size of the name component is less than or equal to a predetermined threshold, selecting a first entry based on the name component;

if the size of the name component is greater than the predetermined threshold;

compressing the name component to obtain a compressed key;

selecting a second entry based on the compressed key; and

in response to determining a lookup collision associated with the selected second entry, wherein the lookup collision indicates that the compressed key and another compressed key both return a same entry when performing the lookup in the first data structure of entries, resolving the lookup collision based on a new lookup key, thereby facilitating forwarding of packets with variable length names.

18. The computer system of claim 17,

wherein if the size of the name component is less than or equal to the predetermined threshold, the method further comprises creating the first entry in the first data structure based on the name component;

and

wherein if the size of the name component is greater than the predetermined threshold, the method further comprises;

performing a first compression function on the name component to obtain the compressed key;

creating the second entry in the first data structure based on the compressed key; and

in response to determining an insertion collision based on the created second entry, wherein the insertion collision indicates that the compressed key and another compressed key both return a same entry when creating the second entry in the first data structure of entries, resolving the insertion collision based on the new lookup key.

19. The computer system of claim 18, wherein if the size of the name component is greater than the predetermined threshold, the method further comprises:

creating a third entry in a second data structure based on the name component, wherein the second data structure indicates the name component and a corresponding index; and

setting a string identifier in the created second entry for the name component in the first data structure to the corresponding index for the created third entry in the second data structure.

20. The computer system of claim 18, wherein resolving the insertion collision further comprises:

including a collision indicator in the created second entry in the first data structure;

performing a second compression function on the name component to obtain the new lookup key; and

creating a fourth entry in a third data structure based on the new lookup key, wherein the third data structure indicates the new lookup key and forwarding information for the name component.

21. The computer system of claim 20, wherein resolving the lookup collision further comprises:

determining that the selected second entry includes the collision indicator;

performing the second compression function on the name component to obtain the new lookup key; and

selecting a fifth entry in the third data structure based on the new lookup key.

22. The computer system of claim 19, wherein the method further comprises:

in response to selecting the second entry in the first data structure based on the compressed key, determining a string identifier for the selected second entry;

retrieving, from the second data structure, the name component based on the determined string identifier; and

comparing the name component of the HSVLI with the retrieved name component from the second data structure.

23. The computer system of claim 17, wherein the plurality of entry identifiers includes a parent identifier and an entry identifier, wherein the entry identifier is unique for each entry in the first data structure, and wherein selecting the entry further comprises:

for each name component, beginning with a name component at the most general level, selecting the entry from the first data structure of entries based on the parent identifier, wherein;

for the most general level name component, the parent identifier of the selected entry corresponds to a predetermined initial value; and

for each subsequent name component, the parent identifier of the selected entry corresponds to the entry identifier of an entry corresponding to the name component of a previous most general level.

24. The computer system of claim 17, wherein the first data structure is a hash table of entries comprised of a key and a result, wherein:

if the size is less than or equal to the predetermined threshold, the key is based on the name component directly; and

if the size is greater than the predetermined threshold, the key is based on the compressed key.