Routing traffic through a virtual router-based network switch

• US 7,522,604 B2
• Filed: 02/05/2007
• Issued: 04/21/2009
• Est. Priority Date: 06/04/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Fortinet Inc.
• Inventors: Lockwood, Greg, Alam, Naveed, Hussain, Zahid, Cheng, Joseph, Millet, Tim, Jain, Samir
• Primary Examiner(s): Cho, Hong
• Assistant Examiner(s): SOL, ANTHONY M
• Application Number:
  US11/671,462
• Publication Number:
  US 20070127382A1
• Time in Patent Office: 806 Days
• Field of Search: None
• 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/586 of virtual routers
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 49/252 Store and forward routing
• CPC Class Codes: H04L 49/505 Corrective measures
• CPC Class Codes: H04L 49/70 Virtual switches

Abstract

Methods and systems are provided for routing traffic through a virtual router-based network switch. According to one embodiment, a method for routing packets in a router includes establishing a flow data structure, which identifies a packet flow through a virtual router in the router. When a packet is received, a comparison is performed between a subset of at least one packet header associated with the packet and a subset of the flow data structure. If the subset of the packet header matches the subset of the flow data structure, then the packet can be hardware accelerated to a network interface. Otherwise, the packet may be either dropped or forwarded to a general purpose processor for processing.

Claims

1. A method comprising:

maintaining a flow cache having a plurality of flow ID cache block entries each identifying one of a plurality of current virtual router (VR) flows through a VR-based network device and corresponding forwarding state information;

receiving an incoming packet at a processing engine of a plurality of processing engines of the VR-based network device;

an ingress unit of a packet forwarding engine (PFE) associated with the processing engine determining whether the incoming packet is associated with a VR flow of the plurality of current VR flows by attempting to retrieve a flow ID cache block entry of the flow cache identified by an index based on one or more of (i) an Internet Protocol (IP) address, (ii) a Multiprotocol Label Switching (MPLS) label, and (iii) a destination logical queue (LQ) ID field, a LQ protocol ID field, one or more layer 3 (L3) header fields and one or more layer 4 (L4) header fields associated with the incoming packet;

if it is determined that the incoming packet is associated with the VR flow, determining, based on the corresponding forwarding state information of the retrieved flow ID cache block entry, whether the incoming packet can be hardware forwarded or whether the incoming packet is to be software forwarded;

if it is determined that the incoming packet can be hardware forwarded, then (i) determining one or more packet transformations that are to be applied to the incoming packet by an egress unit of the PFE as a result of the incoming packet'"'"'s association with the VR flow, (ii) the egress unit applying the one or more packet transformations to the incoming packet, and (iii) hardware forwarding the incoming packet without intervention by a processor of the VR-based network device via a network interface of the VR-based network device;

otherwise, if it is determined that the incoming packet cannot be hardware forwarded, then software forwarding the incoming packet via the processor;

if it is determined that the incoming packet is not associated with any of the plurality of current VR flows, (i) identifying the existence of a new VR flow, (ii) allocating a new flow ID cache block entry within the flow cache for the new VR flow and (iii) forwarding the incoming packet to software on the processor for flow learning.

2. The method of claim 1, further comprising:

establishing a hardware accelerated flow within the flow cache, the hardware accelerated flow having associated therewith an identifier and an invalidation tag;

if the packet is determined to be part of the hardware accelerated flow, then retrieving a value from an invalid tag table by indexing into the invalid tag table with the identifier and comparing the invalidation tag to the retrieved value; and

invalidating the hardware accelerated flow when the retrieved value does not match the invalidation tag.

3. The method of claim 1, further comprising:

associating a rate metering structure with a VR flow of the plurality of current VR flows;

maintaining a rate statistic within the rate metering structure indicative of a number of packets or bytes associated with the VR flow that have been observed during a predefined time interval; and

enforcing a maximum packet or byte rate cap for the VR flow by dropping the packet if the packet would cause the rate statistic to exceed the maximum packet or byte rate cap for the predefined time interval.

4. The method of claim 3, further comprising:

associating a flow metering structure with a VR of a plurality of VRs of the VR-based network device;

for each VR flow assigned to the VR, incrementing a corresponding flow counter in the flow metering structure;

comparing the corresponding flow counter to a predetermined limit value;

if the corresponding flow counter does not exceed the predetermined limit value then establishing the new VR flow, otherwise refusing to establish the new VR flow.

