1. Field of the Invention
The invention relates generally to the field of computer networking devices. More particularly, the invention relates to a method and apparatus for efficiently decimating a mask and identifying a longest matching prefix of a given address in a forwarding database, a routing table, or the like.
2. Description of the Related Art
A network device's performance is based on how quickly it can forward a packet. Before a network device, such as a bridge, a router, or a Layer 2 or Layer 3 switch, can forward a packet, it must locate the most appropriate entry in its forwarding database corresponding to the destination address specified in the packet. As a result, address matching is a critical part of making a high-performance network device. In Transmission Control Protocol/Internet Protocol (TCP/IP), there might be several forwarding database entries that match a particular destination address. To assure proper delivery of the packet to its intended destination, network devices must use the most "specific" matching forwarding database entry. An IP address comprises a portion identifying a network prefix and a portion identifying a host number. An IP address with a longer network prefix describes a smaller set of destinations and is said to be more specific than an IP address with a shorter network prefix. Therefore, when forwarding traffic, a network device must choose the entry with the longest matching network prefix. The length of an entry's network prefix may be identified by a length attribute or by a mask, e.g., a contiguous mask of 1 bits followed by 0 bits, associated with the entry.
Due to its importance to network device performance, much time has been devoted to developing longest match searching algorithms. Referring now to FIG. 1, a prior approach for performing a longest match search using a patricia tree is described. In this example, the addresses in the forwarding database are represented in a binary tree data structure 100 (commonly referred to as a patricia tree in the context of searching for IP addresses). Each vertex represents a binary string comprising 1s and 0s. The root 105 is the null string. Two pointers originate at each vertex. The first pointer consists of the current binary string plus a 0 and the second pointer consists of the current binary string plus a 1. If no address in the forwarding database contains a particular vertex's binary string plus an additional binary digit, then that pointer is either null or points to a vertex indicating failure. Each vertex additionally has a flag associated with it that indicates whether the binary string, if terminated at that vertex, corresponds to a network prefix in the forwarding database. In FIG. 1, this flag is indicated with an asterisk. The data structure 100 of FIG. 1 represents a forwarding database consisting of the following addresses:
00001011.00000001.00000010.00000000 (11.1.2.0/24) PA0 00001011.00000001.00000000.00000000 (11.1.0.0/16) PA0 00001011.00000000.00000000.00000000 (11.0.0.0/8) PA0 10101101.00000000.00000000.00000000 (173.0.0.0/8) PA0 10101111.00000000.00000000.00000000 (175.0.0.0/8) PA0 11110111.00000000.00000000.00000000 (247.0.0.0/8)
To search for the destination address 00001011.00000001.00000010.01000001 (11.1.2.65), the "0" pointer is followed from the root 105 and three additional times to arrive at vertex 110. At vertex 110, the "1" pointer is followed, then the "0" pointer of the subsequent vertex, and the "1" pointer is followed twice to arrive at vertex 115. Upon reaching vertex 115, it is noted that 00001011 is a valid network prefix in the forwarding database that matches the destination address. At this point, vertex 115 represents the longest match. However, the goal now becomes finding a longer match. The search continues, therefore, until a leaf vertex is reached or a failure occurs, e.g., attempting to follow a null pointer or reaching a vertex that indicates failure. Continuing with the present example, from vertex 115, the "0" pointer is followed seven times and subsequently the "1" pointer is followed to arrive at vertex 120, which is marked as being a network prefix in the forwarding database. Therefore, upon reaching vertex 120, it is noted that 00001011 00000001 is the longest match found thus far. From vertex 120, the "0" pointer is followed six times and subsequently the "1" pointer and the "0" pointer are followed to arrive at vertex 125. Next, the "0" pointer is followed, but 00001011 000000010 is not a valid network prefix in the forwarding database, thereby bringing an end to the search. Therefore, 00001011 00000001 is recognized as the longest match corresponding to the destination address (11.1.2.65).
A disadvantage of the longest match search described above and other software approaches, such as a binary search, is that the algorithm depends on knowing the result of the last memory access before it can issue the next memory access. For example, to traverse the patricia tree 100 of FIG. 1, data associated with the root vertex 105 must first be retrieved from memory before an address can be issued for purposes of fetching the next vertex. Similarly, each succeeding memory access is dependent on the last retrieved vertex. These approaches, while efficient in terms of the number of memory accesses required, make inefficient use of the idle time between memory accesses.
In light of the foregoing, what is needed is a more intelligent mechanism for performing a longest match search. In particular, it is desirable to decouple the next memory access from the results of the prior memory access. Additionally, rather than worrying about minimizing memory accesses, emphasis should be put on taking useful action during the memory accesses.
USPTO Backgrounds
USPTO Backgrounds