| 摘要 |
A method and algorithm for IP address lookup for packet forwarding, finds a longest prefix match for a destination address of n bits, using 2<SUP>n/2 </SUP>entries in a lookup table, expanding a given IP address to be matched if its prefix length is more than n/2, and, completing a lookup operation using the table. The number 'n" may be 32 or otherwise. An example teaches an IP address lookup table with a maximum address size of 32 bits, using a lookup table with 2<SUP>16 </SUP>entries. Further, if an IP prefix length is more than 16 bits, then the given address to be matched is expanded to its full prefix length before the lookup operation. The algorithm takes only two memory references for specific hardware, such as IXP1200. For generic hardware, it takes only three memory references. Also taught is a computer readable medium having the method encoded therein.
|
