28 IP ADDRESS LOOKUP 208.12.16/24 110100000000110000010000* 208.12.21/24 110100000000110000010101* .. 208.12.31/24 110100000000110000011111* 208.12.16/20 11010000000011000001* Figure 2.3 Prefix aggregation [1]. 208.12.16/24 208.12.21/24 208.12.31/24 Total IPv4 address space 232-1 Figure 2.4 Prefix ranges [1]. entries for the exception networks.In this example,this will result in only two entries in the forwarding table:208.12.16/20 and 208.12.21/24 (see Fig.2.5 and Table 2.1).However, now some addresses will match both entries because of the prefixes overlap.In order to always make the correct forwarding decision,routers need to do more than search for a prefix that matches.Since exceptions in the aggregations may exist,a router must find the most specific match,which is the longest matching prefix.In summary,the address lookup problem in routers requires searching the forwarding table for the longest prefix that matches the destination address of a packet. Obviously,the longest prefix match is harder than the exact match used for class-based addressing because the destination address of an arriving packet does not carry with it the information to determine the length of the longest matching prefix.Hence,we need to search among the space of all prefix lengths,as well as the space of all prefixes of a given length.Many algorithms have been proposed in recent years regarding the longest prefix match.This chapter provides a survey of these techniques.But before that,we introduce some performance metrics [4]for the comparison of these lookup algorithms. 208.12.2124 208.12.16/20 Total IPv4 address space 0 232-1 These addresses match both prefixes Figure 2.5 Exception prefix [1].28 IP ADDRESS LOOKUP Figure 2.3 Prefix aggregation [1]. Figure 2.4 Prefix ranges [1]. entries for the exception networks. In this example, this will result in only two entries in the forwarding table: 208.12.16/20 and 208.12.21/24 (see Fig. 2.5 and Table 2.1). However, now some addresses will match both entries because of the prefixes overlap. In order to always make the correct forwarding decision, routers need to do more than search for a prefix that matches. Since exceptions in the aggregations may exist, a router must find the most specific match, which is the longest matching prefix. In summary, the address lookup problem in routers requires searching the forwarding table for the longest prefix that matches the destination address of a packet. Obviously, the longest prefix match is harder than the exact match used for class-based addressing because the destination address of an arriving packet does not carry with it the information to determine the length of the longest matching prefix. Hence, we need to search among the space of all prefix lengths, as well as the space of all prefixes of a given length. Many algorithms have been proposed in recent years regarding the longest prefix match. This chapter provides a survey of these techniques. But before that, we introduce some performance metrics [4] for the comparison of these lookup algorithms. Figure 2.5 Exception prefix [1]