Method and apparatus for longest prefix matching

[0001] The present invention relates to a fast LPM (Longest Prefix Match) lookup, particularly for use for packet routing in packet switched networks.

[0002] Longest Prefix Match (LPM) is a problem of finding the longest prefix among a number of prefixes stored in a data base that matches a given lookup key. LPM can be used in many applications and is not limited to IP routing, but since IP routing is one of the major LPM applications, the present invention will be discussed in a context of IP routing, by way of non-limiting example, only.

[0003] The growth of the Internet and the demand for increased bandwidth of networks has necessitated search capabilities that traditional RAMs (Random Access Memory) can barely meet. In a typical routing lookup operation, Internet routers look up the destination address of an incoming packet in its forwarding table to determine the packet's next hop on its way to the final destination. This operation is performed on each arriving packet by every router in the path that the packet takes from its source to the destination.

[0004] The adoption of Classless Inter-Domain Routing (CIDR) since 1993 means that a routing lookup operation requires performing a Longest Prefix Match (LPM), in which a match for the longest prefix with the lookup key is performed (wild card bits allowed), rather than a full match to every bit of the lookup key. A network processor, router, bridge, switch, or other network device performing similar routing lookup functions, maintains a set of destination address prefixes in a forwarding table, also known as a Forwarding Information Base (FIB). A FIB contains a set of prefixes with corresponding output interfaces indicating destination addresses. LPM is used in IPv4 and IPv6 routers to select the most appropriate entry in the routing/forwarding table, which indicates the proper output interface to which the input interface should send a packet to be transmitted by the router.

[0005] Given a packet, the Longest Prefix Match operation consists of finding the longest prefix in the FIB that matches the lookup key, for determining the destination of the packet to be transmitted by the router. The most commonly used lookup keys are the 32 bit address in Internet Protocol version 4 (IPv4), supporting an address space of 2³²-about 10⁹ addresses, or the 128 bit address Internet Protocol version 6 (IPv6), supporting an address space of 2¹²⁸-about 10³⁹ addresses.

[0006] A FIB can be implemented based on Random Access Memories (RAMs). In this case, the FIB prefixes are held in one or more RAMs, and software or hardware which executes search algorithms, such as M-Trie, Bitmap Tree, etc. (which are typically tree based search algorithms) performs the LPM. In a RAM, information is stored and retrieved at a location determined by an address provided to the memory.

[0007] Another alternative for implementing a FIB is by using a fast hardware lookup device, such as a TCAM. In a CAM (Content Addressable Memory), a search datum is provided to the CAM and every location in the memory is compared to it in parallel. The CAM responds with either a “match” or “mismatch” signal and returns the address, the contents of which matched the search data. CAM performs exact (binary) match searches, while the more powerful Ternary CAM (TCAM) adds masking capabilities, by storing and searching a third “don't care” state, enabling pattern matching with the use of “don't care” states. “Don't care” states act as wildcards during a search, and are thus particularly attractive for implementing longest prefix matching (LPM).

[0008] TCAMs have been also used for speeding up the destination address search function and quality of service (QoS) lookup required by network routers. When using TCAMs for FIB implementation, the lookup time is constant and there is no search throughput performance penalty, as opposed to a performance penalty incurred when using RAMs for searching. On the other hand, TCAMs are substantially larger and more complex devices than RAMS and also dissipate significantly more power than RAMs, due to their parallel search capability. Another TCAM disadvantage is a lack of error correction protection (ECC or similar), which reduces the overall system availability, due to the higher probability of an incidence of a memory bit error, particularly as the size of utilized TCAM memory increases.

[0009] While advanced RAM based FIB implementations/algorithms are scalable in terms of the number of prefixes they can hold, they are not scalable from the lookup key width perspective, as the number of accesses to FIB memory depends on the lookup key width. In general, the wider the key, the more lookups are required, and since prefixes will occupy more than one RAM entry, an execution time penalty for searching, proportional to the key width, will result, due to the tree based algorithms used.

