Longest prefix matching (LPM) using a fixed comparison hash table

Described are an apparatus and method of forwarding Internet Protocol (IP) packets. At least one fixed-length key having a predetermined number of bits is produced in response to an IP address in an IP packet. At least a portion of the fixed-length key is hashed to obtain a hash value. The fixed-length key is compared with a key value stored in each data-item in a hash bucket associated with the hash value to find the data item that has the key value that matches the fixed-sized key and to obtain from that data item routing information that is used to forward the IP packet.

FIELD OF THE INVENTION

The invention relates generally to computer networks. More particularly, the invention relates to a system and method of forwarding packets in a computer network.

BACKGROUND

Internet Protocol (IP) address lookup is a bottleneck in the performance of routers and switches operating on the Internet. Expectations are for the bottleneck to worsen with increasingly larger routing tables, faster communication links, heavier packet traffic, and the migration from 32-bit Internet Protocol Version 4 (IPv4) addresses to 128-bit Internet Protocol Version 6 (IPv6) addresses. Consequently, it is becoming increasingly important for routers and switches to employ IP packet forwarding that can meet these increasing demands.

FIG. 1illustrates a network including a router20. The router20receives IP packets22from a node (NODE A) in the network. Each received IP packet22has a header24and data28. The header24includes a destination address field26, which has an IP address of a node (or host) to which the IP packet22is targeted. With this IP address, the router20accesses a forwarding table32to determine to which node to forward the IP packet20. In general, the selected node is that which advances the IP packet22towards its destination.

A technique for implementing a forwarding table is to use a longest prefix matching (LPM) algorithm. A basic principle of IP addressing is that routers and switches can use the prefixes of an IP address to make routing decisions. A familiar dot-notation for a 32-bit IP address includes four decimal values separated by periods (e.g., 208.128.16.10). Each decimal value is represented by 8 bits (a byte). The leftmost 16 bits of the IP address can, for example, identify a corporation, the leftmost 20 bits of the IP address an office in that corporation, the leftmost 24 bits a particular network (e.g., Ethernet) in that office, and all 32 bits a particular host device on that network.

When performing the LPM algorithm, the router20compares the destination address26to entries in the forwarding table32to find the entry with the longest matching prefix. That entry indicates the location (or node) towards which to send the IP packet22. For example, consider that the router20receives an IP packet22with a destination address of 208.128.16.10 and upon searching the forwarding table32finds two entries with matching prefixes, the first entry being 208.128 and the second entry being 208.128.16. The router20then selects the second entry (208.128.16) because it is longer than the first entry.

One way to implement the LPM algorithm is to use a prefix tree (i.e., a binary tree) having a root node, intermediate nodes, and leaf nodes. The leaf nodes represent prefix entries in the forwarding table32. The prefix tree is built only to the extent needed to represent all of the entries in the forwarding table32. The router20searches for the longest prefix in the prefix tree that matches part of or the entire destination IP address26by traversing the prefix tree from root node to a leaf node, possibly passing through one or more intermediate nodes. Each node traversed adds a bit to the matching prefix. From a leaf node the router20obtains the forwarding location. A disadvantage of using a direct implementation of the prefix tree is that the process can require a traversal of as many nodes as there are bits in the IP address to obtain the forwarding location. Thus there is a need for improving implementations that use the longest prefix matching algorithm for forwarding IP packets.

SUMMARY

In one aspect the invention features a method of forwarding Internet Protocol (IP) packets. At least one fixed-length key having a predetermined number of bits is produced in response to an IP address in an IP packet. At least a portion of the fixed-length key is hashed to obtain a hash value. The fixed-length key is compared with a key value stored in each data item in a hash bucket associated with the hash value in order to find the data item that has the key value that matches the fixed-sized key and to obtain from that data item routing information that is used to forward the IP packet.

In another aspect the invention features an apparatus for forwarding IP packets: A key generator produces a fixed-length key having a predetermined number of bits in response to an IP address. A hash value generator hashes a portion of the key to produce a hash value. A comparator compares the fixed-length key with a key value stored in each data item in a hash bucket associated with the hash value in order to find the data item that has the key value that matches the fixed-sized key and to obtain from that data item routing information that is used to forward the IP packet.

