以場效可程式化邏輯陣列為導向的二維封包分類演算法

Size: px

Start display at page:

Download "以場效可程式化邏輯陣列為導向的二維封包分類演算法"

础文
5 years ago
Views:

1 二元決策圖為基礎的 IP 路徑查表演算法之設計與 FPGA 實現二元決策圖為基礎的 IP 路徑查表演算法之設計與 FPGA 實現吳其政施景文吳東旭吳家榮邱煌森龍華科技大學電子工程系 ( 所 ) 摘要隨著網際網路的普及和多媒體資訊的廣泛需求與應用, 網際網路通信量的快速增加, 因此需要更高速的連線速度和路由器, 目前已有 Gigabit 或更快之光纖網路, 因此網際網路訊務的主要瓶頸已由網路線路轉移至路由器路由器主要是根據 IP 封包的目的位址來查詢封包的下一站位址, 由於 CIDR 的使用, 使得在決定封包下一站的位址時必須在路徑表中找出符合 IP 目的位址的最長前置位元, 本論文使用二元決策圖來設計 IP 路徑查表演算法, 由於二元決策圖具有節點共享的優點, 刪除重複的節點, 有效率地降低組合電路的成本, 是一個適合場效可程式化邏輯陣列實現的演算法, 我們成功地以多工器將它以場效可程式化邏輯陣列硬體實現實作模擬的結果顯示, 我們的 8 演算法每秒可執行 10 次查表工作, 若以每封包大小平均為 40 bytes 來計算, 則我們演算法可支援至最快 4Gbps 的連線速率關鍵字 : 路由器二元決策圖場效可程式化邏輯陣列 1. 簡介因為網路的普及化和多媒體的廣泛應用, 使得網際網路的流量快速的增加再者, 光纖線路的普及, 連線的速度大幅提升, 例如 OC-768 光纖線路的速度為 40Gbps, 即每秒可傳輸 400 億位元的資料, 因此網際網路通信量 (traffic) 的主要瓶頸已由網路線路轉移至路由器 (Router) 傳統的路由器主要是查詢 IP ( Internet Protocol ) 封包的目的位址 (Destination Address) 來決定封包的下一站 (Next hop) 由於 CIDR[7] 的使用, 在查詢下一站時必須在路徑表 (Routing Table ) 中找出符合的最長前置位元 (longest prefix matching), 因此,IP 查表可包含二個步驟 : 首先, 在路徑表中尋找與封包的目的位址相符合的集合接著, 在這些相符合的集合中找出符合最長的前置長度例如, 表 1 為一個簡單的路徑表, 假設當一個封包進來時, 它的目的位址為 , 查尋路徑表可以找到 B(01*) 和 G(010*) 等二項跟目的位址相符合的下一站, 依照 CIDR 的定義必須找出符合的最長前置位元, 所以它的下一站為 G (010*) 目前已有許多關於加速 IP 查表方面的研究, 這些研究可略分為以軟體和硬體方法兩方向, 就軟體而言, 它大多以 Trie 資料結構為基礎如 [5, 6, 11, 15], 硬體部分則有 [9, 10, 12] 等相關研究

2 龍華科技大學學報第二十三期, 表 1 簡單路徑表圖 1 是依照表 1 所建造的一個簡單的二元樹架構 (binary trie), 建造的方法是根據路徑表中的每一個項目, 從左至右逐一讀取位元, 首先建立樹根 (root) 節點, 當讀取的位元為 0 時, 就往左建立子節點 ; 為 1 時就往右建立子節點, 直到讀取到 *" 時, 就將下一站存至該節點例如, 建立 H(10*) 時, 第一個位元為 1, 就往右建立子節點, 第二個位元為 0, 接下去往左建立子節點, 因為接下來為 *, 所以就在該節點存入下一站 H", 如圖 1 中用粗線表示其建造節點和路徑過程二元樹的搜尋是依照 IP 目的位址的位元從左到右逐一往下搜尋, 首先從樹根進入, 假設讀取的位元為 0 時, 就往左子樹 (left subtree) 搜尋 ; 為 1 時就往右子樹 (right subtree) 搜尋, 當遇到 * 時 ( 表示已找到相符合的前置位元 ), 則將它的下一站儲存起來, 若尚有子樹, 則繼續往下搜尋, 如此可找出相符合的最長前置位元例如有一個 8-bit 的 IP 目的位址 ( ), 從左到右依序往下搜尋, 可以發現相符合的前置位元長度有 B (01*) 和 C( *) 二項與 IP 目的位址相符合, 在圖 1 中用粗線表示其搜尋路徑, 我們找到了符合 IP 目的位址 ( ) 的最長前置位元並將下一站 C 輸出本篇論文架構如下, 第二節是二元決策圖 (binary decision diagram, BDD) 演算法的介紹, 第三節介紹使用二元決策圖來實作 IP 路徑查表演算法, 第四節為模擬與 FPGA 實現, 最後第五節是結論 2. BDD 演算法二元決策圖 (binary decision diagram, BDD)[3, 4, 8] 已經廣泛應用於邏輯合成 (logic synthesis) 和驗證上, 首先我們介紹 BDD 的架構, 如表 2 為建立二元決策圖的簡單範例, 其中目的位址欄位有三個位元,NHP 欄位只有一個位元根據表 2, 我們可建立出如圖 2 所示的二元決策樹 (binary decision tre e) 和圖 3 所示的 BDD 決策圖如圖 2 和圖 3 所示,BDD 可以有效率地刪除二元樹中的重複的節點 ( 由 15 個節點減少為 7 個節點 ), 不僅降低了電路的成本而且提升了路由器查表搜尋的處理速度圖 1. Trie 架構示意圖

