System for forwarding packets with hierarchically structured variable-length identifiers using an exact-match lookup engine

1. A computer executable method for forwarding packets with hierarchically structured variable-length identifiers (HSVLIs), the method comprising:

converting, by a computer, an HSVLI into a number of fixed-length addresses,

wherein the HSVLI identifies a piece of content, and comprises contiguous components ordered in a hierarchy from a most general level of the hierarchy to a most specific level of the hierarchy; and

performing a longest-prefix-match lookup for forwarding a packet associated with the piece of content by performing multiple exact-match lookups based at least on the fixed-length addresses.

2. The method of claim 1 , wherein converting the HSVLI into a number of fixed-length addresses comprises:

generating a number of prefixes of the HSVLI, wherein a respective prefix indicates one or more contiguous components beginning with a component at the most general level; and

converting each prefix of the HSVLI into at least one fixed-length address.

3. The method of claim 2 , wherein converting each prefix comprises:

indicating the number of components in the prefix with a predetermined number of bits out of the fixed-length address; and

indicating a hash value derived from the prefix with the remaining bits of the fixed-length address.

4. The method of claim 2 , wherein performing the effective longest-prefix match comprises:

iteratively performing the following operations, from the shortest prefix to the longest prefix:

determining forwarding information for the fixed-length address corresponding to a respective prefix using an exact-match lookup; and

selecting forwarding information associated with the prefix with the most components, which has been determined with the exact-match lookup.

5. The method of claim 4 , wherein the forwarding information indicates at least one output port.

6. The method of claim 4 , wherein the exact-match lookup returns a result that includes one or more of the following indications:

whether a match is found;

whether a match is found and a further match is available for a prefix with additional components;

the number of additional components needed to obtain a further match for a prefix with additional components; and

a literal value corresponding to a match for the prefix, wherein the literal value can be loaded into a number of reserved bits in the fixed-length address, thereby facilitating subsequent lookups and reducing the chance of address collisions.

7. The method of claim 1 , wherein the exact-match lookup is performed by an exact-match lookup engine; and

wherein the exact-match lookup engine comprises one or more of:

a hash table;

a direct lookup array; and

a binary content-addressable memory (CAM).

8. The method of claim 1 , wherein a respective contiguous component in the HSVLI comprises one or more of:

a globally routable name;

an organizational name;

a version identifier; and

a digest.

9. An apparatus for forwarding packets with hierarchically structured variable-length identifiers (HSVLIs), the apparatus comprising:

a processor;

a memory;

a converting mechanism configured to convert an HSVLI into a number of fixed-length addresses,

wherein the HSVLI identifies a piece of content, and comprises contiguous components ordered in a hierarchy from a most general level of the hierarchy to a most specific level of the hierarchy; and

a lookup mechanism configured to perform a longest-prefix-match lookup for forwarding a packet associated with the piece of content by performing multiple exact-match lookups based at least on the fixed-length addresses.

10. The apparatus of claim 9 , wherein while converting the HSVLI into a number of fixed-length addresses the converting mechanism is configured to:

generate a number of prefixes of the HSVLI, wherein a respective prefix indicates one or more contiguous components beginning with a component at the most general level; and

convert each prefix of the HSVLI into at least one fixed-length address.

11. The apparatus of claim 10 , wherein while converting each prefix the converting mechanism is configured to:

indicate the number of components in the prefix with a predetermined number of bits out of the fixed-length address; and

indicate a hash value derived from the prefix with the remaining bits of the fixed-length address.

12. The apparatus of claim 10 , wherein while performing the effective longest-prefix match, the matching mechanism is configured to:

iteratively perform the following operations, from the shortest prefix to the longest prefix:

determine forwarding information for the fixed-length address corresponding to a respective prefix using an exact-match lookup; and

select forwarding information associated with the prefix with the most components, which has been determined with the exact-match lookup.

13. The apparatus of claim 12 , wherein the exact-match lookup returns a result that includes one or more of the following indications:

whether a match is found;

whether a match is found and a further match is available for a prefix with additional components;

the number of additional components needed to obtain a further match for a prefix with additional components; and

a literal value corresponding to a match for the prefix, wherein the literal value can be loaded into a number of reserved bits in the fixed-length address, thereby facilitating subsequent lookups and reducing the chance of address collisions.

14. The apparatus of claim 12 , wherein the forwarding information indicates at least one output port.

15. The apparatus of claim 9 , wherein the exact-match lookup is performed by an exact-match lookup engine; and

wherein the exact-match lookup engine comprises one or more of:

a hash table;

a direct lookup array; and

a binary content-addressable memory (CAM).

16. The apparatus of claim 9 , wherein a respective contiguous component in the HSVLI comprises one or more of:

a globally routable name;

an organizational name;

a version identifier; and

a digest.

17. A non-transitory computer-readable storage device storing instructions that when executed by a computer cause the computer to perform a method for forwarding packets with hierarchically structured variable-length identifiers (HSVLIs), the method comprising:

converting an HSVLI into a number of fixed-length addresses,

wherein the HSVLI identifies a piece of content, and comprises contiguous components ordered in a hierarchy from a most general level of the hierarchy to a most specific level of the hierarchy; and

performing an effective longest-prefix-match lookup by performing multiple exact-match lookups based at least on the fixed-length addresses.

18. The device of claim 17 , wherein converting the HSVLI into a number of fixed-length addresses comprises:

generating a number of prefixes of the HSVLI,

wherein a respective prefix indicates one or more contiguous components beginning with a component at the most general level; and

converting each prefix of the HSVLI into at least one fixed-length address.

19. The device of claim 18 , wherein converting each prefix comprises:

indicating the number of components in the prefix with a predetermined number of bits out of the fixed-length address; and

indicating a hash value derived from the prefix with the remaining bits of the fixed-length address.

20. The device of claim 18 , wherein performing the effective longest-prefix match using comprises:

iteratively performing the following operations, from the shortest prefix to the longest prefix:

determining forwarding information for the fixed-length address corresponding to a respective prefix using an exact-match lookup; and

selecting forwarding information associated with the prefix with the most components, which has been determined with the exact-match lookup.

21. The device of claim 20 , wherein the exact-match lookup returns a result that includes one or more of the following indications:

whether a match is found;

whether a match is found and a further match is available for a prefix with additional components;

the number of additional components needed to obtain a further match for a prefix with additional components; and

a literal value corresponding to a match for the prefix, wherein the literal value can be loaded into a number of reserved bits in the fixed-length address, thereby facilitating subsequent lookups and reducing the chance of address collisions.

22. The device of claim 20 , wherein the forwarding information indicates at least one output port.

23. The device of claim 17 , wherein the exact-match lookup is performed by an exact-match lookup engine; and

wherein the exact-match lookup engine comprises one or more of:

a hash table;

a direct lookup array; and

a binary content-addressable memory (CAM).

24. The device of claim 17 , wherein a respective contiguous component in the hierarchical HSVLI comprises one or more of:

a globally routable name;

an organizational name;

a version identifier; and

a digest.