DETAILED DESCRIPTION

The present invention features a length table, a hash table, and fixed-length keys to improve implementations of the longest prefix matching algorithm used by network devices, such as routers and switches, to forward IP (Internet Protocol) packets through a network such as the Internet. In brief overview, a network device practicing the invention produces a plurality of fixed-length keys based on a prefix tree and stores these keys, with corresponding routing information, in a hash table. When an IP packet later arrives at the network device, the network device uses some or all of the destination IP address bits to produce one or more keys that are used to search the hash table for a matching key. If there is more than one key, the network device uses first the key that is constructed from the most destination IP address bits, and ceases from searching the hash table upon finding a match, thus the network device is using the longest prefix matching. Finding the matching key results in the retrieval of routing information.

More specifically,FIG. 2shows a general format for a destination IP address50(e.g., 32 bits), a length table54, fixed-length keys70,74, and78, and a hash table100constructed in accordance with the principles of the invention. When an IP packet arrives at a network device, a predetermined number (“N”) of the most significant bits of the IP address50are used as an index into the length table54. The network device uses the length table54to determine the number of keys and the number of bits of the IP address50used to construct those keys, which are later used to find routing information. In one embodiment, the size of the index is 20 bits in length. The principles of the invention also apply to other versions of IP addresses (e.g., IPv6, which are 128 bits in length) and to other indices of longer or shorter lengths.

The length table54has a plurality of entries58, each entry58including an index field62and a length indicator field66. The index field62stores a value (e.g. INDEX1) that is used to retrieve the length indicator value of that particular entry58. The value of the length indicator indicates one or more prefix lengths for IP addresses that have the N bits that match the index. In one embodiment, each bit that is set (i.e., equal to “1”) in the length indicator value represents a prefix length to be used to construct a key. For example, the value in the length indicator field66that is retrieved using the index INDEX1is “00010010b.” The set bits represent prefix lengths of 1 bit and 4 bits (counting from the right to left and starting from 0). In general, values stored in the length indicator field66can represent prefix lengths up to as many bits as there are in the IP address (e.g., 32 for an IPv4 address, 128 for an IPv6 address).

In another embodiment, each entry has a plurality of length indicator fields, each such field storing a value that represents one prefix length.

As described above, each fixed-length key constructed in accordance with the invention has one of the general formats70,74,78. Each key70,74,78includes a variable-length prefix-bit field82and a fixed-length length-bit field86. The length of the prefix field82can range from 1 bit to a predetermined maximum number of bits. The keys have a “fixed length” in that each key has the same predetermined number of bits.

To ensure that each key has this same number of bits, some keys (i.e., those that do not fully use the maximum number of prefix bits) have a fill-bit field90. The variable length of the prefix field82and the variable length of the fill-bit field90combine to achieve predetermined length (e.g., 32 bits). Key formats70and74illustrate keys that have prefix fields82with less than the maximum number of bits. Each format uses fill bits to reach the maximum number, key format70using more fill bits than key format74. Key format78illustrates those keys that have the maximum number of prefix bits, and thus have no fill bits.

Keys are constructed: 1) when constructing the hash table100; and 2) when routing information for an arriving IP packet needs to be retrieved from the hash table100. When constructing the hash table100, keys are constructed from each prefix in a prefix tree. For each prefix, if the number of prefix bits for that prefix is less than the maximum number (described above), a number of fill bits are inserted to reach the maximum number. These fill bits can have any predetermined value. In one embodiment, each fill bit has a binary value of 1. Other predetermined patterns are usable, provided the same pattern is used to construct each candidate key. The combination of prefix bits and fill bits, if any, is referred to as the IP address portion of the key. Appended to the IP address portion of the key are the length bits which indicate the number of prefix bits in the key. The keys are stored in the hash table100, as described below.

