A multi-index hybrid trie for lookup and updates

摘要: \begin{abstract} 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. structure was constructed by combining useful characteristics of ${\rm B}^{+}$ tree and priority trie. operations can be performed efficiently associating each prefix with key value in MIHT. Furthermore, because required height number prefixes were reduced, using To reduce memory requirement, stored its corresponding suffix node MIHT, rather than storing full prefix. Experiments IPv4 IPv6 routing databases indicated that proposed has efficient usage performs well lookup, insertion, deletion operations. reports results experiments compare other structures benchmark AS1221, AS4637, AS6447, AS65000, AS1221*, AS6447* 407,067, 219,581, 417,995, 406,973 , 12,155, 12,278 prefixes, respectively, where AS1221* are BGP tables.\\ \end{abstract} \begin{IEEEkeywords} Classless inter domain (CIDR), tables, longest matching prefix, multi-index hybrid \end{IEEEkeywords}