Network switching device with pipelined search engines

A network forwarding device for searching a lookup table, comprising:

• a first stage search engine;
• a second stage search engine coupled in series to the first stage search engine;
• a first memory coupled to the first stage search engine;
• a second memory coupled to the second stage search engine;
• a first database stored in the first memory, the first database including only entries selected from the lookup table needed to perform a portion of the iterations of an N iteration binary search;
• a second database stored in the second memory, the second database including either the entire database or only entries selected from the lookup table needed to perform additional iterations of a binary search.

A network forwarding device having multiple ports coupled to network segments, comprising:

• a media interface for receiving a network frame including a destination address;
• a final stage binary search engine;
• a final stage memory coupled to the final stage binary search engine for storing a lookup table of network addresses and port numbers associated with the network addresses;
• at least one precursor binary search engine coupled in series with the final stage binary search engine, and with one precursor binary search engine coupled to the media interface for receiving the network frame;
• at least one precursor memory coupled to one of the precursor binary search engines and having stored therein nodes for a binary search copied from the lookup table, wherein the nodes are stored in sorted order;
• a switch fabric for communicating with other ports in the network forwarding device;
• and
• a switch fabric control coupled to the final stage binary search engine that receives search results from the final stage binary search engine and that controls the switch fabric control so that the network frame is routed to the appropriate port within the network forwarding device.

A method forwarding a network frame in a network forwarding device, the method comprising the steps of:

• providing at least two search engines coupled in series;
• storing a lookup table of keys and storing forwarding information associated with the keys;
• receiving a network frame;
• obtaining a search key associated with the network frame;
• searching the lookup table for a key that matches the search key, the searching step including performing an N iteration binary search with the search engines performing different iterations of the binary search;
• obtaining forwarding information associated with the key found in the lookup table;
• and
• forwarding the network frame based on the obtained forwarding information.

A network switching device comprising:

• a first search engine;
• a second search engine coupled to the first search engine;
• a first memory coupled to the first search engine;
• and
• a second memory coupled to the second search engine, characterized in that the first search engine receives a search key and performs a first search of the first memory for the search key, the first search engine passing results of the first search to the second search engine, the second search engine performing a second search of the second memory for the search key and appending results of the second search to the results of the first search, further characterized in that the first and second search engines together performs a search of N iterations, the first search engine performing a first portion of the N iterations in the first search and the second search engine performing a second portion of the N iterations in the second search.

In a network switching device, a method for forwarding a discrete information unit comprising:

• generating a search key associated with the information unit;
• searching a first memory for the search key using a first search engine and rendering a first search result;
• passing the first search result to a second search engine;
• searching a second memory for the search key using the second search engine and rendering a second search result;
• appending the second search result to the first search result;
• retrieving forwarding information based on the appended search result;
• and
• forwarding the information unit or not based on a the retrieved forwarding information;
• wherein, the first and second search engines together perform a search of N iterations, the first search engine performing a first portion of the N iterations in the first search and the second search engine performing a second portion of the N iterations in the second search.