# US 7,613,189 B1 · Apparatus and method for efficient longest prefix match lookup > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,613,189 B1 - Document ID: US7613189B1 - Status: Granted - Kind: B1 - Application number: 11/796,143 - Filed: 2007-04-26 - Granted: 2009-11-03 - Earliest claimed: 2001-11-27 - Assignees: Marvell Israel (M.I.S.L) Ltd. - Inventors: Yaniv Kopelman; Carmi Arad; Nafea Bishara - Web page: https://patentgrep.com/patent/US7613189B1 ## CPC - H04L 45/00: Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00) - H04L 45/74591: {using content-addressable memories [CAM]} - H04L 49/3009: {Header conversion, routing tables or routing tags} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A network switch includes a matching device that employs a first data structure to select one of N address groups including a first partial address of an IP packet. An action table selects one of a next hop location corresponding to a longest prefix match and a first matching operation for the IP packet based on the selected one of the N groups. When the first matching operation is selected, the matching device employs a second data structure to select one of M address groups including a second partial address of the IP packet. The action table selects one of a next hop location corresponding to a longest prefix match and a second matching operation for the IP packet based on the selected one of the M groups. A routing engine routes the IP packet based on the first and second next hop locations. ## Claims ### Claim 1 A network switch comprising: a matching device that employs a first data structure to select one of N address groups including a first partial address of an Internet Protocol (IP) packet, wherein each of said N address groups includes an address range in a first partial address space, and wherein N is an integer greater than one; an action table that selects one of a next hop location corresponding to a longest prefix match and a first matching operation for said IP packet based on said selected one of said N groups, wherein when said first matching operation is selected, said matching device employs a second data structure to select one of M address groups including a second partial address of said IP packet, wherein each of said M address groups includes an address range in a second partial address space, and wherein M is an integer greater than one, and wherein said action table selects one of a next hop location corresponding to a longest prefix match and a second matching operation for said IP packet based on said selected one of said M groups; and a routing engine that routes said IP packet based on said first and second next hop locations. ### Claim 2 (depends on 1) The network switch of claim 1 wherein said first data structure comprises a first vector. ### Claim 3 (depends on 2) The network switch of claim 2 wherein said first vector includes N markers each representing one of said N address groups. ### Claim 4 (depends on 3) The network switch of claim 3 wherein each of said N markers comprise a bit in said first vector. ### Claim 5 (depends on 4) The network switch of claim 4 wherein each of said bits identify a beginning address of a range of addresses in said first partial address space. ### Claim 6 (depends on 1) The network switch of claim 1 wherein said matching device compares said first and second partial addresses to markers in said first and second data structures to identify said longest prefix match. ### Claim 7 (depends on 2) The network switch of claim 2 wherein said matching device compares said first partial address to said first vector. ### Claim 8 (depends on 3) The network switch of claim 3 wherein said matching device counts a number of said N markers in said first vector to one side of said first partial address in said first vector and selects one of said N address groups based on said count. ### Claim 9 (depends on 8) The network switch of claim 8 wherein said count corresponds to one of said longest matching prefix for said first partial address and said first matching operation. ### Claim 10 (depends on 2) The network switch of claim 2 wherein said first vector includes markers that are arranged in said first data structure according to a trie data structure. ### Claim 11 A method comprising: using a first data structure to select one of N address groups including a first partial address of an Internet Protocol (IP) packet, wherein each of said N address groups includes an address range in a first partial address space, and wherein N is an integer greater than one; selecting one of a next hop location corresponding to a longest prefix match and a first matching operation for said IP packet based on said selected one of said N groups; when said first matching operation is selected, using a second data structure to select one of M address groups including a second partial address of said IP packet, wherein each of said M address groups includes an address range in a second partial address space, and wherein M is an integer greater than one; selecting one of a next hop location corresponding to a longest prefix match and a second matching operation for said IP packet based on said selected one of said M groups; and using a router, routing said IP packet based on said first and second next hop locations. ### Claim 12 (depends on 11) The method of claim 11 wherein said first data structure comprises a first vector. ### Claim 13 (depends on 12) The method of claim 12 wherein said first vector includes N markers each representing one of said N address groups. ### Claim 14 (depends on 13) The method of claim 13 wherein each of said N markers comprise a bit in said first vector. ### Claim 15 (depends on 14) The method of claim 14 further comprising identify a beginning address of a range of addresses in said first partial address space using each of said bits. ### Claim 16 (depends on 11) The method of claim 11 further comprising comparing said first and second partial addresses to markers in said first and second data structures to identify said longest prefix match. ### Claim 17 (depends on 12) The method of claim 12 further comprising comparing said first partial address to said first vector. ### Claim 18 (depends on 13) The method of claim 13 further comprising: counting a number of said N markers in said first vector to one side of said first partial address in said first vector; and selecting one of said N address groups based on said count. ### Claim 19 (depends on 18) The method of claim 18 wherein said count corresponds to one of said longest matching prefix for said first partial address and said first matching operation. ### Claim 20 (depends on 12) The method of claim 12 wherein said first vector includes markers that are arranged in said first data structure according to a trie data structure.