| The explosive growth of the Internet and employment of all kinds of new applications over IP make routers as the bottleneck in the Internet, which is mainly caused by IP address lookup. This thesis proposes a new IP address lookup algorithm to improve the performance of routers. In our proposed algorithm, an index table is used to reduce the search range from the whole database to a small search group whose size is limited to 16. All prefix entries are stored in a hash table that is organized by different length hash keys. To lookup a destination address, the first eight bits of the address are extracted to check the index table. Based on the head information in the index table, the hash table is searched. The search result is either the next hop pointer or a small search group. In the latter case, it is necessary to search the small search group. The index table and the small search group are prefetched into cache memory on general-purpose processors (GPP). The implementation of the algorithm on GPP is carried out. As a result, one main memory access and several fast caching searches are needed to lookup an address. The memory requirements can be controlled by selecting the size of the small search group. Since a prefix insertion/deletion only involves a small number of memory modifications, the algorithm performs quick update. The adaptation of the algorithm to NP architecture will be studied in the future. |