3 二元決策圖為基礎的 IP 路徑查表演算法之設計與 FPGA 實現表 2 建立二元決策圖的簡單範例點和最右邊的 D 3 節點具有相同值的葉節點 1, 所以可將最右邊的 D 3 節點移除, 結果如圖 5 所示最後, 若節點 v 存在有相等的左 (0) 子節點與右 (1) 子節點, 則可將節點 v 移除, 並將所有原來指向節點 v 的邊重新指向節點 v 的左 (1) 子節點, 如圖 5 中最左邊之 D 3 節點, 因其左子節點和右子節點相同, 所以可將此節點移除, 結果如圖 6 所示圖 2. 表 2 所建立二元決策樹圖 4. 由圖 2 化簡所得圖 3. 表 2 所建立的 BDD 決策圖在 BDD 架構中, 其節點的化簡過程有三個步驟, 首先, 將具有相同值的葉節點 (leaf node) 由單一節點來取代, 並將所有原先指向這些節點的邊 (edge) 重新指向這個單一節點, 如圖 2 中, 葉節點的值僅有 0 和 1, 因此可化簡成如圖 4 所示第二步, 由底層至頂層對所有節點作處理, 假如兩個節點 u 和 v 相等, 則可將節點 v 移除, 並將所有原來指向節點 v 的邊重新指向節點 u, 如圖 4 中最左邊的 D 3 節圖 5. 由圖 4 化簡所得 D D 2 D D 3 D 圖 6. 由圖 5 化簡所得之 BDD( 和圖 3 相同 )

4 龍華科技大學學報第二十三期, 我們將 BDD 演算法的製作分三部份來介紹, 首先介紹設計 BDD 演算法時所建立的 BDD 節點 (BDD_node) 資料結構, 如圖 7 所示, 其中,terminal 欄位中的值為 0 表示非最終節點 ; 值為 1 表示最終節點, v 欄位表示 BDD 節點之內含值 (value), 此欄位只在 terminal 欄位值為 1 時有其內含值, 若 terminal 欄位值為 0 時則忽略其內含值, 所以當 v 值為 1 時表示此節點是最終節點其內含值為 1,v 值為 0 時表示此節點是最終節點其內含值為 0, pos 欄位表示節點在 BDD 樹狀架構的階層 (level) 值,left 為指向左子節點的指標, right 為指向右子節點的指標圖 7. BDD 節點資料結構第二部份我們使用遞迴方式來建立 BDD 架構, 其演算法之虛擬碼 (pseudo-code) 如下所示 : 第三部份是雜湊表 (hashtable) 的建立及查尋, 此雜湊表主要用途是查尋 BDD 節點是否存在其演算法之虛擬碼 (pseudo-code) 如下所示 : 3. BDD 實作 IP 路徑查表演算法目前已有使用 B DD 來製作 IP 路徑查尋演算法 [13, 14], 他們的方法是使用 Verilog 與邏輯合成的設計分析工具來實作, 為了降低開發成本, 我們將 BDD 的每一個節點以多工器來設計, 並以 Altera 公司生產之 Stratix EP1S40F780C5 FPGA 來實現在實作部份, 我們的路由器查表搜尋電路的產生可分為兩個階段, 第一階段, 我們根據表 1 簡單路徑表規則來建立出 BDD 決策圖首先, 我們將表 1 轉換如表 3 所示, 其中前置位元 (Prefix) 欄位有八個位元,NHP 欄位有四個位元,NHP 欄位為對表 1 中的 NHP(Next hop) 欄位進行編碼, 由於共有 9 筆不同的下一站位址, 所以我們使用 4 位元的二進制編碼方式來進行編碼, 分別是 A 為 0000 B 為 0001 C 為 0010 D 為 0011 E 為 0100 F 為 0101 G 為 0110 H 為 0111 I 為 1000, 透過上述編碼方式, 我們可以分別建立出四組不同輸出的 BDD 決策圖如圖 8(a) 8(b) 8(c) 及 8(d) 所示從圖 8 中, 我們可看出 BDD 可以有效率地刪除二元樹中的重複的節點, 如此不僅降低了電路的成本而且提升了路由器查表搜尋的處理速度

