US 6,308,220 B1Granted

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

AssigneeNeoMagic Corp.

InventorHarish N. Mathur

Life of this patent

Estimating the term…

Loading patent…

Abstract

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.

Claims20

Dependent claims

A parallel-search integrated circuit comprising:

a free-running sequencer for repeatedly outputting a sequence of addresses in a loop;
a table for storing a plurality of entries, the table outputting an entry in response to an address from the free-running sequencer;
a plurality of search engines, each search engine receiving the entry from the table, the plurality of search engines including:
a first search engine for comparing at least a portion of the entry to a first input and generating a first match signal when the first input matches the at least a portion of the entry;
a second search engine for comparing the at least a portion of the entry to a second input and generating a second match signal when the second input matches the at least a portion of the entry;
a third search engine for comparing the at least a portion of the entry to a third input and generating a third match signal when the third input matches the at least a portion of the entry;
wherein the free-running sequencer repeats the sequence of addresses once all entries have been read from the table;
wherein the first search engine begins a search once the first input is received, the first search engine beginning the search at any address in the sequence of addresses and continuing until all entries have been compared by the first search engine or until the first match signal is generated;
wherein the second search engine begins a search once the second input is received, the second search engine beginning the search at any address in the sequence of addresses and continuing until all entries have been compared by the second search engine or until the second match signal is generated;
wherein the third search engine begins a search once the third input is received, the third search engine beginning the search at any address in the sequence of addresses and continuing until all entries have been compared by the third search engine or until the third match signal is generated;
and
wherein the first, second, and third search engines perform overlapping searches that begin and end at different times and at different addresses in the sequence,
whereby parallel searches are performed.

10 more elements

A switch-based network router comprising:

a network switch, having a plurality of input ports for receiving network packets from different network nodes, for making temporary connections to output ports coupled to other network nodes;
the network switch making a first temporary connection in response to a first port identifier that identifies one of the output ports to connect to a first input port receiving a first packet;
the network switch making a second temporary connection in response to a second port identifier that identifies one of the output ports to connect to a second input port receiving a second packet;
a parallel search chip, coupled to the network switch, for receiving a first destination address from the first packet, the parallel search chip outputting the first port identifier to the network switch, the first port identifier being read from a first matching entry having an address field that matches the first destination address;
the parallel search chip also for receiving a second destination address from the second packet, for outputting the second port identifier to the network switch, the second port identifier being read from a second matching entry having an address field that matches the second destination address;
the parallel search chip further comprising:
sequencer means for generating addresses of entries, the addresses being in a fixed sequence that repeats once all entries are addressed;
routing table means, coupled to the sequencer means, for storing a plurality of entries, each entry containing a network address and a port identifier of an output port of the network switch that is connected to a network node that receives packets for that network address;
internal bus means, receiving an entry from the routing table means selected by the address from the sequencer means, for transferring the entry;
first search means, coupled to receive the entry from the internal bus means, for comparing the network address from the entry to the first destination address, and for outputting the port identifier from the entry as the first port identifier when a match occurs;
second search means, coupled to receive the entry from the internal bus means, for comparing the network address from the entry to the second destination address, and for outputting the port identifier from the entry as the second port identifier when a match occurs;
wherein the first and second search means receive a same entry from the routing table means but begin and end searches at different times,
whereby parallel searches are performed using same entries read from the routing table means.

10 more elements

A parallel-search method for searching a network table, comprising:

generating a continuous-loop sequence of addresses;
reading a current entry from a routing table using an address in the sequence of addresses;
receiving a first packet at a first input port from a first network node;
parsing the first packet to extract a first destination address for the first packet;
in a first search engine, comparing the first destination address to a current network address in the current entry;
reading other entries from the routing table as the current entry and comparing in the first search engine to the first destination address when no match has yet been found;
outputting a first port identifier when the first search engine detects a match between the first destination address and the current network address;
receiving a second packet at a second input port from a second network node at a different time than the first packet is received;
parsing the second packet to extract a second destination address for the second packet;
in a second search engine, comparing the second destination address to a current network address in the current entry at the same time that the first search engine is comparing the first destination address to the current network address;
the second search engine comparing to the second destination address the other entries from the routing table as the current entry when no match has yet been found;
outputting a second port identifier when the second search engine detects a match between the second destination address and the current network address;
receiving a third packet at a third input port from a third network node;
parsing the third packet to extract a third destination address for the third packet;
in a third search engine, comparing the third destination address to a current network address in the current entry at the same time that the first search engine is comparing the first destination address to the current network address;
the third search engine comparing to the third destination address the other entries from the routing table as the current entry when no match has yet been found;
and
outputting a third port identifier when the third search engine detects a match between the third destination address and the current network address;
whereby a same sequence of entries are read from the routing table and compared by different search engines that begin and end searches at different times.

16 more elements

Dependencies are inferred from the claim text.