[0010] A TCAM based FIB, on the other hand, is not scalable in terms of number of prefixes, as it holds a fixed number of entries. The most advanced TCAM device known today has a capacity of 20 Mbit, which can be used to hold up to 0.5 M prefixes.

[0011] Accordingly, there is a long felt need for a system and method for performing a Longest Prefix Match (LPM) operation in a Forwarding Information Base (FIB), which would exploit the respective advantages of TCAMs and RAMs and overcome the respective shortcomings of TCAMs and RAMs, to achieve a scalable FIB organization including a flexible number of entries and a constant LPM lookup time, and it would be very desirable to implement wire-speed packet forwarding using such a system.

[0012] There is provided according to the present invention a lookup table (particularly a FIB) that is constructed as a combination of TCAM and RAM memories. This combination permits creation of lookup table with multi-million prefixes. There is also provided a method for a fast LPM (Longest Prefix Match) using that lookup table, wherein a lookup is performed in two steps, one TCAM access step plus one RAM access step. The lookup can be carried out in a pipeline fashion, by performing simultaneously, in one cycle, a key N lookup step in the RAM and an N+1 key lookup step in the TCAM.

[0013] According to a preferred embodiment, the lookup table is implemented by a dynamic and scalable method of continuously mapping prefix (or other data) entries into an array of multiple RAM pages or windows. Preferably, each window can be read in one cycle. Each such window is organized as an array of entries and each entry contains prefix data and a tag. All windows are organized such that, in each window, all entries or prefixes have a common prefix portion, herein called an “aggregation prefix”, which is shorter than or of equal length to the entire prefix in the entry. It is a particular feature of the invention that the method, and the algorithm implementing it, is agnostic to the length of the key.

[0014] There is thus provided, according to the invention, a lookup table including stored data, the lookup table including a Random Access Memory (RAM) for storing the data, wherein the RAM includes a plurality of windows, and a Ternary Content Addressable Memory (TCAM) for storing indices, each index pointing to one of the windows.

[0015] According to a preferred embodiment, each window can be read in one cycle. Further according to a preferred embodiment, each window contains a plurality of entries, each entry containing at least a prefix field and a tag field.

[0016] There is also provided, according to the invention, a method for performing a Longest Prefix Match (LPM) including organizing data in a lookup table including a Random Access Memory (RAM) for storing the data, the RAM comprising a plurality of windows, and a Ternary Content Addressable Memory (TCAM) for storing indices, each index pointing to one of the windows, searching according to a lookup key in the TCAM, receiving a match signal from the TCAM including an index pointing to one of the windows, and searching according to the lookup key in the pointed to window.

[0017] According to a preferred embodiment, the step of organizing includes organizing the data in the windows into entries, each entry containing at least a prefix and a tag, and the method further includes reading all entries of one of the windows in parallel, generating a masked lookup key for each entry by masking each of the lookup key's least significant bits according to the entry's tag value, comparing each entry's prefix to the masked key to identify a match, selecting an entry with a largest tag value, when more than one entry provides a positive result, and providing an index of the selected matching entry in case of a match.

[0018] Further according to a preferred embodiment, the steps of searching in the TCAM of a present lookup key and searching the RAM for a previous lookup key are performed simultaneously in one cycle.

[0029] The present invention relates to a novel construction of a lookup table, described herein, by way of example only, as a Forwarding Information Base (FIB), and a dynamic and scalable method for performing a Longest Prefix Match (LPM) operation in that lookup table, particularly for use in routing applications. The lookup table according to the invention is organized as a combination of TCAM and RAM memories, while the method for LPM lookup is performed in two steps, one TCAM access step plus one RAM access step. In this way, the combination RAM/TCAM lookup table implementation achieves a scalable lookup table organization including a flexible number of prefixes and a constant LPM lookup time. In a FIB, this organization overcomes the search throughput penalty of a RAM-based FIB, and the non scalability restriction of a TCAM based FIB. It should be noted that, using currently available technology, the number of required TCAM entries for such FIB organization can be 2-3 orders of magnitude lower than the number of required TCAM entries when only TCAM is used for FIB implementation. Any unused TCAM entries can be used for additional classification/lookup features or to scale up the FIB functionality. This also improves system availability due to reduced usage of unprotected TCAM memory.

