Routing traffic through a virtual router-based network switch

• US 8,111,690 B2
• Filed: 10/29/2008
• Issued: 02/07/2012
• Est. Priority Date: 06/04/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hussain, Zahid, Jain, Samir, Alam, Naveed, Cheng, Joseph, Lockwood, Greg, Millet, Tim
• Primary Examiner(s): SOL, ANTHONY M
• Application Number:
  US12/260,524
• Publication Number:
  US 20090073977A1
• Time in Patent Office: 1,196 Days
• Field of Search: None
• US Class Current: 370/389
• 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 flow data structure is established that identifies current packet flows associated with multiple virtual routers in the virtual router-based network device. When an incoming packet is received by the virtual router-based network device, it is then determined whether the incoming packet is associated with a current packet flow by accessing the flow data structure based on a header associated with the incoming packet. If it is determined that the incoming packet is associated with the current packet flow, then the incoming packet is hardware forwarded via a network interface of the virtual router-based network device without intervention by a processor of the virtual router-based network device, otherwise the incoming packet is forwarded to software on the processor for flow learning.

Claims

1. A method comprising:

establishing, by flow learning software running on a processor of a processing element of a plurality of processing elements of a virtual router-based network device, a flow data structure within a memory of the processing element, the flow data structure including (i) information identifying a plurality of current packet flows associated with a plurality of virtual routers running within the processing element and (ii) corresponding forwarding state information for each of the plurality of current packet flows, wherein each of the plurality of virtual routers comprise an instance of software, executing within a processor of the processing element, that emulates functionality of an individual physical router and to which at least a subset of physical hardware resources of the processing element are partitioned;

receiving, by a packet forwarding engine of the processing element, an incoming packet;

determining, by the packet forwarding engine, whether the incoming packet is associated with any of the plurality of current packet flows by accessing the flow data structure based on a header associated with the incoming packet;

if the incoming packet is associated with a current packet flow of the plurality of current packet flows, then

determining, by the packet forwarding engine, whether the incoming packet is to be hardware forwarded or software forwarded based on the forwarding state information corresponding to the current packet flow;

if the incoming packet is to be hardware forwarded, then hardware forwarding the incoming packet, by the packet forwarding engine, via a network interface of the virtual router-based network device without intervention by the processor; and

otherwise, if the incoming packet is to be software forwarded, then software forwarding the incoming packet, by an appropriate virtual router of the plurality of virtual routers, via the network interface; and

otherwise, if the incoming packet is not associated with any of the plurality of current packet flows, then providing information regarding the incoming packet to the flow learning software on the processor to allow the flow data structure to be updated to include information identifying a flow with which the incoming packet is associated within the plurality of current packet flows.

2. The method of claim 1, further comprising:

associating a rate metering structure with each of the plurality of current packet flows;

maintaining a corresponding rate statistic for each current packet flow in the rate metering structures; and

upon detecting that the corresponding rate statistic is exceeded for a particular current packet flow of the plurality of current packet flows dropping packets associated with the particular current packet flow.

3. The method of claim 1, further comprising:

associating a flow metering structure with each of the plurality of virtual routers;

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

comparing the flow counter to a predetermined limit value; and

if the flow counter does not exceed the predetermined limit value then establishing the packet flow as one of the plurality of current packet flows, otherwise refusing to establish the packet flow as one of the plurality of current packet flows.