Network switching device with pipelined search engines

• US 20030058864A1
• Filed: 11/12/2002
• Published: 03/27/2003
• Est. Priority Date: 01/23/1998
• Status: Active Grant

• Current Assignee: Bernard N. Daines, Greg W. Davis, James E. Cathey, Timothy Scott Michels
• Original Assignee: Bernard N. Daines, Greg W. Davis, James E. Cathey, Timothy Scott Michels
• Inventors: Daines, Bernard N., Cathey, James E., Davis, Greg W., Michels, Timothy Scott
• Granted Patent: US 7,023,807 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 2012/5685 Addressing issues
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/309 Header conversion, routing tables or routing tags

Abstract

A switching device for forwarding network traffic to a desired destination on a network, such as a telephone or computer network. The switching device includes multiple ports and uses a lookup table to determine which port to forward network traffic over. The lookup table includes network addresses that are maintained in ascending or descending order. The switching device includes multiple binary search engines coupled in series including one or more precursor binary search engines and a final stage binary search engine. Together, the binary search engines perform an N iteration binary search. Additionally, a single search engine can perform multiple concurrent searches so that source and destination addresses can be obtained simultaneously and without wasted memory cycles.

Claims

1. 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.

2. The network switching device of claim 2, wherein the first memory includes a portion of a lookup table needed for performing the first search.

3. The network switching device of claim 2, wherein the second memory includes a portion of a lookup table needed for performing the second search.

4. The network switching device of claim 2, wherein the second memory includes all entries of a lookup table.

5. 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 the retrieved forwarding information.

6. The method of claim 5, wherein the first memory includes a portion of a lookup table needed for performing the first search.

7. The method of claim 5, wherein the second memory includes a portion of a lookup table needed for performing the second search.

8. The method of claim 7, wherein the second memory includes all entries of a lookup table.

9. A network switching device comprising:

a first search engine;

a second search engine coupled to the first search engine in series;

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.

10. The network switching device of claim 9, wherein the first memory includes a portion of a lookup table needed for performing the first search.

11. The network switching device of claim 9, wherein the second memory includes a portion of a lookup table needed for performing the second search.

12. The network switching device of claim 9, wherein the second memory includes all entries of a lookup table.

13. 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 coupled to the first search engine in series;

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 the retrieved forwarding information.

14. The method of claim 13, wherein the first memory includes a portion of a lookup table needed for performing the first search.

15. The method of claim 13, wherein the second memory includes a portion of a lookup table needed for performing the second search.

16. The method of claim 15, wherein the second memory includes all entries of a lookup table.