網路位址得查詢以及路由表的更新都會影響到路由器隊封包得處理速度。在這篇論文中，我們將針對路由表的查詢以及更新機制提出一個新的資料結構，我們稱它 Multi Inherited Search Trie (MIST)。藉由每個前綴字串的索引值來進行資料的分堆以及移除每筆字串之間的關係，這樣能讓位址的查詢更為快速。同時我們使用“前綴樹”來做為我們資料結構的一部份使得整體佔用記憶體的花費以及更新所要的時間都能夠減少。本篇使用實際的IPv4測試資料來進行實驗並且驗證說此資料結構能在記憶體上以及找尋和更新功能都有不錯的效能。

IP lookup and routing table update will affects the speed of the router to forward packets. In this paper, a new data structure of dynamic router table is proposed for IP lookup and updates, called Multi Inherited Search Trie (MIST). By partition each prefix with a index value and removing the relationship of prefixes, we can perform an IP look operation efficiently. Since we choose prefix trie (PT) for our substructure, the memory consumption and dynamic router-table operations can also be performed efficiently. Experiments using real IPv4 routing databases indicate that, Multi Inherited Search Trie is efficient in memory usage and performs well in terms of lookup, insert and delete operations.

[1] BGP Table obtained from http://bgp.potaroo.net/.
[2] V. Fuller, T. Li, J. Yu and K. Varadhan, Classless inter-domain routing (CIDR):
an address assignment and aggregation strategy, RFC 1519, Sep. 1993.
[3] J. Postel, Internet protocol darpa internet program protocol speciffication,"
RFC791, Sep. 1981.
[4] S. Deering and R. Hinden, Internet protocol version 6 (IPv6) speciffication," RFC
1883, Dec. 1995.
[5] 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.
[6] 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.
[7] Y. K. Chang and Y. C. Lin A Fast and Memory Ecient 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.
[8] Y. K. Chang, Y. C. Lin, and K. Y. Ho Update-aware Controlled Prex Expan-
sion for Fast IP Lookups," in Proceedings of International Conference on High
Performance Switching and Routing, pp. 1-6, 2009.
[9] Y. K. Chang Fast binary and multiway prefix searches for packet forwarding," in
Computer Networks, vol. 51, no. 3, pp. 588-605, Feb. 2007.
[10] 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.
[11] Y. K. Chang, Simple and fast IP lookups using binomial spanning trees," Computer Communi- cations, vol. 28, no. 5, pp. 529-539, Mar. 2005.
[12] 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.
[13] 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.
[14] S. Y. Hsieh, and Y. C. Yang, A Classiffcated Multisuffix Trie for IP Lookup and
Update," IEEE Transactions on Computers, vol. 61, no. 5, pp. 726-731, May. 2012.
[15] S. Y. Hsieh, Y. L. Huang, and Y. C. Yang, Multi-Prefix 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,
hhttp://doi.ieeecomputersociety.org/10.1109/TC.2010.133i.
[16] 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.
[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 Search in a Balanced Tree for IP Address
Lookup," Proceedings of IEEE workshop high performance switching and rout-
ing, pp. 490-494, 2005.
[19] 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.
[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] V. C. Ravikumar, R. Mahapatra, and J. C. Liu, Modiffied LC-trie based efficient
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.
[24] 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.
[25] S. Sahni and K. S. Kim, An O(log n) dynamic router-table design," IEEE Trans-
actions on Com- puters, vol. 53, no. 3, pp. 351-363, Mar. 2004.
[26] S. Sahni and K. S. Kim, Efficient construction of multibit tries for IP lookup,"
IEEE/ACM Transactions on Networking, vol. 11, no. 3, pp. 650-662, 2003.
[27] 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.
[28] K. Sklower, A tree-based packet routing table for Berkeley unix," in Proceedings
of Winter Usenix Conference, pp. 93-99, 1991.
[29] V. Srinivasan and G. varghese, Fast address lookups using controlled prefix expansion," ACM Transactions on Computer Systems, vol. 17, no. 1, pp. 1-40, 1999.
[30] 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.
[31] C. Yim, B. Lee and H. Lim, Efficient Binary Search for IP Address Lookup,"
IEEE comunications letters, vol. 9, no. 7, pp. 652-654, Jul. 2005.
[32] 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.
[33] C. H. Lin, C. Y. Hsu, and S. Y. Hsieh, A Multi-index Hybrid Trie for IP Lookup
and Updates," in IEEE Transactions on Paralle and Distributed Systems, accept.