Lookup front end packet output processor

• US 9,497,117 B2
• Filed: 11/18/2013
• Issued: 11/15/2016
• Est. Priority Date: 08/02/2011
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan, Bouchard, Gregg A., Hardesty, Jeffrey R., Dahlmann, Troy S., Szypulski, Karen A.
• Primary Examiner(s): DAILEY, THOMAS J
• Application Number:
  US14/082,365
• Publication Number:
  US 20140188973A1
• Time in Patent Office: 1,093 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/203 using migration
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0207 with multidimensional access, e.g. row/column, matrix
• CPC Class Codes: G06F 12/04 Addressing variable-length words or parts of words
• CPC Class Codes: G06F 12/06 Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication G06F12/08 takes precedence
• CPC Class Codes: G06F 12/0623 for memory modules
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 13/16 for access to memory bus G06F13/28 takes precedence
• CPC Class Codes: G06F 13/1642 with request queuing
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/027 Frames
• CPC Class Codes: G11C 7/1075 for multiport memories each having random access ports and serial ports, e.g. video RAM
• CPC Class Codes: H04L 43/18 Protocol analysers
• CPC Class Codes: H04L 45/742 : Route cache; Operation thereof
• CPC Class Codes: H04L 45/745 : Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7452 : Multiple parallel or consecutive lookup operations lookup operation involving Bloom filters H04L45/7459
• CPC Class Codes: H04L 47/2441 : relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/39 : Credit based
• CPC Class Codes: H04L 63/0227 : Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/0263 : Rule management
• CPC Class Codes: H04L 63/06 : for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/10 : for controlling access to devices or network resources
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 69/02 : Protocol performance
• CPC Class Codes: H04L 69/22 : Parsing or analysis of headers
• CPC Class Codes: Y02B 70/30 : Systems integrating technologies related to power network operation and communication or information technologies for improving the carbon footprint of the management of residential or tertiary loads, i.e. smart grids as climate change mitigation technology in the buildings sector, including also the last stages of power distribution and the control, monitoring or operating management systems at local level
• CPC Class Codes: Y02D 10/00 : Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A packet processor provides for rule matching of packets in a network architecture. The packet processor includes a lookup cluster complex having a number of lookup engines and respective on-chip memory units. The on-chip memory stores rules for matching against packet data. A lookup front-end receives lookup requests from a host, and processes these lookup requests to generate key requests for forwarding to the lookup engines. As a result of the rule matching, the lookup engine returns a response message indicating whether a match is found. The lookup front-end further processes the response message and provides a corresponding response to the host.

Claims

1. A method of processing a packet comprising:

merging a plurality of sub-tree responses from a processing cluster, the processing cluster performing rule matching for a packet, the plurality of sub-tree responses being responsive to lookup requests associated with the packet, each of the sub-tree responses including a lookup response based on rule matching the packet against a subset of rules specified by a sub-tree; and

outputting a lookup result to a host processor, the lookup result including at least one of the plurality of sub-tree responses based on relative priority of the plurality of sub-tree responses.

2. The method of claim 1, wherein the merging includes selecting one of the sub-tree responses having a highest-priority rule match and eliminating sub-tree responses that are absent the highest-priority rule match, the lookup result including the one of the sub-tree responses.

3. The method of claim 1, wherein the sub-tree responses are a subset of a plurality of responses from the processing cluster, and further comprising:

determining whether the plurality of responses is to be coalesced based on an indicator associated with the packet, the lookup result including a selection of the plurality of responses based on whether the plurality of responses is to be coalesced.

4. The method of claim 3, further comprising updating a table based on the plurality of responses, the table indicating in-process lookup requests at a plurality of processing clusters.

5. The method of claim 4, wherein the indicator is stored at the table.

6. The method of claim 4, further comprising forwarding the plurality of responses to a transmit buffer.

7. The method of claim 6, further comprising configuring a slot of the transmit buffer for placement of the plurality of responses prior to receipt of the plurality of responses.

8. The method of claim 7, wherein the selection of the plurality of responses is placed into the slot.

9. The method of claim 7, wherein the slot is configured having a predetermined order relative to other slots such that the lookup result is output in the predetermined order.

10. The method of claim 6, further comprising configuring a plurality of groups, each group having a plurality of slots of the transmit buffer for placement of the plurality of responses prior to receipt of the plurality of responses.

11. The method of claim 10, wherein responses in a first group of the plurality of groups are output in a predetermined order relative to other responses in the first group.

12. The method of claim 11, wherein responses in a second group of the plurality of groups are output independent of order relative to other responses in the second group.

13. The method of claim 12, further comprising placing the plurality of responses in one of the first and second groups based on data of packets associated with lookup results corresponding to the plurality of slots.

14. The method of claim 1, further comprising:

detecting whether the lookup result includes an interrupt configuration; and

in response to an interrupt configuration, outputting the lookup result to the host processor independent of a predetermined order of lookup results.