[0030] According to a preferred embodiment of the invention, the RAM is divided into many pages or windows, where each window is searched, as a whole, for a match. Preferably, each window can be read in one cycle. A schematic illustration of the organization of one example of a RAM window, according to one embodiment of the present invention, is shown in FIG. 1. In this example, RAM window 1 is organized as an array of entries 3. Each entry 3 in the illustrated embodiment includes a prefix field 6 and a tag field 4, indicating the number of valid Most Significant Bits (MSB) in the prefix field. The prefix and tag sizes can vary in different windows. The windows are preferably organized such that, in each window, all entries have a prefix field with an identical number of most significant bits, herein called an aggregation prefix. The aggregation prefixes are inserted into a TCAM in a non-ascending order of their prefix lengths, each pointing to the corresponding RAM window. It will be appreciated that the non-ascending order ensures correct operation of the LPM, as the TCAM lookup returns the index of the first TCAM entry matching the lookup key and, thus, the one with the longest prefix.

[0031] Each entry 3 may further include an optional memory protection field 2, such as Error Correction Code (ECC). If desired, the memory can be protected by any other protection scheme.

[0032] The plurality of windows can be implemented, for example, by putting multiple embedded RAM blocks, such as DRAM memory blocks, on-chip, and reading these RAM blocks in parallel. Since the width of the windows that are stored in RAM exceeds the word width of a single RAM block, each window is stored in multiple RAM blocks, where each of those RAM blocks contains part of the window information. Reading one window will thus require reading, in parallel, all the RAM blocks where the data of that window are stored.

[0033] A lookup in the window of FIG. 1 for a particular lookup key, according to an exemplary embodiment of the invention, is carried out according to the flow chart in FIG. 2. The entire window (i.e., tags 4 and prefixes 6) is read, preferably in one cycle, as by hardware logic (block 10). The hardware logic performs a replication of the lookup key, so as to provide one replica for each entry 3 in the window (block 12). During comparison, only the most significant bits of each of the lookup key replicas, represented by the value of tag 4, will be compared, and all the other bits of each replica are masked (block 14). For example, if the lookup key is 10.10.10.10 and the tag value is 16, then the key value for purposes of the LPM lookup, after the masking operation, is 10.10.*.*. This operation is carried out during a single cycle (i.e, fixed time period), and is not dependent on the number of replications (i.e., the number of entries).

[0034] Each prefix is compared (block 14), as by the hardware logic, to the corresponding masked key, to determine whether there is a match (block 15). If no match is found, a signal is sent indicating no match (block 13) and no data is read from the DRAM. When there is a miss indication, the rest of the result is “don't care”. According to a preferred embodiment, the database is built in such a way that no miss is possible (i.e., there is always a default (0.0.0.0/0 or default gateway) in the database). All the entries of a single window are read and searched in parallel. Subsequently, in the next cycle, another window, which belongs to the next lookup operation, is read and searched.

[0035] If a match is found, wherein the prefix and the masked key are equal, it is determined whether more than one match was uncovered (block 16). When more than one entry provides a positive result, the entry with the largest tag value is selected (block 17). The result of the lookup is provided (block 18), and the entry index of the best match uncovered in the lookup (i.e., the memory address of the entry in which a match was indicated) is also provided (block 19). In other words, a hit indication plus the result read from the corresponding DRAM location are output.