When seeking to obtain routing information for an arriving IP packet from the hash table100, a candidate key is constructed for each prefix length obtained from the length table54. The uppermost (i.e., most significant) N bits of the IP address50operate as an index that identifies an entry58of the length table54. The entry58lists one or more prefix lengths. A candidate fixed-length key is constructed for each prefix length, each prefix length obtained from the length table54determining the number of prefix bits to use from the destination IP address (from MSB to LSB). The value of the length bits and number of fill bits are as described above for when constructing keys for the hash table100. These fixed-length keys are referred to candidate keys because such keys do not necessarily result in the retrieval of routing information from the hash table100, for instance, when the length table54indicates that there are multiple prefix lengths, only one of the keys constructed from those prefix lengths operates to retrieve routing information.

Having a fixed-length key is advantageous because it leads to a uniform implementation of a hash table100and of hardware and software. Additionally, the use of the fill bits provides that for a given set of prefix bits of the IP address and corresponding length bits, that there is only one candidate fixed-length key.

The hash table100includes a plurality of entries104, each having a hash value108and a hash bucket112. Each hash bucket112is a linked list (e.g., singly or doubly linked) of data items. Each data item includes a key value and associated routing information. Each fixed-length key is hashed to produce an index to the hash table100. In general, any hashing algorithm can be used, preferably one that can equally distribute items within the hash buckets112of the hash table100. In one embodiment, the hash algorithm produces hash values by exclusive-ORing the odd and even bits of the key.

When an IP packet with a destination IP address50arrives at the network device, the network device obtains a prefix length or lengths from the length table54based on the destination IP address50and constructs a candidate fixed-length key or keys (as described above) for each prefix length. Using first the candidate key with the most prefix bits (e.g., as indicated by the length bits), the network device produces a hash value108for that candidate key, uses the hash value108as an index into the hash table to select a hash bucket112to search, and compares the candidate key with the key value in each of the data items116in that hash bucket. If the candidate key matches one of the key values of a data item in the hash bucket, the routing information associated with the matching key value is used for forwarding the IP packet. The searching process does not need to continue with the other candidate keys, if any, because of the match.

If the candidate key does not match the key value of any data item116in that hash bucket, the network device selects the next candidate key (with the next highest number of prefix bits). If no key values are ultimately found to match any of the candidate keys, the network device can use a default route.

FIG. 3AandFIG. 3Bprovide an example to illustrate the present invention.FIG. 3Ashows a simplified example of a prefix tree200constructed for four-bit IP addresses having a root node204, a plurality of intermediate nodes208(not circled), and leaf nodes212(circled and underlined). Each leaf node212represents a prefix. Each intermediate node208of the prefix tree contributes a bit to a prefix used to produce fixed-length keys for the hash table270(FIG. 3B). In this example, some prefixes are two bits in length, others three bits, and others four bits. The prefix tree200is built only to the extent needed to represent all of the prefixes available or known to the network device. Prefixes can be added or removed from the prefix tree as the network topology to which the network device is connected changes.

The prefix tree200ofFIG. 3Aprovides the information used to construct the length table220shown inFIG. 3B. For this example, consider that the index to the length table220is 2 bits in length, giving four entries224to the length table220. FromFIG. 3Ait can be seen that the index “01,” for example, has three possible prefixes: “0111,” “0110,” and “010.” These prefixes have lengths of 4 bits, 4 bits, and 3 bits, respectively. The entry224for index “01” thus has length indicators of 3 bits and 4 bits. As another example, the index “10” has one possible prefix: “10”, which has a length of 2 bits.

FIG. 3Balso shows a list240of the candidate keys244derived from the length table220. Each key244includes prefix bits248, fill bits (here “1”s)252, if any, and a predetermined number of length bits256. There is one key244for each prefix (leaf node) in the prefix tree200ofFIG. 3A. For the prefix “11,” for example, the key244has two prefix bits “11,” two fill bits “11,” and length bits “01” (indicating 2 bits). Note that in some cases the key244does not have fill bits because the prefix is four bits in length. Prefix “0111” in the prefix tree200ofFIG. 3Ais such an example. The key244for prefix “0111” has four prefix bits “1111,” zero fill bits, and length bits “11” (indicating 4 bits).

