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

• US 7,266,120 B2
• Filed: 11/18/2002
• Issued: 09/04/2007
• Est. Priority Date: 11/18/2002
• Status: Active Grant

• Current Assignee: Fortinet Inc.
• Original Assignee: Fortinet Inc.
• Inventors: Millet, Tim, Hussain, Zahid, Cheng, Joseph
• Primary Examiner(s): Chan; Wing
• Assistant Examiner(s): ABELSON, RONALD B
• Application Number:
  US10/298,815
• Publication Number:
  US 20040095934A1
• Time in Patent Office: 1,751 Days
• Field of Search: None
• 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

1. An article comprising a computer-readable storage medium having stored thereon computer-readable instructions for packet multicasting, 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.

2. The article of claim 1 wherein the computer-readable 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.

69. The article of claim 2 wherein the computer-readable instructions further result in during reading, the multicast packet is read from a same buffer for each instance of multicasting.

70. The article of claim 2 wherein the computer-readable instructions further result in:

identifying a plurality of flow classification indices for the 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.

71. The article of claim 70 wherein the computer-readable instructions further result in:

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;

transforming the multicast 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 of the next transform control instructions, the reading and the transforming of the multicast packet, to generate multicast packets for transmission.

72. The article of claim 71 wherein the computer-readable instructions further result in prior to transforming, providing the multicast packet with each next flow classification index of the plurality to an egress processor of the computing platform, and

wherein transforming further comprises transforming the 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 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 of the transform control instructions and providing the multicast packet with each next flow classification index of the plurality to the egress processor.

3. 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;

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.

4. The method of claim 3 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.

5. The method of claim 4 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.

6. The method of claim 5 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.

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

8. The method of claim 3 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 3 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 3 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; and

reading a packet from the memory; and

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

12. 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;

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

wherein the flow classification index corresponds with a packet flow for a packet, and when the packet flow is a multicast packet, 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.

13. The method of claim 12 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.

14. The method of claim 13 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.

15. The method of claim 14 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.

16. The method of claim 15 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.

17. The method of claim 12 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.

18. The method of claim 12 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.

19. The method of claim 12 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.

20. The method of claim 19 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; and

reading a packet from the memory; and

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

21. 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;

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

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.

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

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

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

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

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

27. The method of claim 21 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.

28. The method of claim 21 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.

29. The method of claim 21 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.

30. The method of claim 29 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; and

reading a packet from the memory; and

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

31. 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;

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

identifying a single flow classification index for a unicast packet;

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.

32. The method of claim 31 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.

33. The method of claim 32 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.

34. The method of claim 33 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.

35. The method of claim 34 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.

36. The method of claim 35 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.

37. The method of claim 31 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.

38. The method of claim 31 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.

39. The method of claim 31 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.

40. The method of claim 31 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; and

reading a packet from the memory; and

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

41. 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, wherein the packet classifier sends a next of the flow classification indices without the multicast packet to the packet transformer, and the packet transformer identifies 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.

42. The system of claim 41 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.

43. The system of claim 41 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 of the next transform control instructions, the reading and the transforming of the multicast packet, to generate multicast packets for transmission.

44. The system of claim 41 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.

45. The system of claim 41 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.

46. The system of claim 45 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.

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

48. 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, 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.

49. The system of claim 48 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.

50. The system of claim 49 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.

51. The system of claim 50 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.

52. The system of claim 48 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.

53. The system of claim 52 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.

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

55. A packet multicasting system comprising:

a packet transformer, comprised of a first multiprocessor system, to transform a multicast packet in accordance with transform control instructions; and

a packet classifier, comprised of a second multiprocessor system, 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.

56. The system of claim 55 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.

57. The system of claim 56 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.

58. The system of claim 57 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.

59. The system of claim 55 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.

60. The system of claim 55 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.

61. The system of claim 60 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.

62. 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 and a second multicast packet from a same service provider, wherein the first received multicast packet and the second received multicast packet have identical layer-two through layer-four (L2-L4) headers;

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 a first set of multicast destinations;

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 a second set of multicast destinations.

63. The method of claim 62 further comprising:

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

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

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

65. The method of claim 62 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.

66. The method of claim 62 further comprising:

identifying a plurality of flow classification indices for a 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.

67. The method of claim 66 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 received packet from the memory;

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

68. The method of claim 67 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 received packet with each next flow classification index of the plurality to the egress processor.