Lookup front end packet input processor

Patent metadata

Field	Value
Publication number	US-9729527-B2
Application number	US-201213599276-A
Country	US
Kind code	B2
Filing date	Aug 30, 2012
Priority date	Aug 2, 2011
Publication date	Aug 8, 2017
Grant date	Aug 8, 2017

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.

First claim

What is claimed is:

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.

Assignees

• Goyal Rajan
• Bouchard Gregg A
• Cavium Inc

Inventors

• Goyal Rajan
• Bouchard Gregg A

Classifications

• G06F9/5027

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title

• H04L69/22

  Parsing or analysis of headers · CPC title

• H04L43/18 Primary

  Protocol analysers · CPC title

• G06F13/16

  for access to memory bus (G06F13/28 takes precedence) · CPC title

• G06N5/02

  Knowledge representation; Symbolic representation · CPC title