Lookup front end packet input processor

• US 9,729,527 B2
• Filed: 08/30/2012
• Issued: 08/08/2017
• 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: Bouchard, Gregg A., Goyal, Rajan
• Primary Examiner(s): Zhu, Alvin
• Application Number:
  US13/599,276
• Publication Number:
  US 20130058332A1
• Time in Patent Office: 1,804 Days
• 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. An apparatus comprising:

a memory storing a Rule Compiled Data Structure (RCDS), the RCDS representing a set of rules for packet classification, the RCDS including a decision tree for selecting a subset of the set of rules for filtering a given packet, the decision tree including a root node and a plurality of leaf nodes, each of the plurality of leaf nodes indicating one of the subset of the set of rules, the root node indicating a starting address in the memory for the set of rules;

a host command interface, the host command interface configured to receive one or more host commands for an incremental update for the RCDS;

a processor coupled to the memory and the host command interface, the processor configured to;

a) receive a key extracted from the packet, the key indicating which of the set of rules are applicable to the packet, and

b) perform an active search of the RCDS to;

     1) apply the key to the decision tree to locate a matching leaf node out of the plurality of leaf nodes, the matching leaf node indicating the subset of the set of rules, and

     2) classify the given packet based on the subset of the set of rules and independent of rules excluded from the subset of rules, the RCDS being updated based on the one or more host commands received, the RCDS being updated after the active search is completed.

2. The apparatus of claim 1, wherein the one or more host commands is a host request packet including a request host transaction identifier and a host access command, the host access command specifying a host read or host write access to the RCDS, the host access command including a control header, the control header including one or more ordering flags, the processor further configured to:

decode the one or more ordering flags; and

determine an ordering of a host lookup request and the host access command specified based on the one or more ordering flags decoded.

3. The apparatus of claim 2, wherein the one or more ordering flags includes a host response flag, the host response flag indicating an explicit response being sent after completion of the host access command, the explicit response being a packet including a response host transaction identifier matching the request host transaction identifier, wherein the explicit response is sent for a host write access completed and the explicit response is not sent for a host read access completed.

4. The apparatus of claim 3, wherein the one or more ordering flags includes a local response flag, the local response flag indicating host access commands being completed based on bus order, wherein bus order forces completion of the host access command before a subsequent host lookup request or host access command.

5. The apparatus of claim 4, wherein the one or more ordering flags includes an atomic flag, the atomic flag indicating pending host lookup requests being completed before the host access command is completed.

6. The apparatus of claim 5, wherein the host command indicates a table identifier, wherein the pending host lookup requests are completed before the host access command is completed given the pending host lookup request is for a table identified by the table identifier.

7. The apparatus of claim 6, wherein the table identifier identifies a tree, the tree being the RCDS.