Volume 29 Issue 1 - April 24, 2015 PDF
Multi-Index Hybrid Trie for IP Lookup and Update
Chia-Hung Lin1, Chia-Yin Hsu1, Sun-Yuan Hsieh 1,2,3,*
1 Department of Computer Science and Information Engineering, National Cheng Kung University,
2 Institute of Manufacturing Information and Systems, National Cheng Kung University
3 Institute of Medical Informatics, National Cheng Kung University
Font Enlarge
High performance routers require high-speed IP address lookup to achieve wire speed packet forwarding. In this thesis, a new data structure of dynamic router table is proposed for IP lookup and updates, called Multi-Index Hybrid Trie (MIHT). By associating each prefix with a key value, we can perform an IP lookup operation efficiently in a balanced search tree. Furthermore, because the tree height and the number of prefixes that need to be compared is reduced, the dynamic router-table operations can also be performed efficiently. To reduce the memory requirement, for each prefix we store its corresponding suffix in a node of MIHT instead of storing a full binary string. Experiments using real IPv4 routing databases indicate that, the proposed data structure is efficient in memory usage and performs well in terms of lookup, insert and delete operations. We report the results of experiments conducted to compare the proposed data structure with other structures using the benchmark IPv4 prefix databases AS1221, AS4637, AS6447, and AS65000 with 407,067, 219,581, 417,995, and 406,973 prefixes, respectively.
< Previous
Next >
Copyright National Cheng Kung University