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.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
   This application is a continuation of U.S. Ser. No. 10/167,005, filed Jun. 10, 2002, now U.S. Pat. No. 7,212,531, issued May 1, 2007, which application claims the benefit of U.S. Provisional Application No. 60/333,712, filed Nov. 27, 2001. The disclosures of the above applications are incorporated herein by reference. 

   FIELD OF THE INVENTION 
   The present invention relates to network routers and switches, and more particularly to search engines for network routers and switches that employ longest prefix matching (LPM) of packet IP addresses. 
   BACKGROUND OF THE INVENTION 
   Routers and layer-3 switches read an IP address of packets and route the packets according to destination address. The packet is received on an incoming link of the router. The router selects an outgoing link or next hop based on the destination address. When a packet is routed from a computer in California to a computer in Michigan, multiple routers typically receive and forward the packet. Each router in the path is also referred to as a hop. For most of the routers along the path, only the network part of the destination address is used to route the packet. 
   The router typically employs a forwarding table that includes a next hop pointer for IP addresses. The forwarding table includes two types of IP addresses: individual host IP addresses and network IP addresses. A host IP address designates one host computer. Host IP addresses are fully specified. An IPv4 host address specifies 32 bits, while an IPv6 host IP address specifies 128 bits. 
   A network (subnet) IP address aggregates one or more consecutive host IP addresses. Network IP addresses are specified by a prefix. For example, the IPv4 network IP address 0x123456/24 specifies all host IP addresses in the range [0x12345600, 0x123456FF]. When a packet arrives, the router looks up the IP addresses stored in the forwarding table using the packet&#39;s destination IP address. The router finds the most specific IP address according to a LPM (Longest Prefix Match) criteria. The router forwards the packet to the next hop associated with this address. 
   The LPM criteria states that when the search yields multiple matches (i.e. the searched IP address is contained in several subnets), the packet should be routed to the next hop associated with the network address having the longest prefix. For example, given the IPv4 forwarding table [0x123456/24, 3]; [0x1234567/28, 2]; [0x12345678, 1], a packet with destination IP address 0x12345666 is forwarded to 3 (having only one matching subnet address). A packet with destination address 0x12345677 is forwarded to 2 (having 2 matching subnet addresses and selecting the one with longest matching prefix). A packet with destination address 0x12345678 is forwarded to 1 (having 3 matching subnets and selecting the one with the longest matching prefix). 
   Operating or routing speed and the cost of the router hardware are very important to router design. If the forwarding table includes a next hop pointer for each individual host IP address, the forwarding table would have 2 32  entries for a 32-bit IPv4 addresses and 2 128  entries for a 128-bit IPv6 addresses. The search time would be too long and the amount of memory too large. To compress the forwarding table and increase speed, the forwarding table is frequently arranged using network IP addresses. 
   SUMMARY OF THE INVENTION 
   A longest prefix matching (LPM) search engine includes a first bit vector with set bits corresponding to address ranges of an address space. A set bit counter counts the set bits in the bit vector based on a first address. A first next hop table contains first pointers for each of the set bits. One of the first pointers is selected based on a number of set bits counted by the set bit counter. 
   In other features, the address ranges are associated with an address prefix. The set bits are associated with the address ranges. The set bit represents a lowest address of the prefix that is assigned to the address range. 
   In still other features, the first address is divided into n address portions. The search engine includes a trie data structure that has n levels. The n levels of the trie data structure include nodes representing non-overlapping address space. The trie data structure initially searches at a first level using a first address portion. The first address portion contains consecutive most significant bits of the address. The set bit counter counts the set bits of the first bit vector using the first address portion. 
   In yet other features, the first pointers include next hop pointers and next bucket pointers. If one of the next hop pointers is output by the next hop table, the search is terminated and the router routes a first packet based on one of the next hop pointers. 
   The search engine further includes a second bit vector and a second next hop table that are associated with one of the next bucket pointers. The set bit counter counts set bits in the second bit vector based on a second address portion. The second next hop table outputs one of a next hop pointer and a next bucket pointer based on a second number of set bits counted by the set bit counter. 
   Further areas of applicability of the present invention will become apparent from the detailed description provided hereinafter. It should be understood that the detailed description and specific examples, while indicating the preferred embodiment of the invention, are intended for purposes of illustration only and are not intended to limit the scope of the invention. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention will become more fully understood from the detailed description and the accompanying drawings, wherein: 
       FIG. 1A  is a functional block diagram of an exemplary network topology including a longest prefix match (LPM) router according to the prior art; 
       FIG. 1B  is a functional block diagram of the router of  FIG. 1A  including a search engine and a forwarding table; 
       FIG. 1C  illustrates an exemplary forwarding table for the network of  FIG. 1A ; 
       FIG. 2A  is a functional block diagram of an exemplary network topology including a LPM router according to the present invention; 
       FIG. 2B  is a simplified functional block diagram of a single-stage LPM search; 
       FIG. 3  illustrates a bit vector data structure for a 4-bit address space; 
       FIG. 4  illustrates a bit vector data structure for the 4-bit address space with exemplary prefixes that are associated with next hop pointers; 
       FIG. 5  illustrates a forwarding table for the exemplary 4-bit address space of  FIG. 4 ; 
       FIG. 6  is a table illustrating address ranges for the exemplary 4-bit address space; 
       FIGS. 7 and 8  illustrate bit vector and next hop data structures; 
       FIG. 9  illustrates a trie data structure for handling a 32-bit address space; 
       FIG. 10  illustrates bit vectors and next hop tables for level 0 and level 1 of a 32-bit address space example; 
       FIG. 11  is a flowchart illustrating steps performed by the LPM router; 
       FIG. 12  illustrates an enhanced bit vector that reduces memory cycles; 
       FIG. 13  illustrates one line compressed bit vector; and 
       FIG. 14  illustrates a two line compressed bit vector. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   The following description of the preferred embodiment(s) is merely exemplary in nature and is in no way intended to limit the invention, its application, or uses. For purposes of clarity, the same reference numbers will be used in the drawings to identify the same elements. 
   Referring now to  FIGS. 1A ,  1 B and  1 C, an exemplary network  10  is shown. An IP packet  20  is received by a LPM router  22  according to the prior art. A header of the packet  20  is used by the router  22  to route the packet  20  to one or more subnets  26 - 1 ,  26 - 2 ,  26 - 3 , . . . , and  26 - n , computers  30  or any other network devices. The header typically contains a source address, destination address, and other information. The router  22  includes a forwarding table  32 , which is a data structure that includes a list of address prefixes. While the present invention will be described in conjunction with a router, other network devices that utilize LPM criteria are contemplated. A search engine  34  of the router  22  matches portions of the header (such as the destination address) of the packet  20 . The searched header portions may contain one or more fields or portions of fields of the header. While the present invention will be described below using a destination address of the header, skilled artisans will appreciate that other header portions may be utilized. 
   The LPM router  22  selects the longest prefix in the forwarding table  32  that matches the searched address. In a preferred embodiment, the IP packets  20  are IPv4 packets that contain a 32-bit address. However, the invention applies to other address spaces that require longest prefix match, such as IPv6. A next hop pointer that is associated with a longest prefix that matches the header portions is used to route the packet  20 . 
   An example forwarding table  32  for a 4-bit address space is shown in  FIG. 1C . The LPM router  22  stores the following address prefixes: * (a default route—the subnet  26 - 1 ), 0* (all addresses with 0 as their MSb—the subnet  26 - 2 ), 001* (all addresses having three MSbs equal to 001—the subnet  26 - 3 ), and 10* (all addresses having two MSbs equal to 10—the subnet  26 - n ) and 1110 (an exact address—the computer  30 ). Continuing with the above example, an address 0001 is matched to a forwarding table entry 0*. An address 0010 is matched to a forwarding table entry 001*. An address 1010 is matched to a forwarding table entry 10* and an address 1100 is matched to a forwarding table entry *. 
   Referring now to  FIGS. 2A and 2B , an LPM router  36  according to the present invention is shown. A search engine  38  of the LPM router  36  includes a set bit counter  40  that receives an address of the packet  20 . The set bit counter  40  uses the address to count set bits of a bit vector data structure  42 . The set bit counter  40  outputs the number of set bits for the address to the next hop data structure or table  44 , which outputs a corresponding next hop pointer. The next hop pointer is used to route the packet. 
   As can be appreciated, the exemplary LPM router  36  stores address prefixes rather than exact addresses. The LPM router  36  can also store host addresses. In other words, the LPM router  36  can store both subnetwork and host addresses. 
   The search engine  38  minimizes the search time and forwarding table space requirements. The search engine  38  allows incremental updates of the forwarding table so that the search process is not blocked for long periods. The search engine  38  also allows synchronization of forwarding tables among several routers and is easy to implement in hardware. 
   Referring now to  FIGS. 3 and 4 , an example address space is addressed by 4 bits and includes 16 different addresses. A bit vector is 2 4  long and covers 0000 to 1111. The prefix 0* covers the address range 0000-0011. Similarly, the prefix 01* covers the address range 0100-0111. The term “covering” means that a search for an address in the range 0100-0111 should be matched to the next hop associated to prefix 01* as shown in  FIG. 4 . The bit vector is 2 4 =16 bits long and is arranged in order from 0000 binary to 1111 binary. The bit vector is split into four consecutive address ranges as shown for 3 prefixes used in this example. 
   An exemplary next hop table that is shown in  FIG. 5  contains 3 prefixes: * (the default route), 0* and 001*. The prefixes split the address space into 4 address ranges as shown in  FIG. 6 . A first range 0000-0001 is associated with prefix 0*; a second range 0010-0011 is associated with prefix 001*; a third range 0100-0111 is associated with (again) prefix 0*; and a fourth range 1000-1111 is associated with the default route (prefix *). 
   The LPM rule is applied so that address spaces that are covered by more than one prefix are associated with the longest prefix covering that range. An important consequence of the LPM rule is that more than a single address range can be associated with the same prefix (as can be observed for prefix 0*) in  FIG. 6 . However, N prefixes will create less than or equal to 2N−1 different address ranges 
   Referring now to  FIG. 7 , an exemplary bit vector data structure  42  (or bit vector) for the example 4-bit address space is shown. Set bits  45  are set equal to 1&#39;s. In  FIG. 8 , a next hop data structure or table  44  (or next hop pointer) is shown. The next hop table  44  has a next hop pointer  46 - 1 ,  46 - 2 ,  46 - 3  and  46 - 4  for each set bit. The set bit counter  40  of  FIG. 2B  receives the address of the packet  20  and counts the number of “1” bits (inclusive) to the left in the bit vector  42 . The number of “1” bits is used to select the next hop pointer in the next hop table  44 . 
   The search engine  38  assigns a next hop pointer to every address range. The search engine  38  receives a given address and identifies the address range including the address. A next hop pointer that is associated with the identified range is selected. The bit vector  42  reserves a bit for every address in the address space. The set bits are used to indicate the lowest address of each address range. 
   The table of next hop pointers  56  holds the next hop pointer for each address range. If an address equal to 1010 is received, the number of set bits in the bit vector is counted from position 1010 down to position zero (inclusive). In this example, there are 4 set bits. Therefore, the 4th next hop pointer is selected. The LSb in the bit vector  42  is set by default (the bit corresponding to address 0) because the address space contains at least one address range. 
   The search mechanism for IPv4 addresses is similar to the example described above. IPv4 addresses span 2 32  addresses. Therefore, the approach set forth above can be expanded from 4 to 32 bits (and any other space, particularly, 128 bits address space) if sufficient memory and response times are present. However, modifications that will be described below are preferably made to improve efficiency when handling 32-bit or larger addresses. 
   Referring now to  FIG. 9 , to limit the size of the bit vector (and also maintain relatively small next hop tables), a trie data structure  50  (or a trie of buckets) is constructed. In binary tries, the value of successive bits in the address determines a path from the root to lower search levels. A binary trie is a tree with paths determined by the data that is stored. The number of bits that are required to identify a next hop pointer depends on the values in the prefixes. Searches are terminated when a next hop pointer is encountered. This implies that search time, as well as the depth of the trie data structure  50 , is proportional to the length of the search key or address. Updates are also easier when using binary tries as compared with binary trees. 
   Every bucket or node in the trie data structure  50  has the same structure as in the 4-bit example described above. For 32-bit addresses, as an example, each bucket can be searched by 8 bit address portions, has a bit vector with a length equal to 256 bits and a next hop table with 2 to 256 lines. In order to cover the whole IPv4 address space, the buckets are nodes in a 4 level trie that is illustrated in  FIG. 9 . In the trie data structure  50 , nodes on the same level cover non-overlapping address spaces associated with the four address portions. Every node may have at most 256 child nodes. A prefix is stored in a node (or bucket) that covers the prefix&#39;s address space and that is positioned in a level that matches the prefix length. Other portioning of IP addresses in additional to {8,8,8,8} are contemplated. 
   For example, prefix 0x0A0A/16 is stored in a level 1 node covering the address space 0x0A0A0000-0x0A0AFFFF. The root node (level 0 bucket) holds a pointer to the level 1 node. The convention 0x0A0A/16 means that the 16 MSbs from the address 0x0A0A . . . (hexadecimal format) are used. In order to maintain the tree structure, the next hop table of a node must hold pointers to lower level buckets or nodes in the tree data structure  50  (in addition to “real” next hop pointers). In other words, the next hop tables  44  contain two types of pointers: next hop pointers and next bucket pointers. 
   For larger address sizes such as 32-bit or larger, searches are performed by breaking the IP address into two or more address portions with blocks of bits. The optimal split is a function of the width of the memory bus, the number of accesses allowed and the length of the address space. For a 32-bit address and a 32-bit memory bus, four octets are preferred. Blocks are used from the most significant block to the least significant block to iteratively traverse the trie data structure  50  starting from the root level (level 0) and ending at level 3. A search in a node may produce a next hop pointer or a next bucket pointer. When a next hop pointer is encountered, the search is complete and the remaining IP address portion blocks are not used. When a next bucket pointer is encountered, the next IP block is used as a search index to the pointed bucket. The “next bucket” pointer creates a new address range in the address space that is covered by the selected bucket. The next bucket pointer increases the next hop table size by 1 or 2 entries. 
   Referring now to  FIG. 10 , an example address space and forwarding table includes the following prefixes: 0x0/0 (default route), 0x00/5 (0000-0* in binary format), 0x02/8 (0000-0010* in binary format), and 0x0402/15 (0000-0100-0000-001* in binary format). The prefix 0x0402/15 splits the address range covered by 0x0/5 in the root bucket. A search for 0x0401 . . . (only the 16 MSb are relevant in this example) is conducted in following steps. 
   The most significant IP address portion or block (0x04) is used as an index to the bit vector of the root bucket (level 0). The set bits are counted (4) and the 4th pointer  52  in the next hop table is selected. The pointer  52  is a “next bucket” pointer. Therefore, processing continues at a lower level bucket (level 1). The next address portion or octet (0x02), from the IP address, is used to index the bit vector of bucket  1 . The set bits, in the bit vector, from the LSb to the address 0x02 are counted. There is only one set bit. Therefore, the 1st pointer in the next hop table of the level 1 bucket is selected. Since the selected pointer is a next hop pointer, the search is done. 
   Referring now to  FIG. 11 , steps performed by the search engine are shown. Control begins with step  54 . In step  56 , control determines whether a packet is received. If not, control loops back to step  54 . Otherwise, control continues with step  58  where the address is obtained from the packet. In step  60 , a counter counts set bits in the bit vector based on first address portion, such as an octet for a 32-bit address. In step  62 , a pointer is selected from the next hop table based on the number of set bits. In step  64 , control determines whether the pointer is a next hop pointer. If true, control continues with step  66  where the packet is routed based on the next hop pointer. 
   If the pointer is a next bucket pointer, control continues with step  68  and selects a bit vector in the next level based on the next bucket pointer from the prior level. In step  70 , set bits are counted in the current bit vector based on a next address portion. For example, the second octet of a 32-bit address is used. In step  72 , the pointer from the next hop table is selected based on the number of set bits. In step  74 , control determines whether a next hop pointer is selected from the next hop table. If not, control loops back to step  68 . Otherwise, control continues with step  76  and routes the packet based on the next hop pointer. Control continues from step  76  to step  56 . 
   Referring now to  FIG. 12 , an enhanced bit vector data structure  80  is shown. The data structure is design to have one access to the bucket structure to retrieve one memory line (with a 32-bit size in this example). Currently available memories typically have a width between 8 and 64 bits. As a result, more than a single memory read cycle is required to read the bit vector if the bit vector has more bits than the width of the memory (for example, the bit vector discussed above has 256 bits). The additional memory read cycles that are required increase search time. A modification to the bit vector according to the present invention limits the number of memory cycles to read the bit vector to one, regardless of the width of the memory. This modification enables a search that is limited to two memory accesses per bucket. 
   Assuming that a 32-bit width memory is used, the 256 bit-length bit vector is split into 11 lines  82  having a 24-bit width (the last line has unused bits). An 8-bit counter is associated with each line (for a total of 32 bits). The counter  84  holds the number of set bits in the previous lines  82  of the enhanced bit vector  80 . 
   The address portion such as an octet is used to index the correct line in the enhanced bit vector  80 . The formula is line=octet div 24 (where the 1 st  line is indexed as the 0′th line). For example, address octets having values between 0-23 address a first line  82 - 1 . Address octets having values between 24-47 address the second line  82 - 2 . The number of set bits from the beginning of the line up to the address octet (inclusive) is counted. The formula is column=octet %  24  (where column  0  is the LS column in every line). The number of set bits is added to the value in the counter  84 . The total is used as an offset to the next hop table. 
   In order to provide an offset to the next hop table relative to the bucket&#39;s base address, rather than an offset relative to the base address of the next hop table, every counter (e.g. counter  84 ) is biased by 10-N, where N is the counter&#39;s line number (N=0, 1, . . . , 10). This formula assumes that the LSb of the bit vector is always set. 
   If the number of set bits in the bit vector is small, the size of the bit vector can be reduced. For a typical core Internet router, most of the buckets are small and therefore, a considerable amount of memory space can be saved by compressing the bit vector. Compressing the bit vector by replacing the bit vector with the indices of the set bits (8 bits per index for 256 bits length bit vector) provides a compression ratio of about 10% (relative to an uncompressed bit vector). 
   In a first exemplary compressed bit vector in  FIG. 13 , a single line indices list  100  is used to compress buckets with 2-5 next hop entries, which correspond to bit vectors having 2-5 set bits, respectively. The first set bit in a bit vector is always the LSb and therefore, its index is known. The indices of the other set bits are written to a 32-bit line, allocating an octet per index. If the number of the set bits is less than 5, a zero is written in the “empty” octets. 
   A search is conducted by counting the number of indices in the compressed bit vector satisfying IP address block&lt;=index, and excluding zero indices. In a second bit vector in  FIG. 14 , a double line indices list  110  is used for buckets with 6-10 next hop entries. By allocating an octet to an index of a set bit, up to 8 indices can be stored in two 32-bit lines. The index of the 1 st  set bit is always zero. The indices of set bits  2 - 5  are written to the 1 st  line. The 6th index is held in the parent level next bucket pointer. The indices of set bits  7 - 10  are written to the 2 nd  line. If the number of set bits is smaller than 10, a zero is written in the “empty” octets of the 2 nd  line. 
   A search is conducted by deciding whether the 1 st  or the 2 nd  line of the compressed bit vector should be read. This is done by comparing the IP address block to the 6 th  index (stored in the parent next bucket pointer). If IP address block &lt;6th index then the 1st line is read. Otherwise, the 2 nd  line is read. The offset to the next pointer table is obtained by counting the number of indices that are smaller or equal to the IP address block (excluding zero indices). If 2 nd  line has been read  5  should be added to the offset (because the offset should index the “higher” half of the next hop table). With the incorporation of compressed bit vectors, four types of pointers populate the next hop table: a pointer to a single line compressed bucket, a pointer to a double line compressed bucket, a pointer to a regular bucket and a next hop pointer. 
   In one implementation, the normal bit vector has a size of 256 bits and the compressed bit vectors are 32 or 64 bits. The 32-bit compressed bit vector is capable of indexing “next . . . ” tables of up to 5 entries. The 64-bit compressed bit vector is capable of indexing “next . . . ” tables of up to 10 entries and is used when the table size is 6-10 entries. 
   To implement a compressed bit vector, an ordinary 256-bit bit vector is constructed. The number of ‘1’s in the bit vector are counted. If number of ‘1’s is less that 6, a 32-bit compressed bit vector is constructed. If the number of ‘1’s is less than 11, a 64 bit compressed bit vector is constructed Otherwise a normal (uncompressed) bit vector is constructed. 
   Constructing and searching a 32-bit compressed bit vector is performed as follows. The 32 bits are divided into 4 octets and are optionally named Octet  1 , Octet 2 , . . . , and Octet 4 . For each octet, the indices of the ‘1’s in the corresponding bit vector are written. The zero bit in the bit vector is preferably set by default and need not be written into the octet. If the number of set bits in the normal bit vector is smaller than 5, the empty octets are filled with zeroes. The zero index is invalid because this index is set by definition. Therefore, zero can be used as a filler symbol. 
   For example, assume that the indices of the set bits are: 0, 2, and 5 (0 is mandatory). In this example, the address space of the bucket is divided into 3 intervals: {[0,1]; [2,4]; and [5,255]}. A 32-bit compressed bit vector is used and is filled as follows: Octet 1 =2, Octet 2 =5, Octet  3  and  4 =0 (fillers). 
   A search for IP address octet=123 is conducted as follows. The “next bucket” pointer that points to this pointer indicates that the pointed bucket is a 32-bit compressed bit vector. The bit vector is read.
         Set i=0.   For every octet in the bit vector (exclude octets equal to zero) {i+=(OCTET[j]&lt;=123)?1:0}.   Pick the i th  entry in the next hop pointers table.       

   Constructing and searching a 64-bit compressed bit vector is performed as follows. The 64 bits are divided into 8 octets and are optionally named Octet  1 , Octet 2 , . . . , Octet 4 , Octet 6 , . . . , Octet 9 . Note that Octet 5  is omitted. The indices of the ‘1’s are written in the bit vector. The indices of the 1st and the 6′th ‘1’s are skipped. Note that index  0  (i.e. the 1st ‘1’) in the bit vector is always set and, therefore, need not be written into an octet. The index of the 6′th ‘1’ is written to the “next bucket” pointer that points to this bucket. If the number of set bits in the normal bit vector is smaller than 10, the empty octets are filled with zeroes. 
   For example, assume that the indices of the set bits are: 0, 2, 5, 10, 11, 12, and 20. In other words, the address space of the bucket is divided into 7 intervals: {[0,1]; [2,4]; [5,9]; [10,10]; [11,11]; [12,19]; and [20,255]}. A 32-bit compressed bit vector is filled as follows: Octet 1 =2, Octet 2 =5, Octet 3 =10, Octet 4 =11, Octet 6 =20, Octet 7 =0, Octet 8 =0, and Octet 9 =0. 
   The bucket&#39;s parent pointer carries Octet 5 =12. A search with IP address octet=15 is conducted as follows. The “next bucket” pointer that points to this pointer indicates that the pointed bucket is a 64-bit compressed bit vector. Note that Octet 5  is contained as a field in the next bucket pointer data structure. If Octet 5  is less than 15, the 1st 32 bits of the bit vector (Octets[1:4]) are read. The offset into the “next hop” pointer table is calculated as if the bit vector is a 32-bit compressed bit vector. Otherwise, the 2nd 32 bits of the bit vector (Octets[6:9]) are read. The offset into the “next hop” pointers table is calculated as if the bit vector is a 32-bit compressed bit vector+5. 
   Those skilled in the art can now appreciate from the foregoing description that the broad teachings of the present invention can be implemented in a variety of forms. Therefore, while this invention has been described in connection with particular examples thereof, the true scope of the invention should not be so limited since other modifications will become apparent to the skilled practitioner upon a study of the drawings, the specification and the following claims.