5. The method of claim 1, wherein the processing engine comprises a Virtual Service Engine (VSE) configured to provide one or more services.

6. The method of claim 5, wherein the VSE provides antivirus services.

7. The method of claim 5, wherein the VSE provides firewall services.

8. The method of claim 1, wherein the processing engine comprises an Advanced Security Engine (ASE) capable of providing data encryption services.

9. A method comprising:

a step for maintaining a flow cache having a plurality of flow ID cache block entries each identifying one of a plurality of current virtual router (VR) flows through a VR-based network device and corresponding forwarding state information;

a step for receiving an incoming packet at a processing engine of a plurality of processing engines of the VR-based network device;

a step for, an ingress unit of a packet forwarding engine (PFE) associated with the processing engine, determining whether the incoming packet is associated with a VR flow of the plurality of current VR flows by attempting to retrieve a flow ID cache block entry of the flow cache identified by an index based on one or more of (i) an Internet Protocol (IP) address, (ii) a Multiprotocol Label Switching (MPLS) label, and (iii) a destination logical queue (LQ) ID field, a LQ protocol ID field, one or more layer 3 (L3) header fields and one or more layer 4 (L4) header fields associated with the incoming packet;

a step for, if it is determined that the incoming packet is associated with the VR flow, determining, based on the corresponding forwarding state information of the retrieved flow ID cache block entry, whether the incoming packet can be hardware forwarded or whether the incoming packet is to be software forwarded;

a step for, if it is determined that the incoming packet can be hardware forwarded, (i) determining one or more packet transformations that are to be applied to the incoming packet by an egress unit of the PFE as a result of the incoming packet'"'"'s association with the VR flow, (ii) the egress unit applying the one or more packet transformations to the incoming packet, and (iii) hardware forwarding the incoming packet without intervention by a processor of the VR-based network device via a network interface of the VR-based network device;

otherwise, a step for, if it is determined that the incoming packet cannot be hardware forwarded, software forwarding the incoming packet via the processor;

a step for, if it is determined that the incoming packet is not associated with any of the plurality of current VR flows, (i) identifying the existence of a new VR flow, (ii) allocating a new flow ID cache block entry within the flow cache for the new VR flow and (iii) forwarding the incoming packet to software on the processor for flow learning.

10. The method of claim 9, further comprising:

a step for establishing a hardware accelerated flow within the flow cache, the hardware accelerated flow having associated therewith an identifier and an invalidation tag;

a step for, if the packet is determined to be part of the hardware accelerated flow, retrieving a value from an invalid tag table by indexing into the invalid tag table with the identifier and comparing the invalidation tag to the retrieved value; and

a step for invalidating the hardware accelerated flow when the retrieved value does not match the invalidation tag.

11. The method of claim 9, further comprising:

a step for associating a rate metering structure with a VR flow of the plurality of current VR flows;

a step for maintaining a rate statistic within the rate metering structure indicative of a number of packets or bytes associated with the VR flow that have been observed during a predefined time interval; and

a step for enforcing a maximum packet or byte rate cap for the VR flow by dropping the packet if the packet would cause the rate statistic to exceed the maximum packet or byte rate cap for the predefined time interval.

12. The method of claim 11, further comprising:

a step for associating a flow metering structure with a VR of a plurality of VRs of the VR-based network device;

a step for, for each VR flow assigned to the VR, incrementing a corresponding flow counter in the flow metering structure;

a step for comparing the corresponding flow counter to a predetermined limit value;

a step for, if the corresponding flow counter does not exceed the predetermined limit value, establishing the new VR flow, otherwise refusing to establish the new VR flow.

13. The method of claim 9, wherein the processing engine comprises a Virtual Service Engine (VSE) configured to provide one or more services.

14. The method of claim 13, wherein the VSE provides antivirus services.

15. The method of claim 13, wherein the VSE provides firewall services.

16. The method of claim 9, wherein the processing engine comprises an Advanced Security Engine (ASE) that provides data encryption services.

17. A network device comprising:

a means for maintaining a flow cache having a plurality of flow ID cache block entries each identifying one of a plurality of current virtual router (VR) flows through a VR-based network device and corresponding forwarding state information;

a means for receiving an incoming packet at a processing engine of a plurality of processing engines of the VR-based network device;