[0036] It should be noted that the result of such a RAM organization is the performance, in parallel, of an order independent, longest prefix match on multiple entries in one window. It will be appreciated that entry placement in a window is order independent, so new entry inserting is order independent, as well. Order independence simplifies the lookup table management and decreases the typical lookup table entry insert time.

[0037] An example of the organization of a FIB 20, according to a preferred embodiment of the invention, is shown in FIG. 3. FIB 20 includes a plurality of RAM windows, only two of which are shown, for ease of understanding. RAM window 22 contains, in all its entries, values in prefix field 6 of 192.168.*.*. In other words, the 16 most significant bits of all the prefixes in window 22 have an identical value of 192.168, while the remaining bits (least significant bits) contain values which differ from one another. Thus, in window 22, the aggregation prefix is 16 bits long. Similarly, RAM window 24 contains, in all its entries, prefix values of 10.*.*.*, wherein the 8 most significant bits of the prefix fields in all entries have an identical value of 10, and the 24 least significant bits contain other values. Thus, the aggregation prefix of RAM window 24 is 10.

[0038] FIB 20 further includes a TCAM 26, having a plurality of entries 28, each consisting of an aggregation prefix and an index pointing to the RAM window in which all the entries have that aggregation prefix. Thus, one entry 30 contains the aggregation prefix value 192.168 and an index 32, pointing to RAM window 22, in which all entries have an aggregation prefix of 192.168. The second exemplary entry 34 contains the aggregation prefix value 10. and an index 36, pointing to RAM window 24, in which all entries have the common aggregation prefix value of 10.

