近幾年來許多針對高效能查詢 IP 位址的方法陸續被提出。這些方法大致上可被分為兩大類：一種是針對路由表使用靜態的資料結構，通常這種方法需要先預先計算；而另一種是針對路由表使用動態的資料結構，而使之方便支援更新。使用預先計算可以對路由表的資料結構進行簡化，進而可以加快其搜尋速度和降低記憶體使用量。然而，預先計算的缺點在於當一筆新的資料要加入路由表或要從路由表刪除一筆資料時，整個資料結構會需要被重新建立。重建路由表會大為降低一個骨幹路由器的效能。另一方面，若使用動態的方法則不需要重建整個路由表的資料結構，故使得更新動作更為容易，但動態方法可能導致較差的搜尋效能及記憶體使用量。
在本篇論文中，我們設計且實作了一個基於在研究報告裡 [5] 提出的動態資料結構方法的管線化多層的多元平衡搜尋樹，稱之為「Multiway Most Specific Prefix 樹」 (MMSPT)。為了降低晶片外記憶體的存取延遲，針對提出的資料結構進行最佳化以求符合現有可獲得的可重新組態晶片上的記憶體容量限制。Multiway Most Specific Prefix 樹採用 (n + 1) 位元的 prefix 表示法和區段表 [10] 來降低記憶體使用量。其多元平衡搜尋樹為本篇論文所提出「受制的B 樹建立演算法」 (CBA) 下建造的 B 樹，此演算法不但提昇原本 B 樹節點的使用率，也保持了能有效率的更新的特性。我們的設計實作並模擬於 Vertex-5 FPGA 家族的 XC5VSX240T 晶片上 [21]。其效能實驗中顯示出其設計的搜尋速度可達到使用單一搜尋引擎的每秒 37.51G 位元和直接延伸單一搜尋引擎組成的每秒 113.27G 位元的產量。
關鍵詞：路由位置查詢、Most Specific Prefix、封包轉送

In the last couple of years, various schemes for high-performance IP address lookups have been proposed. Those schemes can be broadly classified into two categories: one that uses static data structure for the routing tables which usually requires precomputations and the other uses dynamic data structure to support updates. The precomputations can simplify the data structure of the routing tables so that the lookup speed can be increased and memory consumption can be reduced. However, a disadvantage of the precomputation is that the entire data structure may need to be rebuilt when a new entry is added or removed from the routing tables. Rebuilding the routing tables greatly degrades the update performance of a backbone router. On the other hand, dynamic schemes make update easier without rebuilding the entire data structure, but they may result in worse performance of lookup speed and memory consumption.
In this thesis, we design and implement the pipelined multi-layered multiway balanced search trees based on the dynamic data structure scheme proposed in [5] which is called “Multiway Most Specific Prefix Trees” (MMSPT). To reduce the access delay of off-chip memory, the proposed data structure is optimized to fit into the on-chip memory of the currently available reconfigurable hardware. MMSPT uses (n + 1)-bit prefix representation and segmentation tables [10] to reduce the memory consumption. The multiway balanced search trees are B-trees built by the proposed “Controlled B-tree building Algorithm” (CBA) to improve the utilization of B-tree nodes as well as to maintain efficient updates. Our design is implemented and simulated on the chip XC5VSX240T of Vertex-5 FPGA family [21]. The performance experiments show that throughputs of 37.51Gbps and 113.27Gbps can be achieved by a single search engine and by a straightforward extension of the search engines, respectively.
Keywords: IP lookup, Most Specific Prefix, Packet forwarding

[1] F. Baboescu, D. M. Tullsen, G. Rosu, and S. Singh, “A Tree Based Router Search Engine Architecture With Single Port Memories,” IEEE International Symposium on Computer Architecture (ISCA), 2005.
[2] M. Behdadfar, H. Saidi, H. Alaei, and B. Samari, “Scalar Prefix Search: A New Route Lookup Algorithm for Next Generation Internet,” IEEE INFOCOM 2009. The 28th Conference on Computer Communications.
[3] BGP Routing Table Analysis Reports, http://bgp.potaroo.net/.
[4] Y.-K. Chang and D.-J. Lin, “Design and Implementation of Dynamic Routing Tables,” Master Thesis of Computer Science and Information Engineering, NCKU, 2005.
[5] Y.-K. Chang and Y.-C. Lin, “Dynamic Routing Tables Using Simple Balanced Search Trees,” Lecture Notes on Computer Science (LNCS) 3961 (International Conference on Information Networking (ICOIN)), 2006.
[6] Y.-K. Chang, “Fast Binary and Multiway Prefix Searches for Packet Forwarding,” COMPUTER NETWORKS, SCI, 2007.
[7] 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, 2010.
[8] Cypress Semiconductor Corp., “CY7C1024DV33, 3-Mbit (128K24) Static RAM”, Revised September10, 2007, at http://www.cypress.com/products/
[9] V. Fuller, T. Li, J. Yu, and K. Varadhan, "Classless inter-domain routing (CIDR): an address assignment and aggregation strategy," RFC 1519, Sept. 1993.
[10] W. Jiang and V. K. Prasanna, “A Memory-Balanced Linear Pipeline Architecture for Trie-based IP Lookup,” IEEE Symposium on High-Performance Interconnects, 2007.
[11] S. Kumar, M. Becchi, P. Crowley, and Jonathan Turner, “CAMP: Fast and Efficient IP Lookup Architecture,” ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS), 2006.
[12] H. Le, W. Jiang, and V. K. Prasanna, “A SRAM-based Architecture for Trie-based IP Lookup Using FPGA,” International Symposium on Field-Programmable Custom Computing Machines, 2008.
[13] H. Lu, K. Kim, and S. Sahni, “Prefix and interval-partitioned dynamic IP router-tables,” IEEE Transactions on Computers, vol. 54, no. 5, pages 545-557, May 2005.
[14] H. Lu and S. Sahni, “A B-tree dynamic router-table design,” IEEE Transactions on Computers, vol. 54, no. 7, pages 813-824, July 2005.
[15] X. Meng, Z. Xu, B. Zhang, G.. Huston, S. Lu, and L. Zhang, “IPv4 Address Allocation and the BGP Routing Table Evolution,” ACM SIGCOMM, pp. 71-80, Jan. 2005.
[16] RIPE RIS Raw Data, http://www.ripe.net/projects/ris/rawdata.html.
[17] M. Á. Ruiz-sánchez, I. S. Antipolis, E. W. Biersack, S. Antipolis, W. Dabbous, and I. S. Antipolis, “Survey and Taxonomy of IP Address Lookup Algorithms,” IEEE Network, vol. 15, no. 2, pp. 8-23, Apr. 2001.
[18] V. Srinivasan and G. Varghese, “Fast Address Lookups using Controlled Prefix Expansion,” Proc. ACM Sigmetrics ’98, June 1998, pp. 1–11.
[19] X. Sun and Y. Q. Zhao, “An On-Chip IP Address Lookup Algorithm,” IEEE TRANSACTIONS ON COMPUTERS, VOL. 54, NO. 7, JULY 2005.
[20] P. Warkhede, S. Suri, and G. Varghese, “Multiway range trees: scalable IP lookup with fast updates,” Computer Networks, vol. 44, no. 3, pages 289-303, February 2004.
[21] Xilinx, “Virtex-5 Family Overview,” Advance Product Specification, DS100 (v5.0) February 6, 2009, at http://www.xilinx.com.