在路由器中，網路位址查詢是一個重要的運算，此運算必須為每個傳入的封包決定出口，它會影響路由器轉送封包的速度。隨著網際網路流量的快速成長，我們需要一個高效的網路位址查詢技術。此外，由於網路的千變萬化，前綴的插入和刪除可能會頻繁地發生。在這篇論文中，我們提出了一個新的資料結構來設計動態路由表格，此新結構稱為 Classified Multi-Suffix Trie (CMST)。為了達到性能更好的動態路由表格運算，CMST的每個結點可以儲存多個前綴，並且可能在一個內結點，即找到符合的最長前綴，而不需要比對到葉結點。此外，我們在每個結點內對前綴做分類，使得CMST可以提供更有效率的查詢、插入和刪除運算。在我們所提出的結構中，只儲存每前綴的後綴而不是整個二元字串，運用此技術，可以減少記憶體的需求。根據使用實際的網際網路通訊協定第四版(IPv4)之路由資料庫的實驗結果顯示，我們所提出的新資料結構不僅在記憶體的使用有效率，並且也在查詢、插入和刪除運算方面有良好的效能。

IP address lookup in a router is an essential operation that should determine the output port for each incoming packet and it affects the speed of the router to forward packets. With the rapid growth of internet traffic, an efficient IP lookup technique is required. Moreover, with the instability of Internet, the insertion and deletion of prefixes may occur frequently. In this paper, a new data structure, called classified multi-suffix trie (CMST) is proposed for designing dynamic router-tables. To achieve better performance, each node in CMST can store more than one prefix and may find the longest matching prefix in an internal node rather than on a leaf. Furthermore, with the classification in each node, the dynamic router-table operations can be performed efficiently. We also utilize a technique to reduces the memory requirement by storing the suffix of each prefix instead of the 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.

[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, 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.
[4] Y. K. Chang and Y. C. Lin “A Fast and Memory Efficient Dynamic IP Lookup Al- gorithm Based on B-Tree,” in proceedings of the 23rd IEEE International Conference on Advanced Information Networking and Applications, pp. 278-284, 2009.
[5] Y. K. Chang, Y. C. Lin, and K. Y. Ho “Update-aware Controlled Prefix Expansion for Fast IP Lookups,” in Proceedings of International Conference on High Performance Switching and Routing, pp. 1-6, 2009.
[6] Y. K. Chang and Y. C. Lin, “Dynamic segment trees for ranges and prefixes,” IEEE Transactions on Computers, vol. 56, no. 6, pp. 769-784, Jun. 2007.
[7] Y. K. Chang, “Simple and fast IP lookups using binomial spanning trees,” Computer Communications, vol. 28, no. 5, pp. 529-539, Mar. 2005.
[8] Y. K. Chang and W. H. Cheng “A Small IP Forwarding Table Using Hashing,” in proceedings of International Conference on Advanced Information Networking and Applications, vol. 1, pp. 482-487, Mar. 2004.
[9] P. Crescenzi, L. Dardini, and R. Grossi, “IP address lookup made fast and simple,” in Proceedings of Seventh Annual European Symposium Algorithms, Technical Report TR-99-01, Univ. of Pisa, 1999.
[10] S. Deering and R. Hinden, “Internet protocol version 6 (IPv6) specification,” RFC 1883, Dec. 1995.
[11] 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.
[12] S. Dharmapurikar, P. Krishnamurthy, and D. E. Taylor, “Longest prefix matching using bloom filters,” IEEE/ACM Transactions on Networking, vol. 14, no. 2, pp. 397-409, Apr. 2006.
[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] V. Fuller, T. Li, J. Yu, and K. Varadhan, “Classless inter-domain routing (CIDR): an address assignment and aggregation strategy,” RFC 1519, Sep. 1993.
[15] Sun-Yuan Hsieh, Yi-Ling Huang, Ying-Chi 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] N. F. Huang and S. M. Zhao, “A novel IP-routing lookup scheme and hardware architecture for multigigabit switching routers,” IEEE Journal on Selected Areas in Communications, vol. 17, no. 6, pp. 1093- 1104, Jun. 1999.
[17] W. Jiang, Q. Wang, and V. Prasanna, “Beyond TCAMs: an SRAM-based parallel multi-pipeline architecture for terabit IP lookup,” in Proceedings of IEEE INFO-COM, pp. 1786-1794, Apr. 2008.
[18] B. Lampson, V. Srinivasan, and G. Varghese, “IP lookups using multiway and multi-column search,” IEEE/ACM Transactions on Networking, vol. 7, no. 3, pp. 324-334, Jun. 1999.
[19] H. Lu, K. S. Kim, and S. Sahni, “Prefix 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 specification,” RFC791, Sep. 1981.
[24] V. C. Ravikumar, R. Mahapatra, and J. C. Liu, “Modified LC-trie based efficient routing lookup,” in Proceedings of the 10th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MAS-COTS), 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, K. S. Kim, and H. Lu, “Data structures for one-dimensional packet classification using most-specific-rule matching,” International Journal of Foundations of Computer Science, vol. 14, no. 3, pp. 337-358, 2003.
[28] 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.
[29] 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.
[30] K. Sklower, “A tree-based packet routing table for Berkeley unit,” in Proceedings of Winter Usenix Conference, pp. 93-99, 1991.
[31] S. Soh, L. Hiryanto and S. Rai,”Efficient prefix updates for IP router using lexicographic ordering and updatable address set,” IEEE Transactions on Computers, vol. 57, no. 1, pp. 110-125, Jan. 2008.
[32] 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.
[33] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable high speed IP routing lookups,” in Proceedings of ACM SIGCOMM, pp.25-36, 1997.
[34] 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.