US6161144A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Network switching device with concurrent key lookups
Assignee: Nokia of America Corp
•
Filing: 1998-10-05
•
Granted: 2000-12-12
•
Expires: 2018-10-05
Abstract
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.
Inventors
- 👤 Timothy Scott Michels
- 👤 James E. Cathey
- 👤 Greg W. Davis
- 👤 Bernard N. Daines
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 20:37
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/30; H04L49/3081; H04L49/309; H04L12/00; H04L12/54; H04L12/56; H04L45/00; H04L45/74; H04L45/745; H04L45/74591; H04L12/5601; H04L2012/5685; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
112 words
A network forwarding device, comprising N search engines connected in series, where N is an integer greater than one, each search engine including a memory having one or more addresses of database entries stored therein, each search engine configured to perform first and second independent searches concurrently on the database by accessing its respective memory during successive clock cycles and alternating between accessing memory for an iteration of the first search and an iteration of the second search, each of the first (N-1) search engines further configured to pass results of its iteration of the first and second searches to a next search engine in the series for a next search iteration.
Claim 2
Dependent Claim
112 words
A network forwarding device, comprising N search engines connected in series, where N is an integer greater than one, each search engine including a memory having one or more addresses of database entries stored therein, each search engine configured to perform first and second independent searches concurrently on the database by accessing its respective memory during successive clock cycles and alternating between accessing memory for an iteration of the first search and an iteration of the second search, each of the first (N-1) search engines further configured to pass results of its iteration of the first and second searches to a next search engine in the series for a next search iteration.
Claim 3
Dependent Claim
73 words
The network forwarding device of claim 1 wherein the memory includes a memory address input and further including first and second address registers having outputs coupled to the memory address input and a clock for switching the memory address input so that on successive clock cycles the memory address input switches between address data on the output of the first address register and address data on the output of the second address register.
Claim 4
Dependent Claim
43 words
The network forwarding device of claim 1 wherein the search engine further includes two address registers, one for storing an address for accessing the memory for the first search and another for storing an address for accessing the memory for the second search.
Claim 5
Dependent Claim
66 words
The network forwarding device of claim 1 wherein the search engine further includes first and second address registers and first and second comparators, the first and second address registers for storing addresses for accessing memory for the first and second searches, respectively, and the first and second comparators for comparing the results from the memory accesses to search keys relating to the first and second searches.
Claim 6
Dependent Claim
54 words
The network forwarding device of claim 1 further including first and second address registers for accessing memory for the first and second searches, respectively, and a multiplexer coupled between the first and second address registers and the memory for switching a memory input between the first and second address registers on successive clock cycles.
Claim 7
Dependent Claim
70 words
The network forwarding device of claim 1 further including first and second search keys and first and second comparators with the first search key coupled to the first comparator and the second search key coupled to the second comparator, the first and second comparators for reading output data from the memory during successive clock cycles and comparing the output data from the memory to the first and second search keys.
Claim 8
Dependent Claim
47 words
The network forwarding device of claim 1 further including first and second address registers for accessing memory on successive clock cycles and search termination logic coupled to the first and second address registers for determining if the searches are complete and for outputting results of the searches.
Claim 9
Dependent Claim
177 words
A network forwarding device, comprising: N search engines connected in series, where N is an integer greater than one, each search engine including: a memory having an address input and a data output; a first comparator having an input coupled to a first search key; a second comparator having an input coupled to a second search key; a first address register coupled to the first comparator for storing an address relating to a first search and coupled to the address input of the memory; a second address register coupled to the second comparator for storing an address relating to a second search and coupled to the address input of the memory; and a clock signal for switching the address input of memory on successive clock cycles between addresses from the first and second address registers so that the first and second searches are performed concurrently; wherein, each of the first (N-1) search engines is configured to pass results of its first and second searches to a next search engine in that series for a next search iteration.
Claim 10
Dependent Claim
177 words
A network forwarding device, comprising: N search engines connected in series, where N is an integer greater than one, each search engine including: a memory having an address input and a data output; a first comparator having an input coupled to a first search key; a second comparator having an input coupled to a second search key; a first address register coupled to the first comparator for storing an address relating to a first search and coupled to the address input of the memory; a second address register coupled to the second comparator for storing an address relating to a second search and coupled to the address input of the memory; and a clock signal for switching the address input of memory on successive clock cycles between addresses from the first and second address registers so that the first and second searches are performed concurrently; wherein, each of the first (N-1) search engines is configured to pass results of its first and second searches to a next search engine in that series for a next search iteration.
Claim 11
Dependent Claim
41 words
The network forwarding device of claim 8 having a multiplexer coupled between the address registers and the memory and coupled to the clock for switching the address input of the memory between the first address register and the second address register.
Claim 12
Dependent Claim
87 words
The network forwarding device of claim 8 further including first and second data registers coupled to the clock signal and the data output from the memory, the first data register for latching data on the data output of the memory when an address from the first address register is on the address input of the memory and the second data register for latching data on the data output of the memory when an address from the second address register is on the address input of the memory.
Claim 13
Dependent Claim
60 words
The network forwarding device of claim 8 further including a first address calculation logic circuit coupled between the first comparator and the first address register and a second address calculation logic circuit coupled between the second comparator and the second address register, the address calculation logic circuits for determining next addresses to store in the first and second address registers.
Claim 14
Dependent Claim
22 words
The network forwarding device of claim 8 wherein the first and second address registers have tristate outputs controlled by the clock signal.
Claim 15
Dependent Claim
122 words
A network forwarding device comprising N search engines connected in series, where N is an integer greater than one, each search engine including a memory for storing one or more addresses of lookup table entries, each search engine performing iterations of two independent searches within three clock cycles, wherein during at least one of the three clock cycles an iteration of one of the searches is completing while an iteration of another of the searches is beginning such that there is overlapping between execution of the iterations of the two independent searches, each of the first (N-1) search engines configured to pass results of its first and second searches to a next search engine in that series for a next search iteration.
Claim 16
Dependent Claim
122 words
A network forwarding device comprising N search engines connected in series, where N is an integer greater than one, each search engine including a memory for storing one or more addresses of lookup table entries, each search engine performing iterations of two independent searches within three clock cycles, wherein during at least one of the three clock cycles an iteration of one of the searches is completing while an iteration of another of the searches is beginning such that there is overlapping between execution of the iterations of the two independent searches, each of the first (N-1) search engines configured to pass results of its first and second searches to a next search engine in that series for a next search iteration.
Claim 17
Dependent Claim
20 words
The network forwarding device of claim 13 wherein the lookup table is accessed three times during the three clock cycles.
Claim 18
Dependent Claim
65 words
The network forwarding device of claim 13 wherein the search engine accesses memory during a first clock cycle for an iteration of a first search and wherein during a second clock cycle the search engine accesses memory for an iteration of a second search and simultaneously analyzes results of the access of memory from the first clock cycle for the iteration of the first search.
Claim 19
Dependent Claim
24 words
The network forwarding device of claim 13 wherein the search engine includes two address registers, one for each of the first and second searches.
Claim 20
Dependent Claim
199 words
In a network forwarding device having N search engines connected in series, where N is an integer greater than one, a method of searching a lookup table, the method comprising the steps of: (a) providing a lookup table including network addresses and forwarding information associated with the network addresses; (b) receiving a network frame that includes a source address and a destination address; (c) storing a lookup address in a source address register; (d) using the lookup address in the source address register to obtain a network address from the lookup table relating to a first search; (e) comparing the network address obtained from the lookup table to the source address from the network frame; (f) if the network address from the lookup table is not equal to the source address from the network frame, calculating a next lookup address and storing the next lookup address in the source address register; (g) during the comparison step (e), using a destination address register to obtain a network address from the lookup table relating to a second search; and (h) passing results of the first and second searches to a next search engine in the series for a next search iteration.
Claim 21
Dependent Claim
199 words
In a network forwarding device having N search engines connected in series, where N is an integer greater than one, a method of searching a lookup table, the method comprising the steps of: (a) providing a lookup table including network addresses and forwarding information associated with the network addresses; (b) receiving a network frame that includes a source address and a destination address; (c) storing a lookup address in a source address register; (d) using the lookup address in the source address register to obtain a network address from the lookup table relating to a first search; (e) comparing the network address obtained from the lookup table to the source address from the network frame; (f) if the network address from the lookup table is not equal to the source address from the network frame, calculating a next lookup address and storing the next lookup address in the source address register; (g) during the comparison step (e), using a destination address register to obtain a network address from the lookup table relating to a second search; and (h) passing results of the first and second searches to a next search engine in the series for a next search iteration.
Claim 22
Dependent Claim
56 words
The method of claim 17 further including switching a multiplexer so that the source address register is used to access the lookup table on every other clock cycle and the destination address register is used to access the lookup table on clock cycles that the source address register is not used to access the lookup table.
Claim 23
Dependent Claim
14 words
The method of claim 17 whereby the first and second searches are performed concurrently.
Claim 24
Dependent Claim
145 words
A network forwarding device comprising: a database including a plurality of data entries; a first search engine having a first memory including one or more first addresses to a first set of data entries in the database; a second search engine having a second memory including one or more second addresses to a second set of data entries in the database; wherein, the first search engine performs a first search of the database by comparing a first search key with the first set of data entries, and the second search engine performs a second search of the database by comparing a second search key with at least a portion of the second set of data entries, the first and second searches being performed in series, wherein an output produced by the second search engine is dependent on an output produced by the first search engine.
Claim 25
Dependent Claim
145 words
A network forwarding device comprising: a database including a plurality of data entries; a first search engine having a first memory including one or more first addresses to a first set of data entries in the database; a second search engine having a second memory including one or more second addresses to a second set of data entries in the database; wherein, the first search engine performs a first search of the database by comparing a first search key with the first set of data entries, and the second search engine performs a second search of the database by comparing a second search key with at least a portion of the second set of data entries, the first and second searches being performed in series, wherein an output produced by the second search engine is dependent on an output produced by the first search engine.
Claim 26
Dependent Claim
16 words
The network forwarding device of claim 20, wherein the first and second search keys are identical.
Claim 27
Dependent Claim
33 words
The network forwarding device of claim 21, wherein the output produced by the first search engine indicates the portion of the second set of data entries to be searched during the second search.
Claim 28
Dependent Claim
31 words
The network forwarding device of claim 21, wherein the outputs produced by the first and second search engines are portions of an address in the database storing the first search key.
Claim 29
Dependent Claim
29 words
The network forwarding device of claim 21, wherein each of the search engines is configured to perform concurrent searches of two search keys within each of the search engines.
Claim 30
Dependent Claim
17 words
The network forwarding device of claim 24, wherein the two search keys are destination and source addresses.
References Cited (Backward Citations)
US5386413A
Cited
US5796944A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-12-12 | 2004-06-12 | 2004-12-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-12-12 | 2008-06-12 | 2008-12-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-12-12 | 2012-06-12 | 2012-12-12 | $7700.00 | Window Closed / Lapsed |