高效能路由器必須能夠提供高速的網路位址查詢。在這篇論文中，我們提出
了一個動態的路由表資料結構，我們稱之為 Multi-Index Hybrid Trie (MIHT)。藉由賦予每筆前綴一個鍵值，使得我們能夠在平衡的搜尋樹上有效率地實施網路位址查詢。此外，由於樹高和需被比對的前綴數量同時減少了，使得動態路由表的各項運作變得更有效率。為了減少對記憶體容量大小的需求，我們只儲存後綴在我們的MIHT中而非整個的前綴字串。我們的實驗使用實際的網際網路通訊協定第四版(IPv4)的路由資料庫。透過實驗結果顯示，我們所提出的資料結構不但提供更小的記憶體需求，且在路由表的查詢以及更新運作的效能表現良好。在我們的實驗中所使用的四個前綴資料庫是AS1221、AS4637、AS6447和AS65000，它們分別有407,067、219,581、417,995和406,973筆前綴資料。

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 e±cient 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.

[1] BGP Table obtained from http://bgp.potaroo.net/.
[2] M. Berger, IP lookup with low memory requirement and fast update," in Proceedings of IEEE High Performance Switching and Routing, pp. 287{291, Jun. 2003.
[3] Y. K. Chang Fast binary and multiway pre¯x searches for packet forwarding," in Computer Networks, vol. 51, no. 3, pp. 588{605, Feb. 2007.
[4] Y. K. Chang and Y. C. Lin, Dynamic segment trees for ranges and pre¯xes," IEEE Transactions on Computers, vol. 56, no. 6, pp. 769{784, Jun. 2007.
[5] Y. K. Chang, Simple and fast IP lookups using binomial spanning trees," Computer Communications, vol. 28, no. 5, pp. 529{539, Mar. 2005.
[6] Y. K. Chang and Y. C. Lin A Fast and Memory E±cient Dynamic IP Lookup Algorithm Based on B-Tree," in proceedings of the 23rd IEEE International Conference on Advanced Information Networking and Applications, pp. 278{284, 2009.
[7] Y. K. Chang, Y. C. Lin, and K. Y. Ho Update-aware Controlled Pre¯x Expansion for Fast IP Lookups," in Proceedings of International Conference on High
Performance Switching and Routing, pp. 1{6, 2009.
[8] Y. K. Chang, Y. C. Lin, and C. C. Su, Dynamic multiway segment tree for IP lookups and the fast pipelined search engine," IEEE Transactions on Computers, vol. 59, no. 4, pp. 492{506, Apr. 2010.
[9] S. Deering and R. Hinden, Internet protocol version 6 (IPv6) speci¯cation," RFC 1883, Dec. 1995.
[10] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, Small forwarding tables for fast routing lookups," in Proceedings of ACM SIGCOMM Computer Communication Review, pp. 3-14, 1997.
[11] W. Eatherton, G. Varghese, and Z. Dittia, Tree bitmap: hardware/ software IP lookup with incremental updates," in Proceedings of ACM SIGCOMM Computer Communication Review, 34, 2, Apr. 2004.
[12] V. Fuller, T. Li, J. Yu, and K. Varadhan, Classless inter-domain routing (CIDR): an address assignment and aggregation strategy," RFC 1519, Sep. 1993.
[13] S. Y. Hsieh, Y. L. Huang, Y. C. Yang, Multi-Pre¯x Trie: a New Data Structure for Designing Dynamic Router-Tables," IEEE Transactions on Computers, 09
Junary 2010. IEEE computer Society Digital Library. IEEE Computer Society, http://doi.ieeecomputersociety.org/10.1109/TC.2010.133i.
[14] S. Y. Hsieh, Y. C. Yang, A Classi¯ed Multisu±x Trie for IP Lookup and Update," IEEE Transactions on Computers, vol. 61, no. 5, pp. 726{731, May. 2012.
[15] B. Lampson, V. Srinivasan, and G. Varghese, IP lookups using multiway and multicolumn search," IEEE/ACM Transactions on Networking, vol. 7, no. 3, pp. 324{334, Jun. 1999.
[16] H. Lim, W. Kim and B. Lee, Binary Search in a Balanced Tree for IP Address Lookup," Proceedings of IEEE workshop high performance switching and routing, pp. 490{494, 2005.
[17] H. Lim, C. Yim and E. E. Swart, Priority trie for IP address lookup," IEEE Transactions on Computers, vol. 59, no. 6, pp. 784{794, Jun. 2010.
[18] H. Lim, W. Kim and B. Lee, Binary Searches on Multiple Small Trees for IP Address Lookup," IEEE comunications letters, vol. 9, no. 1, pp. 75{77, Jan. 2005.
[19] H. Lu, K. S. Kim, and S. Sahni, Pre¯x and interval-partitioned dynamic IP router-tables," IEEE Transactions on Computers, vol. 54, no. 5, pp. 545{557, May 2005.
[20] H. Lu and S. Sahni, A B-tree dynamic router-table design," IEEE Transactions on Computers, vol. 54, no. 7, pp. 813{824, Jul. 2005.
[21] H. Lu and S. Sahni, Enhanced interval trees for dynamic IP router-tables," IEEE Transactions on Computers, vol. 53, no. 12, pp. 1615{1628, Dec. 2004.
[22] S. Nilsson and G. Karlsson, IP-address lookup using LC-trie," IEEE Journal on selected Areas in Communications, vol. 17, no. 6, pp. 1083{1092, Jun. 1999.
[23] J. Postel, Internet protocol darpa internet program protocol speci¯cation," RFC791, Sep. 1981.
[24] V. C. Ravikumar, R. Mahapatra, and J. C. Liu, Modi¯ed LC-trie based e±cient routing lookup," in Proceedings of the 10th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems
(MASCOTS), pp. 177{182, Oct. 2002.
[25] M. A. Ruiz-Sanchez, E. W. Biersack, and W. Dabbous, Survey and taxonomy of IP address lookup algorithms," IEEE Network, vol. 15, pp. 8{23, 2001.
[26] S. Sahni and K. S. Kim, An O(log n) dynamic router-table design," IEEE Transactions on Computers, vol. 53, no. 3, pp. 351{363, Mar. 2004.
[27] S. Sahni and K. S. Kim, E±cient construction of multibit tries for IP lookup," IEEE/ACM Transactions on Networking, vol. 11, no. 3, pp. 650{662, 2003.
[28] S. Sahni and H. Lu, Dynamic tree bitmap for IP lookup and update," in Proceedings of the Sixth International Conference on Networking, pp. 79{84, 2007.
[29] K. Sklower, A tree-based packet routing table for Berkeley unix," in Proceedings of Winter Usenix Conference, pp. 93{99, 1991.
[30] V. Srinivasan and G. varghese, Fast address lookups using controlled pre¯x expansion," ACM Transactions on Computer Systems, vol. 17, no. 1, pp. 1-40, 1999.
[31] P. R. Warkhede, S. Suri, and G. Varghese, Multiway range tree: scalable IP lookup with fast updates," Computer Network, vol. 44, no. 3, pp. 289{303, Feb. 2004.
[32] C. Yim, B. Lee and H. Lim, E±cient Binary Search for IP Address Lookup," IEEE comunications letters, vol. 9, no. 7, pp. 652{654, Jul. 2005.
[33] N. Yazdani and P. S. Min, Fast and Scalable schemes for the IP address Lookup Problem," Proceedings of IEEE workshop high performance switching and routing, pp. 83{92, 2000.