ROUTING TRAFFIC THROUGH A VIRTUAL ROUTER-BASED NETWORK SWITCH

• US 20070127382A1
• Filed: 02/05/2007
• Published: 06/07/2007
• Est. Priority Date: 06/04/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Fortinet Inc.
• Inventors: Millet, Tim, Lockwood, Gregory, Alam, Naveed, Hussain, Zahid, Cheng, Joseph, Jain, Samir
• Granted Patent: US 7,522,604 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• 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:

establishing a flow data structure identifying packet flows associated with a plurality of virtual routers in a virtual router-based network device;

receiving an incoming packet, the packet having at least one packet header;

comparing a subset of the at least one packet header to a subset of the flow data structure;

if the subset of the at least one packet header matches the subset of the flow data structure, then hardware forwarding the incoming packet via a network interface of the virtual router-based network device without intervention by a processor of the virtual router-based network device, otherwise forwarding the incoming packet to software on the processor for flow learning.

2. A method comprising:

establishing a hardware accelerated micro-flow by configuring forwarding state information of a flow cache entry associated with the hardware accelerated micro-flow, the hardware accelerated micro-flow having an identifier and an invalidation tag;

upon receiving an incoming packet that is part of the hardware accelerated micro-flow, comparing the invalidation tag to a value in an invalid tag table, the value located by the identifier; and

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

3. A method comprising:

associating a rate metering structure with each micro-flow of a plurality of micro-flows of a virtual router-based network device;

maintaining a corresponding rate statistic for each micro-flow in the rate metering structures;

upon detecting that the corresponding rate statistic is exceeded for a micro-flow of the plurality of micro-flows with which an incoming packet is associated, dropping the incoming packet.

4. A method comprising:

associating a flow metering structure with a virtual router;

upon detecting a packet flow is to be assigned to the virtual router, incrementing a flow counter in the flow metering structure;

comparing the flow counter to a predetermined limit value;

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

5. 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) an 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 current 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.

6. The method of claim 5, 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.

7. The method of claim 5, 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.

8. The method of claim 7, 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.

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

10. The method of claim 11, wherein the VSE provides antivirus services.

11. The method of claim 9, wherein the VSE provides firewall services.

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