基本信息
- 項目名稱:
- 基于NoC的分布式路由器
- 小類:
- 信息技術(shù)
- 大類:
- 科技發(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地址查找。 技術(shù)關(guān)鍵: 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)的關(guān)鍵問題; 5.片上網(wǎng)絡NoC和路由器的功能驗證與性能統(tǒng)計是保證系統(tǒng)正確,穩(wěn)定工作的關(guān)鍵。 主要技術(shù)指標: 基于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地址查找技術(shù)[2],該技術(shù)采用與DPRLF類似的體系結(jié)構(gòu)。該系統(tǒng)實現(xiàn)分布式路由表存儲,各子查找單元完成獨立無關(guā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路由查找和分組分類技術(shù)的研究, 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)新點、技術(shù)關(guān)鍵和主要技術(shù)指標
- 設計目的:在短線互連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查找引擎。 技術(shù)關(guān)鍵:1.制定片上網(wǎng)絡NoC的片上網(wǎng)絡通信協(xié)議,該協(xié)議的優(yōu)劣直接影響到片上通信的性能;2.采用硬件流水線的設計并實現(xiàn)Tree Bitmap查找算法;3.將整個路由表劃分并存儲在N個查找節(jié)點上,且制定負載均衡策略;4.實現(xiàn)任務的保序處理,解決分布式系統(tǒng)中的亂序問題。 主要技術(shù)指標: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地址查找技術(shù)。與該結(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é)果
- 無
作品所處階段
- 實驗室階段
技術(shù)轉(zhuǎn)讓方式
- IP授權(quán)
作品可展示的形式
- 實物、現(xiàn)場演示、錄像
使用說明,技術(shù)特點和優(yōu)勢,適應范圍,推廣前景的技術(shù)性說明,市場分析,經(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地址查找技術(shù)將前綴看作是整個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路由查找和分組分類技術(shù)的研究, 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.