Neomagic Corporation

Netlogic Microsystems, Inc

Harish Narian Mathur

Sanjay Sreenath

David Way Ng

A method of controlling a content addressable memory (CAM) device. A data structure is generated that specifies (i) a prioritized set of rules and (ii) storage locations within the CAM device for one or more match clauses of each of the rules. A new rule having a specified priority is recorded in the data structure. Candidate storage locations within the CAM device are identified within the CAM device for the match clauses of each of the rules having a lower priority than the new rule. The candidate storage locations are compared with the storage locations specified by the data structure. Each match clause for which the candidate storage location does not match the specified storage location is stored in the CAM device.

Table management within a policy-based routing system

A store-and-forward network switch uses an embedded dynamic-random-access memory (DRAM) packet memory. An input port controller receiving a packet writes the packet to the embedded packet memory. The input port controller then sends a message to the output port over an internal token bus. The message includes the row address in the embedded packet memory where the packet was written and its length. The output port reads the message and reads the packet from the embedded memory at the row address before transmitting the packet to external media. Packets are stored at row boundaries so that DRAM page-mode cycles predominate. Only one packet is written to each DRAM row or page. Thus the column address is not sent between ports with the message sent over the token bus. A routing table can also be included in the embedded DRAM.

Store-and-forward network switch using an embedded DRAM

A search engine for a network switch reads a routing table for an entry with a matching MAC or IP address. The routing table is contained in an embedded DRAM. The search engine and the embedded-DRAM routing table are integrated together on the same integrated circuit chip, allowing a very wide data path between the search engine and the routing table. A free-running sequencer outputs addresses to the routing table so that each entry is read in a continuous-loop sequence. The same entry is sent to comparators for all active searches. Destination addresses for different input ports are compared to the entry read from the table. A match ends the search for a port while searches for other ports continue. Since ports can begin and end searches at any point in the continuous-loop sequence, a same low latency is provided for all input ports, even when other searches are in progress. The wide data path from the embedded-DRAM allows several entries to be read and compared for each cycle and for each port. Thus multiple entries are compared in parallel for each port, and ports are searched in parallel.

Circulating parallel-search engine with random inputs for network routing table stored in a wide embedded DRAM

Low-latency arbitration is provided for a super-priority communications device such as modems and ISDN/DSL routers, LAN switches and routers. Phantom arbitration slots are inserted between each pair of permanent slots. When a request from the super-priority agent is received, the next phantom slot is used to service the request. The initial latency is just one slot period rather than the whole arbitration loop. Other phantom slots are skipped until the same phantom slot is again activated at the same point in the arbitration loop during subsequent rounds of arbitration. Thus only the initial latency is reduced; subsequent requests from the super-priority agent are handled just once for each arbitration cycle. The low initial latency allows the communications device to quickly respond to an incoming call. Other real-time agents are assigned a fixed slot in a round-robin arbitration. The last arbitration slot is used by all non-real-time agents. The last time slot uses a priority arbiter to grant access in a priority order to the non-real-time agents. A timer is used to limit the time that the last arbitration slot services non-real-time agents. The next arbitration loop then begins with the first real-time agent or a phantom slot. The amount of access time given the non-real-time agents is maximized while the real-time agents are ensured access within the maximum loop period.

Growing community of inventors

San Jose, CA, United States of America

Harish Narian Mathur