Packet distribution with prefetch in a parallel processing network device

Abstract

A packet processing system comprises a plurality of packet processing nodes configured to process packets. The packet processing nodes are arranged in a plurality of packet processing clusters. The packet processing system also includes a plurality of prefetch buffers respectively associated with different ones of the packet processing clusters. A first prefetch buffer of the plurality of prefetch buffers is associated with a first packet processing cluster and is configured to store packets distributed for processing to the first packet processing cluster when the first packet processing clusters does not include any packet processing nodes available for processing of the packets.

What is claimed is: 
     
       1. A packet processing system, comprising:
 a plurality of packet processing nodes configured to process packets and to determine respective egress ports via which the packets are to be transmitted, the packet processing nodes arranged in a plurality of packet processing clusters; 
 a plurality of prefetch buffers, ones of prefetch buffers respectively corresponding to different ones of the packet processing clusters, a first prefetch buffer corresponding to a first packet processing cluster and configured to store packets distributed to the first packet processing cluster for subsequent processing by one or more of the packet processing nodes of the first packet processing cluster before processing by any packet processing nodes of the first packet processing cluster and while packet processing nodes of the plurality of packet processing nodes of the first packet processing cluster are currently processing other packets; 
 a global distributor coupled to the plurality of packet processing clusters, the global distributor configured to selectively distribute a packet to one of the packet processing clusters for processing of the packet by one of a plurality of packet processing nodes included in the packet processing cluster to which the packet is distributed; and 
 a local distributor of the first packet processing cluster, the local distributor configured to distribute packets, received from the global distributor, to available packet processing nodes of the plurality of packet processing nodes of the first packet processing cluster and configured to cause a delay in distribution of the packets by the global distributor to the local distributor. 
 
     
     
       2. The packet processing system of  claim 1 , wherein the global distributor is further configured to
 receive, from ones of the respective packet processing clusters one or both of (i) respective available processor indications indicative of whether the packet processing cluster includes packet processing nodes available for processing of the packets and (ii) respective buffer space indications indicative of availability of buffer space in the respective prefetch buffer corresponding to the packet processing cluster, and 
 selectively distribute the packets to one of the packet processing clusters based on the received one or both of respective available processor indications and respective buffer space indications. 
 
     
     
       3. The packet processing system of  claim 1 , wherein the local distributor is configured to:
 generate a buffer space indication indicative of a fill level of the first prefetch buffer; 
 mask the fill level of the first prefetch buffer to cause the delay in the distribution of the packets by the global distributor to the local distributor until at least one of the packet processing nodes has completed a predetermined portion of processing of a packet currently being processed by the packet processing node; and 
 provide the buffer space indication to the global distributor. 
 
     
     
       4. The packet processing system of  claim 1 , wherein the local distributor is further configured to, while the packet processing nodes of the plurality of packet processing nodes of the first packet processing cluster are processing other packets:
 store a packet distributed by the global distributor to the first packet processing cluster in the first prefetch buffer, and 
 when a packet processing node of the plurality of packet processing nodes of the first packet processing cluster becomes available for processing the packet, 
 retrieve the packet from the first prefetch buffer, and 
 provide the packet to the available processing node for processing of the packet. 
 
     
     
       5. The packet processing system of  claim 1 , wherein the local distributor is further configured to
 generate one or both of (i) an available processor indication indicative of whether the first packet processing cluster includes a packet processing node, of the plurality of packet processing nodes of the first packet processing cluster, available for processing packets and (ii) a buffer space indication indicative of a fill level of the first prefetch buffer, and 
 provide the one or both of available processor indication and buffer space indication to the global distributor. 
 
     
     
       6. The packet processing system of  claim 5 , wherein the global distributor is configured to
 receive, from the local distributor, the one or both of (i) the available processor indication and (ii) the buffer space indication, and 
 determine, based on the received one or both of (i) the available processor indication and (ii) the buffer space indication, whether the first packet processing cluster is to be considered for selection of a packet processing cluster, of the plurality of packet processing clusters, to which to send a packet. 
 
     
     
       7. The packet processing system of  claim 5 , wherein the local distributor is further configured to generate the buffer space indication to indicate a fill level of the first prefetch buffer. 
     
     
       8. The packet processing system of  claim 5 , wherein the local distributor is further configured to, when the plurality of packet processing nodes of the first packet processing cluster does not include any packet processing nodes available for processing packets, mask the fill level of the first buffer until at least one of the packet processing nodes has completed a predetermined portion of processing of a packet currently being processed by the packet processing node. 
     
     
       9. A method for processing packets in a network device, the method comprising:
 receiving a plurality of packets, including at least a first packet, at an ingress port of the network device, wherein the network device includes a plurality of packet processing nodes configured to process the packets and determine respective egress ports via which the packets are to be transmitted, the packet processing nodes arranged in a plurality of packet processing clusters, 
 distributing, by a global distributor of the network device, the packets to the packet processing clusters for processing of the packets, including distributing the first packet to a first packet processing cluster of the plurality of packet processing clusters, wherein ones of the packet processing clusters respectively correspond to ones of a plurality of prefetch buffers, a first prefetch buffer corresponding to the first packet processing cluster and configured to store packets distributed to the first packet processing cluster for subsequent processing by one or more of the packet processing nodes of the first packet processing cluster before processing by any packet processing nodes of the first packet processing cluster and while packet processing nodes of the plurality of packet processing nodes of the first packet processing cluster are currently processing other packets, and 
 causing, by a local distributor of the first packet processing cluster, a delay in distribution of the first packet by the global distributor to the first packet processing cluster. 
 
     
     
       10. The method of  claim 9 , further comprising
 receiving the first packet at the local distributor of the first packet processing cluster, 
 distributing the first packet to a packet processing node included in the plurality of packet processing nodes of the first packet processing cluster, and 
 processing the packet using the packet processing node in the plurality of packet processing nodes of the first packet processing cluster. 
 
     
     
       11. The method of  claim 10 , wherein distributing the first packet to the packet processing node included in the plurality of packet processing nodes of the first packet processing cluster includes
 when none of the packet processing nodes included in the plurality of packet processing nodes of the first packet processing cluster are available for processing of the first packet, storing the packet in the first prefetch buffer of the plurality of prefetch buffers, the first prefetch buffer corresponding to the first packet processing cluster, and 
 when a packet processing node of the plurality of packet processing nodes of the first packet processing cluster becomes available for processing the first packet,
 retrieving the first packet from the first prefetch buffer, and 
 providing the first packet to the packet processing node available for processing of the first packet. 
 
 
     
     
       12. The method of  claim 11 , further comprising
 generating, by the local distributor, one or both of (i) an available processor indication indicative of whether the first packet processing cluster includes a packet processing node, of the plurality of packet processing nodes of the first packet processing cluster, available for processing packets and (ii) a buffer space indication indicative of a fill level of the first prefetch buffer, and 
 providing the one or both of (i) the available processor indication and (ii) the buffer space indication to the global distributor. 
 
     
     
       13. The method of  claim 12 , further comprising
 receiving, at the global distributor from the local distributor, the one or both of (i) the available processor indication and (ii) the buffer space indication, and wherein 
 distributing the first packet includes determining, based on the received one or both of (i) the available processor indication and (ii) the buffer space indication, whether the first packet processing cluster is to be considered for selection of a packet processing cluster, of the plurality of packet processing clusters, to which to distribute the first packet. 
 
     
     
       14. The method of  claim 12 , further comprising generating the buffer space indication to indicate a fill level of the first prefetch buffer. 
     
     
       15. The method of  claim 14 , wherein generating the buffer space indication includes, when the first packet processing cluster does not include any packet processing nodes available for processing packets, masking the fill level of the first buffer until at least one of the packet processing nodes has completed a predetermined portion of processing of a packet currently being processed by the packet processing node. 
     
     
       16. The method of  claim 9 , further comprising
 receiving, from respective packet processing clusters one or both of (i) respective available processor indications indicative of whether the packet processing clusters include packet processing nodes available for processing of the packets and (ii) respective buffer space indications indicative of availability of buffer space in respective prefetch buffers corresponding to ones of the packet processing clusters, and 
 wherein distributing the packets to the packet processing clusters includes selecting the packet processing clusters to which to distribute particular packets based on the one or both of respective the packets to the packet processing clusters based on the received one or both of respective available processor indications and respective buffer space indications. 
 
     
     
       17. A packet processing system, comprising:
 a plurality of packet processing nodes configured to process packets and determine respective egress ports via which the packets are to be transmitted, the packet processing nodes arranged in a plurality of packet processing clusters, 
 a global distributor configured to distribute packets for processing to the packet processing clusters, the global distributor comprising a distribution controller configured to select packet processing clusters to which to distribute a packet based on one or both of (i) respective available processor indications indicative of whether ones of the packet processing clusters include packet processing nodes available for processing of the packet and (ii) respective buffer space indications indicative of availability of buffer space in respective prefetch buffers corresponding to ones of the packet processing clusters, and 
 a local distributor corresponding to a first packet processing cluster of the plurality of packet processing clusters and configured to cause a delay in distribution of packets by the global distributor to the first packet processing cluster; 
 wherein a first prefetch buffer corresponding to the first packet processing cluster is configured to store packets distributed for subsequent processing by one or more of the packet processing nodes of the first packet processing cluster before processing by any packet processing nodes of the first packet processing cluster and while packet processing nodes of the plurality of packet processing nodes of the first packet processing cluster are currently processing other packets. 
 
     
     
       18. The packet processing system of  claim 17 , wherein the packet processing system further comprises a local distributor associated with the first packet processing cluster, the local distributor configured to distribute packets, received from the global distributor, to available packet processing nodes of the plurality of packet processing nodes of the first packet processing cluster. 
     
     
       19. The packet processing system of  claim 18 , wherein the local distributor is further configured to, while the packet processing nodes of the plurality of packet processing nodes of the first packet processing cluster are currently processing other packets,
 store the packet in the first prefetch buffer corresponding to the first packet processing cluster, and 
 when a packet processing node of the plurality of packet processing nodes of the first packet processing cluster becomes available for processing the packet, 
 retrieve the packet from the prefetch buffer, and 
 provide the packet to the available processing node for processing of the packet. 
 
     
     
       20. The packet processing system of  claim 19 , wherein the local distributor is further configured to
 generate one or both of (i) an available processor indication indicative of whether the first packet processing cluster includes any packet processing nodes, of the plurality of packet processing nodes of the first packet processing cluster, available for processing packets and (ii) a buffer space indication indicative of a fill level of the first prefetch buffer, and 
 provide the one or both of available processor indication and buffer space indication to the global distributor. 
 
     
     
       21. The packet processing system of  claim 20 , wherein the global distributor is configured to
 receive, from the local distributor, the one or both of (i) the available processor indication and (ii) the buffer space indication, and 
 determine, based on the received one or both of (i) the available processor indication and (ii) the buffer space indication, whether the first packet processing cluster is to be considered for selection of a packet processing cluster, of the plurality of packet processing clusters, to which to send a packet. 
 
     
     
       22. The packet processing system of  claim 20 , wherein the local distributor is further configured to generate the buffer space indication to indicate a fill level of the first prefetch buffer. 
     
     
       23. The packet processing system of  claim 20 , wherein the local distributor is further configured to, when the plurality of packet processing nodes of the first packet processing cluster does not include any packet processing nodes available for processing packets, mask the fill level of the first buffer until at least one of the packet processing nodes has completed a predetermined portion of processing of a packet currently being processed by the packet processing node. 
     
     
       24. The packet processing system of  claim 18 , wherein the global distributor is further configured to:
 account for one or both (i) available processors at respective ones of the packet processing clusters and (ii) available buffer space in respective prefetch buffers corresponding to ones of the packet processing clusters, and 
 generate one or both of (i) the respective available processor indications based on the accounting of available processors at the packet processing clusters and (ii) the respective buffer space indications based on the accounting of available buffer space in respective prefetch buffers corresponding to ones of the packet processing clusters. 
 
     
     
       25. A method for processing packets in a network device, the method comprising:
 receiving packets at the network device, wherein the network device includes a plurality of packet processing nodes, the packet processing nodes arranged in a plurality of packet processing clusters, and 
 distributing the packets to the plurality of packet processing clusters for processing of the packets, including distributing the packets based on one or both of (i) respective available processor indications indicative of whether ones of the packet processing clusters include packet processing nodes available for processing of the packets and determination of respective egress ports via which the packets are to be transmitted and (ii) respective buffer space indications indicative of availability of buffer space in respective prefetch buffers corresponding to ones of the packet processing clusters; 
 wherein the plurality of packet processing clusters includes a first packet processing cluster, a first prefetch buffer corresponding to a first packet processing cluster and configured to store packets distributed to the first packet processing cluster for subsequent processing by one or more of the packet processing nodes of the first packet processing cluster before processing by any packet processing nodes of the first packet processing cluster and while packet processing nodes of the plurality of packet processing nodes of the first packet processing cluster are currently processing other packets; 
 wherein the method further comprises causing a delay in distribution of packets to the first packet processing cluster. 
 
     
     
       26. The method of  claim 25 , the method further comprising distributing, using a local distributor associated with the first packet processing cluster to available packet processing nodes of the plurality of packet processing nodes of the first packet processing cluster, packets distributed to the first packet processing cluster by the global distributor. 
     
     
       27. The method of  claim 26 , further comprising, while the packet processing nodes of the plurality of packet processing nodes of the first packet processing cluster are currently processing other packets,
 storing a packet distributed by the global distributor to the first packet processing cluster in the first prefetch buffer corresponding to the first packet processing cluster, and 
 when a packet processing node of the plurality of packet processing nodes of the first packet processing cluster becomes available for processing the packet, 
 retrieving the packet from the first prefetch buffer, and 
 providing the packet to the available processing node for processing of the packet. 
 
     
     
       28. The method of  claim 27 , further comprising
 generating, by the local distributor associated with the first packet processing cluster, one or both of (i) an available processor indication indicative of whether the first packet processing cluster includes any packet processing nodes, of the plurality of packet processing nodes of the first packet processing cluster, available for processing packets and (ii) a buffer space indication indicative of a fill level of the first prefetch buffer, and 
 providing the one or both of available processor indication and buffer space indication to the global distributor. 
 
     
     
       29. The method of  claim 28 , further comprising
 receiving, at the global distributor from the local distributor associated with the first packet processing cluster, the one or both of (i) the available processor indication and (ii) the buffer space indication, and 
 determining, based on the received one or both of (i) the available processor indication and (ii) the buffer space indication, whether the first packet processing cluster is to be considered for selection of a packet processing cluster, of the plurality of packet processing clusters, to which to send a packet. 
 
     
     
       30. The method of  claim 28 , wherein generating the buffer space indication comprises generating the buffer space indication to indicate a fill level of the first prefetch buffer. 
     
     
       31. The method of  claim 30 , wherein generating the buffer space indication includes, while the plurality of packet processing nodes of the first packet processing cluster are currently processing other packets, masking the fill level of the first prefetch buffer until at least one of the packet processing nodes of the plurality of packet processing nodes of the first packet processing cluster has completed a predetermined portion of processing of a packet currently being processed by the packet processing node. 
     
     
       32. The method of  claim 25 , further comprising:
 accounting for one or both (i) available processors at respective ones of the packet processing clusters and (ii) available buffer space in respective prefetch buffers corresponding to ones of the packet processing clusters, and 
 generating one or both of (i) the respective available processor indications based on the accounting of available processors at the packet processing clusters and (ii) the respective buffer space indications based on the accounting of available buffer space in respective prefetch buffers associated with ones of the packet processing clusters.