System and method for hardware accelerated packet multicast in a virtual routing system

• US 20040095934A1
• Filed: 11/18/2002
• Published: 05/20/2004
• Est. Priority Date: 11/18/2002
• Status: Active Grant

• Current Assignee: Fortinet Inc.
• Original Assignee: CoSine Communications, Inc. (Steel Partners Holdings LP)
• Inventors: Millet, Tim, Hussain, Zahid, Cheng, Joseph
• Granted Patent: US 7,266,120 B2
• Time in Patent Office: Days
• 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

A packet-forwarding engine (PFE) of a multiprocessor system uses an array of flow classification block (FCB) indices to multicast a packet. Packets are received and buffered in external memory. In one embodiment, when a multicast packet is identified, a bit is set in a packet descriptor and an FCB index is generated and sent with a null-packet to the egress processors which generate multiple descriptors with different indices for each instance of multicasting. All the descriptors may point to the same buffer in the external memory, which stores the multicast packet. A DMA engine reads from the same buffer multiple times and egress processors may access an appropriate transform control block (TCB) index so that the proper headers may be installed on the outgoing packet. The buffer may be released after the last time the packet is read by setting a particular bit of the FCB index.

Claims

12. A packet multicasting system comprising:

a packet transformer to transform a multicast packet in accordance with transform control instructions; and

a packet classifier to identify a plurality of flow classification indices for the multicast packet, and send the multicast packet and a first of the flow classification indices to the packet transformer.

13. The system of claim 12 further comprising a memory associated with the packet transformer and wherein the packet transformer buffers the multicast packet in the memory after receipt of the multicast packet from the packet classifier.

14. The system of claim 13 wherein the packet classifier sends a next of the flow classification indices without the multicast packet to the packet transformer, and the packet transformer identifying next transform control instructions from the next of the flow classification indices, reads the multicast packet from the memory and transforms the multicast packet in accordance with the next transform control instructions.

15. The system of claim 14 wherein the packet classifier repeats, for each of the flow classification indices of the plurality, the sending the next flow classification index,

and wherein the packet classifier repeats the identifying the next transform control instructions, the reading and the transforming the multicast packet, to generate multicast packets for transmission.

16. The system of claim 12 wherein the packet classifier performs a hash on header portions of a received packet to determine a flow classification block index, and looks up the flow classification block index in a flow classification block (FCB) to determine a flow classification index for a unicast packet and a location of the plurality of flow classification indices for the multicast packet.

17. The system of claim 12 wherein the packet transformer replaces at least portions of a header of multicast packet with new portions, the new portions being in accordance with the transform control instructions.

18. The system of claim 17 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.

19. The system of claim 12 wherein the packet classifier is comprised of a first multiprocessor system and the packet transformer is comprised of a second multiprocessor system.

20. An article comprising a computer-readable storage medium having stored thereon instructions, that when executed by a computing platform, result in:

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

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;

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

transforming the multicast packet in accordance with the first transform control instructions;

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.

1. A method for packet multicasting comprising:

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

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;

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

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

2. The method of claim 1 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.

3. The method of claim 2 further comprising repeating, for each of the flow classification indices of the plurality, the sending the next flow classification index, the identifying the next transform control instructions, the reading and the transforming the multicast packet, to generate multicast packets for transmission.

4. The method of claim 3 wherein prior to transforming, the method further comprises providing the multicast packet with each next flow classification index of the plurality to an egress processor, and

wherein transforming further comprises transforming the multicast packet by the egress processor in accordance with each next flow classification index.

5. The method of claim 4 wherein a packet classifier performs identifying the plurality of flow classification indices, sending the multicast packet and the first flow classification index, and sending each next flow classification index without the multicast packet, and

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

6. The method of claim 5 wherein the packet classifier is comprised of a first multiprocessor system and the packet transformer is comprised of a second multiprocessor system which includes the egress processor.

7. The method of claim 1 wherein the flow classification index corresponds with a packet flow for a packet, and when the packet flow is a multicast packet, the method further comprises retrieving an additional flow classification index for each instance of multicasting, and sending each additional of the flow classification indices without the multicast packet to the packet transformer,

wherein the flow classification indices include a descriptor to identify the flow as a multicast flow.

8. The method of claim 1 further comprising:

performing a hash on header portions of a received packet to determine a flow classification block index; and

looking up the flow classification block index in a flow classification block (FCB) to determine a flow classification index for a unicast packet and a location of the plurality of flow classification indices for the multicast packet.

9. The method of claim 1 wherein transforming includes replacing at least portions of a header of multicast packet with new portions, the new portions being in accordance with the transform control instructions.

10. The method of claim 1 wherein a single flow classification index is identified for a unicast packet and the method includes:

sending the unicast packet and a single flow classification index to the packet transformer,

buffering the unicast packet in the memory associated with the packet transformer;

identifying transform control instructions for the unicast packet from the single flow classification index; and

transforming the unicast packet in accordance with the identified transform control instructions.

11. The method of claim 10 wherein when an incoming packet is identified as a unicast packet, the method further includes refraining from performing for the unicast packet:

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

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

reading a packet from the memory; and

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

21. The article of claim 20 wherein the instructions further result in repeating, for each of the flow classification indices of the plurality, the sending the next flow classification index, the identifying the next transform control instructions, the reading and the transforming the multicast packet, to generate multicast packets for transmission, and

wherein prior to transforming, the multicast packet is provided with each next flow classification index of the plurality to an egress processor, and

wherein transforming further results in transforming the multicast packet by the egress processor in accordance with each next flow classification index.

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

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

28. The method of claim 21 further comprising:

identifying a plurality of flow classification indices for the packet;

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

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

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

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

29. The method of claim 28 further comprising:

sending a next of the flow classification indices without the 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;

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

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

30. The method of claim 29 wherein prior to transforming, the method further comprises providing the packet with each next flow classification index of the plurality to an egress processor, and

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

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

22. In a virtual routing system having a plurality of virtual routers (VRs) instantiated by a virtual routing engine (VRF), 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 received packet; and

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

23. The method of claim 22 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.

24. The method of claim 23 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;

25. The method of claim 23 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.

27-1. The method of claim 21 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 VRE, each capable of instantiating a plurality of VRs.