an ingress means, of a packet forwarding engine (PFE) associated with the processing engine, for determining whether the incoming packet is associated with a VR flow of the plurality of current VR flows by attempting to retrieve a flow ID cache block entry of the flow cache identified by an index based on one or more of (i) an Internet Protocol (IP) address, (ii) a Multiprotocol Label Switching (MPLS) label, and (iii) a destination logical queue (LQ) ID field, a LQ protocol ID field, one or more layer 3 (L3) header fields and one or more layer 4 (L4) header fields associated with the incoming packet;

a means for, if it is determined that the incoming packet is associated with the VR flow, determining, based on the corresponding forwarding state information of the retrieved flow ID cache block entry, whether the incoming packet can be hardware forwarded or whether the incoming packet is to be software forwarded;

a means for, if it is determined that the incoming packet can be hardware forwarded, (i) determining one or more packet transformations that are to be applied to the incoming packet by an egress unit of the PFE as a result of the incoming packet'"'"'s association with the VR flow, (ii) the egress unit applying the one or more packet transformations to the incoming packet, and (iii) hardware forwarding the incoming packet without intervention by a processor of the VR-based network device via a network interface of the VR-based network device;

otherwise, a means for, if it is determined that the incoming packet cannot be hardware forwarded, software forwarding the incoming packet via the processor;

a means for, if it is determined that the incoming packet is not associated with any of the plurality of current VR flows, (i) identifying the existence of a new VR flow, (ii) allocating a new flow ID cache block entry within the flow cache for the new VR flow and (iii) forwarding the incoming packet to software on the processor for flow learning.

18. The network device of claim 17, further comprising:

a means for establishing a hardware accelerated flow within the flow cache, the hardware accelerated flow having associated therewith an identifier and an invalidation tag;

a means for, if the packet is determined to be part of the hardware accelerated flow, retrieving a value from an invalid tag table by indexing into the invalid tag table with the identifier and comparing the invalidation tag to the retrieved value; and

a means for invalidating the hardware accelerated flow when the retrieved value does not match the invalidation tag.

19. The network device of claim 17, further comprising:

a means for associating a rate metering structure with a VR flow of the plurality of current VR flows;

a means for maintaining a rate statistic within the rate metering structure indicative of a number of packets or bytes associated with the VR flow that have been observed during a predefined time interval; and

a means for enforcing a maximum packet or byte rate cap for the VR flow by dropping the packet if the packet would cause the rate statistic to exceed the maximum packet or byte rate cap for the predefined time interval.

20. The network device of claim 19, further comprising:

a means for associating a flow metering structure with a VR of a plurality of VRs of the VR-based network device;

a means for incrementing a corresponding flow counter for each VR flow assigned to the VR in the flow metering structure;

a means for comparing the corresponding flow counter to a predetermined limit value;

a means for, if the corresponding flow counter does not exceed the predetermined limit value, establishing the new VR flow, otherwise refusing to establish the new VR flow.

21. The network device of claim 17, wherein the processing engine comprises a Virtual Service Engine (VSE) configured to provide one or more services.

22. The network device of claim 21, wherein the VSE provides antivirus services.

23. The network device of claim 21, wherein the VSE provides firewall services.

24. The network device of claim 17, wherein the processing engine comprises an Advanced Security Engine (ASE) that provides data encryption services.

25. A virtual router (VR) based network device comprising:

a flow cache having stored therein a plurality of flow ID cache block entries each identifying one of a plurality of current VR flows through the VR-based network device and corresponding forwarding state information;

a processor operable to software forward packets that cannot be hardware forwarded and perform flow learning in relation to incoming packets not associated with any of the plurality of current VR flows

a plurality of network interfaces through which incoming packets are received by and outgoing packets are transmitted by the VR-based network device;

a plurality of processing engines coupled to the plurality of network interfaces, each of the plurality of processing engines having an associated packet forwarding engine (PFE) which has access to the flow cache;

an egress unit associated with each of the PFEs operable to apply packet transformations to outgoing packets;

an ingress unit associated with each of the PFEs operable to determine whether an incoming packet is associated with a VR flow of the plurality of current VR flows by attempting to retrieve a flow ID cache block entry of the flow cache identified by an index based on one or more of (i) an Internet Protocol (IP) address, (ii) a Multiprotocol Label Switching (MPLS) label, and (iii) a destination logical queue (LQ) ID field, a LQ protocol ID field, one or more layer 3 (L3) header fields and one or more layer 4 (L4) header fields associated with the incoming packet; and

