Hardware-accelerated packet multicasting

• US 9,407,449 B2
• Filed: 02/27/2015
• Issued: 08/02/2016
• 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): Sloms, Nicholas
• Application Number:
  US14/633,981
• Publication Number:
  US 20150195098A1
• Time in Patent Office: 522 Days
• Field of Search: None
• US Class Current: 1/1
• 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 for hardware-accelerated packet multicasting are provided. According to one embodiment, a first packet to be multicast to a first destination and a second packet to be multicast to a second destination are received. The first and second packets are classified in accordance with different virtual routers (VRs) of multiple VRs instantiated by a virtual routing engine (VRE) of a virtual routing system by determining a first selected VR to multicast the first packet and a second selected VR to multicast the second packet. For each of the first and second packets: a routing context of the VRE is switched to a routing context associated with the selected VR; at least a portion of the packet is read from one of multiple multicast address spaces associated with the selected VR; and the packet is forwarded to the destination.

Claims

1. 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:

receiving a first multicast packet to be multicast to a first multicast destination and a second multicast packet to be multicast to a second multicast destination;

classifying the first received multicast packet and the second received multicast packet in accordance with different VRs of the plurality of VRs by determining a first selected VR of the plurality of VRs to multicast the first received multicast packet and a second selected VR of the plurality of VRs to multicast the second received multicast packet;

switching a routing context of the VRE to a routing context associated with the first selected VR for the first received multicast packet; and

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

forwarding the first received multicast packet to the first multicast destination;

switching the routing context of the VRE to a routing context associated with the second selected VR for the second received multicast packet;

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

forwarding the second received multicast packet to the second multicast destination.

2. The method of claim 1 further comprising:

transforming headers of the first received multicast packet in accordance with transform control instructions of the routing context associated with the first selected VR; and

transforming headers of the second received multicast packet in accordance with transform control instructions of the routing context associated with the second selected VR.

3. The method of claim 1 wherein during reading, multicast packets are read from a same buffer of the multicast address spaces associated with the selected VR for each instance of multicasting.

4. The method of claim 1 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 multiple VRs.

5. The method of claim 1 further comprising:

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

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

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

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

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

6. The method of claim 5 further comprising:

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

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

reading the first received multicast packet from the memory;

transforming the first received multicast 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 first received multicast packet, to generate multicast packets for transmission.

7. The method of claim 6 wherein prior to transforming, the method further comprises:

providing the first received multicast packet with each next flow classification index of the plurality of flow classification indices to an egress processor; and

wherein transforming further comprises transforming the first received multicast 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 first received multicast packet and the first flow classification index, and sending each next flow classification index without the first received multicast packet; and

wherein the packet transformer performs the buffering, the identifying the transform control instructions and providing the first received multicast packet with each next flow classification index of the plurality to the egress processor.

8. A non-transitory computer-readable storage medium 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 of multicasting packets comprising:

receiving, by a virtual routing system having a plurality of virtual routers (VRs) instantiated by a virtual routing engine (VRE), a first multicast packet to be multicast to a first multicast destination and a second multicast packet to be multicast to a second multicast destination, wherein each VR instance of the plurality of VRs includes an associated routing context;

classifying the first received multicast packet and the second received multicast packet in accordance with different VRs of the plurality of VRs by determining a first selected VR of the plurality of VRs to multicast the first received multicast packet and a second selected VR of the plurality of VRs to multicast the second received multicast packet;

switching a routing context of the VRE to a routing context associated with the first selected VR for the first received multicast packet; and

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

forwarding the first received multicast packet to the first multicast destination;

switching the routing context of the VRE to a routing context associated with the second selected VR for the second received multicast packet;

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

forwarding the second received multicast packet to the second multicast destination.

9. The non-transitory computer-readable storage medium of claim 8, wherein the method further comprises:

transforming headers of the first received multicast packet in accordance with transform control instructions of the routing context associated with the first selected VR; and

transforming headers of the second received multicast packet in accordance with transform control instructions of the routing context associated with the second selected VR.

10. The non-transitory computer-readable storage medium of claim 8, wherein during reading, multicast packets are read from a same buffer of the multicast address spaces associated with the selected VR for each instance of multicasting.

11. The non-transitory computer-readable storage medium of claim 8, 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 multiple VRs.

12. The non-transitory computer-readable storage medium of claim 8, wherein the method further comprises:

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

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

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

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

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

13. The non-transitory computer-readable storage medium of claim 12, wherein the method further comprises:

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

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

reading the first received multicast packet from the memory;

transforming the first received multicast 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 first received multicast packet, to generate multicast packets for transmission.

14. The non-transitory computer-readable storage medium of claim 13, wherein prior to transforming, the method further comprises:

providing the first received multicast packet with each next flow classification index of the plurality of flow classification indices to an egress processor; and

wherein transforming further comprises transforming the first received multicast 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 first received multicast packet and the first flow classification index, and sending each next flow classification index without the first received multicast packet; and

wherein the packet transformer performs the buffering, the identifying the transform control instructions and providing the first received multicast packet with each next flow classification index of the plurality to the egress processor.