近年來隨著Internet應用的增加，使得網路流量急速增加，除了造成網路骨幹路由器的負擔加重外，亦面臨IPv4位址空間不足的問題。IPv4位址空間不足的問題可藉由IPV6來解決，但如何讓路由器處理更多的網路封包及加速路由選擇的决度是IPV6路由器面臨首要的問題，以防止IPV6路由器成為網路骨幹的瓶頸，對於現階段的高速路由器來說，快速的路徑搜尋機制將是影響其效能的主要關鍵。
在本論文中，將提出了一套IPv6的快速路徑搜尋機制，我們利用硬體DRAM來實作Lookup Table，並加入了壓縮機制及從中間的Hash Table開始搜尋，減少搜尋的層次及減少Table Size，來達到更佳的路由快速搜尋，本方法在骨幹網路下利用50000筆routing entries測試，平均只需1.62 memory access，所需的記憶體約29.98 MB。

The rapid growth of the internet applications leads to the fast increase of network traffic. Internet rapid growth Not only cause additional overload of the network backbone router, but also have some problem with no enough IPv4 address space for internet application. The problem of no enough IPv4 address space can be solved by using IPv6 solution. But the most important problem is how IPv6 router can handle more network packets and speed up IP Lookup performance to avoid the bottleneck in network backbone. Regarding to the high-speed router, the fast IP Lookup scheme will be the key factor to influence IP Lookup performance.
In this thesis, we propose a fast IP lookup scheme for IPv6. It’s suitable for utilizing DRAM to implement Lookup Tables and have some additional nice scheme with table compression and starting search at middle hash table. He proposed scheme uses less table size and less search levels to achieve a faster and better IP Lookup scheme than traditional schemes. We use about 50,000 backbone routing prefix for simulating performance. We got a result in 1.62 memory accesses in average case and only need 29.98 MB memory requirement.

誌謝.....................1
論文摘要.................2
ABSTRACT.................3
目錄.....................4
圖次目錄.................6
表次目錄.................8
第一章 簡介..............9
第二章 背景知識..........12
第三章 文獻採討..........25
第四章 架構設計..........46
第五章 效能評估..........72
第六章 結論與未來展望....78
參考文獻.................79

[1] Rekhter, B. Moskowitz, D. Karrenberg, G. J. de Groot, E. Lear. “Address Allocation for Private Internets”, RFC1918, Feb. 1996.
[2] V. Fuller, T. Li, J. Yu, K. Varadhan. “Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy “, RFC1519, Sept. 1993.
[3] S. Deering, R. Hinden , “Internet Protocol Version 6 (IPv6) Specification”, RFC 1883 , Dec. 1995
[4] R. Hinden and S. Deering, “IP Version 6 (IPv6) Addressing Architecture”, RFC 1884, Dec. 1995.
[5] R. Hinden and S. Deering, “IP Version 6 (IPv6) Addressing Architecture”, RFC 2373, July. 1998.
[6] R. Hinden and S. Deering, “Internet Protocol Version 6 (IPv6) Specification”, RFC 2460, Dec. 1998.
[7] R. Hinden and S. Deering, “Internet Protocol Version 6 (IPv6) Addressing Architecture”, RFC 3513, April. 2003.
[8] R. Hinden and S. Deering, “IPv6 Multicast Address Assignments”, RFC 2375, July. 1998.
[9] Wiillibald Doeringer, Mechdi Nassehi, “Routing on Longest-Matching Prefixes” , IEEE/ACM Trans. On Network, vol.4, No.1, Feb. 1996, pp.86-96.
[10] Miguel ´ A. Ruiz-S´anchez, Ernst W. Biersack, and Walid Dabbous. , “Survey and taxonomy of IP address lookup algorithms”, IEEE Network, Mar/Apr 2001, vol. 15, no. 2, pp. 8-23.
[11] D. R. Morrison “PATRICIA-Practical Algorithm to Retrieve Information Coded in Alphanumeric”, J. ACM, Oct. 1968, pp. 514-534.
[12] K. Sklower “A Tree-Based Packet Routing Table for Berkeley Unix”, in Proc. 1991 Winter Usenix Conf., 1991, pp. 93-99.
[13] S. Nilsson and G. Karlsson “IP-Address Lookup Using LC-Tries”,IEEE JSAC, June 1999, vol. 17, no. 6, pp. 1083-1092.
[14] P. Crescenzi, L. Dardini and R. Grossi. “IP Address Lookup Made Fast and Simple”, 7th Annual Euro. Symp. On Algorithms, pp.65-76.
[15] M. Degermark, A. Brodnik, S. Carlsson and S. Pink. “A small Forwarding Tables for Fast Routing Lookups.”, ACM SIGCOMM 97, pp.3-14, Sept. 1997.
[16] P. Gupta, S. Lin, and N. McKeown. “Routing Lookups in Hardware at Memory Access Speeds.” , IEEE INFOCOM98, pp.1240-1247, Apr. 1998.
[17] Nen-Fu Huang, Shi-Ming Zhao, Jen-Yi Pan and Chi-An Su. “A Fast IP Routing Lookup Scheme for Gigabit Switching Routers”, in Proc. of the Conf. on Computer Communications (IEEE INFOZCOM), New York, USA, Mar. 1999.
[18] David E. Taylor, John W. Lockwood, Todd S. Sproull, Jonathan S. Turner, David B. Parlour,”Scalable IP Lookup for Programmable Routers”, in Proc. IEEE INFOCOM 2002, the 21st Annual Joint Conference of the IEEE Computer and Communications Societies, New York, USA, June 2002.
[19] Marcel Waldvogel, George Varghese, Jon Turner and Bernhard Plattner, “Scalable High Speed IP Routing Lookups”, ACM Sigcomm 97, vol. 27, no. 4, pp. 25-36.
[20] W. Z. Zhang, “On the Routing Lookup Algorithm for IPv6”, Master Thesis, Dept. of CSE, National Sun Yat-Sen University, Taiwan, 1999.
[21]Butler Lampson、V Srinivasan and George Varghese,”IP Lookups Using Multiway and Multicolumn Search“,IEEE INFOCOM’98, San Francisco, April 1998, Session 10B-2.
[22] Lu-Meng B. Hsu“Fast IP Lookup Scheme for Next Generation Router” Master Thesis, Institute of Computer Science, National Chung-Hsing University, Taiwan, 1999.
[23] Wen-Shyen E. Chen and Chung-Ting, “A Fast and Scalable IP Lookup Scheme for High-Speed Networks” , in Proc. IEEE ICON’99, Brisbane, Australia, Sept. 1999