Ccn routing using hardware-assisted hash tables

Patent metadata

Field	Value
Publication number	US-2016173445-A1
Application number	US-201414570144-A
Country	US
Kind code	A1
Filing date	Dec 15, 2014
Priority date	Dec 15, 2014
Publication date	Jun 16, 2016
Grant date	—

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.

First claim

What is claimed is:

1 . A computer-implemented method for forwarding 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; performing a longest prefix match lookup for forwarding the packet by selecting an entry from a first data structure of entries that indicate a name component, forwarding information for the name component, and a plurality of entry identifiers that chain an entry to another entry, by:
in response to determining that a size of a name component is less than or equal to a predetermined threshold, selecting an entry based on the name component;
in response to determining that the size is greater than the predetermined threshold:
compressing the name component to obtain a compressed key; and
selecting an entry based on the compressed key; and

in response to determining a lookup collision associated with the selected entry, resolving the lookup collision, thereby facilitating forwarding of packets with variable length names.

2 . The method of claim 1 , further comprising:
in response to determining that the size of the name component is less than or equal to the predetermined threshold, creating an entry in the first data structure based on the name component; and in response to determining that the size of the name component is greater than the predetermined threshold:
performing a first compression function on the name component to obtain a compressed key; and
creating an entry in the first data structure based on the compressed key; and
in response to determining an insertion collision based on the created entry, resolving the insertion collision.

3 . The method of claim 2 , further comprising:
creating an entry in a second data structure based on the name component, wherein the second data structure indicates the name component and a corresponding index; setting a string identifier in the entry for the name component in the first data structure to the corresponding index for the created entry in the second data structure.

4 . The method of claim 2 , wherein resolving the insertion collision comprises:
including a collision indicator in the created entry in the first data structure; performing a second compression function on the name component to obtain a new lookup key; creating an 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 entry includes the collision indicator; performing the second compression function on the name component to obtain the new lookup key; and selecting an 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 entry in the first data structure based on the compressed key, determining a string identifier for the selected entry; retrieving, from the second data structure, the name component based on the determined string identifier; 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 component at the most general level, selecting the entry based on the parent identifier, wherein:
for the most general level name component, the parent identifier of the entry corresponds to a predetermined initial value; and
for each subsequent name component, the parent identifier of the 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 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; performing a longest prefix match lookup for forwarding the packet by selecting an entry from a first data structure of entries that indicate a name component, forwarding information for the name component, and a plurality of entry identifiers that chain an entry to another entry, by:
in response to determining that a size of a name component is less than or equal to a predetermined threshold, selecting an entry based on the name component;
in response to determining that the size is greater than the predetermined threshold:
compressing the name component to obtain a compressed key; and
selecting an entry based on the compressed key; and

in response to determining a lookup collision associated with the selected entry, resolving the lookup collision, thereby facilitating forwarding of packets with variable length names.

10 . The storage medium of claim 9 , wherein the method further comprises:
in response to determining that the size of the name component is less than or equal to the predetermined threshold, creating an entry in the first data structure based on the name component; and in response to determining that the size of the name component is greater than the predetermined threshold:
performing a first compression function on the name component to obtain a compressed key; and
creating an entry in the first data structure based on the compressed key; and
in response to determining an insertion collision based on the created entry, resolving the insertion collision.

11 . The storage medium of claim 10 , wherein the method further comprises:
creating an entry in a second data structure based on the name component, wherein the second data structure indicates the name component and a corresponding index; setting a string identifier in the entry for the name component in the first data structure to the corresponding index for the created entry in the second data structure.

12 . The storage medium of claim 10 , wherein resolving the insertion collision comprises:
including a collision indicator in the created entry in the first data structure; performing a second compression function on the name component to obtain a new lookup key; creating an 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 entry includes the collision indicator; performing the second compression function on the name component to obtain the new lookup key; and selecting an 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 r

Assignees

• Palo Alto Res Ct Inc

Inventors

• Mosko Marc E
• Solis Ignacio

Classifications

• H04L61/1552

  Electricity · mapped topic

• H04L67/327

  Electricity · mapped topic

• H04L61/303

  Electricity · mapped topic

• H04L45/748 Primary

  using longest matching prefix · CPC title

• H04L45/7453

  using hashing · CPC title