System and method for hash-based forwarding of packets with hierarchically structured variable-length identifiers

• US 9,407,549 B2
• Filed: 10/29/2013
• Issued: 08/02/2016
• Est. Priority Date: 10/29/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Mosko, Marc E., Plass, Michael F.
• Primary Examiner(s): Daniel, Jr., Willie J
• Application Number:
  US14/065,691
• Publication Number:
  US 20150117449A1
• Time in Patent Office: 1,008 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 45/306 Route determination based on the nature of the carried application
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

One embodiment of the present invention provides a system for forwarding packets with hierarchically structured variable-length identifiers (HSVLIs). During operation, the system receiving a packet with an HSVLI. The packet includes a first value and a second value. The first value uniquely represents an interest corresponding to the HSVLI. The second value is derived based on at least a subset of the HSVLI components. The system then makes a forwarding decision for the packet based on the first hash value and second hash value.

Claims

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

receiving, at a packet-forwarding device in a content-centric network, a packet with an HSVLI comprising contiguous name components ordered from a most general level to a most specific level, wherein the packet includes at least a first hash value and a second hash value that are different from the name components;

extracting the first hash value and the second hash value from the received packet, wherein the first hash value and the second hash value are generated by one or more devices separate from the packet-forwarding device, wherein the first hash value uniquely represents an Interest corresponding to the HSVLI, and wherein the second hash value is derived based on at least a subset of the name components of the HSVLI; and

making a forwarding decision for the packet based on the first hash value and the second hash value extracted from the packet.

2. The method of claim 1, wherein the packet is an Interest in a piece of content corresponding to the HSVLI;

wherein the first hash value is a hash derived based on the entire HSVLI and optionally additional information in the packet;

wherein the second hash value is a hash derived on the subset of the HSVLI components; and

wherein the method further comprises updating the second hash value based on a longer prefix match for the HSVLI.

3. The method of claim 1, wherein the packet contains a content object in response to an Interest in the content.

4. The method of claim 1, further comprising maintaining a pending Interest table, wherein a respective entry in the pending Interest table indicates a pending Interest associated with the first hash value and optionally the second hash value.

5. The method of claim 1, further comprising maintaining a forwarding information base, wherein a respective entry in the forwarding information base indicates forwarding information for a packet that contains a particular second value.

6. The method of claim 5, wherein the entry in the forwarding information base further indicates that a longer prefix match exists for the HSVLI.

7. The method of claim 1, wherein the packet is an Interest in the piece of content;

and

wherein the method further comprises searching a local content store for content corresponding to the Interest based on the first hash value and optionally the second hash value.

8. The method of claim 1, wherein the packet contains a content object in response to an Interest in a piece of content corresponding to the HSVLI;

and

wherein the method further comprises updating the second hash value for the packet based on a second hash value of a corresponding Interest packet that is previously received.

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

a processor; and

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

receiving, at a packet-forwarding device in a content-centric network, a packet with an HSVLI comprising contiguous name components ordered from a most general level to a most specific level, wherein the packet includes at least a first hash value and a second hash value that are different from the name components;

extracting the first hash value and the second hash value from the received packet, wherein the first hash value and the second hash value are generated by one or more devices separate from the packet-forwarding device, wherein the first hash value uniquely represents an Interest corresponding to the HSVLI, and wherein the second hash value is derived based on at least a subset of name components of the HSVLI; and

making a forwarding decision for the packet based on the first hash value and the second hash value extracted from the packet.

10. The system of claim 9, wherein the packet is an Interest in a piece of content corresponding to the HSVLI;

wherein the first hash value is a hash derived based on the entire HSVLI and optionally additional information in the packet;

wherein the second hash value is a hash derived on the subset of the HSVLI components; and

wherein the method further comprises updating the second hash value based on a longer prefix match for the HSVLI.

11. The system of claim 9, wherein the packet contains a content object in response to an Interest in the content.

12. The system of claim 9, wherein the method further comprises maintaining a pending Interest table, wherein a respective entry in the pending Interest table indicates a pending Interest associated with the first hash value and optionally the second hash value.

13. The system of claim 9, wherein the method further comprises maintaining a forwarding information base, wherein a respective entry in the forwarding information base indicates forwarding information for a packet that contains a particular second value.

14. The system of claim 13, wherein the entry in the forwarding information base further indicates that a longer prefix match exists for the HSVLI.

15. The system of claim 9, wherein the packet is an Interest in the piece of content;

and

wherein the method further comprises searching a local content store for content corresponding to the Interest based on the first hash value and optionally the second hash value.

16. The system of claim 9, wherein the packet contains a content object in response to an Interest in a piece of content corresponding to the HSVLI;

and

wherein the method further comprises updating the second hash value for the packet based on a second hash value of a corresponding Interest packet that is previously received.

17. A 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:

receiving, at a packet-forwarding device in a content-centric network, a packet with an HSVLI comprising contiguous name components ordered from a most general level to a most specific level, wherein the packet includes at least a first hash value and a second hash value that are different from the name components;

extracting the first hash value and the second hash value from the received packet, wherein the first hash value and the second hash value are generated by one or more devices separate from the packet-forwarding device, wherein the first hash value uniquely represents an Interest corresponding to the HSVLI, and wherein the second hash value is derived based on at least a subset of the name components of the HSVLI; and

making a forwarding decision for the packet based on the first hash value and the second hash value extracted from the packet.

18. The device of claim 17, wherein the packet is an Interest in a piece of content corresponding to the HSVLI;

wherein the first hash value is a hash derived based on the entire HSVLI and optionally additional information in the packet;

wherein the second hash value is a hash derived on the subset of the HSVLI components; and

wherein the method further comprises updating the second hash value based on a longer prefix match for the HSVLI.

19. The device of claim 18, wherein the packet contains a content object in response to an Interest in the content.

20. The device of claim 18, wherein the method further comprises maintaining a pending Interest table, wherein a respective entry in the pending Interest table indicates a pending Interest associated with the first hash value and optionally the second hash value.

21. The device of claim 18, wherein the method further comprises maintaining a forwarding information base, wherein a respective entry in the forwarding information base indicates forwarding information for a packet that contains a particular second value.

22. The device of claim 21, wherein the entry in the forwarding information base further indicates that a longer prefix match exists for the HSVLI.

23. The device of claim 17, wherein the packet is an Interest in the piece of content;

and

wherein the method further comprises searching a local content store for content corresponding to the Interest based on the first hash value and optionally the second hash value.

24. The device of claim 17, wherein the packet contains a content object in response to an Interest in the content;

and

wherein the method further comprises updating the second hash value for the packet based on a second hash value of corresponding Interest packet that is previously received.