System for forwarding a packet with a hierarchically structured variable-length identifier
View Patent ↗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.
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 1 , . . . , s c ;
indicating component hashes for first c−1 components of the HSVLI with segments s 1 , . . . , 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 1 , . . . , s c ;
indicate component hashes for first c−1 components of the HSVLI with segments s 1 , . . . , 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 1 , . . . , s c ;
indicating component hashes for first c−1 components of the HSVLI with segments s 1 , . . . , 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.