From each of the keys244, a hash value260is produced. The hash value algorithm used in this example is an exclusive-OR of the odd and even bits of the key244. This example produces four different hash values260. Each hash value260represents a hash bucket274of a hash table270. The hash buckets274are implemented as a linked list memory structure. Each hash bucket274has one or more data items278. Each data item278includes a key value and routing information associated with that key value. Each key value corresponds to one of the keys240produced from the prefix tree200(FIG. 3A).

FIG. 3Balso shows an example, in tabular form, of process for obtaining routing information for forwarding an IP packet having an exemplary destination IP address of “0110” using the length table220and hash table270. Using the first two bits of the IP address (i.e., “01”) as an index to the length table220, the identified entry224indicates that the possible prefix lengths are 3 and 4. This means that two candidate keys can be constructed. The first candidate key has 3 prefix bits, “011,” one fill bit “1,” and length bits (“10”) that indicate that the prefix bit length is 3. The second candidate key has 4 prefix bits, which in this example is the full destination IP address, and so no fills bits are used. Length bits (“11”) indicate that the prefix bit length is 4 bits.

Using the hash algorithm described above, the first and second candidate keys hash to a hash value 00. Accordingly, each candidate key is compared against the key values of each data item278in the hash bucket274identified by the hash value260. For the first candidate key, “011110,” no data item278has a key value that matches. For the second candidate key, “011011,” a match is found. In this instance, the matching data item278has data indicating that the routing information identifies “location B.” Thus, for this example, network device forwards the IP packet associated with the example destination IP address to location B (e.g., an output port, a network node). In one embodiment, the network device searches for a match for the second candidate key before the first candidate key because the second candidate key has a greater number of prefix bits. Consequently, after detecting a match, the network device does not need to continue because the longest prefix has been matched and thus does not waste processor instruction cycles searching for a match for keys with fewer prefix bits, such as the first candidate key. Also, in accordance with the present invention, at most one match exists for each candidate key, an advantage being that the comparisons in a hash bucket can cease when the match is found.

In the simplified example ofFIG. 3AandFIG. 3B, the IP address is 4 bits in length. An advantage of the present invention over prefix-tree searching becomes more apparent for IP addresses with a greater number of bits (e.g., 32 bits). The use of the hash table270with a large number of hash buckets274(e.g., 64 K) over which the data items278are distributed, has fewer comparisons (between the candidate key and data item key values) than searching along a prefix tree. The fewer comparisons effectively quicken forward matching algorithms.

FIG. 4shows an embodiment of a forwarding table280of the present invention that can be used by a network device (e.g., a router) to forward IP packets toward their destinations. The forwarding table280can be implemented in hardware, software, or a combination of hardware and software. The forwarding table280includes a length table282, a key generator284, a hash value generator286, and a hash table288. The forwarding table280is in communication with a buffer290for receiving a destination IP address taken from an IP packet that has arrived at the network device. A switch292is in communication with the buffer290to receive the IP packet and with the forwarding table280to receive routing information. The routing information indicates to the switch292a direction in which to forward the IP packet over the network.

The length table282includes the lengths of potentially matching IP address prefixes and is indexed by the first (i.e., most significant) N bits of the destination IP address. Preferably, the number of entries in the length table282is a power of two. For example, the uppermost byte of the IP address (i.e., N=8) can operate as an index to a length table282with 256 entries. Each index maps to a length table entry and each bit that is set in the length indicator field of that length table entry corresponds to a potentially matching IP address prefix having that many matching most significant bits.

An address with fewer bits than one byte can map to multiple entries of the 256-entry table (provided the length table282has multiple entries with bits that match the corresponding bits of the IP address). Table 1 below provides an example of the 256-entry length table282described above.

TABLE 1INDEX VALUELENGTH(ENTRY NO.)INDICATOROPERATION00x00010000 (HEX)When the first byte of the IPaddress is 0000 0000, then theprefix length is 16 bits (the“1” in the length indicator is inthe 17thbit position, indicatinga length of 16 bits).10x00100000 (HEX)When the first byte of the IPaddress is 0000 0001, then theprefix length is 20 bits (the“1” in the length indicator is inthe 21stbit position, indicatinga length of 20 bits).20x00000080 (HEX)When the first byte of the IPaddress is 0000 0010, then theprefix length is 7 bits.30x00000080 (HEX)When the first byte of the IPaddress is 0000 0011, then theprefix length is 7 bits.2540x01000000 (HEX)When the first byte of the IPaddress is 1111 1110, then theprefix length is 24 bits.2550x00010000 (HEX)When the first byte of the IPaddress is 1111 1111, then theprefix length is 16 bits.

