基于網(wǎng)絡(luò)處理器IXP2800的聚合組播路由并行查找算法的研究.pdf

1、組播作為一種高效網(wǎng)絡(luò)數(shù)據(jù)傳送技術(shù)，已經(jīng)在各種寬帶應(yīng)用領(lǐng)域得到廣泛應(yīng)用。目前，組播主干網(wǎng)的核心路由器速率已經(jīng)達(dá)到2.5Gbps~10Gbps，這一速率要求核心路由器每秒能夠轉(zhuǎn)發(fā)幾百萬乃至上千萬個(gè)以上的分組。分組轉(zhuǎn)發(fā)的重要一步就是查找路由表，因此快速的路由查找算法是實(shí)現(xiàn)高速分組轉(zhuǎn)發(fā)的關(guān)鍵． 本文根據(jù)組播路由轉(zhuǎn)發(fā)的特點(diǎn)，設(shè)計(jì)出一種基于網(wǎng)絡(luò)處理器(Network Processor Unit，NPU)的聚合路由并行查找的算法，并在多核多

2、線程體系結(jié)構(gòu)IntelIXP2800 NPU平臺(tái)上進(jìn)行編程實(shí)現(xiàn)，達(dá)到了OC-192的線速轉(zhuǎn)發(fā)性能。 組播路由查找是基于(組播組G，組播源S)二元組進(jìn)行的，與基于目的地址查找的單播路由相比更為復(fù)雜。同時(shí)未來報(bào)文的處理對算法提出了更高的性能需求?；谲浖?shí)現(xiàn)的查找算法雖然具有設(shè)計(jì)靈活等特點(diǎn)，但查找性能低，而基于硬件實(shí)現(xiàn)的查找算法又存在開發(fā)周期長、成本高和功耗大等問題。本文采用[30]中位圖映射的設(shè)計(jì)思想將二維查找轉(zhuǎn)化為一維查找，依據(jù)

3、組播路由的實(shí)際應(yīng)用背景，設(shè)計(jì)出基于IXP2800體系結(jié)構(gòu)的組播聚合路由轉(zhuǎn)發(fā)查找算法，克服了采用CAM/TCAM等硬件查找?guī)淼某杀靖吆蛯M播支持規(guī)模的限制。 IXP2800為Intel第二代多核多線程體系結(jié)構(gòu)網(wǎng)絡(luò)處理器，根據(jù)NPU的特性，本文設(shè)計(jì)了一種多處理器多線程可并行查找的組播路由算法。為研究算法的性能，分兩組不同前綴分布特征、分為500個(gè)和1000個(gè)組播組地址、每個(gè)組播組中分別包含不大于6個(gè)和不大于20個(gè)組播聚合源地址，8

4、種組播路由表轉(zhuǎn)發(fā)表的情況，對其在IXP2800上進(jìn)行性能測試。實(shí)驗(yàn)在Intel IXP2800網(wǎng)絡(luò)處理上通過優(yōu)化配置等方法可滿足OC-192線速轉(zhuǎn)發(fā)的性能。 基于多核多線程體系結(jié)構(gòu)的NPU編程是一項(xiàng)具有挑戰(zhàn)性的工作，通過研究并行算法設(shè)計(jì)和體系結(jié)構(gòu)映射之間的關(guān)系，在網(wǎng)絡(luò)處理器上高效實(shí)現(xiàn)了并行組播路由查找算法。本文著重?cái)⑹隽嗽谶@種多核多線程結(jié)構(gòu)上設(shè)計(jì)實(shí)現(xiàn)網(wǎng)絡(luò)處理程序和算法的五個(gè)關(guān)鍵問題：指令選擇、數(shù)據(jù)分配、任務(wù)切分、長延遲隱藏和線程