wherein

if it is determined that the incoming packet is associated with the VR flow, then determining, based on the corresponding forwarding state information of the retrieved flow ID cache block entry, whether the incoming packet can be hardware forwarded or whether the incoming packet is to be software forwarded;

if it is determined that the incoming packet can be hardware forwarded, then (i) determining one or more packet transformations that are to be applied to the incoming packet by the egress unit as a result of the incoming packet'"'"'s association with the VR flow, (ii) the egress unit applying the one or more packet transformations to the incoming packet, and (iii) hardware forwarding the incoming packet without intervention by the processor via a network interface of the plurality of network interfaces;

otherwise, if it is determined that the incoming packet cannot be hardware forwarded, then software forwarding the incoming packet via the processor;

if it is determined that the incoming packet is not associated with any of the plurality of current VR flows, then (i) identifying the existence of a new VR flow, (ii) allocating a new flow ID cache block entry within the flow cache for the new VR flow and (iii) forwarding the incoming packet to software on the processor for flow learning.

26. A program storage device readable by one or more processors of a virtual router (VR) based network device, tangibly embodying a program of instructions executable by the VR-based network device to perform method steps for routing traffic through the VR-based network device, said method steps comprising:

maintaining a flow cache having a plurality of flow ID cache block entries each identifying one of a plurality of current virtual router (VR) flows through a VR-based network device and corresponding forwarding state information;

receiving an incoming packet at a processing engine of a plurality of processing engines of the VR-based network device;

an ingress unit of a packet forwarding engine (PFE) associated with the processing engine, determining whether the incoming packet is associated with a VR flow of the plurality of current VR flows by attempting to retrieve a flow ID cache block entry of the flow cache identified by an index based on one or more of (i) an Internet Protocol (IP) address, (ii) a Multiprotocol Label Switching (MPLS) label, and (iii) a destination logical queue (LQ) ID field, a LQ protocol ID field, one or more layer 3 (L3) header fields and one or more layer 4 (L4) header fields associated with the incoming packet;

if it is determined that the incoming packet is associated with the VR flow, determining, then based on the corresponding forwarding state information of the retrieved flow ID cache block entry, whether the incoming packet can be hardware forwarded or whether the incoming packet is to be software forwarded;

if it is determined that the incoming packet can be hardware forwarded, then (i) determining one or more packet transformations that are to be applied to the incoming packet by an egress unit of the PFE as a result of the incoming packet'"'"'s association with the VR flow, (ii) the egress unit applying the one or more packet transformations to the incoming packet, and (iii) hardware forwarding the incoming packet without intervention by the one or more processors via a network interface of the VR-based network device;

otherwise, if it is determined that the incoming packet cannot be hardware forwarded, then software forwarding the incoming packet via a processor of the one or more processors;

if it is determined that the incoming packet is not associated with any of the plurality of current VR flows, (i) identifying the existence of a new VR flow, (ii) allocating a new flow ID cache block entry within the flow cache for the new VR flow and (iii) forwarding the incoming packet to the one or more processors for flow learning.

27. The program storage device of claim 26, wherein the method further comprises:

establishing a hardware accelerated flow within the flow cache, the hardware accelerated flow having associated therewith an identifier and an invalidation tag;

if the packet is determined to be part of the hardware accelerated flow, then retrieving a value from an invalid tag table by indexing into the invalid tag table with the identifier and comparing the invalidation tag to the retrieved value; and

invalidating the hardware accelerated flow when the retrieved value does not match the invalidation tag.

28. The program storage device of claim 26, wherein the method further comprises:

associating a rate metering structure with a VR flow of the plurality of current VR flows;

maintaining a rate statistic within the rate metering structure indicative of a number of packets or bytes associated with the VR flow that have been observed during a predefined time interval; and

enforcing a maximum packet or byte rate cap for the VR flow by dropping the packet if the packet would cause the rate statistic to exceed the maximum packet or byte rate cap for the predefined time interval.

29. The program storage device of claim 28, wherein the method further comprises:

associating a flow metering structure with a VR of a plurality of VRs of the VR-based network device;

for each VR flow assigned to the VR, incrementing a corresponding flow counter in the flow metering structure;

comparing the corresponding flow counter to a predetermined limit value;

if the corresponding flow counter does not exceed the predetermined limit value, then establishing the new VR flow, otherwise refusing to establish the new VR flow.