Hardware-accelerated packet multicasting in a virtual routing system

• US 8,644,311 B2
• Filed: 04/24/2011
• Issued: 02/04/2014
• Est. Priority Date: 11/18/2002
• Status: Active Grant

• Current Assignee: Fortinet Inc.
• Original Assignee: Fortinet Inc.
• Inventors: Cheng, Joseph, Hussain, Zahid, Millet, Tim
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): HALIYUR, VENKATESH N
• Application Number:
  US13/092,962
• Publication Number:
  US 20110200044A1
• Time in Patent Office: 1,017 Days
• Field of Search: 370228-403, 709217-246
• US Class Current: 370/390
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 2012/6489 Buffer Management, Threshold setting, Scheduling, Shaping
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Methods and systems are provided for hardware-accelerated packet multicasting in a virtual routing system. According to one embodiment, a virtual routing engine (VRE) including virtual routing processors and corresponding memory systems are provided. The VRE implements virtual routers (VRs) operable on the virtual routing processors and associated routing contexts utilizing potentially overlapping multicast address spaces resident in the memory systems. Multicasting of multicast flows originated by subscribers of a service provider is simultaneously performed on behalf of the subscribers. A VR is selected to handle multicast packets associated with a multicast flow. A routing context of the VRE is switched to one associated with the VR. A packet of the multicast flow is forwarded to multiple destinations by reading a portion of the packet from a common buffer for each instance of multicasting and applying transform control instructions to the packet for each instance of multicasting.

Claims

1. A method comprising:

providing a virtual routing engine (VRE) including a plurality of virtual routing processors and corresponding memory systems, the VRE implementing a plurality of virtual routers (VRs) operable on one or more of the plurality of virtual routing processors and associated routing contexts utilizing a plurality of multicast address spaces resident in the corresponding memory systems; and

simultaneously performing multicasting on behalf of a plurality of subscribers of a service provider by, for each of a plurality of multicast flows originated by the plurality of subscribers;

selecting a VR of the plurality of VRs to handle multicast packets associated with the multicast flow;

switching a routing context of the VRE to the associated routing context of the selected VR; and

forwarding a multicast packet of the multicast flow to a plurality of multicast destinations by reading at least a portion of the multicast packet from a common buffer for each instance of multicasting and applying destination specific transform control instructions to the multicast packet for each instance of multicasting.

2. The method of claim 1, further comprising:

identifying a plurality of flow classification indices for the multicast packet flow;

sending the multicast packet and a first of the flow classification indices to a packet transformer;

buffering the multicast packet in a memory associated with the packet transformer; and

identifying first transform control instructions from the first flow classification index.

3. The method of claim 2, further comprising:

sending a next of the flow classification indices without the multicast packet to the packet transformer;

identifying next transform control instructions from the next of the flow classification indices;

reading the multicast packet from the memory; and

transforming the multicast packet in accordance with the next transform control instructions.

20. The method of claim 1, wherein the plurality of multicast address spaces include overlapping multicast address spaces.

4. A virtual routing system comprising:

a plurality of virtual routing engines (VREs) each including a plurality of virtual routing processors and corresponding memory systems, each of the plurality of VREs implement a plurality of virtual routers (VRs) operable on one or more of the plurality of virtual routing processors and associated routing contexts utilizing a plurality of multicast address spaces resident in the corresponding memory systems;

a flow manager operable to cause appropriate VRs of the plurality of VRs to handle multicast packets received from a service provider; and

wherein the virtual routing system simultaneously handles multicasting for a plurality of subscribers of the service provider by performing a method comprising for each of a plurality of multicast flows originated by the plurality of subscribers;

dynamically identifying a VRE of the plurality of VREs for the multicast flow by selecting a VR of the plurality of VRs implemented by the identified VRE to handle multicast packets associated with the multicast flow;

switching a routing context of the identified VRE to the associated routing context of the selected VR; and

forwarding a multicast packet of the multicast flow to a plurality of multicast destinations by reading at least a portion of the multicast packet from a common buffer for each instance of multicasting and applying destination specific transform control instructions to the multicast packet for each instance of multicasting.

5. The virtual routing system of claim 4, wherein the service provider comprises an Internet Service Provider (ISP) and wherein the plurality of subscribers comprise a plurality of access clients.

