SYSTEM AND METHOD FOR HASH-BASED FORWARDING OF PACKETS WITH HIERARCHICALLY STRUCTURED VARIABLE-LENGTH IDENTIFIERS

• US 20150117449A1
• Filed: 10/29/2013
• Published: 04/30/2015
• 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.
• Granted Patent: US 9,407,549 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• 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 a packet with an HSVLI;

wherein the packet includes a first value and a second value;

wherein the first value uniquely represents an interest corresponding to the HSVLI; and

wherein the second value is derived based on at least a subset of the HSVLI components; and

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

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

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

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

wherein the method further comprises updating the second 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 value and optionally the second 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 value and optionally the second 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 value for the packet based on a second 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 a packet with an HSVLI;

wherein the packet includes a first value and a second value;

wherein the first value uniquely represents an interest corresponding to the HSVLI; and

wherein the second value is derived based on at least a subset of the HSVLI components; and

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

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

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

wherein the second 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 value and optionally the second 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 value and optionally the second 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 value for the packet based on a second 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 a packet with an HSVLI;

wherein the packet includes a first value and a second value;

wherein the first value uniquely represents an interest corresponding to the HSVLI; and

wherein the second value is derived based on at least a subset of the HSVLI components; and

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

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

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

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

wherein the method further comprises updating the second 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 value and optionally the second 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 value and optionally the second 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.