Source: http://www.freepatentsonline.com/9031075.html
Timestamp: 2017-10-17 04:10:32
Document Index: 49376538

Matched Legal Cases: ['Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61', 'Application No. 61']

Lookup front end packet input processor - Cavium, Inc.
United States Patent 9031075
14/138931
370/395.32, 370/474, 370/475, 709/203, 709/216, 709/218, 709/219, 709/229
G06F9/46; G06F9/50; G06F12/02; G06F12/04; G06F12/08; G06F13/16; G06N5/02; H04L12/26; H04L12/741; H04L12/747; H04L12/801; H04L12/851; H04L29/06; H04L29/08
370/389, 370/392, 370/395.3, 370/395.31, 370/395.32, 370/474, 370/475, 709/203, 709/216, 709/217, 709/218, 709/219, 709/225, 709/229
Download PDF 9031075 PDF help
20140269718 PACKET EXTRACTION OPTIMIZATION IN A NETWORK PROCESSOR 2014-09-18 Goyal et al.
20140188973 LOOKUP FRONT END PACKET OUTPUT PROCESSOR 2014-07-03 Goyal et al.
8711861 Lookup front end packet input processor 2014-04-29 Goyal et al.
8606959 Lookup front end packet output processor 2013-12-10 Goyal et al.
20130058332 LOOKUP FRONT END PACKET INPUT PROCESSOR 2013-03-07 Goyal
20130036152 LOOKUP FRONT END PACKET OUTPUT PROCESSOR 2013-02-07 Goyal et al.
20130034100 LOOKUP FRONT END PACKET INPUT PROCESSOR 2013-02-07 Goyal et al.
8352391 Fast update filter 2013-01-08 Kapadia
20080031258 Overload protection for SIP servers 2008-02-07 Acharya et al.
7277425 High-speed router switching architecture 2007-10-02 Sikdar
20060136570 Runtime adaptable search processor 2006-06-22 Pandya
20040260832 Bandwidth, framing and error detection in communications between multi-processor clusters of multi-cluster computer systems 2004-12-23 Kota et al.
20030225909 Address space management in systems having multiple multi-processor clusters 2003-12-04 Glasco et al.
5995511 Digital network including mechanism for grouping virtual message transfer paths having similar transfer service rates to facilitate efficient scheduling of transfers thereover 1999-11-30 Zhou et al.
JP11127195 May, 1999
JP2002152268A 2002-05-24 MULTILAYER PACKET PROCESSING UNIT
JP2007020226A 2007-01-25 METHODS AND APPARATUS FOR SWITCHING ATM, TDM, AND PACKET DATA THROUGH SINGLE COMMUNICATIONS SWITCH
JP2009027286A 2009-02-05 NETWORK, NETWORK DEVICE AND TRANSMISSION PATH REDUNDANCY FORMATION METHOD USED FOR THEM
JP2012044379A 2012-03-01 NODE, PACKET TRANSFER METHOD, AND COMMUNICATION NETWORK
WO2011078812A1 2011-06-30 SYSTOLIC ARRAY ARCHITECTURE FOR FAST IP LOOKUP
WO2013019996A1 2013-02-07 LOOKUP FRONT END INPUT PROCESSOR
WO2013020001A1 2013-02-07 LOOKUP FRONT END OUTPUT PROCESSOR
JPH11127195A 1999-05-11
Notification of Transmittal of the International Search Report and The Written Opinion of the International Searching Authority for PCT/US2012/049400, “Lookup Front End Input Processor,” mailed Dec. 21, 2012.
Notice of Publication of Application for U.S. Appl. No. 13/565,767, “Lookup Front End Packet Output Processor,” Date of Publication, Feb. 7, 2013.
Decision on Request for Participation in the Patent Prosecution Highway Program and Petition to Make Special Under 37 CFR 1.102(a) for U.S. Appl. No. 13/565,767, “Lookup Front End Packet Output Processor,” Date Mailed, Mar. 11, 2013.
Non-Final Office Action for U.S. Appl. No. 13/565,767, “Lookup Front End Packet Output Processor,” Dated Apr. 22, 2013.
Notice of Allowance and Fees Due for U.S. Appl. No. 13/565,767, “Lookup Front End Packet Output Processor,” Date Mailed, Aug. 5, 2013.
Notification of Transmittal of International Search Report and Written Opinion of the International Searching Authority of PCT/US2012/049405, “Lookup Front End Packet Output Processor,” date of mailing, Oct. 19, 2012.
Notice of Publication of Application for U.S. Appl. No. 13/599,276, “Lookup Front End Packet Input Processor,” Date of Publication, Mar. 7, 2013.
Non-Final Office Action for U.S. Appl. No. 13/565,727, “Lookup Front End Packet Input Processor,” Dated Jul. 31, 2013.
Notification Concerning Transmittal of International Preliminary Report on Patentability, PCT/US2012/049400, “Lookup Front End Input Processor,” mailed Feb. 13, 2014.
Notification Concerning Transmittal of International Preliminary Report on Patentability, PCT/US2012/049405, “Lookup Front End Output Processor,” mailed Feb. 13, 2014.
First Action Interview Pilot Program Office Action for U.S. Appl. No. 13/599,276 “Lookup Front End Packet Input Processor,” Dated Aug. 14, 2014.
This application is a continuation of U.S. application Ser. No. 13/565,727, filed Aug. 2, 2012, which claims the benefit of U.S. Provisional Application No. 61/514,344, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,382, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,379, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,400, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,406, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,407, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,438, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,447, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,450, filed on Aug. 2, 2011; U.S. Provisional Application No. 61/514,459, filed on Aug. 2, 2011; and U.S. Provisional Application No. 61/514,463, filed on Aug. 2, 2011. The entire teachings of the above applications are incorporated herein by reference.
1. A method of processing a packet comprising: generating at least one key based on data of a lookup request; determining, based on an identifier of the lookup request, a subset of processing clusters that are capable of operating rule matching for the at least one key; selecting at least one of the processing clusters of the subset based on availability; and forwarding at least one key request to the at least one selected processing cluster, the key request including the at least one key to initiate rule matching using the key.
2. The method of claim 1, further comprising comparing the identifier against a table to determine a packet header index (PHIDX).
3. The method of claim 2, wherein the at least one key is generated according to the PHIDX.
4. The method of claim 3, wherein the PHIDX indexes an entry in a packet header table (PHT), the entry indicating rules for extracting data from the lookup request to generate the at least one key.
5. The method of claim 1, further comprising comparing the identifier against a table to determine a key format table index (KFTIDX).
6. The method of claim 5, wherein the KFTIDX indexes an entry in a key format table, the entry indicating instructions for extracting fields from the key at the processing cluster.
7. The method of claim 5, wherein the key request further includes the KFTIDX.
8. The method of claim 1, wherein the at least one key includes a plurality of keys and the at least one key request includes a plurality of key requests, each of the plurality of key requests including a different one of the plurality of keys.
9. The method of claim 8, wherein each of the plurality of keys include at least a portion of the data of the lookup request that is distinct from the data included in another of the plurality of keys.
10. The method of claim 1, wherein the processing cluster is selected based on a number of pending requests at the processing cluster relative to a number of pending requests at each of the subset of processing clusters.
11. The method of claim 10, wherein the number of pending requests at the selected cluster is the least among the subset of processing clusters.
12. The method of claim 10, further comprising maintaining a count of the number of pending requests at each of the subset of processing clusters.
13. The method of claim 1, further comprising, upon detection of a selected cluster being unavailable, forwarding the at least one key request to a retry queue.
14. The method of claim 13, further comprising accessing the selected cluster to forward the at least one request from the retry queue to the selected cluster.
15. The method of claim 13, further comprising, in response to detecting a threshold, processing entries in the retry queue until the retry queue is empty.
16. The method of claim 15, wherein the threshold includes at least one of: a timeout, a number of entries in the retry queue, and a number of entries processed by a new work queue.
17. The method of claim 1, further comprising generating an indication of which of the processing clusters has the greatest unused capacity, and wherein selecting one of the processing clusters is based on the indication.
18. The method of claim 1, further comprising dividing the at least one key request into a plurality of sub-tree requests.
19. The method of claim 18, further comprising comparing each of the plurality of sub-tree requests against a respective sub-table.
20. The method of claim 19, wherein each of the sub-tables is located at a separate one of the subset of processing clusters.
21. The method of claim 1, further comprising comparing the identifier of the lookup request against a table to determine at least one table identifier (TID), the TID indicating the subset of processing clusters.
22. An apparatus for processing a packet comprising: a packet header extractor (PHE) configured to generate at least one key based on data of a lookup request; a scheduler output manager configured to: determine, based on an identifier of the lookup request, a subset of processing clusters that are capable of operating rule matching for the at least one key; select at least one of the processing clusters of the subset based on availability; and forward at least one key request to the at least one selected processing cluster, the key request including the at least one key to initiate rule matching using the key.
23. The apparatus of claim 22, wherein the distributor is further configured to compare the identifier against a global definition table to determine a packet header index (PHIDX).
24. The apparatus of claim 23, wherein the at least one key is generated according to the PHIDX.
25. The apparatus of claim 22, further comprising a distributor configured to compare the identifier against a table to determine at least one table identifier (TID), the TID indicating the subset of processing clusters.
Example embodiments of the present disclosure provide methods of processing a packet. The method may be operated by a lookup front-end (LUF) processor that interfaces between a host providing lookup requests via packet header data and a search cluster for providing rule-matching of the packet data. A lookup request, including a packet header of a packet and an associated group identifier (GID), is first received. At least one key is then generated based on data of the packet header. The GID is compared against a global definition table to determine at least one table identifier (TID). Based on the TID, a subset of processing clusters that are capable of operating rule matching for the packet is determined. One of the processing clusters is then selected based on availability. A key request, which includes the key and the TID to initiate rule matching using the key, is then forwarded to the selected processing cluster.
FIGS. 11A and 11B are block diagrams of an example LUF input processor (LIP).
FIGS. 21A and 21B are block diagrams of example data structures for implementing example embodiments of the present disclosure.
A TCAM is a hardware device that functions as a fully associative memory. A TCAM cell stores three values: 0, 1, or ‘X,’ which represents a don't-care bit and operates as a per-cell mask enabling the TCAM to match rules containing wildcards, such as a kleen star ‘*’. In operation, a whole packet header can be presented to a TCAM to determine which entry (rule) it matches. However, the complexity of TCAMs has allowed only small, inflexible, and relatively slow implementations that consume a lot of power. Therefore, a need continues for efficient algorithmic solutions operating on specialized data structures.
FIG. 1 is a block diagram 100 of a typical network topology including network elements employing example embodiments of a search processor. The network topology includes an Internet core 102 including a plurality of core routers 104a-h. Each of the plurality of core routers 104a-h are connected to at least one other of the plurality of core routers 104a-h. Core routers 104a-h that are on the edge of the Internet core 102 (i.e., core routers 102b-e and 102h) are coupled with at least one edge router 106a-f. Each edge router 106a-f is coupled to at least one access router 108a-e.
Likewise, the second host processor 214 is an egress host processor. The second host processor 214 receives egress packets to send from the network 216. The second host processor 214 forwards a lookup request with a packet header (or field) from the egress packets 216 to the search processor 202 over a second Interlaken interface 218. The search processor 202 then processes the packet header using a plurality of rule processing engines employing a plurality of rules to determine a path to forward the packets on the network. The second host processor 214 forwards the processed ingress packets 220 to another network element in the network.
FIG. 3B is a block diagram 320 illustrating an example embodiment of a router employing the search processor 202. The router includes the switched backplane 302 which is coupled to the line cards 306a-b and the processor card 303. The processor card 303 includes a processor 308 and a routing table 328, which can be stored in the memory 304 of the processor card 303. Each line card 306a-b includes a respective local buffer memory 322a-b, a forwarding table 324a-b, and a media access control (MAC) layer 326a-b. The search processor 202 exists within the forwarding table 324a-d of the line card 306a-b.
As an example, a packet is received by the line card 304a at the MAC layer 326a. The MAC layer 326a sends the packet to the forwarding table 324a. Then, the packet and appropriate forwarding table information is stored in the local buffer memory 322a. The processor card 303 then accesses its routing table 328 to determine where to forward the received packet. Based on the determination, the router selects an appropriate line card 304b, stores the packet and forwarding information in the local buffer memory 322b of the appropriate line card, and forwards the packet out to the network.
FIG. 3D is a block diagram 360 illustrating an example embodiment of a router employing the switched backplane 302. The switched backplane 302 is coupled with the processor card 303 and the service card 342a or line cards 342b-h. The line cards 342a-b can either be a service card 342a or linecard 342b-h. The line card 342a-b includes a forwarding table and corresponding policies module 344a-b, and a MAC layer 326a-b. The search processor 202 is included in the line card 342a-b. The line card 342a receives a packet from a network through the MAC layer 346a at the forwarding table and policies module 344a. The search processor 202 processes the packet according to the forwarding table and policies module 344a according to the routing table 328 in the processor card 303 and forwards the packet to an appropriate line card 342b to be forwarded into the network.
The crossbar 412 is coupled with a first supercluster 410a and a second supercluster 410b. Within each supercluster 410a-b are a plurality of search blocks 412a-d. Each search block 412, or search cluster, is configured to receive a key from a received packet, determine and load a set of rules to process the key, and output results of the search executed using those rules. The crossbar 412 and the superclusters 410a-b are part of a lookup cluster complex (LCC) 414.
From the standpoint of the processor described herein, executing a lookup request begins with:
1) receiving the lookup request from a host processor. The lookup request includes a packet header and group identifier (GID).
4) Each TID also indexes an entry in a tree access table (TAT). Each TAT entry provides the starting address (e.g., a root node) in memory of a collection of rules (or pointers to rules) called a table or tree of rules. The terms table of rules, tree of rules, table, or tree are used interchangeably throughout the application. In all, the TID identifies the TAT, which identifies the collection or set of rules in which to look for one or more matching rules
The search processor provides a method to launch from 1 to 4 searches off of a single packet header. Each of these requests may search completely different and completely independent field sets within the headers. The searches are in every way independent searches with the caveat that they are related to the same packet header. The search fabric (LCC) treats them as completely different searches and has no knowledge (other than passing sub-key IDs in and out) of the initial request expansion
The key is parsed according to the instructions provided from the KFT (and indexed by the KFTIDX). The TWE 660 then uses the parsed key to walk a tree representing a set of rules that may match the parsed key. The tree walked by the TWE 660 includes nodes and leaves. The TWE 660 starts the walk at a root node of the tree. The location of the root node is provided from the TAT 665 (and indexed by the TID). The TWE 660 walks the tree until it reaches a leaf Each leaf in the tree represents a subset of the rules, called a bucket of rules (or simply bucket). When the TWE 660 reaches a leaf, it passes a corresponding bucket to the BWE 670 for processing.
Once a TWE's sub-tree walk has detected a leaf node, control for processing is transferred to the pool of bucket walk engines BWEs 670. BWEs 670 use the bucket info descriptor from the leaf node to fetch bucket entries. Bucket entries (BEs) are then processed by rule walk engines (RWEs) 680a-c. The RWEs 680a-c process the Bucket Entries (BEs), which contain pointers to rule chunks (RulChkPtr). The RWEs 680a-c fetch rule data and deliver to the pending pool of RMEs 680a-c. The RMEs 680a-c will use the fetched OCM Rule chunk data along with the corresponding rule format data (from the RFT 667), to process the chunk of rules specified by each bucket entry (BE). The RWEs 680a-c will aggregate partial RME match results for each rule chunk for all Bucket entries (BE) within the entire bucket. Once a match/nomatch result is acquired, the lookup response (LURSP) is driven back to the LRQ/LRD, which are driven back to the lookup front-end (LUF) via the STRSP bus.
At any time during a rule-matching operation, a BWE 670 may make a remote Bucket Entry (BE) request, or an RWE 680a-c may make a remote rule chunk request to another cluster via the remote output queue (ROQ). The OCM Bank Select (OBS) 695 arbiter is responsible for all accesses to the common OCM, which houses all rree/bucket and rule data structures. A remote cluster may access the OCM of another cluster by making a remote OCM request over the XBR 412, which is enqueued to the remote input queue (RIQ). The TWE pool, BWE pool, RIQ and HRF can all make requests into the common OCM, which has complex dynamic arbitration schemes to minimize overall OCM latency and to maximize OCM bandwidth (bank conflict avoidance) for optimal overall search performance.
FIG. 11 is a block diagram of an example LUF input processor (LIP) 424. The LIP 424 receives lookup requests (LUREQs) and host commands from the Interlaken or I2C interfaces 485a-d. The LIP 424 parses the requests and commands, and then schedules them to internal resources, such as the lookup clusters, double data rate (DDR) memory, BPP or global control status registers (CSRs) and tables.
The LIP 424 includes one or more distributors 460a-b that receive the aforementioned lookup requests and host commands from the Interlaken or I2C interfaces 485a-d. The distributors 460a-b may provide load-balancing between super clusters or within a super cluster. The distributors 460a-b then forward the lookup requests to schedulers 428a-b for output to the lookup clusters (e.g., the LCC 414 in FIG. 4B).
The distributors 460a-b and schedulers 428a-b may together provide for several functions, including load balancing, cluster assignment, key extraction, generation of key requests, splitting key requests into sub-tree requests, and scheduling output of key requests and sub-tree requests to lookup clusters. To facilitate those functions, and to control how searches are performed at an associated lookup cluster, the LIP 424 may employ a number of tables. A Group Definition/Description Table (GDT) 426 provides indexes to other tables. A Packet Header Table (PHT) 433a-b provides instructions on how to parse a packet. A Tree Location Table (TLT) 430a-b provides information about which clusters should do a search.
The TLT table 430a-b contains information about which m (of n) possible clusters can honor a particular tree ID (set of rules). If a Host Lookup Request is for that particular tree ID, then the LUF's least full cluster hardware logic selects the “least full” 1 (of m) clusters to service the Key Request. In this manner, the LUF load balances the Host Lookup requests equally amongst the possible clusters to provide minimum overall lookup latency, which will increase the overall lookup rate across the processor.
Each of the schedulers 428a-b processes each lookup request (LURED) to generate up to four key requests (KRQs) having keys. An example of this key extraction is described above with reference to FIG. 5, and is also described in further detail below with reference to FIG. 14. The KRQs (with keys) are scheduled and sent to the lookup cluster complex (LCC) for processing. In further embodiments, where a tree at one or more clusters is divided into a number of “sub-trees,” the key requests may be “split” into a number of “sub-tree requests,” each of which are associated with a particular sub-tree. The sub-trees, in turn, may be associated with different clusters within the LCC, or may be associated with a common cluster. In this manner, a subset of rules that are specified by a tree may be further narrowed to a smaller subset of rules specified by a sub-tree, thereby providing further refinement to a search.
Following key request generation, the schedulers 428a-b schedule the KRQs out of the LIP 424. The schedulers 428a-b include a payload header extractor (PHE) (described below with reference to FIG. 12) and a scheduler output manager (described below with reference to FIG. 15).
To support ordering of host lookup requests with respect to the host read/write requests used to incrementally update the rule table image, specialized HW mechanisms may be used at the scheduler 428a-b. Host R/W requests (exclude Host Lookups) include access to CSR, TABLE, OCM and DDR RCDS image data structures required during the Lookup/Key Request process.
2) LOCAL_RSP—When set, the search processor will ensure Host R/W requests are executed in bus order. In other words, a Host Write request (tree update) is forced to ‘complete’ or execute, before any subsequent Host Lookup Requests are issued. (Used where RAW conflict avoidance is required=Lookup Read after Write HW ordering must be maintained)
FIG. 12 is a block diagram of an example Payload Header Extractor (PHE) 470, which may be a component of the schedulers 428a-b of the LIP 424 described above with reference to FIG. 11. The PHE 470 includes one or more of the following blocks: New Queue(s) 472, Tree Location Table (TLT) 433, Payload Header Table (PHT) 430, TLT Table Manager 474, PHT Table Manager 476, New Queue Payload Manager 478, PHT Byte Swapper 480, bit packer 484, and Payload/Packet Header Extractor Finite State Machine (482), each of which is described below.
Each scheduler 428a-b has a new queue 472 (or “new work queue”) at the front end. If the size of these new queues is sufficiently large, then short term overloading of one scheduler will not cause head of line (HOL) blocking for the entire system, the scheduler backlog will be absorbed by the queue, allowing new work to flow to the other scheduler 428a-b.
The new queue 472 may be 16 locations deep for receiving packet headers. The packet headers are buffered in a 128 bits wide slice of this FIFO, and may limit the number of lookup packets that the queue will hold, as each header, regardless of size, will take up at least 1×128 bits of FIFO. The new queue 472 is loaded as packets flow into the device. The queue will contain lookup requests and IL Channel 0 DDR/OCM/Table requests from LUF Distributer 0 (LD0). The new queue 472 provides elasticity for the scheduler 428a-b because the bit packer 484 can generate between 1 and 4 KRQs for each lookup received. The Host read/write commands are placed unparsed in the new queue with format identical to that sent from the host.
The new queue may be divided into 3 sections (Payload, HID, and TID) such that the scheduler 428a-b can more efficiently manage the processing of each packet. LD0 may write all 3 sections simultaneously at Start of Packet (SOP). The HID and TID sections of the new queue 472 may have one entry per packet. The packet payload is stored in the payload section of the new queue 472 in 128-bit entries. Up to 5 entries in the FIFO may be required for a single packet. LD0 calculates parity across the entire New Queue and writes that value as a common entry (NQ_par) in all 3 section of the New Queue to assist the PHE in monitoring data alignment.
The PHE 470 may pull from each section of the new queue 472 independently. This allows the PHE 470 to pipeline and pre-process table data while simultaneously pulling multiple clocks of payload data. The NQ_par entries are compared across all 3 sections to monitor data alignment and an error indication in a status register is flagged if this check fails.
The Tree Location Table (TLT) 433 is used by the least full cluster generator (LFCG) of the scheduler 428a-b to determine which clusters can process a given job. The tree identifier (TID) is used as an index into the TLT 433. The TLT 433 may be host-loadable and may contain one or more of the following fields:
KFTIDX—Key format Index—Sent to Clusters as payload with a KEYREQ. The clusters use this to reference 1 (of 64) Key Formats which define how the clusters should extract up to 28 (max) DIMENSIONs within the KEYDATA for each KEY. Also used to index RFT (Rule Format Table). Sent with every KEYREQ command and is stored at each Cluster's KDT table (along with the KEYDATA).
TWCLMSK—TreeWalk Cluster Mask [1 per ST=subtree upto 8 (max)]: specifies which clusters (within the super-cluster) may accept TreeWalk Requests (TWReq). For LUF0, these relate to SC0, for LUF1, these relate to SC1. Used by HW to determine ‘least full cluster’ when scheduling a new TreeWalk request into the cluster complex. SW may have previously loaded Tree (N+L) image into specified clusters in the mask.
TWCLMSK_ALT—Alternate TreeWalk Cluster Mask [1 per ST=subtree upto 8 (max)]: Same as TWCLKSK above but specifies which clusters within the opposit super-cluster may accept TreeWalk Requests (TWReq). Valid in Single LUF mode only. For LUF0, these relate to SC1. For LUF1 these are not valid. USAGE IS AS FOLLOWS:
SINGLE LUF MODE (LUF0 Only): Each TWCL Mask={TWCLMSK_ALT, BWCLMSK}
BWCLMSK_ALT—Alternate BucketWalk Cluster Mask: Same as BWCLMSK above, but specifies which clusters in the which clusters within the opposit super-cluster will be responsible for BucketWalks. Valid in Single LUF mode only. For LUF0, these relate to SC1. For LUF1 these are not valid. USAGE IS AS FOLLOWS:
SINGLE LUF MODE (LUF0 Only): Full Bucket mask={BWCLMSK_ALT, BWCLMSK}
PHT Index for TID3=HID+3
Each line of the PHT 430 contains 9 dimensions that specify how to mask and multiplex the header data. Each of these dimensions specifies the following:
Destination Field Size (in bits)
For each KRQ retrieved or generated, a 2 bit SXID is generated. LRT and LRT INFO entries are reserved for each Key by pulling a KID from the free pools. The KIDs need to be pulled in advance and cached. If the system runs out of KIDs, the scheduler HOL blocks until KIDs become available through search completion.
The KRQ, along with the corresponding TLT 433 data, is sent to the scheduler output manager (FIG. 15). The KRQ data may be transmitted in 128-bit increments. The TLT 433 data may be sent in a single transmission with the KRQ start of packet (SOP).
No Swap—do nothing
FIG. 14 is a packet diagram showing the PHE 470 operating in normal key expansion mode. In this example embodiment, the PHE 470 extracts and processes header data to convert LUREQs and read/write requests into key requests (KRQs) in a LUF procedure referred to as key expansion or packet header extraction. There are two modes of key expansion for LUREQs: normal key expansion mode (when GID>0, which uses the Bit Packer block), and one-to-one Mode (when GID=0).
In normal key expansion mode, each LUREQ can spawn up to 4 Key Requests (KRQs), as described above with reference to FIG. 5. The programmable tables stored in the Packet Header Table (PHT) may be used to parse the LUREQs into the Key Requests. As shown in FIG. 5, a LUREQ may include the following fields:
Lookup Data—(Up to 512 bits)—Keys are formed from this data
Using the PHT 430 (FIG. 12), up to 4 Keys (KRQs) are generated from each LUREQ. Generated Keys (KRQs) are then passed to the PHE FSM 482 (FIG. 12), which sends them as KRQs to the scheduler output manager (FIG. 15) in 128-bit increments.
FIG. 15 is a block diagram of an example scheduler output manager 480, which may be a component of the scheduler 428a-b of the LIP 424. The scheduler output manager may operate as the “back-end” of the scheduler 428a-b. The scheduler output manager includes one or more of the following blocks: least full cluster generator (LFCG) 492, retry queue 493, output source selector 494, and scheduler output manager Finite State Machine (FSM) 495, each of which are described below.
Directs scheduled KRQs out one or more of 6 possible KRQ busses.
The scheduler output manager 490 selects one KRQ at a time from 3 possible sources, the PHE, LD1, and Retry Queue. The scheduler output manager 490 schedules each KRQ to be sent out one or more of the 6 possible KRQ busses (SC0, SC1, BPP0, BPP1, MWQ (DDR), Global CSR/Tables). Alternatively, the scheduler output manager 490 can move LUREQ KRQs from the PHE to the Retry Queue or recirculate KRQs from the front of the Retry Queue to the back of the queue. The scheduler output manager 490 makes those decisions based on the KRQ CMD, noting credits available from each KRQ destination and running the Least Full Cluster Generator (LFCG) for LUREQ KRQs.
LFTWCLMKS
When a scheduling attempt for a single Key fails, the request is moved to the retry queue 493 to avoid head of line (HOL) blocking HOL blocking will happen when the clusters that match the TWCLMSK are too busy to accept the job.
The retry queue 493 entries may be of the same format as the interface from the PHE 470 (FIG. 12). This includes both the fully formed KRQ (in 128 bit increments of data) plus the entire TLT data for that Key. It may require up to 3 FIFO entries (3 clocks) to store the entire KRQ data. The scheduler 428a-b (FIG. 11) outputs IDLE to the KRQ busses while the scheduler 428a-b moves the data from the PHE 470 to the retry queue 493.
Further, a programmable RETRY_HIGH_WATERMARK determines the maximum fill level for the retry queue before the retry queue is drained. The minimum setting for RETRY_HIGH_WATERMARK is 0x3. A setting of “N” means that the Retry Queue will be drained when N+1 KRQ Beats are written into it. If the RETRY_HIGH_WATERMARK is set larger than the size of the RETRY QUEUE, then the retry queue 493 will be drained if it reaches the maximum fill level of the memory.
Once the retry queue 493 is selected for draining, the new queue data from the PHE 470 will not be selected again until the retry queue is empty (i.e., drained). This prevents a lockout condition. During the draining of the retry queue 493, any KRQ that cannot be scheduled due to lack of success from the LFCG 492 are recirculated to the back of the retry queue 493. The scheduler 428a-b will output IDLE (up to 3 clock cycles) while the KRQ is recirculated to the back the queue and new data is advanced to the front of the retry queue.
LCC Table RD/WRT
The scheduler output source selector 494 provides for selection among the connect outputs for transfer of the output of the SOM FSM 495. The Schedule Output Manager 490 controls the selector 494 to select the source of the next KRQ to be sent from the scheduler (SCH) 428a-b based on the following states:
Recirculate RetryQ (SCH recirculates data on the retry queue and outputs idle on the next clock
FIG. 17 is a block diagram of an example LUF output processor (LOP) 446, which is a component of lookup front end (LUF) 408 as described above with reference to FIG. 4B. The LOP 446 receives responses from internal chip resources (e.g., lookup clusters 413a-d, FIG. 4A) that are initiated by the LIP (e.g., LIP 424, FIG. 11). These responses are processed and transmitted back to the host processor over Interlaken or I2C modules. Responses may include host read or write responses from resources, such as DDR, Clusters, BPP or global tables, and CSRs. Responses may also include lookup responses that are evaluated by the LOP for best match before transmission back to the host processor.
The LOP 446 includes a response-processing front end block (LOP_FE) 750a-b, a response-processing backend block (LOP_BE) 760, and output processing block (LOP_OP) 770.
Further, The LOP 446 maintains two tables that are initialized by the LIP 424 (FIG. 11) and lookup clusters. The tables hold the context for searches in progress, and include the lookup response table (LRT) 765a-b, which tracks searches currently being performed by the clusters; and the transmit Buffer (TXBUFF) 775, which buffers results of searches that the clusters have completed. As described below, the results are optionally stored and returned in order of request or coalesced.
In a general operation, the LOP_FE 750a-b receives work from either the LUE clusters or Bucket Packet Processors (BPP). As responses are received, they are located in the LRT 765a-b, and optionally coalesced with other keys from the same packet, an operation described in detail below. A single LOP_FE 750a may be configured to interface with a single corresponding super cluster (e.g., super cluster 410a in FIG. 4A), may interface with multiple super clusters, or may share a common super cluster with another LOP_FE 750b.
The LOP_BE 760 interfaces with the LUF_FE 750a-b. The LOP_BE 760 may provide for buffering and reordering responses. The buffering and reordering of responses is done to preserve lookup order and for grouping responses into coalescing groups. The LOP_BE 760 collects responses and places them into the TXBUFF 775 slots that were reserved by the LIP 424 (FIG. 11) prior to initiating a search. When responses are ready for transmit, the LOP_BE 760 places indexes of TXBUFF 775 into a TX_LIST register for the output processing block LOP_OP 770.
Lookup responses are tracked and processed by a coordinated operation of the LIP 424 and LOP 446. The tracking of responses is begun, as described above, by the LIP 424 distributer (e.g., 460a-b, FIG. 11) when the LIP distributer initializes fields in the TXBUFF. The operation is continued by the LIP 424 schedulers (e.g., 428a-b, FIG. 11) when the LIP schedulers initialize the LRT and LRT_INFO tables. The LOP_FE 765a-b uses this information to process the responses to determine the best response of all tree walks for a given KEY/SXID. Control then passes to the LOP_BE 760 to process the now finished KEY/SXID. Based on the coalesce bit of the LRT 765a, the LOP_BE 760 will either coalesce all the SXIDs for a given XID into a single response or send a response to the host as soon as available. Based on the range of TXID, the LOP_BE 760 will either reorder this response or return the response in the order that the associated request was received.
FIG. 18 is a block diagram of an example LUF Response Processing Front End (LOP_FE) 750. The LOP_FE 750 includes, among other components, a LUF Rule Calculator (LRC) 752a-c, LUF Rule Calculator Preprocessor (LRCP) 753, and LUF Response FIFO (LRF) 754, which are described in greater detail below.
KID—Key ID
The LUF Rule Calculator (LRC) 752a-c receives sub-tree responses (STRSPs) from the clusters via the STRSP bus 756. One of the LRCs (e.g., 752c) may receive responses exclusively from the BPPs.
For each STMIN response returned, the LRC 752a-c does the following:
Each of the LRCs 752a-c may receive responses for the same KID on the same clock. This result would be a problem if each LRC 752a-c attempted to update the same HPMRULE and TWRSPCNT on the same clock. To avoid this, the preprocessing block 753 combines the STRSP responses for any matching keys into a single response by retaining the minimum and discarding the others. The “winning” response continues to the LRC 752a-c, while the others are eliminated. A LRC_TWRSPCNT_DEC[1:0] signal is generated and passed to LRC0, causing TWRSPCNT to be decremented by the number of responses returned, rather than just by one as in a typical case. Any responses for KIDs that do not match may be passed through unmodified with a LRC_TWRSPCNT_DEC==1.
Host read/writes responses for OCMEM and Super Cluster and BPP tables also flow to the LRCP 753 over their respective clusters and BPP response busses 756. Such responses are redirected to the LUF output processing block (LOP_OP 770, FIG. 20) to be buffered for transmit. They may not flow to the LRC 752a-c.
The 64-entry LUF RESPONSE_FIFO (LRF) 754 holds KIDs for Keys/SXIDs that have received all the responses for that key, meaning that STRSP (sub-tree response) has been determined. In this manner, when a key request was split into multiple sub-tree request by the LIP 424 (described above with reference to FIG. 11), the corresponding results are merged back into a single response at the LRF 754. The LOP_OP 770 (FIGS. 17, 20) reads the LRF 754 to determine the entries that are ready to transfer from the LRT 765a-b to the TXBUFF 775.
The LRF 754 may be fed by busses associated with the output of the LRC 752a-c and the BPP buses. In an example embodiment, up to 3 KIDs may be written to the LRF (FIFO) during each clock cycle each clock. One entry is read from the LRF each clock. In general, reads may occur more quickly than writes, as multiple STRSPs are required for a single KID write.
In-order responses (polling mode): A pointer tracks the TXBUFF entry corresponding to the oldest request (determined by walking TXIDs in a circular fashion within that order group range) in the LRT. When the final STRSP for that XID is received, all SXID's are enqueued for transmission to the host, and removed from the LRT. The pointer is then incremented to point to the next oldest TXID. This causes HOL blocking until the next in order response returns.
In all cases of ordering and coalescing, when an entry is read off the Response FIFO 754 by FIFO read block 767, the LOP 760 does the following:
DONE_CNT—how many SXIDs left to coalesce
The LOP does the following additional actions listed in Table 1.
Order LOP Action based on reading Response FIFO,
Mode Coalesce then LRT and LRT_INFO
OOO No If LRT[SXID] == SXIDO or SXID1,
Set SXID_INFO of TXLIST to indicate which
SXID. (Set to value of LRT[SXID]).
VALID_ODD set FREE_TXID
Place TXID_FIRST and TXID_LAST on
DONE_CNT = DONE_CNT-1
Order Case(LRT[SXID_NUM]) // How many SXIDs are
The in-order machine 768a-b provides for reordering responses so they are returned in order of requests, rather than in order of finishing processing. The in-order machine 768a-b will park at the first non-valid TXBUFF location within a region, which is defined by IN_ORDER_MIN_N to IN_ORDER_MAX_CSR values. When the LOP_FE sets the valid flags for that location, indicating that all necessary information has been moved from LRT 765 to TXBUFF 775, the in-order machine 768a-b will process this line of TXBUFF 775 and then increment to the next location in TXBUFF 775, waiting to repeat the process. Since TXBUFF 775 entries are assigned to incoming packets in increasing sequential order as they arrive, the in-order machine 768a-b will pull the entries off the list in order, regardless of the sequence that the arrive in the TXBUFF 775. When the in-order machine 768a-b determine it has a handle to all the TXIDs required for a single coalesced packet, it writes these TXIDs to the TXLIST 769.
The in-order machine 768a-b may put up to two TXBUFF lines at a time in the TXLIST 769. The downstream output processor may read these lines off the FIFO back-to-back. For this mode, if 3 or 4 keys, the machine 768a-b must store TXID_FIRST in TXID_FIRST_REGISTER, and write TXID_FIRST and TXID_LAST onto the TXLIST 769 in a single cycle. Like the out-of-order machine, it keeps a SXID_COUNTER to track which SXID we are working on. The in-order machine 768a-b actions are detailed in Table 2.
Order Need Valid Valid
Mode Coalesce Both Even Odd LOP In Order Machine Action
Order We know this because it must be
SXID0 of a 1 key packet,
or SXID3 of
a 3 key packet.
If SXID_COUNTER indicates
one or 2 keys:
In 1 1 1 1 If LAST==0
Order Advance TXID
The TXLIST 769 is a FIFO of TXIDs. The TXLIST 769 is written by the LOP, and is used by the TX Queue DMA engine (described below with reference to FIG. 20) to determine which TXBUFFs to transfer to the Interlaken SHIM for transmission back to the host. For in-order processing, the order of TXIDs on the list generally determines the order of transmission to the host.
The TXLIST 769 is read by the DMA engine (FIG. 20) one entry at a time. The order that TXIDs are placed on this list may generally determine the order of transmission. In an example embodiment, the TXLIST 769 includes the following information, which can be stored as one or more bits in corresponding entries:
C—Coalesce.
FIG. 20 is a block diagram of an example LOP Output Processor (LOP_OP) 770 in an example embodiment. The TXQ DMA engine 772 pulls TXIDs from the TX_LIST FIFO. The corresponding locations in the TXBUFF 775 are then read and formed into response packets before being placed in the TX FIFO 778 for transmission over Interlaken.
SXID3—use only TXID_LAST to index TXBUFF, DATA_ODD field is valid
The LRT 765 and LRT_INFO 766 tables are initialized by the scheduler 428a-b of the LIP 424 (FIG. 11) as lookup requests are sent to the clusters. The LRT 765 and LRT_INFO 766 tables are used by the LUF response processor LRC 752a-c to determine the minimum highest-priority rule (HPRULE) for each key, and to determine that all responses for that key have been returned. Each LRT 765 entry corresponds to a single key search (single SXID) that is in progress. The LRT 765 is indexed/referenced by a KID, which in turn is distributed from a KID free pool (described below). After scheduling, fields in the LRT 765 are updated by the LUF output processor front end (LOP_FE) 765a-b.
Valid=3′b1xx—RSP0 bank is valid
Valid=3′bx1x—RSP1 bank is valid
Valid=3′bxx1=BPP bank is valid
Response data fields—implemented by array of flops, or 3 banks of dual ports managed with valid
The TXBUFF 775 table is initialized by a LIP distributer 460a-b (FIG. 11) as requests arrive from the host. The TXBUFF 775 table is used by the LOP output processor (LOP_OP) 770 (FIG. 20) to optionally reorder responses so that the responses are sent back to the host in the same order that the requests were received. The TXBUFF 775 table also provides buffering for times when the rate that lookup responses are returned by the clusters exceeds the rate that the host interface can drain them. The TXBUFF 775 table is indexed/referenced by a TXID, which is distributed from a TXID free pool (described later in greater detail).
The TXID free pool distributes TXIDs to the scheduler 428a-b (FIG. 11). Each TXID represents one line in the TXBUFF 775 array. The TXID free pool is built from a memory-less FIFO, and may be initialized to full. The TXID free pool may be employed for in-order operation, wherein entries are distributed in increasing order and returned in the same order. Therefore, when an increasing TXID is used to index the TXBUFF 775, the entries will be pulled in order.
<- Previous Patent (Method and apparatus...) | Next Patent (Processing requests) ->