A current bottleneck in the performance of routers and switches operating on the Internet is Internet Protocol (IP) address lookup. The bottleneck is likely 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. 1 shows an example of a communications network 10 having a router 20. The router 20 receives IP packets 22 from a node 12 (Node A) in the network 10. Each received IP packet 22 has a header 24, including a destination address field 26, and data 28. The destination address field 26 has an IP address of a node (or host) to which the IP packet 22 is targeted. With this IP address, the router 20 accesses a routing (or forwarding) table 32 to determine to which node (e.g., Node B, C, or D) to forward the IP packet 22. In general, the router 20 selects the node that advances the IP packet 22 towards its targeted destination.
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 eight 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.
One technique for using a routing table is longest prefix matching (LPM). When performing LPM, the router 20 compares the destination address 26 to entries in the forwarding table 32 to find the entry with the longest matching prefix. That entry indicates the location (or node) towards which to send the IP packet 22. For example, consider that the router 20 receives an IP packet 22 with a destination address 26 of 208.128.16.10 and upon searching the routing table 32 finds two entries with matching prefixes, the first entry being 208.128 and the second entry being 208.128.16. The router 20 then selects the second entry (208.128.16) because it is longer and more specific 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 table 32. The prefix tree is built only to the extent needed to represent all of the entries in the forwarding table 32. The router 20 searches for the longest prefix in the prefix tree that matches part of or the entire destination IP address 26 by traversing the prefix tree from root node to a leaf node, possibly passing through one or more intermediate nodes. Each traversed node adds a bit to the matching prefix. From a leaf node the router 20 obtains 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. Consequently, searching for the longest prefix match and updating the prefix tree can be slow.
Another implementation of a routing table uses a hash table of indexes and linked lists of entries. The entries of each linked list provide a range of prefix data, and each index points to a linked list. A general disadvantage with this implementation is that tuning the routing table to perform fast prefix searching slows the performance of table updates, and tuning the routing table to perform fast table updates slows the performance of prefix searching. Thus there is a need for a longest prefix matching implementation that can perform fast prefix searching and fast table updates without the performance tradeoff described above.
USPTO Backgrounds
USPTO Backgrounds