Hardware-accelerated packet multicasting in a virtual routing system

• US 7,933,269 B2
• Filed: 09/03/2007
• Issued: 04/26/2011
• Est. Priority Date: 11/18/2002
• Status: Active Grant

• Current Assignee: Fortinet Inc.
• Original Assignee: Fortinet Inc.
• Inventors: Hussain, Zahid, Cheng, Joseph, Millet, Tim
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): HALIYUR, VENKATESH N
• Application Number:
  US11/849,352
• Publication Number:
  US 20070291755A1
• Time in Patent Office: 1,331 Days
• Field of Search: 370235-503, 709203-247
• 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 multicast packet is received at an ingress system of a packet-forwarding engine (PFE). The ingress system identifies flow classification indices for the multicast packet. Then, for each instance of multicasting, the ingress system sends a single copy of the multicast packet and the flow classification indices to an egress system of the PFE. The single copy of the multicast packet is buffered in a memory accessible by the egress system. The egress system prepares the multicast packet for transmission by for each flow classification index, identifying corresponding transform control instructions based on the flow classification index, reading the single copy of the multicast packet from the memory, causing the multicast packet to be transformed in accordance with the identified transform control instructions and outputting the transformed multicast packet.

Claims

1. A method for packet multicasting in a virtual routing system, the method comprising:

receiving a multicast packet at an ingress system of a packet-forwarding engine (PFE) of the virtual routing system, the virtual routing system including one or more virtual service engines (VSEs) and a flow manager configured to load balance service requests to the one or more VSEs;

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

for each instance of multicasting, the ingress system sending a single copy of the multicast packet and the plurality of flow classification indices to an egress system of the PFE;

buffering the single copy of the multicast packet in a memory accessible by the egress system; and

the egress system preparing the multicast packet for transmission by for each flow classification index of the plurality of flow classification indices, identifying corresponding transform control instructions based on the flow classification index, reading the single copy of the multicast packet from the memory, causing the multicast packet to be transformed in accordance with the identified transform control instructions and outputting the transformed multicast packet.

2. The method of claim 1, wherein causing the multicast packet to be transformed includes replacing at least one or more portions of a header of the multicast packet with one or more new portions, the one or more new portions being in accordance with the identified transform control instructions.

7. The system of claim 1, wherein the one or more VSEs provide firewall or antivirus services.

3. A system comprising:

one or more virtual service engines (VSEs);

a flow manager configured to load balance service requests to the one or more VSEs; and

one or more virtual routing engines (VREs) coupled to the one or more VSEs, each of the VREs including a packet classifier; and

a packet transformer;

wherein,

the packet classifier is configured to receive multicast packets and for each of the received multicast packets, the packet classifier configured to identify a plurality of flow classification indices and configured for each instance of multicasting to send a single copy of the multicast packets and the identified plurality of flow classification indices to the packet transformer;

the packet transformer is configured to transform each of the multicast packets by operating on the single copy in accordance with one or more transform control instructions identified based on the identified plurality of flow classification indices.

4. The system of claim 3, further comprising a memory associated with the packet transformer and wherein the packet transformer buffers the single copy of the multicast packet in the memory after receipt of the single copy of the multicast packet from the packet classifier.

5. The system of claim 4, wherein the packet transformer replaces at least one or more portions of a header of the multicast packet with new portions, the new portions being in accordance with the identified transform control instructions.

6. The system of claim 5, wherein the system is a packet routing system and the transformed packets are provide to a network for routing in accordance with the replaced headers.

8. In a virtual routing system having a plurality of virtual routers (VRs) instantiated by a virtual routing engine (VRE), wherein the instantiation of each VR includes an associated routing context, a method of multicasting packets comprising:

determining one of the plurality of VRs for a packet received from a service provider for multicasting;

switching a routing context of the VRE to a routing context associated with the VR determined for the received packet;

reading at least a portion of the received packet from one of a plurality of multicast address spaces associated with the selected VR to multicast the received packet;

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

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

buffering the received packet in a memory associated with the packet transformer;

identifying first transform control instructions from the first flow classification index; and

transforming the received packet in accordance with the first transform control instructions.

9. The method of claim 8, wherein the packet is a first packet received from a service provider for multicasting to a first multicast destination, and wherein a second packet is received from the service provider for multicasting, and the method comprises:

determining another one of the VRs for the second packet;

switching the routing context of the VRE to a routing context associated with the VR determined for the second packet;

reading at least a portion of the second packet from another of the plurality of multicast address spaces associated with the VR determined for the second packet to multicast the second packet; and

forwarding the second packet to second multicast destinations.

10. The method of claim 9, further comprising:

transforming headers of the first packet in accordance with transform control instructions of the routing context of the first packet; and

transforming headers of the second packet in accordance with transform control instructions of the routing context of the second packet.

11. The method of claim 10, wherein the first and second packets are received from a same service provider and have identical layer-two through layer-four (L2-L4) headers, and the method includes classifying the first and second packets in accordance with different VRs of the plurality of VRs.

12. The method of claim 8, wherein during reading, the packet is read from a same buffer for each instance of multicasting.

13. The method of claim 8, wherein selecting comprises classifying the received packet to determine one of the VRs having a routing context associated with the received packet.

14. The method of claim 8, wherein each VR of the plurality of VRs has a multicast address space associated therewith, and wherein switching the routing context of a VR includes switching a memory state of the VRE, and wherein the virtual routing system includes a plurality of VREs, each capable of instantiating a plurality of VRs.

15. The method of claim 8, further comprising:

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

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

reading the multicast received packet from the memory;

transforming the packet in accordance with the next transform control instructions; and

repeating, for each of the flow classification indices of the plurality of flow classification indices, the sending the next flow classification index, the identifying the next transform control instructions, the reading and the transforming the received packet, to generate multicast packets for transmission.

16. The method of claim 15, wherein prior to transforming, the method further comprises providing the received packet with each next flow classification index of the plurality to an egress processor, and wherein transforming further comprises transforming the received packet by the egress processor in accordance with each next flow classification index, and wherein a packet classifier performs identifying the plurality of flow classification indices, sending the received packet and the first flow classification index, and sending each next flow classification index without the received packet, and wherein the packet transformer performs the buffering, the identifying the transform control instructions and providing the multicast received packet with each next flow classification index of the plurality of flow classification indices to the egress processor.

17. A non-transitory computer-readable storage medium tangibly embodying a set of instructions, which when executed by one or more processors of a virtual routing system, cause the one or more processors to perform a method comprising:

receiving a multicast packet at an ingress system of a packet-forwarding engine (PFE) of the virtual routing system, the virtual routing system including one or more virtual service engines (VSEs) and a flow manager configured to load balance service requests to the one or more VSEs;

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

for each instance of multicasting, the ingress system sending a single copy of the multicast packet and the plurality of flow classification indices to an egress system of the PFE;

buffering the single copy of the multicast packet in a memory accessible by the egress system; and

the egress system preparing the multicast packet for transmission by, for each flow classification index of the plurality of flow classification indices, identifying corresponding transform control instructions based on the flow classification index, reading the single copy of the multicast packet from the memory, causing the multicast packet to be transformed in accordance with the identified transform control instructions and outputting the transformed multicast packet.

18. The non-transitory computer-readable storage medium of claim 17, wherein causing the multicast packet to be transformed includes replacing at least one or more portions of a header of the multicast packet with one or more new portions, the one or more new portions being in accordance with the identified transform control instructions.