由於科技的進步，現今的高速路由器已經能達到每秒40Gbits的產量。路由位址查詢是路由器設計的一個重要考慮因素之一，為了設計一個好的路由位址查詢引擎，研究人員通常將查找速度，記憶體的需求量，路由更新時間，以及可改變性當作設計的主要考量。因此，利用硬體設計來達到更高的需求是現今常被使用的方法。
在本篇論文中，我們設計了兩個管線化的路由查詢引擎，目標在減少路由更新所造成的影響，並將其實作在元件可編程邏輯閘陣列(FPGA)。在第一個方法中，我們把路由表裡的路由分割成許多不相交的群體，並將同一個群體的路由交錯放到不同的記憶體模組，讓比較階段能達到平行的比較。透過管線化的設計，我們的系統的產量能達到OC-768。第二個方法中，我們對於 [15] 所提出的多元樹結構做了兩個改進。我們的目標在平衡每個作業階段的記憶體使用量，以達到較好的產量，並且能減低路由更新所造成的影響。

Thanks to the technology, the line-card transfer rate in high speed routers is reaching 40 gigabit-per-second in the recent year. IP address lookup is one of the important domains of the router design. To design a good forwarding engine, researchers usually take lookup speed, storage requirement, update time and scalability into major concern. Due to the reason, hardware-based method solutions are often used to develop a high speed router nowadays.
In the paper, we develop two schemes that focus on reducing the update overhead of the pipeline forwarding engine on FPGA. The first approach is to partition the routing tables into several disjoint groups. We interleaving store the prefixes which reside in the same group into several memory modules to ensure the parallel comparison at the comparison stage. With pipeline enabled, the throughput of our design can reach to OC-768. In the second approach, we proposed two techniques to adjust the multiple-bit trie which proposed in [15]. We aim on balancing the memory across the stages to get a better throughput. Our scheme also can reduce the update bubbles. Hence, the throughput of the design increased.

[1] Mohammad J. Akhbarizadeh and Mehrdad Nourani, “Hardware-based IP Routing Using Partitioned Lookup Table,” IEEE/ACM Transactions on Computer. Volume 13, issue 4 August 2005.
[2] Florin Baboescu, Dean M. Tullsen, Grigore Rosu, Sumeet Singh, “A Tree Based Router
Search Engine Architecture with Single Port Memories,” International Symposium on Computer Architecture 2005
[3] Anindya Basu and Girija Narlikar, “Fast Incremental Updates for Pipeline Forwarding
Engine,” IEEE/ACM Transactions on Networking. Volume 13, no. 3, JUNE 2005
[4] BGP Routing Table Analysis Reports, http://bgp.potaroo.net/.
[5] Y. K. Chang and Y. C. Lin, “Dynamic Routing Tables Using Simple Balanced Search Trees.” Lecture Notes on Computer Science LNCS 3961 (ICOIN 2006), Vol. 3961, January 2006
[6] CACTI. http://quid.hpl.hp.com:9081/cacti/.
[7] M.Gray. Internet Growth Summary, http://www.mit.edu/people/mkgray/net/internet-growth-summary.html, 1996
[8] Jahangir Hasan and T. N. Vijaykumar, “Dynamic Pipelining Making IP-Lookup Truly
Scalable,” SIGCOMM’05, Volume 35 , Issue 4.
[9] Weirong Jiang and Viktor K.Prasanna, “A Memory-Balanced Linear Pipeline Architecture for Trie-based IP Lookup,” Proc. HotI’07, 2007
[10] S.Kumar, M.Becchi, P.Crowley, and J.Turner, “CAMP: Fast and Efficient IP Lookup Architecture,” 2006 ACM/IEEE symposium on Architecture for networking and communications systems.
[11] Wencheng Lu, Sartaj Sahni, “Packet Forwarding Using Pipelined Multibit Tries,” IEEE Symposium on Computers and Communications 2006(ISCC06).
[12] D. R. Morrison, “PATRICIA - Practical Algorithm to Retrieve Information Coded in Alpha Numeric,” Journal of the ACM, 1968
[13] S. Nilsson and G. Karlsson, “IP-Address Lookup Using LC-trie,” IEEE Journal on selected Areas in Communications, 17(6):1083-1092, June 1999.
[14] Timothy Sherwood, George Varghese and Brad Calder, “A Pipelined Memory Architecture for High Throughput Network Processors,” International Symposium on Computer Architecture 2003.
[15] V. Srinivasan and George Varghese, “Fast Address Lookups Using Controlled Prefix
Expansion,” ACM Transactions on Computer Systems, 1999.
[16] A. Tammel, “How to Survive as an ISP,” Proc of Networld interop 1997.
[17] Xilinx Virtex-II Pro FPGA. http://www.xilinx.com