So far, all our algorithms have been trie variants and the main difficulty in finding the longest matching prefix is because of the prefix length and value. The need for developing a new speedy algorithms that uses less memory space must take into consideration values or lengths of the prefixes to find the longest matching prefix.
The search by length can be either linear or binary. So far, the prefixes were arranged in a trie. Searching the trie can be considered as a sequential search on the length dimension. As we have seen earlier, in the unibit trie first it searches prefixes of length 1, then on prefixes of length 2, and so on. Moreover, the prefixes are arranged in such a way the search space is reduced as the trie is descended because of branching. Another possible way for organizing the prefixes is to use a hash table for each unique length and use either a linear search or binary search on these tables to locate the best matching prefix. To simplify the discussion, let L represent a sorted array in order of 0-bit prefixes followed by 1-bit prefixes followed by 2-bit prefixes and so on. Each entry contains the length of the prefixes it represents and a pointer to the hash table that contains the actual prefixes. In the next few sections, we describe the linear and the binary search on L.
Linear Search on Prefix Lengths
It is a common sense to start the search with the longest prefixes as we need to find the longest match prefix. If the destination address is D and the greatest-length hash table is l, the search would extract the first l bits from the destination address D into Dl and then search the length-l hash table for Dl . If an entry matches, then the search stops since it is the best matching prefix has been found. If not, the process is repeated in a decreasing order among the set of possible prefix lengths until it either finds a match or runs out of lengths. In the worst case scenario, this algorithm needs to do a linear search among all distinct prefix lengths. Therefore, it requires O(W) time, where W is the address length in bits. Assuming perfect hashing, then an IPv4 lookup will need at most 32 memory accesses while an IPv6 lookup will need at most 128 memory accesses. If the hash function is not perfect that means collisions could happen, which usually is the case in reality, each hash probe for the matching prefix might require more than a single memory access. In such cases, an IPv4 lookup could cost more than 32 memory accesses.
Binary Search on Prefix Lengths
A better search approach is to use a binary search on prefix lengths to find the longest matching using log2W and avoid the worst case scenario in the approach described above. The binary search must start at the median prefix length and each hash must divide the prefix lengths in each step by half. At every step, the hash table associated with that length is searched. Based on the results of searching the hash table, the choice of the half on which to continue the search is determined. The result of the hash search can only be either found or not found. If a match is found at length m, then lengths strictly greater than m must be searched for a longer match. If no match was found at length m, then the search must continue on the half in which the length of prefixes are strictly less than m.
For example. Consider the set of prefixes P1 = 1∗, P2 = 00∗, and P3 = 111∗ shown in Figure 1.
Fig. 1: “Binary Search on Prefix Lengths Example”
Suppose search begins at median length-2 hash table for a destination address that begins with 111, the search starts with the hash table of length 2. As can be seen, the hash will not match and the search will continue to length 1. However, there is a longer matching prefix P3 in the length 3 table. To direct the search toward the right half, an “artificial match,” or marker needs to be introduced if there is a potential longer match. Hence, the marker 11∗ is added to the length 2 table as shown in Figure 1.b. . Now revisiting the search for the address starting with 111, the marker in the length 2 table will indicate a match and the search will move to the length 3 table and find the correct prefix P3. While markers direct the search toward tables greater than the median length for specific matches, they also ensure that the probe failures in the median to rule out all the lengths greater than the median.
For any prefix P, the marker needs to be placed at all lengths where the binary search makes a decision about the half on which to continue the search. Since at most log2W length tables will be traversed on any search. For a prefix of length 32, markers are needed only at lengths 16, 24, 28, and 30.
The algorithm described so far is still not correct. This is because sometimes the markers can cause the search to follow false leads that may fail. Consider consider a search for an address D’ whose first three bits are 110. The search starts at the length 2 table, which contains the prefix P2 and the marker 11*. Since the marker matches the address, this forces the algorithm to search in the third hash table for 110 and to fail. But the correct best matching prefix is at the first hash table, prefix P1. In this case, the marker 11∗ that was needed to find P3 misleads the search. Hence, the search has to backtrack and search the left half, resulting in a linear time.
To ensure logarithmic time, each marker node M contains a value is augmented to contain its best matching prefix, denoted by bmp(M). This is precomputed when M is inserted into its hash table. When the algorithm follows marker M and searches for prefixes of lengths greater than M, and if the algorithm fails to find such a long prefix, then the answer is M.BMP. For the previous example, a BMP field as 1* has been added to the 11*, which is nothing but P1. When the algorithm searches for 110, and finds a match in the median length-2 table, it remembers the value of the corresponding BMP entry P1 before it searches the length-3 table. Once the search fails in the length-3 table, the algorithm returns the BMP field of the last marker encountered. The final set of prefix length tables is shown in Figure 1c.
“The binary search requires five hash table lookups ( log232) in the worst case for IPv4 . This assumes that the expected case observation of probes in a hash table for a given prefix consume only O(1). However, in practice, it is expected to take only two memory accesses since the majority of the prefixes are either 16 or 24 bits (at least today). For IPv6 addresses that are 128 bits long, seven hash lookups will be required. The use of markers makes the update more complex. The complexity arises from precomputing the best matching prefix for each marker, which itself is a function of the prefixes of the marker. The addition or deletion of a prefix may change the best matching prefix for many of the markers that are longer than the prefix entry being added or deleted. Since the added or deleted prefix can potentially be a prefix of N − 1 longer entries, each of their log2W markers needs to be updated and hence the complexity is O(Nlog2W). The memory consumption is O(Nlog2W) as each prefix might need log2W markers.” (Morgan, 2007)
A trivial algorithm for building the simple binary search data structure from scratch is as follows. The algorithm takes as input a set of prefixes of different lengths and first determines the distinct prefix lengths to search. Then add each prefix P into the corresponding hash table of length length(P) . For each prefix P added, appropriate markers are also added into the hash tables of length L < length(P) that the binary search will visit. Using a separate 1-bit trie, the best matching prefix for each marker M is determined and stored along with it.
Search by Value Approach
Binary Search on Ranges
To find the longest matching prefix using a search on values requires the elimination of the length dimension. Since prefixes can be arbitrary lengths, one possible approach is to expand them such that all of them have a unique length. The addresses can be as long as 32 bits in the case of IPv4 and hence all the prefixes can be transformed into 32-bit length addresses. After transformation, the addresses are stored in a table in sorted order and a binary search on this table will find the longest prefix match. While this approach is simplistic, it requires a huge amount of memory as the number of entries in the table can be as much as 232. Fortunately, it is not necessary to store every address of a prefix since a great deal of information is redundant. Let us see how.
Consider a tiny forwarding table with only three prefixes, P1 = 0* , P2 = 00001*, and P3 = 001*. The starting point for this scheme is to consider a prefix as a range of addresses. To keep things simple, imagine that addresses are 5 bits instead of 32 bits. Thus P1 = 0* is the range of 00000 to 01111, the prefix P2 = 00001* represents the range 00001 to 00001, and P3 = 001* is the range of 00100 to 00111. Next, after adding in the range for the entire address space (00000 to 11111), the endpoints of all ranges are sorted into a binary search table ash shown in Table 1.
Table 1: “Prefix Range Search Table”
The range endpoints are written on the left column. The table also shows ranges covered by each of the prefixes. Next, two next-hop entries are associated with each endpoint. The leftmost entry, called the > entry, is the next hop corresponding to addresses that are strictly greater than the endpoint but strictly less than the next range endpoint in sorted order. The right most entry, called the = entry, corresponding to addresses that are exactly equal to the endpoint.
For example, it should be clear from ranges covered by the prefixes that any addresses greater than or equal to 00000 but strictly less than 00001 must match prefix P1 = 0*. The first subtle case, which illustrates the need for two separate entries for > and =, is the entry for 00001. If an address is strictly greater than 00001 but strictly less than the next entry, 00100, then the best match is P1. Thus the > pointer is P1. On the other hand, if an address is exactly equal to 00001, its best match is P2. Thus the = pointer is P2. Similarly, any address greater than or equal to 00100 but strictly less than 00111 must match prefix P3 = 001*. The second subtle case, which illustrates the need for two separate entries for > and =, is the entry for 00111. If an address is strictly greater than 00111 but strictly less than the next entry, 01111, then the best match is P1. Thus the > pointer is P1. On the other hand, if an address is exactly equal to 00111, its best match is P3. Thus the = pointer is P3. It should be clear from the ranges if covered by the prefixes that any addresses greater than 01111 do not any match prefix. Hence the the entries corresponding to 01111 and 11111 are with no prefixes. However, if an address is exactly equal to 01111, its best match is P1. Thus the = pointer = is P1.
For N prefixes, there will be a maximum of 2N + 1 disjoint intervals, referred to as basic intervals. All the addresses that fall in a basic interval have the same best matching prefix. The basic intervals for prefixes P1, P2, and P3 and their best matching prefixes are shown in Figure 15.23.
The algorithm starts with the endpoints of the given prefixes, sorts them in ascending order, and builds a search table. Each entry in the table stores the endpoint and the next-hop information for the two best matching prefixes > and =. The best matching prefixes for each entry are precomputed and stored in the table. The > entry is used for addresses that are strictly greater than the endpoint and strictly less than the next endpoint in the sorted order. The = entry is used for addresses that are exactly equal to the endpoint. The search table for prefixes P1, P2, and P3 and the ranges covered by the prefixes are shown in Figure 15.24, which actually shows the best matching prefixes instead of their next-hop information.
Let us try to find the best matching prefix for the address 00011 using table 1. A binary search on the table for 00011 will terminate at the endpoint 00001 and since the address is greater than the endpoint 00001 and less than the next endpoint 00100, the pointer will be used and hence the best matching prefix is P1. However, if we were to find a matching prefix for the address 00111, the binary search will end at the endpoint 00111. Since the address is equal to the endpoint, the = pointer will be used to retrieve the best matching prefix P3.
The entire data structure can be built as a binary search table, where each table entry has three items, consisting of an endpoint, a > next-hop pointer, and a = next-hop pointer.The number of entries in the table can be at most 2N since each of the N prefixes can insert two endpoints. The table can be searched in log2(2N) since at every step the binary search reduces the search space by half.
Alternatively, the table can be drawn as a binary trie where each node contains the endpoint it represents and the next-hop information for the two best matching prefixes > and =. Again in this case, the worst-case time required is log2(2N). A further reduction in search time is possible with the use of binary trees of higher radix, such as B-trees used in fast retrieval of records in a large database. Such trees reduce the height of the tree and make the search faster. Binary search on prefix values requires multiple memory access when compared to multibit tries. It also requires a higher amount of storage than the multibit trie variants that employ compression. However, if the size of the entire node is such that it can fit in an L1 cache, then the search time might be negligible. Alternatively, The hardware implementations of this scheme typically uses wider memory access and pipelining to make it faster
IP Address Lookup TUTORIAL 