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

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

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

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

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