Longest Prefix Match Using Binary Search Tree

Abstract

Longest Prefix Match (LPM) is implemented using a binary tree based search algorithm. Masked entries are stored in a plurality of binary search engines, wherein each of the binary search engines stores masked entries of a corresponding mask length. A search value is applied to each of the binary search engines in parallel. The search value is masked within each of the binary search engines, thereby creating a plurality of masked search values, each having a masked length equal to the mask length of the corresponding binary search engine. Each of the masked search values is compared with the masked entries of the corresponding binary search engine. An LPM result is selected from the binary search engine that detects a match, and has the longest corresponding mask length. Alternately, each binary search engine stores masked entries of N mask lengths, and N consecutive comparisons are performed to identify the LPM.

We claim: 
     
         1 . A binary search engine comprising:
 a binary search tree including a plurality of nodes arranged in a plurality of levels, wherein each of the nodes is either a valid node that stores a valid entry, or a free node that does not store a valid entry, wherein the plurality of levels includes a leaf level, wherein all nodes above the leaf level are valid nodes, all nodes below the leaf level are free nodes, and the leaf level includes one or more free nodes, wherein all of the free nodes in the leaf level are continuous and adjacent, without any intervening valid nodes.   
     
     
         2 . The binary search engine of  claim 1 , further comprising a single pointer that identifies all of the free nodes in the leaf level. 
     
     
         3 . The binary search engine of  claim 1 , further comprising:
 a left free pointer that identifies a left-most free node in the leaf level; and   a right free pointer that identifies a right-most free node in the leaf level.   
     
     
         4 . The binary search engine of  claim 1 , wherein each of the nodes is implemented by random access memory (RAM). 
     
     
         5 . The binary search engine of  claim 1 , further comprising:
 a first index that orders the nodes located at and above the leaf level based on relative physical locations of the nodes within the binary search tree; and   a second index that orders the nodes located at and above the leaf level based on relative logical locations of the nodes within the binary search tree.   
     
     
         6 . The binary search engine of  claim 5 ,
 wherein the first index orders the nodes located at or above the leaf level consecutively between a left-most node of the leaf level and a right-most node of the leaf level; and   wherein the second index orders the nodes located at or above the leaf level by the levels in which the nodes are located.   
     
     
         7 . The binary search engine of  claim 5 , further comprising one or more conversion blocks for converting between the first index and the second index. 
     
     
         8 . The binary search engine of  claim 1 , wherein the plurality of nodes are logically grouped into a plurality of super nodes, each of the super nodes including a first number of nodes that span a plurality of levels of the binary search tree. 
     
     
         9 . The binary search engine of  claim 1 , further comprising a second binary search tree, coupled in parallel with the first binary search tree. 
     
     
         10 . The binary search engine of  claim 9 , wherein the second binary search tree includes a second plurality of nodes arranged in a second plurality of levels, wherein each of the second plurality of nodes is either a valid node that stores a valid entry, or a free node that does not store a valid entry, wherein the second plurality of levels includes a second leaf level, wherein all nodes above the second leaf level are valid nodes, all nodes below the second leaf level are free nodes, and the second leaf level includes one or more free nodes, wherein all of the free nodes in the second leaf level are continuous and adjacent, without any intervening valid nodes. 
     
     
         11 . A method of operating a binary search engine comprising:
 storing entries in a binary search tree that includes a plurality of nodes arranged in a plurality of levels, wherein each of the nodes is either a valid node that stores a valid entry, or a free node that does not store a valid entry; and   maintaining the entries of the binary search tree such that one of the levels of the binary search tree forms a leaf level, wherein all nodes above the leaf level are valid nodes, all nodes below the leaf level are free nodes, and the leaf level includes one or more free nodes, wherein all of the free nodes in the leaf level are continuous and adjacent, without any intervening valid nodes.   
     
     
         12 . The method of  claim 11 , further comprising identifying all of the one or more free nodes in the leaf level with a single pointer. 
     
     
         13 . The method of  claim 11 , further comprising logically grouping the nodes of the binary search tree into a plurality of super nodes, each of the super nodes including a plurality of nodes that span a plurality of levels of the binary search tree. 
     
     
         14 . The method of  claim 11 , further comprising:
 associating a first pointer with a first free node located at a first end of the one or more continuous and adjacent free nodes in the leaf level; and   associating a second pointer with a second free node located at a second end of the one or more continuous adjacent free nodes in the leaf level.   
     
     
         15 . The method of  claim 14 , further comprising comparing a new entry to be added to the binary search tree with entries of the binary search tree to identify an add-node position where the new entry will be added to the binary search tree. 
     
     
         16 . The method of  claim 15 , further comprising:
 determining whether the add-node position is closer to the first pointer or the second pointer, and designating the closer of the first and second pointers as a nearest free pointer;   performing a bubble movement of the entries of the binary search tree from the add-node position to the nearest free pointer; and   adding the new entry at the add-node position.   
     
     
         17 . The method of  claim 14 , further comprising identifying a del-node position, which corresponds with a node from which an existing entry of the binary search tree will be deleted. 
     
     
         18 . The method of  claim 17 , further comprising:
 determining whether the del-node position is closer to the first pointer or the second pointer, and designating the closer of the first and second pointers as a nearest free pointer;   performing a bubble movement of the entries of the binary search tree from a valid node adjacent to the nearest free pointer in the leaf level to the del-node position.   
     
     
         19 . A network switch comprising:
 a search engine that performs search operations in response to received packets, the search engine including a binary search tree that stores a plurality of entries in random access memory (RAM), and means for comparing the received packets with entries of the binary search tree to provide search results.   
     
     
         20 . The network switch of  claim 19 , further comprising a processor that uses the search results to address the received packets for forwarding. 
     
     
         21 . The network switch of  claim 20 , wherein the processor and the search engine are fabricated on the same integrated circuit chip. 
     
     
         22 . The network switch of  claim 20 , further comprising a switch fabric coupled to receive the packets addressed by the processor. 
     
     
         23 . The network switch of  claim 19 , wherein the search engine further comprises add/delete logic that adds and deletes entries of the binary search tree. 
     
     
         24 . The network switch of  claim 19 , wherein the search engine comprises a plurality of binary search trees, each storing a unique plurality of entries in RAM, and means for comparing the received packets with entries of the plurality of binary search trees in parallel to provide search results. 
     
     
         25 . The network switch of  claim 24 , wherein the plurality of binary search trees store over 1 million unique entries in RAM. 
     
     
         26 . The network switch of  claim 19 , further comprising means for pipelining the search operations within the search engine, whereby the search engine provides search results during consecutive cycles of a clock used to access the RAM. 
     
     
         27 . The network switch of  claim 19 , wherein the plurality of entries comprise layer 2 (L2) information. 
     
     
         28 . The network switch of  claim 27 , wherein the L2 information includes media access controller (MAC) addresses and/or virtual local area network (ULAN) instances. 
     
     
         29 . The network switch of  claim 19 , wherein the plurality of entries comprise layer 3 (L3) information.