5 二元決策圖為基礎的 IP 路徑查表演算法之設計與 FPGA 實現在第二階段, 我們依照所建立 BDD 決策圖來產生相對應的組合 (combinational) 電路, 在 BDD 決策圖中的每一個節點我們使用多工器 () 來代替, 多工器的輸入為 0 或 1, 節點內含值當作多工器選擇線的輸入如圖 9(a) 9(b) 9(c) 及 9(d) 所示, 即為圖 8 (a) 8(b) 8(c) 及 8(d) 之 BDD 決策圖的多工器組合電路表 3 路徑表資料庫圖 8(b). 表 3 NHP 欄位為 V 2 所建立的 BDD 決策圖圖 8(a). 表 3 NHP 欄位為 V 1 所建立的 BDD 決策圖圖 8(c). 表 3 NHP 欄位為 V 3 所建立的 BDD 決策圖

6 龍華科技大學學報第二十三期, 圖 8(d). 表 3 NHP 欄位為 V 4 所建立的 BDD 決策圖圖 9(b). 圖 8(b) 之 BDD 決策圖的多工器組合電路 OUT OUT D1 D1 D2 D3 D2 D3 D4 D4 D5 D5 D6 D6 D7 D7 D 圖 9(a). 圖 8(a) 之 BDD 決策圖的多工器組合電路圖 9(c). 圖 8(c) 之 BDD 決策圖的多工器組合電路

二元決策圖為基礎的 IP 路徑查表演算法之設計與 FPGA 實現最後, 我們將 BDD 決策圖建立的組合電路以 Altera 公司生產之 Stratix EP1S40F780C5 FPGA 來實現, 其總邏輯元素 (total logic elements) 使用率是小於 1 %, 在

模擬與 FPGA 實現根據這些多工器組合電路我們使用 Altera 公司之 Quartus II 發展軟體 [1, 2, 16] 來發展與模擬 BDD 決策圖, 並且以 FPGA 實現所建立的組合電路, 其模擬波形圖如圖 10 所示由圖中可看出, 每 10ns 可執行 8 一次查表工作,

結論由於 BDD 具有節點共享的優點, 刪除重複的節點, 可以有效率地降低組合電路的成本, 而且提升了路由器查表搜尋的處理速度, 是一個適合 FPGA 實現的演算法在本論文中, 我們使用 BDD 方法設計出 IP 路徑查表演算法, 並將 BDD 的每一個節點以多工器來設計, 我們以

7 二元決策圖為基礎的 IP 路徑查表演算法之設計與 FPGA 實現最後, 我們將 BDD 決策圖建立的組合電路以 Altera 公司生產之 Stratix EP1S40F780C5 FPGA 來實現, 其總邏輯元素 (total logic elements) 使用率是小於 1 %, 在個邏輯元素上使用了 17 個邏輯元素 FPGA 的電路合成圖如圖 11 所示圖 9(d). 圖 8(d) 之 BDD 決策圖的多工器組合電路 4. 模擬與 FPGA 實現根據這些多工器組合電路我們使用 Altera 公司之 Quartus II 發展軟體 [1, 2, 16] 來發展與模擬 BDD 決策圖, 並且以 FPGA 實現所建立的組合電路, 其模擬波形圖如圖 10 所示由圖中可看出, 每 10ns 可執行 8 一次查表工作, 亦即 10 lookups/second 若以每封包大小平均為 40 bytes 來計算, 則我們演算法可支援至最快 4Gbps 的連線速率圖 11. BDD 多工器 FPGA 電路合成圖 5. 結論由於 BDD 具有節點共享的優點, 刪除重複的節點, 可以有效率地降低組合電路的成本, 而且提升了路由器查表搜尋的處理速度, 是一個適合 FPGA 實現的演算法在本論文中, 我們使用 BDD 方法設計出 IP 路徑查表演算法, 並將 BDD 的每一個節點以多工器來設計, 我們以 Altera 公司生產之 Stratix EP1S40F780C5 FPGA 來實現, 其總邏輯元素使用率是小於 1%, 在個邏輯元素上使用了 17 個邏輯元素, 我們成功地以多工器將它以場效可程式化邏輯陣列硬體實現實作模擬的結果 8 顯示, 我們的演算法每秒可執行 10 次查表工作, 若以每封包大小平均為 40 bytes 來計算, 則我們演算法可支援至最快 4Gbps 的連線速率誌謝圖 10. BDD 多工器組合電路模擬波形圖作者要感謝龍華科技大學在設備與經費上的援助, 使本研究能夠順利完成