As shown in TABLE 1, multiple entries of this embodiment of the length table282indicate a 7 bit prefix length. If, for example, the route for any IP address prefix of length 7 is equal to “0000 001,” which is shorter than the predetermined index length of one byte, these bits match index entry no. 2 and index entry no. 3 (and map to the same hash table entry). Accordingly when the route length is less than the log2of the number of length table entries, a a length is inserted for each length table index that matches (i.e., here matching indices have the most significant bits, where M is the number of bits in the route length).

FIG. 5shows an embodiment of a process300of constructing the hash table288ofFIG. 4and of obtaining the routing information for a destination IP address in accordance with the principles of the invention. Referring also toFIG. 4, the length table282(step304) is constructed based on a prefix tree and a predetermined index size. For each possible index having the predetermined index size, one or more prefix lengths are determined from the prefix tree. The length table282includes each prefix length determined for that index.

In step308, the key generator284constructs a key value for each prefix in the prefix tree. The keys are constructed using the prefix bits, fill bits, if any, and prefix length bits. The hash value generator286hashes (step312) each key to produce a hash value for that key. Each key is then stored in the hash table288. More specifically, the hash value for each key identifies a hash bucket in the hash table288in which that key is stored as a key value. Also stored in the data item with the key value is associated routing information. Performance of steps304,308, and312to construct the length table282and hash table288can occur as a background operation, and in some embodiments, periodically (e.g., every five minutes) to update the tables282and288.

Pseudo-code for adding entries to the length and hash tables282,288is as follows: Given “IP_Addr”=the IP address, ‘>>’ is a logical right shift, and PLT[ ] represents the length table282having PLT_SIZE entries:

Pseudo-code for deleting entries from the length and hash tables282,288is as follows:Given “IP_Addr”=the IP address, ‘>>’ is a logical right shift, and PLT[ ] represents the length table282having PLT_SIZE entries:// delete entry from hash tableKey.IP_addr=IP_Addr|( )×ffffffff>>prefix_length)Key.prefix=prefix_lengthDel_Table_Entry(Key)

Removing prefix lengths from the length table282is less straightforward than removing entries from the hash table288. Each length bit in the length table282may correspond to more than one prefix in the prefix tree. Thus, in one embodiment, the network device maintains a reference count for each prefix length so that a prefix length is not removed from the length table282prematurely. In another embodiment, prefix lengths are not removed from the length table. Although this embodiment does not cause any functional failures, keeping obsolete prefix lengths can decrease performance by causing hash table lookups for a non-existing prefix.

Use of the length table282and hash table288occurs upon receiving an IP packet. In step316, a predetermined number of most significant bits of the destination IP address in the IP packet are compared with the indices of the length table282to obtain the list of possible prefix lengths. The key generator284constructs (step320) a candidate key for a possible prefix length obtained from the length table282, in one embodiment starting with the longest possible prefix length to the shortest length if the list includes more than one. The candidate key may have one or more fill bits.

In step324, the hash value generator286hashes the candidate key to produce a hash value. The hash value is used to access (step328) the hash bucket288in which to search for a data item that has a key value that matches the candidate key. The comparator/hash table288compares the candidate key with the key value of each data item in the appropriate hash bucket288. Each comparison of a key value occurs as a single step that does not require masking.

When a data item with a matching key value is found (step330), the routing information in the matching data item is used (step332) to forward the IP packet.

If the comparator/hash table288does not find a match for the candidate key (step330), and if there is another prefix length in the list retrieved from the length table282(step336and step340), the process300continues at step320with the next prefix length. If there is no other prefix length (step336), the network device uses a default route (step344) to route the IP packet.

Pseudo-code for performing the process300is as follows:Given “IP_Addr”=the IP address, ‘>>’ is a logical right shift, and PLT[ ] represents the length table282having PLT_SIZE entries: