Volume 31 Issue 4 - March 3, 2017 PDF
A multi-index hybrid trie for IP lookup and updates
Chia-Hung Li1, Chia-Yin Hsu1, Sun-Yuan Hsieh1,2,*
1 Department of Computer Science and Information Engineering, National Cheng Kung University
2 Institute of Manufacturing Information Systems, National Cheng Kung University
Font Enlarge
High-performance routers require high-speed IP address lookup to achieve wire-speed packet forwarding. This study proposes a new data structure, the Multi-Index Hybrid Trie (MIHT), for dynamic router table designs. This data structure was constructed by combining the useful characteristics of the B+ tree and priority trie. Figure 1 is an example.
Figure 1. (4,4)-MIHT

IP lookup operations can be performed efficiently by associating each prefix with a key value in the MIHT. Furthermore, because the required tree height and number of prefixes were reduced, dynamic router table operations were performed efficiently using the MIHT. To reduce the memory requirement, each prefix stored its corresponding suffix in a node of the MIHT, rather than storing a full prefix. Experiments using IPv4 and IPv6 routing databases indicated that the proposed data structure has efficient memory usage and performs well for lookup, insertion, deletion operations. This study reports the results of the experiments performed to compare the proposed data structure with other structures using the benchmark IPv4 and IPv6 prefix databases AS1221, AS4637, AS6447, AS65000, AS1221*, and AS6447* with 407,067, 219,581, 417,995, 406,973, 12,155, and 12,278 prefixes, respectively, where AS1221* and AS6447* are IPv6 BGP routing tables. Tables 1-3 are the performance comparison for the various data structures.

Table 1. Average Tree Heights and Storage Comparisons of the Various Data Structures

Table 2. Performance Comparisons for Lookup for the Various Data Structures

Table 3. Performance Comparison for Updating for the Various Data Structures
< Previous
Next >
Copyright National Cheng Kung University