System for forwarding a packet with a hierarchically structured variable-length identifier

• US 8,160,069 B2
• Filed: 09/23/2009
• Issued: 04/17/2012
• Est. Priority Date: 01/30/2009
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Jacobson, Van L., Thornton, James D.
• Primary Examiner(s): Wilson, Robert
• Assistant Examiner(s): KAMARA, MOHAMED A
• Application Number:
  US12/565,005
• Publication Number:
  US 20100195653A1
• Time in Patent Office: 937 Days
• Field of Search: 370/390, 370/392, 370/256, 370/400
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

One embodiment provides a system that receives a packet with a hierarchically structured variable-length identifier (HSVLI). An HSVLI indicates a piece or collection of content and may be hierarchically structured, comprising contiguous components ordered from a most general level to a most specific level. The length of a respective identifier is not fixed. During operation, the system converts the HSVLI into a fixed-length key. Subsequently, the system obtains forwarding information based on one or more longest-prefix matches with a longest-prefix-match lookup engine using the fixed-length key. Next, the system forwards the packet to an output port based on the forwarding information.

Claims

1. A method comprising:

receiving on an input port of a computer a packet with a hierarchically structured variable-length identifier (HSVLI),

wherein the HSVLI indicates a piece of content and can be hierarchically structured, comprising contiguous components ordered from a most general level to a most specific level; and

wherein the length of a respective identifier is not fixed;

converting the HSVLI into a fixed-length key;

obtaining forwarding information based on one or more longest-prefix matches with a longest-prefix-match lookup engine using the fixed-length key; and

forwarding the packet to an output port based on the forwarding information.

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

dividing the fixed-length key into c segments s₁, . . . , s_c;

indicating component hashes for first c−

1 components of the HSVLI with segments s₁, . . . , s_c-1; and

indicating a hash over the remaining components of the HSVLI with segment s_c.

3. The method of claim 2, wherein the lengths of the c segments are not equal and wherein the length of a respective segment can be dynamically re-configured.

4. The method of claim 2, further comprising dynamically determining the lengths of the c segments, the number of HSVLI components hashed into each segment, and/or a value to be arithmetically combined with the fixed-length key, based at least on one or more of the initial components of the HSVLI.

5. The method of claim 1, wherein the longest-prefix-match lookup engine is an Internet Protocol (IP) router.

6. The method of claim 1, wherein the fixed-length key has an Internet Protocol version 4 (IPv4) or an Internet Protocol version 6 (IPv6) address format.

7. The method of claim 1, wherein the forwarding information comprises at least one output port.

8. The method of claim 1, wherein a component in the hierarchical structure comprises one or more of:

a globally routable name;

an organizational name;

a version identifier; and

a digest.

9. An apparatus comprising:

a receiving mechanism configured to receive on an input port of a computer a packet with hierarchically structured variable-length identifier HSVLI,

wherein the HSVLI indicates a piece of content and can be hierarchically structured, comprising contiguous components ordered from a most general level to a most specific level; and

wherein the length of a respective identifier is not fixed;

a converting mechanism configured to convert the HSVLI into a fixed-length key;

a forwarding-information-obtaining mechanism configured to obtain forwarding information based on one or more longest-prefix matches with a longest-prefix-match lookup engine using the fixed-length key; and

a packet-forwarding mechanism configured to forward the packet to an output port based on the forwarding information.

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

divide the fixed-length key into c segments s₁, . . . , s_c;

indicate component hashes for first c−

1 components of the HSVLI with segments s₁, . . . , s_c-1; and

indicate a hash over the remaining components of the HSVLI with segment s_c.

11. The apparatus of claim 10, wherein the lengths of the c segments are not equal, and wherein the length of a respective segment can be dynamically re-configured.

12. The apparatus of claim 10, wherein the converting mechanism is further configured to dynamically determine the lengths of the c segments, the number of HSVLI components hashed into each segment, and/or a value to be arithmetically combined with the fixed-length key, based at least on one or more of the initial components of the HSVLI.

13. The apparatus of claim 9, wherein the longest-prefix-match lookup engine is an Internet Protocol (IP) router.

14. The apparatus of claim 9, wherein the fixed-length key has an Internet Protocol version 4 (IPv4) or an Internet Protocol version 6 (IPv6) address format.

15. The apparatus of claim 9, wherein the forwarding information comprises at least one output port.

16. The apparatus of claim 9, wherein a component in the hierarchical structure comprises one or more of:

a globally routable name;

an organizational name;

a version identifier; and

a digest.

17. A computer-readable storage device storing instructions that when executed by a computer cause the computer to perform, the following:

receiving on an input port of a computer a packet comprising an hierarchically structured variable-length identifier (HSVLI),

wherein the HSVLI indicates a piece of content and can be hierarchically structured, comprising contiguous components ordered from a most general level to a most specific level; and

wherein the length of a respective identifier is not fixed;

converting the HSVLI into a fixed-length key;

obtaining forwarding information based on one or more longest-prefix matches with a longest-prefix-match lookup engine using the fixed-length key; and

forwarding the packet to an output port based on the forwarding information.

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

dividing the fixed-length key into c segments s₁, . . . , s_c;

indicating component hashes for first c−

1 components of the HSVLI with segments s₁, . . . , s_c-1; and

indicating a hash over the remaining components of the HSVLI with segment s_c.

19. The device of claim 18, wherein the lengths of the c segments are not equal and wherein the length of a respective segment can be dynamically re-configured.

20. The device of claim 18, wherein the method further comprises dynamically determining the lengths of the c segments, the number of HSVLI components hashed into each segment, and/or a value to be arithmetically combined with the fixed-length key, based at least on one or more of the initial components of the HSVLI.

21. The device of claim 17, wherein the longest-prefix-match lookup engine is an Internet Protocol (IP) router.

22. The method of claim 17, wherein the fixed-length key has an Internet Protocol version 4 (IPv4) or an Internet Protocol version 6 (IPv6) address format.

23. The device of claim 17, wherein the forwarding information comprises at least one output port.

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

a globally routable name;

an organizational name;

a version identifier; and

a digest.