System and method for packet forwarding using a conjunctive normal form strategy in a content-centric network

• US 9,391,896 B2
• Filed: 03/10/2014
• Issued: 07/12/2016
• Est. Priority Date: 03/10/2014
• 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.
• Primary Examiner(s): SMARTH, GERALD A
• Application Number:
  US14/202,984
• Publication Number:
  US 20150256460A1
• Time in Patent Office: 855 Days
• Field of Search: 370/392
• US Class Current: 1/1
• CPC Class Codes: H04L 45/748 using longest matching prefix

Abstract

One embodiment of the present invention provides a system for forwarding packets with hierarchically structured variable-length identifiers (HSVLIs) in a content-centric network (CCN). During operation, the system receives a packet with an HSVLI and determines, based on the HSVLI, a plurality of ports to which the packet should be forwarded. The plurality of ports include a set of individual port groups, and a respective port group includes one or more individual physical ports. The system derives a forwarding strategy based on the set of individual port groups and the one or more individual physical ports. The forwarding strategy is expressed as a formula in conjunctive normal form that indicates a logical conjunction among the set of port groups and a logical disjunction among the one or more individual physical ports. The system then forwards the packet using the derived forwarding strategy.

Claims

1. A computer-executable method for forwarding packets with hierarchically structured variable-length identifiers (HSVLIs) in a content-centric network (CCN), the method comprising:

receiving a packet with an HSVLI;

determining, based on the HSVLI, a set of standalone physical ports;

determining, based on the HSVLI, a set of virtual port groups, wherein a respective virtual port group includes one or more individual physical ports;

deriving a forwarding strategy expressed as a formula in conjunctive normal form that indicates a logical conjunction among the standalone physical ports and the virtual port groups, and wherein the respective virtual port group is expressed as a logical disjunction among the one or more individual physical ports belonging to the virtual port group; and

forwarding the packet using the derived forwarding strategy.

2. The method of claim 1, wherein the packet is an interest in a piece of content corresponding to the HSVLI, wherein determining the set of standalone physical ports and the set of virtual port groups involves performing a longest-match lookup in a forwarding information base.

3. The method of claim 2, wherein performing the longest-match lookup involves calculating a fixed-length hash function of the HSVLI.

4. The method of claim 1, wherein the set of virtual port groups include a link aggregation group (LAG), and wherein the method further comprises using a scheduler associated with the LAG to make forwarding decisions among multiple physical ports associated with the LAG.

5. The method of claim 1, wherein the set of virtual port groups include a multi-path port group generated by a higher-level routing protocol, and wherein the method further comprises using the higher-level routing protocol to make forwarding decisions among multiple physical ports associated with the multi-path port group.

6. The method of claim 1, wherein the forwarding strategy specifies that the packet is to be forwarded to each and every standalone physical port and to at least one individual physical port within the respective virtual port group.

7. The method of claim 6, wherein the forwarding strategy further specifies that the packet is to be forwarded to a minimum number of physical ports among ports within the set of virtual port groups.

8. A system for forwarding packets with hierarchically structured variable-length identifiers (HSVLIs) in a content-centric network (CCN), 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;

determining, based on the HSVLI, a set of standalone physical ports;

determining, based on the HSVLI, a set of virtual port groups, wherein a respective virtual port group includes one or more individual physical ports;

deriving a forwarding strategy expressed as a formula in conjunctive normal form that indicates a logical conjunction among the standalone physical ports and the virtual port groups, and wherein the respective virtual port group is expressed as a logical disjunction among the one or more individual physical ports belonging to the respective virtual port group; and

forwarding the packet using the derived forwarding strategy.

9. The system of claim 8, wherein the packet is an interest in a piece of content corresponding to the HSVLI, wherein determining the set of standalone physical ports and the set of virtual port groups involves performing a longest-match lookup in a forwarding information base.

10. The system of claim 9, wherein performing the longest-match lookup involves calculating a fixed-length hash function of the HSVLI.

11. The system of claim 8, wherein the set of virtual port groups include a link aggregation group (LAG), and wherein the method further comprises using a scheduler associated with the LAG to make forwarding decisions among multiple physical ports associated with the LAG.

12. The system of claim 8, wherein the set of virtual port groups include a multi-path port group generated by a higher-level routing protocol, and wherein the method further comprises using the higher-level routing protocol to make forwarding decisions among multiple physical ports associated with the multi-path port group.

13. The system of claim 8, wherein the forwarding strategy specifies that the packet is to be forwarded to each and every standalone physical port and to at least one individual physical port within the respective virtual port group.

14. The system of claim 13, wherein the forwarding strategy further specifies that the packet is to be forwarded to a minimum number of physical ports among ports within the set of virtual port groups.

15. 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) in a content-centric network (CCN), the method comprising:

receiving a packet with an HSVLI;

determining, based on the HSVLI, a set of standalone physical ports;

determining, based on the HSVLI, a set of virtual port groups, wherein a respective virtual port group includes one or more individual physical ports;

deriving a forwarding strategy expressed as a formula in conjunctive normal form that indicates a logical conjunction among the standalone physical ports and the virtual port groups, and wherein the respective virtual port group is expressed as a logical disjunction among the one or more individual physical ports belonging to the respective virtual port group; and

forwarding the packet using the derived forwarding strategy.

16. The device of claim 15, wherein the packet is an interest in a piece of content corresponding to the HSVLI, wherein determining the set of standalone physical ports and the set of virtual port groups involves performing a longest-match lookup in a forwarding information base.

17. The device of claim 16, wherein performing the longest-match lookup involves calculating a fixed-length hash function of the HSVLI.

18. The device of claim 15, wherein the set of virtual port groups include a link aggregation group (LAG), and wherein the method further comprises using a scheduler associated with the LAG to make forwarding decisions among multiple physical ports associated with the LAG.

19. The device of claim 15, wherein the set of virtual port groups include a multi-path port group generated by a higher-level routing protocol, and wherein the method further comprises using the higher-level routing protocol to make forwarding decisions among multiple physical ports associated with the multi-path port group.

20. The device of claim 15, wherein the forwarding strategy specifies that the packet is to be forwarded to each and every standalone physical port and to at least one individual physical port within the respective virtual port group.

21. The device of claim 20, wherein the forwarding strategy further specifies that the packet is to be forwarded to a minimum number of physical ports among ports within the set of virtual port groups.