查詢結果分析
來源資料
頁籤選單縮合
題名 | 二元決策圖為基礎的IP路徑查表演算法之設計與FPGA實現=A Fast IP Routing Lookup Algorithm with Binary Decision Diagrams and Implementation Using FPGA |
---|---|
作者 | 吳其政; 施景文; 吳東旭; 吳家榮; 邱煌森; Wu, Chi-cheng; Shih, Jing-wun; Wu, Dong-shiuh; Wu, Jia-long; Chiu, Huang-sen; |
期刊 | 龍華科技大學學報 |
出版日期 | 20070900 |
卷期 | 23 2007.09[民96.09] |
頁次 | 頁27-35 |
分類號 | 448.6 |
語文 | chi |
關鍵詞 | 路由器; 二元決策圖; 場效可程式化邏輯陣列; Router; Binary decision diagrams; BDDs; Field programmable gate array; FPGA; |
中文摘要 | 隨著網際網路的普及和多媒體資訊的廣泛需求與應用,網際網路通信量的快速增加,因此需要更高速的連線速度和路由器,目前已有Gigabit或更快之光纖網路,因此網際網路訊務的主要瓶頸已由網路線路轉移至路由器。路由器主要是根據IP封包的目的位址來查詢封包的下一站位址,由於CIDR的使用,使得在決定封包下一站的位址時必須在路徑表中找出符合IP目的位址的最長前置位元,本論文使用二元決策圖來設計IP路徑查表演算法,由於二元決策圖具有節點共享的優點,刪除重複的節點,有效率地降低組合電路的成本,是一個適合場效可程式化邏輯陣列實現的演算法,我們成功地以多工器將它以場效可程式化邏輯陣列硬體實現。實作模擬的結果顯示,我們的演算法每秒可執行10⁸次查表工作,若以每封包大小平均為40bytes來計算,則我們演算法可支援至最快4Gbps的連線速率。 |
英文摘要 | The Internet traffic is rapidly growing not only because of the increase of users but also because of the multimedia applications. With the increased traffic, fast link speed and routers are required. Currently, since gigabit links are available, the chief bottleneck of the traffic has been moved from the links to the routers. Routers lookup routing table for next-hop address based on packet's destination IP address. Since the use of CIDR, IP routing lookup must find out the longest matching prefix with the IP packet destination address in the routing table. In this paper, we have implemented and IP routing lookup algorithm with binary decision diagrams. Since binary decision diagrams technique have the abilities of node sharing, can eliminating redundant nodes and reduce the cost of combinational circuit efficiently. We have designed a fast IP routing lookup algorithm with binary decision diagrams and implemented this algorithm by using Multiplexer in reconfigurable hardware, FPGA. Our simulation and experimental results shows that the proposed scheme can perform 10⁸ lookups per second. If the average size of each packet is 40 bytes, the fastest link rates can up to 4Gbps in our scheme. |
本系統之摘要資訊系依該期刊論文摘要之資訊為主。