6. The virtual routing system of claim 4, wherein the portion of the multicast packet excludes a header of the multicast packet or one or more portions of the header of the multicast packet.

7. The virtual routing system of claim 6, further comprising a packet classification system and wherein the header or the one or more portions of the header are removed by the packet classification system.

8. The virtual routing system of claim 4, further comprising a packet transforming system and wherein a new header or one or more portions of the new header are added to the multicast packet by the packet transforming system.

21. The virtual routing system of claim 4, wherein the plurality of multicast address spaces include overlapping multicast address spaces.

9. A virtual routing system comprising:

a plurality of virtual routing engines (VREs) each including a plurality of virtual routing processors and corresponding memory systems, each of the plurality of VREs implement a plurality of virtual routers (VRs) operable on one or more of the plurality of virtual routing processors and associated routing contexts utilizing a plurality of multicast address spaces resident in the corresponding memory systems;

a flow manager operable to cause appropriate VRs of the plurality of VRs to handle multicast packets received from a service provider; and

wherein the virtual routing system simultaneously handles multicasting for a plurality of subscribers of the service provider by performing a method comprising;

receiving a first multicast flow from the service provider that is originated by a first subscriber of the plurality of subscribers;

dynamically identifying a first VRE of the plurality of VREs for the first multicast flow by selecting a first VR of the plurality of VRs implemented by the first VRE to handle multicast packets associated with the first multicast flow;

switching a routing context of the first VRE to the associated routing context of the first VR;

forwarding a first multicast packet of the first multicast flow to a multicast destination associated with the first multicast flow by reading at least a portion of the first multicast packet from a first multicast address space of the plurality of multicast address spaces;

receiving a second multicast flow from the service provider that is originated by a second subscriber of the plurality of subscribers;

dynamically identifying the first VRE for the second multicast packet flow by selecting a second VR of the plurality of VRs implemented by the first VRE to handle multicast packets associated with the second multicast flow;

switching a routing context of the first VRE to the associated routing context of the second VR; and

forwarding a second multicast packet of the second multicast flow to a multicast destination associated with the second multicast flow by reading at least a portion of the second multicast packet from a second multicast address space of the plurality of multicast address spaces.

10. The virtual routing system of claim 9, wherein the method further comprises:

transforming a header of the first multicast packet in accordance with transform control instructions of the associated routing context of the first VR; and

transforming a header of the second multicast packet in accordance with transform control instructions of the associated routing context of the second VR.

11. The virtual routing system of claim 9, wherein the method further comprises:

reading the first multicast packet from a same buffer for each instance of multicasting.

12. The virtual routing system of claim 9, wherein the method further comprises:

reading the second multicast packet from a same buffer for each instance of multicasting.

13. The virtual routing system of claim 9, wherein the service provider comprises an Internet Service Provider (ISP) and wherein the plurality of subscribers comprise a plurality of access clients.

14. The virtual routing system of claim 9, further comprising a packet transformer and wherein the method further comprises:

identifying a first plurality of flow classification indices for the first multicast packet flow;

sending the first multicast packet of the first multicast flow and a first flow classification index of the first plurality of flow classification indices to the packet transformer;

buffering the first multicast packet in a memory associated with the packet transformer; and

identifying first transform control instructions from the first flow classification index.

15. The virtual routing system of claim 14, wherein the method further comprises:

sending a next flow classification index of the first plurality of flow classification indices without the first multicast packet to the packet transformer;

identifying next transform control instructions from a next classification index of the first plurality of flow classification indices;

reading the first multicast packet from the memory; and

transforming the first multicast packet in accordance with the next transform control instructions.

16. The virtual routing system of claim 9, wherein the portion of the first multicast packet excludes a header of the first multicast packet or one or more portions of the header of the multicast packet.

17. The virtual routing system of claim 16, further comprising a packet classification system and wherein the header or the one or more portions of the header are removed by the packet classification system.

18. The virtual routing system of claim 9, further comprising a packet transforming system and wherein a new header or one or more portions of the new header are added to the first multicast packet by the packet transforming system.

19. The virtual routing system of claim 9, wherein the first multicast address space and the second multicast address space overlap.