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