[0039] The principle of the FIB organization and the distribution of the prefixes into a number of windows, as described above, are based, in the illustrated example, on a unibit trie organization. Distribution of prefixes into a number of windows is illustrated in FIG. 4. The database of prefixes arranged and stored in the FIB is organized as a unibit trie 40. The following prefix database will be used as an example. The prefixes are represented by a binary notation 0, 1 and * (don't care):

[0040] P1=100*

[0041] P2=0*

[0042] P3=1*

[0043] P4=11*

[0044] P5=101*

[0045] P6=*(Default Gate Way)

[0046] P7=1000*

[0047] Each node in the corresponding unibit trie 40 can represent a real prefix (i.e., one of the prefixes listed above (e.g. P1, P2, etc.)) or a pseudo prefix (which has no associated prefix). P6 is selected as the root, because it has a *, or don't care, value. The sequence of building the tree for the given list of prefixes is as follows: The Most Significant Bit (MSB) of the prefix is checked. In the case of P2 and P3, where the prefix length is one, the MSB is the only bit. If the MSB has a value of “0”, prefix P2 is indicated, and if it has a value of “1”, prefix P3 is indicated. Since there are no other prefixes in this example which have a MSB bit of “0” value, P2 is a leaf node in this tree.

[0048] For longer prefixes, the bit next to the MSB (bit 2) is checked next. For P4 (P4=″11″) this bit value is “1”. There are no other prefixes in this example whose two most significant bits have a “11” value, and thus, P4 is also a leaf node in this tree. Since there is no prefix in this example having a “10” value, but there are longer prefixes with “10” value as their first two MSB bits, the node representing “10” is indicated in the example tree as a pseudo node A1 (i.e., not a real prefix), and the third bit is checked. For bit 3 equals “1”, prefix P5 (P5=″101″) is indicated in the tree as a leaf node (there are no other prefixes with “101” as their first 3 bits value). For bit 3 equals “0”, prefix P1 (P1=“100”) is designated. Subsequently P7 (P7=″1000″) is indicated, if bit 4 equals “0”.

[0049] For arranging data in the FIB of the present invention, unibit trie 40 is divided into a number of sub-trees. A weight (W) for each sub-tree is defined as the number of real prefix nodes (excluding pseudo nodes), that are included in this sub-tree. For example, the weight of a sub-tree whose root is P6 is W(P6)=7 (the entire tree 40, in this example); similarly the weight of a sub-tree whose root is P2 is W(P2)=1 (only P2); while the weight of a sub-tree whose root is P3 is W(P3)=5 (including nodes P3,P4,P1,P5,P7).

[0050] In order to distribute the prefixes into a number of windows, the tree is split into a number of sub-trees, while keeping the weight (W) of each sub-tree root node less than the window size. The tree can be split by a number of heuristic methods. One exemplary method is illustrated by the flow chart in FIG. 5.

[0051] First, a root of the prefix tree is selected (block 50).

[0052] The tree is traversed downward (block 52), starting from the tree root, selecting the child node with the largest weight at each node. If this child node has a weight (W) which is more than the window size (WS) (block 54), the traversing of the tree continues (block 56).

[0053] When the first node N having a weight (W) which is less than the window size (WS) is reached, the tree is split (block 58), forming a sub-tree rooted at node N, and it is determined whether node N is a real node (block 60). If N is a real node, the sub-tree real prefixes are written into a RAM window.

[0054] If N is not a real prefix node, an entry with zero length prefix is written into the RAM window pointing to the same lookup result as N's closest parent that represents a real prefix (block 64). Such an entry is called a backtracking pointer.

[0055] The aggregation prefix of N (either real or not) is then written into the TCAM, pointing to the corresponding RAM window (block 62). The aggregation prefixes are inserted into the TCAM in a non-ascending order of their prefix lengths, each pointing to the corresponding RAM window.

[0056] If, after splitting the above sub-tree, the main tree still has a number of nodes greater than the window size, the process of splitting the tree reiterates from traversing the tree (block 52), starting at the same root and calculating the new weights of the various child nodes, as the remaining tree has changed. After the entire tree has been split, the number of real prefixes in the remaining tree is less than the window size, so it can be written into a RAM window (block 62) and a TCAM window (block 64), like the sub-trees described above.

[0057] For a window size of WS=4, one possible split according to this invention is illustrated in FIG. 6 and the corresponding FIB 160 is shown in FIG. 7, according to the method illustrated in FIG. 5. Starting at root P6, the tree is traversed. At node P6, the child with the highest weight is P3. Since P3 has a weight greater than the window size, traversing continues. At P3, A1 is the child with the highest weight. Since the weight (W) of A1 is less than the window size (WS=4), the tree is split above node A1, creating two sub trees, one with a root at P6 and the other with a root at A1. It will be appreciated that, due to the size of this exemplary tree, no further splits are required.

[0058] The respective representation of this tree in a RAM 162 (having a window size of 4) and a TCAM 164 of the FIB 160 is shown in FIG. 7. FIB 160 includes two RAM windows 166, 168 of size WS=4. Window 166 stores the prefixes of the sub-tree whose root is P6, while window 168 stores the prefixes of the sub-tree whose root is A1. These prefixes may be inserted into the respective RAM windows in any arbitrary order.

[0059] Window 166 includes the four prefixes (P1, P5, P7, P3) with the aggregation prefix of 10*. It will be appreciated that, since A1 is merely a pseudo node (which does not represent a real prefix), a zero-length prefix is inserted into window 168 pointing to P3, since P3 is A1's closest parent that represents a real prefix, as shown in FIG. 6. Window 168 includes the four prefixes (P2, P3, P4, P6) with the aggregation prefix of *.

[0060] The two aggregation prefixes are written in the TCAM 164, aggregation prefix 165 10* pointing to window 166 and aggregation prefix 167* pointing to window 168.

[0061] A block diagram of a system 100 for performing a Longest Prefix Match, constructed and operative according to one embodiment of the invention, is illustrated in FIG. 8. LPM system 100 includes a first stage (TCAM) lookup logic 106 coupled to a TCAM 102, that contains a plurality of aggregation prefixes and associated indices, as described above, a TCAM associated result memory 104 and a lookup result interface 108 for outputting lookup results. A second stage (RAM) lookup logic 70 (described in detail in FIG. 9, below) is coupled to a longest match result memory 80, implemented in DRAM in one embodiment of the invention, for storing results of the Longest Prefix Match search. Result memory 80 contains the results associated with each window entry. One result for each entry is located at a predetermined RAM location.

[0062] Second stage lookup logic 70 is also coupled to a lookup key and window ID 72 interface for receiving lookup keys and associated window IDs from first stage lookup logic 106 output via lookup result interface 108. First stage lookup logic 106 includes an input interface 110 for receiving lookup keys and a control interface 103 for receiving control lines for programming the logic and writing in the database from a host system (not shown), which may be a host CPU or another proprietary block.

[0063] Referring now to FIG. 9, as stated above, second stage lookup logic 70 includes lookup key interface 72 for receiving input lookup keys and associated window IDs. Lookup key interface 110′ is coupled to an ECC protection block 74 which, in turn, is coupled to a replicator 76 for replicating the lookup key. Replicator 76 is coupled to comparison means 78, which is also coupled to a database or memory 86 to be searched, i.e., any Random Access Memory, here illustrated, by way of example only, as an SRAM.

[0064] Memory 86 contains all the windows holding the database, from which one window is accessed at a time. Second state lookup logic 70 also includes control lines 103′, arranged for programming the logic and writing in the database to control memory 86. Comparison means 78 is arranged to provide signals indicating matches to a module 94 for selecting the longest of the matches and outputting the corresponding result data to a result memory 80, preferably a DRAM. Result memory 80 is coupled to an output interface 84, preferably via a further ECC block 82, providing a protected output result.

[0065] Operation of this system is as follows: An exemplary lookup key (LU) is input to first stage lookup logic 106 via lookup key interface 110. Logic 106 searches in TCAM 102 for the first aggregation prefix entry matching lookup key LU and returns a miss or match indication together with a window ID index where a match was found. TCAM matching results are also stored in TCAM associated result memory 104. The exemplary lookup key LU and window ID are output via output interface 108 and input into the second stage lookup logic 70 via interface 72. The ECC block 74 performs error detection and correction on the lookup key, for example, based on an ECC section in the lookup key, and outputs a corrected lookup key. One entire window, located in the SRAM 86, is read, preferably in one cycle, and input to the comparator 78. Replicator 76 replicates the lookup key outputting a plurality of replicas 90 of the lookup key.

[0066] Each prefix in the window read from the SRAM 86 is compared by comparator 78 to an associated lookup key replica output by replicator 76, after a number of the replica's least significant bits, according to the tag value of the corresponding window, have been masked, and the comparator outputs a result. A positive result signal including the index of the appropriate entry is provided by comparator 78 if it finds a match, whereby a prefix and the masked key are equal. A negative result signal is output if no match is found.

[0067] When more than one prefix provides a positive result, the prefix with the largest tag value (i.e., longest prefix) is selected by module 94 which outputs an address 96 for accessing the result memory 80.

[0068] The result memory 80, here illustrated by way of example as a DRAM, is preloaded by the host CPU and contains a database corresponding to memory 86—for each entry entered in the memory window, a corresponding entry is entered in the result memory 80. When a match is found, the location of the result block in memory 80 can be calculated therefrom. Result memory 80 provides a result 97 for address 96, which preferably is checked by ECC block 98, providing the final result 84. When using the FIB of the present invention in a router, the result is a data block describing where the packet with the given destination address (lookup key) matching the FIB prefix should be sent to.

[0069] It will be appreciated that the lookup can be carried out in a pipeline fashion, by performing simultaneously, in one cycle, a key N lookup step in the RAM and an N+1 key lookup step in the TCAM.

[0070] While the invention has been described with respect to a limited number of embodiments, it will be appreciated that many variations, modifications and other applications of the invention may be made. It will further be appreciated that the invention is not limited to what has been described hereinabove merely by way of example. Rather, the invention is limited solely by the claims which follow.