Network switching device with concurrent key lookups

• US 6,453,358 B1
• Filed: 09/06/2000
• Issued: 09/17/2002
• Est. Priority Date: 01/23/1998
• Status: Expired due to Fees

• Current Assignee: Alcatel Internetworking Incorporated (Nokia Corporation)
• Original Assignee: Alcatel Internetworking Incorporated (Nokia Corporation)
• Inventors: Cathey, James E., Davis, Greg W., Michels, Timothy Scott, Daines, Bernard N.
• Primary Examiner(s): VU, VIET DUY
• Application Number:
  US09/776,940
• Time in Patent Office: 741 Days
• Field of Search: 709/230, 709/238, 709/242, 709/245, 709/249, 709/250, 370/389, 370/392, 711/149, 711/150, 711/157, 711/168, 711/169, 712/300
• US Class Current: 709/238
• 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/309 Header conversion, routing tables or routing tags
• CPC Class Codes: Y10S 707/99936 Pattern matching access

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 first memory coupled to the first search engine;

a second search engine;

a second memory coupled to the second search engine characterized in that the first search engine performs a search of the first memory for a first key concurrently with a search of a second key and passes results of the search for the first and second keys to the second search engine for concurrently searching the second memory for the first and second keys.

2. The network switching device of claim 1, wherein the first key is a source address and the second key is a destination address.

3. The network switching device of claim 1, wherein each search engine accesses its respective memory during successive clock cycles and alternates between accessing the memory for search of the first key and search of the second key.

4. The network switching device of claim 1, wherein each search engine performs iterations of searches of the first and second keys in three clock cycles, wherein during at least one of the three clock cycles an iteration of the search for the first key is completing while an iteration of the search for the second key is beginning such that there is an overlapping between execution of the iterations of the searches of the first and second keys.

5. The network switching device of claim 1, wherein the first and second search engines together perform a search of N iterations, and wherein the first search engine performs a first portion of the N iterations and the second search engine performs second portion of the N iterations.

6. The network switching device of claim 5, wherein the first memory only includes a first portion of a lookup table necessary to perform the first portion of the N iterations and the second memory only includes a second portion of the lookup table necessary to perform the second portion of the N iterations.

7. The network switching device of claim 1, wherein the first and second search engines are binary search engines.

14. The network switching device of claim 1, wherein the first and second search engines are binary search engines.

8. In a network switching device, a method for searching a lookup table comprising the steps of:

receiving a data packet including a first key and a second key;

extracting the first and second keys from the data packet;

performing by a first search engine a search of a first memory for the first key;

performing by the first search engine a search of the first memory for the second key concurrently with the search for the first key; and

passing results of the search for the first and second keys to a second search engine coupled to the first search engine for concurrently searching the second memory for the first and second keys.

9. The method of claim 8, wherein the first key is a source address and the second key is a destination address.

10. The method of claim 8, wherein each search engine accesses its respective memory during successive clock cycles and alternates between accessing the memory for search of the first key and search of the second key.

11. The method of claim 8, wherein each search engine performs iterations of searches of the first and second keys in three clock cycles, wherein during at least one of the three clock cycles an iteration of the search for the first key is completing while an iteration of the search for the second key is beginning such that there is an overlapping between execution of the iterations of the searches of the first and second keys.

12. The method of claim 8, wherein the first and second search engines together perform a search of N iterations, and wherein the first search engine performs a first portion of the N iterations and the second search engine performs a second portion of the N iterations.

13. The method of claim 12, wherein the first memory only includes a first portion of a lookup table necessary to perform the first portion of the N iterations and the second memory only includes a second portion of the lookup table necessary to perform the second portion of the N iterations.