# US 6,678,678 B2 · Method and apparatus for high speed table search > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 6,678,678 B2 - Document ID: US6678678B2 - Status: Granted - Kind: B2 - Application number: 09/800,784 - Filed: 2001-03-08 - Published: 2001-10-18 - Granted: 2004-01-13 - Earliest claimed: 2000-03-09 - Assignees: Braodcom Corporation - Inventors: Dennis Sungik Lee; Michael Veng-Chong Lau; Pei-Feng Adrian Wang; Chuen-Shen Bernard Shung - Web page: https://patentgrep.com/patent/US6678678B2 ## CPC - H04L 12/56: {Packet switching systems} - G06F 16/9017: {using directory or table look-up (use of a directory or look-up table in file systems G06F16/13)} - Y10S 707/99933: Query processing, i.e. searching - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS ## Abstract A table searching system for facilitating high speed linear searching of a table of information by a plurality of searching agents is provided. The system includes: a memory unit for storing a table of information including a plurality of data entries each having data contents; a plurality of searching agents each being communicatively coupled with the memory unit, and having a port for receiving an associated search key value; and a memory controller unit providing a centralized interface between the memory unit and each of the agents, the controller unit being operative to control the memory unit to provide the contents of a current one of the table entries to each of the agents during each of a plurality of cycles of operation. Each of the searching agents is operative to determine an associated best matching one of the data entries based on comparisons between the associated key value and the contents of the data entries provided by the memory unit. ## Claims ### Claim 1 A table searching method, the method comprising the steps of: providing at least one memory unit having a table of information including a plurality of data entries; providing a plurality of searching agents each being communicatively coupled with said memory unit, each of said searching agents receiving an associated search value; receiving at least one table entry from said plurality of data entries, broadcast by said at least one memory unit, by each of said agents; and processing said at least one table entry by each of said searching agents to determine if a match occurs between the associated search value and the at least one table entry. ### Claim 2 (depends on 1) A table searching method as recited in claim 1 wherein said step of providing at least one memory unit comprises providing at least one memory unit having a plurality of tables and said step of receiving at least one table entry comprises receiving said at least one table entry and a table address associated with a selected table of said plurality of tables. ### Claim 3 (depends on 1) A table search method as recited in claim 1 wherein said step of receiving at least one table entry comprises receiving multiple table entries at the same time and said step of processing said at least one table entry comprises comparing the multiple table entries with the associated search value. ### Claim 4 (depends on 1) A table search method as recited in claim 1 wherein said step of receiving at least one table entry comprises each of said plurality of search agents receiving said at least one table entry at the same time. ### Claim 5 (depends on 1) A table search method as recited in claim 1 wherein said step of receiving at least one table entry comprises a first search agent of said plurality of search agents receiving said at least one table entry and the first search agent passing said at least one table entry to a next search agent such that all of the plurality of search agents receive said at least one table entry in turn. ### Claim 6 (depends on 5) A table searching method as recited in claim 5 wherein each of said agents is communicatively coupled with said controller unit and each of said agents provides a search enable signal to said controller unit in response to receiving said associated search value, said step of providing said series of memory address values occurs in response said search enable signal by at least one of said agents. ### Claim 7 (depends on 1) A table searching method as recited in claim 1 wherein in said processing step each of said searching agents determines said match as an associated best matching of a plurality of table entries in accordance with a longest prefix match searching process. ### Claim 8 (depends on 1) A table searching method as recited in claim 1 wherein in said processing step each of said searching agents determines said match as an associated best matching of a plurality of table entries in accordance with a policy match searching process. ### Claim 9 (depends on 1) A table searching method as recited in claim 1 further comprising the steps of: providing a controller unit that controls said memory unit; and providing a series of memory address values to said memory unit by said controller unit, wherein said memory unit responds to said memory address values, and table entries received by each of said agents are based on said memory address values. ### Claim 10 A table searching method, the method comprising the steps of: providing at least one memory unit having a table of information including a plurality of data entries; providing a plurality of searching agents each being communicatively coupled with said memory unit, each of said searching agents receiving an associated search value; and broadcasting at least one table entry from said plurality of data entries by said at least one memory unit to each of said agents; wherein each of said searching agents determines if a match occurs between the associated search value and the table entry. ### Claim 11 (depends on 10) A table search method as recited in claim 10 wherein said step of broadcasting at least one table entry comprises broadcasting multiple table entries at the same time and said searching agents determines if a match occurs between the multiple table entries and the associated search value. ### Claim 12 (depends on 10) A table search method as recited in claim 10 wherein said step of broadcasting at least one table entry comprises broadcasting to each of said plurality of search agents said at least one table entry at the same time. ### Claim 13 (depends on 10) A table search method as recited in claim 10 wherein said step of broadcasting at least one table entry comprises providing a first search agent of said plurality of search agents with said at least one table entry and the first search agent passing said at least one table entry to a next search agent, such that all of the plurality of search agents receive said at least one table entry in turn. ### Claim 14 (depends on 10) A table searching method as recited in claim 10 wherein said step of providing at least one memory unit comprises providing at least one memory unit having a plurality of tables and said step of broadcasting at least one table entry comprises broadcasting said at least one table entry and a table address associated with a selected table of said plurality of tables. ### Claim 15 (depends on 10) A table searching method as recited in claim 10 wherein in said searching agents determines said match as an associated best matching of a plurality of table entries in accordance with a longest prefix match searching process. ### Claim 16 (depends on 10) A table searching method as recited in claim 10 wherein in said searching agents determines said match as an associated best matching of a plurality of table entries in accordance with a policy match searching process. ### Claim 17 (depends on 10) A table searching method as recited in claim 10 further comprising the steps of: providing a controller unit that controls said memory unit; and providing a series of memory address values to said memory unit by said controller unit, wherein said memory unit responds to said memory address values, and table entries broadcast to each of said agents are based on said series of memory address values. ### Claim 18 (depends on 17) A table searching method as recited in claim 17 wherein each of said agents is communicatively coupled with said controller unit and each of said agents provides a search enable signal to said controller unit in response to receiving said associated search value, said step of providing said series of memory address values occurs in response said search enable signal by at least one of said agents. ### Claim 19 A table searching system comprising: a memory unit for storing a table of information including a plurality of data entries each having data contents; a plurality of searching agents each being communicatively coupled with said memory unit, and having a port for receiving an associated search key value; and a memory controller unit providing a centralized interface between said memory unit and each of said agents, said controller unit being operative to control said memory unit to broadcast the contents of a current one of said table entries to each of said agents during each of a plurality of cycles of operation; each of said searching agents being operative to determine an associated best matching one of said data entries based on comparisons between said associated key value and the contents of said data entries broadcast by said memory unit. ### Claim 20 (depends on 19) A table searching system as recited in claim 19 wherein said memory unit comprises a static random access memory (SRAM) unit. ### Claim 21 (depends on 19) A table searching system as recited in claim 19 wherein each of said searching agents is operative to determine said associated best matching one of said data entries in accordance with a longest prefix match searching process. ### Claim 22 (depends on 19) A table searching system as recited in claim 19 wherein each of said searching agents is operative to determine said associated best matching one of said data entries in accordance with a policy match searching process. ### Claim 23 (depends on 19) A table searching system as recited in claim 19 wherein said controller unit controls said memory unit by providing a series of memory address values to said memory unit, and wherein said memory unit is responsive to said memory address values, and operative to broadcast the contents of one of said table entries to each of said agents during each of said cycles. ### Claim 24 (depends on 23) A table searching system as recited in claim 23 wherein each of said agents is communicatively coupled with said controller unit for providing an associated one of a plurality of search enable signals to said controller unit, each of said agents being operative to assert said associated enable signal in response to receiving said associated search key value, said controller unit being operative to provide said series of memory address values to said memory unit in response to at least one of said search enable signals being asserted. ### Claim 25 (depends on 19) A table searching system as recited in claim 19, wherein each of said agents further comprises: a comparison logic unit for receiving said associated search key value, and for receiving said contents of said table entries provided by said memory unit; a data register communicatively coupled with said comparison logic unit; a match quality register communicatively coupled with said comparison logic unit, said quality register for storing temporarily selected match quality values associated with temporarily selected ones of said entries; said comparison logic unit being operative during each of said cycles to perform a best match table searching process including the steps of, comparing said associated key value to a selected portion of the contents of said current entry to determine whether there is a current match, and if a current match is determined between said associated key value and said selected portion of said contents of said current entry, determining a current match quality value associated with said current entry, said current match quality value being indicative of a quality of said current match, comparing said current match quality value to a previous temporarily selected match quality value stored in said match quality register to determine if said current match is a more desirable match than a match associated with said previous temporarily selected match quality value, and if said current match is a more desirable match than a match associated with said previous temporarily selected match quality value, replacing the contents of said match quality register with said current match quality value, and replacing the contents of said data register with the data contents of said current entry. ### Claim 26 (depends on 25) A table searching system as recited in claim 25 wherein: said table of information is a policy match table; each of said data entries includes key fields for storing associated stored key values and mask value fields storing associated mask values; and said searching process includes comparing an unmasked portion of said associated received key value to an unmasked portion of said stored key value of said current entry, each of said unmasked portions of said received key value and said stored key value being defined by masking a number of least significant bits indicated by the mask value of said current entry.