Fast IP-Lookup Algorithm for IPv6 Global Unicast Address

近年來隨著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 參考文獻.................7