15. The method of claim 14, wherein the sub-tree responses are a subset of a plurality of responses from the processing cluster, and wherein the lookup result includes a single one of the plurality of responses, the single one of the plurality of responses being a first-most received response.

16. The method of claim 1, wherein the sub-tree responses are a subset of a plurality of responses from the processing cluster, and further comprising:

determining whether the plurality of responses is to be transmitted in-order or out-of-order; and

outputting a lookup result to a host processor according to the determination, the lookup result including a selection of the plurality of responses.

17. The method of claim 16, wherein determining whether the plurality of responses is to be transmitted in-order or out-of-order includes querying a table indicating an in-order or out-of-order status for the packet.

18. The method of claim 16, further comprising forwarding the plurality of responses to a slot of a transmit buffer.

19. An apparatus for processing a packet comprising:

a front-end, implemented in a packet processing circuit, configured to merge a plurality of sub-tree responses from a processing cluster, the processing cluster performing rule matching for a packet, the plurality of sub-tree responses being responsive to lookup requests associated with the packet, each of the sub-tree responses including a lookup response based on rule matching the packet against a subset of rules specified by a sub-tree; and

an output module, implemented in a packet processing circuit, configured to output a lookup result to a host processor, the lookup result including at least one of the plurality of sub-tree responses based on relative priority of the plurality of sub-tree responses.

20. The apparatus of claim 19, wherein the front-end is further configured to select one of the sub-tree responses having a highest-priority rule match and eliminate sub-tree responses that are absent the highest-priority rule match, the lookup result including the one of the sub-tree responses.

21. The apparatus of claim 19, wherein the sub-tree responses are a subset of a plurality of responses from the processing cluster, and further comprising:

a back-end configured to determine whether the plurality of responses is to be coalesced based on an indicator associated with the packet, the lookup result including a selection of the plurality of responses based on whether the plurality of responses is to be coalesced.

22. The apparatus of claim 21, further comprising a table, the front-end updating the table based on the plurality of responses, the table indicating in-process lookup requests at a plurality of processing clusters.

23. The apparatus of claim 22, wherein the indicator is stored at the table.

24. The apparatus of claim 22, further comprising a transmit buffer configured to receive the plurality of responses.

25. The apparatus of claim 24, wherein the back-end configures a slot of the transmit buffer for placement of the plurality of responses prior to receipt of the plurality of responses.

26. The apparatus of claim 25, wherein the selection of the plurality of responses is placed into the slot.

27. The apparatus of claim 25, wherein the slot is configured having a predetermined order relative to other slots such that the lookup result is output in the predetermined order.

28. The apparatus of claim 24, wherein the back-end configures a plurality of groups, each group having a plurality of slots of the transmit buffer for placement of the plurality of responses prior to receipt of the plurality of responses.

29. The apparatus of claim 28, wherein responses in a first group of the plurality of groups are output in a predetermined order relative to other responses in the first group.

30. The apparatus of claim 29, wherein responses in a second group of the plurality of groups are output independent of order relative to other responses in the second group.

31. The apparatus of claim 30, wherein the back-end is further configured to place the plurality of responses in one of the first and second groups based on data of packets associated with lookup results corresponding to the plurality of slots.

32. The apparatus of claim 19, wherein the output block is further configured, in response to a signal indicating that the lookup result includes an interrupt configuration, to output the lookup result to the host processor independent of a predetermined order of lookup results.

33. The apparatus of claim 32, wherein the sub-tree responses are a subset of a plurality of responses from the processing cluster, wherein the lookup result includes a single one of the plurality of responses, the single one of the plurality of responses being a first-most received response.

34. The apparatus of claim 19, wherein the sub-tree responses are a subset of a plurality of responses from the processing cluster, and further comprising a back-end configured to determine whether the plurality of responses is to be transmitted in-order or out-of-order, the output module outputting the lookup result to a host processor according to the determination, the lookup result including a selection of the plurality of responses.

35. The apparatus of claim 34, wherein the back-end is further configured to query a table indicating an in-order or out-of-order status for the packet.

36. The apparatus of claim 34, wherein the back-end is further configured to forward the plurality of responses to a slot of a transmit buffer.

37. An apparatus for processing a packet comprising:

a computer processor configured to receive a plurality of responses from a processing cluster and output a lookup result to a host processor, the plurality of responses include a plurality of sub-tree responses, the computer processor operating a front-end, a back-end, and an output module;

the front-end configured to merge a plurality of sub-tree responses from a processing cluster, the processing cluster performing rule matching for a packet, the plurality of sub-tree responses being responsive to lookup requests associated with the packet;

the back-end configured to determine;

     1) whether the plurality of responses is to be coalesced based on an indicator associated with the packet, and

     2) whether the plurality of responses is to be transmitted in-order or out-of-order;

the output module configured to output the lookup result to the host processor according to the determination, the lookup result including at least one of the plurality of sub-tree responses based on relative priority of the plurality of sub-tree responses, the lookup result further including a selection of the plurality of responses based on whether the plurality of responses is to be coalesced.