8 龍華科技大學學報第二十三期, 參考文獻 1. 陸瑞強, 廖裕評, 系統晶片設計使用 Quartus II, 全華科技圖書股份有限公司 (2005) 2. 鄭信源,Verilog 硬體描述語言數位電路設計實務, 儒林圖書有限公司 (2000) 3. Akers, S. B. Binary Decision Diagrams, IEEE Transactions on Computers, C-27, 6, (1978). 4. Bryant, R. E. Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, C-35, 8, (1986). 5. Cheung, G. and McCanne S. Optimal Routing Table Design for IP Address Lookups under Memory Constraints, th Proceedings of the 18 Annual Joint Conference of the IEEE Computer and Communications Societies, 3, (1999). 6. Doeringer, W., Karjoth, G. and Nassehi, M. Routing on longest-matching prefixes, IEEE/ACM Transactions on Networking, 4, 1, (1996). 7. Fuller, V., Li, T., Yu, J. and Varadhan, K. Classless Inter-Domain Routing(CIDR): an Address Assignment and Aggregation Strategy. RFC1519, (1993). 8. Gerez, S. H., Algorithms for VLSI Design Automation, John Wiley & Sons Ltd, (1999). 9. Gupta, P., Lin, S. and McKeown, N. Routing lookups in hardware at memory access speeds, Proceedings of the 17 th Annual Joint Conference of the IEEE Computer and Communications Societies, 3, (1998). 10. Nen-Fu Huang and Shi-Ming Zhao A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers, IEEE Journal on selected areas in Communications, 17, 6, (1999). 11. Nilsson, S. and Karlsson, G. IP-Address Lookup using LC-Tries, 17, 6, (1999). 12. Pi-Chung Wang, Chia-Tai Chan and Yaw-Chung Chen A fast IP routing lookup scheme, Proceedings of the IEEE International Conference on Communications, 2, (2000). 13. Sangireddy, R. and Somani, A. K. Binary Decision Diagrams for Efficient Hardware Implementation of Fast IP Routing Lookups, Proceedings of 10 th International Conference on Computer Communications and Networks, (2001). 14. Sangireddy, R. and Somani, A. K. High-Speed IP Routing With Binary Decision Diagrams Based Hardware Address Lookup Engine, IEEE Journal on selected areas in Communications, 21, 4, (2003). 15. Tzeng, H.H.-Y. and Przygienda, T. On Fast Address Lookup Algorithms, IEEE Journal on selected areas in Communications, 17, 6, (1999)

9 二元決策圖為基礎的 IP 路徑查表演算法之設計與 FPGA 實現 A Fast IP Routing Lookup Algorithm with Binary Decision Diagrams and Implementation Using FPGA Chi-Cheng Wu Jing-Wun Shih Dong-Shiuh Wu Jia-Long Wu Huang-Sen Chiu Department of Electronic Engineering Lunghwa University of Science and Technology Abstract 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 an 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 8 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. Keywords:router, binary decision diagrams(bdds), field programmable gate array (FPGA)

Microsoft PowerPoint - Aqua-Sim.pptx

Microsoft PowerPoint - Aqua-Sim.pptx Peng Xie, Zhong Zhou, Zheng Peng, Hai Yan, Tiansi Hu, Jun-Hong Cui, Zhijie Shi, Yunsi Fei, Shengli Zhou Underwater Sensor Network Lab 1 Outline Motivations System Overview Aqua-Sim Components Experimental