基本信息
- 項目名稱：
- 基于NoC的分布式路由器
- 小類：
- 信息技術
- 大類：
- 科技發(fā)明制作A類
- 簡介：
- 本項目采用2D Mesh片上網(wǎng)絡NoC（Network on Chip）體系結(jié)構(gòu)，提出了一種分布式查找的路由器的結(jié)構(gòu)，制定了NoC節(jié)點之間的通信協(xié)議，構(gòu)造了通用可配置路由器的驗證環(huán)境，在NetFPGA平臺上設計并實現(xiàn)了一個路由器軟硬件系統(tǒng)。通過PCI接口，SCONE軟件可完成路由器轉(zhuǎn)發(fā)表和控制寄存器的配置并讀取查找信息，Linux GUI界面實時的顯示路由器當前的工作狀態(tài)和分布式轉(zhuǎn)發(fā)表的性能信息。
- 詳細介紹：
- 設計目的： 在短線互連Mesh結(jié)構(gòu)上提出分布式并行地址查找算法，提高核心路由器SoC系統(tǒng)的性能，并為解決深亞微米工藝下，集成電路設計中出現(xiàn)的“紅磚墻（Red Brick Wall）”問題提供一種方案。 基本思路： 1．利用片上網(wǎng)絡NoC思想，在Mesh網(wǎng)絡上，實現(xiàn)分布式IP地址并行查找； 2．單節(jié)點的查找采用Tree Bitmap算法，硬件實現(xiàn)采用流水線設計方法； 3．構(gòu)建通用可配置IP路由器驗證平臺，并利用該平臺對路由器設計進行驗證； 4．用FPGA實現(xiàn)路由器原型系統(tǒng)，開發(fā)路由器軟件系統(tǒng)，組網(wǎng)測試。 創(chuàng)新點： 1．采用規(guī)則的Mesh結(jié)構(gòu)連接IP地址查找節(jié)點，實現(xiàn)各個節(jié)點之間的并行計算。該結(jié)構(gòu)具有良好的擴展性，系統(tǒng)處理能力隨著節(jié)點的增多而提高。同時節(jié)點之間采用短線連接，可以避免深亞微米工藝下集成電路設計的“紅磚墻”問題，為未來工藝下查找和交換融合的路由器設計提供了一種解決思路； 2．采用分布式存儲原理，將路由表按照一定策略劃分并存儲在各個查找節(jié)點上，路由表存儲開銷不隨Mesh結(jié)構(gòu)的節(jié)點的增多而增加； 3．開發(fā)了通用可配置IP路由器驗證平臺，通過配置該平臺可以對查找引擎、交換結(jié)構(gòu)及硬件數(shù)據(jù)平面進行仿真驗證，也可進行FPGA測試； 4．采用流水線的方法設計并實現(xiàn)了基于Tree Bitmap的IP地址查找引擎，該引擎平均每2個時鐘周期完成1個IP地址查找。 技術關鍵： 1．用片上網(wǎng)絡NoC的思想實現(xiàn)分布式IP地址并行查找需要制定片上網(wǎng)絡通信協(xié)議，該協(xié)議的優(yōu)劣直接影響到片上通信的性能； 2．為了增加IP地址查找的吞吐量，采用硬件流水線的設計方法實現(xiàn)Tree Bitmap查找算法； 3．為了實現(xiàn)分布式查找，將整個路由表劃分為N份，存儲在N個查找節(jié)點上，該表項的劃分策略直接影響到片上通信與各查找節(jié)點的負載均衡； 4．在分布式系統(tǒng)中，各節(jié)點處理時間不同，任務在片上網(wǎng)絡傳輸時間也不同。這便會造成任務順序輸入，亂序輸出。因此任務的保序處理是分布式并行系統(tǒng)的關鍵問題； 5．片上網(wǎng)絡NoC和路由器的功能驗證與性能統(tǒng)計是保證系統(tǒng)正確，穩(wěn)定工作的關鍵。 主要技術指標： 基于2×2 Mesh結(jié)構(gòu)實現(xiàn)分布式IP轉(zhuǎn)發(fā)引擎，在Xilinx V2芯片上處理速度可以達到62.5Mpps(系統(tǒng)時鐘125MHz)。該轉(zhuǎn)發(fā)結(jié)構(gòu)具有非常好的擴展性，在更高端的FPGA上或者ASIC設計中，其性能隨著系統(tǒng)時鐘頻率的提高和Mesh的節(jié)點增多而提高。 科學性與先進性： 1．基于Mesh結(jié)構(gòu)的NoC實現(xiàn)分布式IP地址查找，實現(xiàn)各個節(jié)點之間的并行計算，各節(jié)點之間采用短線連接。 (1)清華大學提出的分布式并行路由查找框架（Distributed Parallel Router Lookup Framework，DPRLF）[1]是分布式并行計算在地址查找中的典型應用。本設計的結(jié)構(gòu)與DPRLF相比的優(yōu)勢在于采用NoC的思想，具有大規(guī)模集成、擴展性強、可復用性強等優(yōu)點。 (2)Venkatesh等提出的基于分布式存儲的高性能并行IP地址查找技術[2]，該技術采用與DPRLF類似的體系結(jié)構(gòu)。該系統(tǒng)實現(xiàn)分布式路由表存儲，各子查找單元完成獨立無關IP查找。該結(jié)構(gòu)具有16個子查找單元，采用集中式任務分配。與該結(jié)構(gòu)相比本作品具有NoC中短線互聯(lián)的優(yōu)勢，片上通信效率高、擴展性強、可復用性強和分布式任務分配等優(yōu)點。 (3)Baboescu等在基于Trie樹的IP地址查找引擎體系結(jié)構(gòu)[3]中，提出了利用單端口存儲器構(gòu)建一種環(huán)形的IP地址查找流水線——Ring Pipeline，提高了路由信息表到流水線結(jié)點映射的靈活性。與該結(jié)構(gòu)相比本設計的優(yōu)勢在于，基于NoC的結(jié)構(gòu)，任務可以按照片上路由算法到相應的節(jié)點進行查找計算而不必按流水線經(jīng)過每一級，這樣的優(yōu)勢在于縮短任務傳輸延遲。與該結(jié)構(gòu)相比本作品所采用的結(jié)構(gòu)同樣具有大規(guī)模集成，擴展性強等優(yōu)點。 2．對樹位圖(Tree bitmap)[4]傳統(tǒng)的設計方法進行了改進，采用流水線的方法設計并實現(xiàn)了基于Tree Bitmap的IP地址查找引擎，在延時不變的基礎上使吞吐量增加了3倍 參考文獻： [1].鄭凱, 高性能IP路由查找和分組分類技術的研究, 2006, 清華大學: 北京 [2].Venkatesh, K., et al. A high performance parallel IP lookup technique using distributed memory organization. 2004. Las Vegas, Nevada: IEEE Computer Society. [3].Baboescu, F., et al. A tree based router search engine architecture with single port memories. 2005: IEEE Computer Society. [4].Eatherton, W., G. Varghese and Z. Dittia, Tree bitmap: hardware/software IP lookups with incremental updates. ACM SIGCOMM Computer Communication Review, 2004. 34(2): p. 97-122. 本作品滿足OC-192標準的核心路由器標準，可直接用于OC-192標準的核心網(wǎng)絡。 本作品采用Xilinx-Virtex2實現(xiàn)。由于受FPGA資源限制，硬件的工作頻率為125MHz時鐘頻率，處理速度為62.5Mpps（可處理32Gbps線速的數(shù)據(jù)），滿足OC-192標準（10Gbps）。如果采用性能更高的FPGA或者采用最新工藝的ASIC設計，節(jié)點的規(guī)模與工作頻率都可以得到大幅度的提高，可滿足OC-768標準（40Gbps），同時也可擴展更多接口。對協(xié)議管理軟件及外圍電路進一步完善優(yōu)化會更有市場價值與市場競爭力。
作品圖片
作品專業(yè)信息
設計、發(fā)明的目的和基本思路、創(chuàng)新點、技術關鍵和主要技術指標
- 設計目的：在短線互連Mesh結(jié)構(gòu)上提出分布式并行地址查找算法，提高核心路由器SoC系統(tǒng)的性能。 基本思路：1．利用片上網(wǎng)絡NoC思想，在Mesh網(wǎng)絡上，實現(xiàn)分布式IP地址并行查找；2．單節(jié)點采用Tree Bitmap算法，硬件實現(xiàn)采用流水線；3．構(gòu)建通用可配置IP路由器驗證平臺對路由器設計進行驗證；4．用FPGA實現(xiàn)路由器原型系統(tǒng)，組網(wǎng)測試。 創(chuàng)新點：1．采用Mesh結(jié)構(gòu)連接IP查找節(jié)點，實現(xiàn)各個節(jié)點間的并行計算。該結(jié)構(gòu)擴展性好，系統(tǒng)處理能力隨著節(jié)點的增多而提高；2．采用分布式存儲原理，將路由表按照負載均衡策略劃分并存儲在各個查找節(jié)點上，路由表存儲開銷不隨Mesh結(jié)構(gòu)的節(jié)點的增多而增加；3．開發(fā)通用可配置IP路由器VMM驗證平臺，通過配置該平臺可以對查找引擎、交換結(jié)構(gòu)及硬件數(shù)據(jù)平面進行驗證與FPGA測試；4．采用流水線的方法實現(xiàn)了Tree Bitmap的IP查找引擎。 技術關鍵：1．制定片上網(wǎng)絡NoC的片上網(wǎng)絡通信協(xié)議，該協(xié)議的優(yōu)劣直接影響到片上通信的性能；2．采用硬件流水線的設計并實現(xiàn)Tree Bitmap查找算法；3．將整個路由表劃分并存儲在N個查找節(jié)點上，且制定負載均衡策略；4．實現(xiàn)任務的保序處理，解決分布式系統(tǒng)中的亂序問題。 主要技術指標：2×2 Mesh結(jié)構(gòu)的分布式IP轉(zhuǎn)發(fā)引擎，在Xilinx V2芯片上處理速度可達到62.5Mpps(時鐘125MHz)。該轉(zhuǎn)發(fā)結(jié)構(gòu)具有很好的擴展性，在高端FPGA上或者ASIC實現(xiàn)，其性能隨著時鐘頻率的提高和節(jié)點的增多而提高。
科學性、先進性
- 1．基于Mesh結(jié)構(gòu)的NoC實現(xiàn)分布式IP地址查找，實現(xiàn)各個節(jié)點之間的并行計算，各節(jié)點之間采用短線連接。(1)清華大學提出了分布式并行路由查找框架[1]。本作品的優(yōu)勢在于采用NoC的思想，具有大規(guī)模集成、擴展性強、可復用性強等優(yōu)點。(2)文獻[2]提出的基于分布式存儲的高性能并行IP地址查找技術。與該結(jié)構(gòu)相比本作品具有NoC中短線互聯(lián)的優(yōu)勢，片上通信效率高、擴展性強、可復用性強和分布式任務分配等優(yōu)點。(3)文獻[3]在基于Trie樹的IP地址查找引擎體系結(jié)構(gòu)中，提出了利用單端口存儲器構(gòu)建一種環(huán)形的IP地址查找流水線。與該結(jié)構(gòu)相比本設計的優(yōu)勢在于，任務可以按照片上路由算法到相應的節(jié)點進行查找計算而不必按流水線經(jīng)過每一級，縮短任務傳輸延遲，且同樣具有大規(guī)模集成，擴展性強等優(yōu)點。 2．對樹位圖[4]傳統(tǒng)的設計方法進行了改進，采用流水線的方法設計并實現(xiàn)了基于Tree Bitmap的IP地址查找引擎，在延時不變的基礎上使吞吐量增加了3倍。 （參考文獻見表C：國內(nèi)外同類課題研究水平概述）
獲獎情況及鑒定結(jié)果
- 無
作品所處階段
- 實驗室階段
技術轉(zhuǎn)讓方式
- IP授權
作品可展示的形式
- 實物、現(xiàn)場演示、錄像
使用說明,技術特點和優(yōu)勢,適應范圍,推廣前景的技術性說明,市場分析,經(jīng)濟效益預測
- 本作品滿足OC-192標準的核心路由器標準，可直接用于OC-192標準的核心網(wǎng)絡。 本作品采用Xilinx-Virtex2實現(xiàn)。由于受FPGA資源限制，硬件的工作頻率為125MHz時鐘頻率，處理速度為62.5Mpps（可處理32Gbps線速的數(shù)據(jù)），滿足OC-192標準（10Gbps）。如果采用性能更高的FPGA或者采用最新工藝的ASIC設計，節(jié)點的規(guī)模與工作頻率都可以得到大幅度的提高，可滿足OC-768標準（40Gbps），同時也可擴展更多接口。對協(xié)議管理軟件及外圍電路進一步完善優(yōu)化會更有市場價值與市場競爭力。
同類課題研究水平概述
- 一.基本查找算法 1．線性查找算法：線性查找算法按照線性表的方式來組織路由前綴信息。2．基于樹的查找算法：基于Trie樹的算法是IP地址查找的經(jīng)典算法之一。根據(jù)前綴的二進制比特值，將路由前綴映射到Trie樹的結(jié)點上。3．二分查找算法：二分查找的算法是將最長前綴匹配分解成一系列的精確匹配。該算法具有良好的可擴展性，但有較大的存儲的復雜度。4．基于范圍的查找算法：基于范圍的IP地址查找技術將前綴看作是整個IP地址空間內(nèi)的一個“區(qū)間”，不同的前綴將整個地址空間分成多個子區(qū)間。5．基于Hash的查找算法：基于Hash的算法根據(jù)路由前綴某個特定的Hash函數(shù)值，構(gòu)造Hash表對前綴進行組織和存儲。但是Hash沖突的存在，使得該查找算法的最好和最壞情況下的性能差異較大。6．基于TCAM的查找算法：TCAM是一種基于內(nèi)容尋址的存儲器件，在IP地址查找中用來存儲路由信息表項。TCAM由于其高速的查找性能和確定的查找延遲， 廣泛地用于商用路由器中。然而，TCAM芯片價格昂貴，功耗大，難以大規(guī)模集成。 二.并行IP查找結(jié)構(gòu) （參見作品先進性與科學性） 參考文獻： [1].鄭凱, 高性能IP路由查找和分組分類技術的研究, 2006, 清華大學: 北京 [2].Venkatesh, K., et al. A high performance parallel IP lookup technique using distributed memory organization. 2004. Las Vegas, Nevada: IEEE Computer Society. [3].Baboescu, F., et al. A tree based router search engine architecture with single port memories. 2005: IEEE Computer Society. [4].Eatherton, W., G. Varghese and Z. Dittia, Tree bitmap: hardware/software IP lookups with incremental updates. ACM SIGCOMM Computer Communication Review, 2004. 34(2): p. 97-122.
