基于多核多線程網(wǎng)絡(luò)處理器的高性能IPv6路由查找算法研究.pdf

1、Internet骨干鏈路速度的不斷提高，要求Internet核心路由器必須以10Gbps或者更高的速度處理IP最長前綴匹配(LongestPrefixMatch，LPM)，這一問題已成為Internet核心路由器的主要性能瓶頸之一。IPv6地址的出現(xiàn)要求最長前綴匹配的查找長度從IPv4的32比特增加到128比特，使IP路由查找更加困難。 本文介紹了一個支持高速查找和快速增量更新的的IPv6路由查找算法TrieC，以及算法基于多核

2、多線程體系結(jié)構(gòu)IntelIXP2800網(wǎng)絡(luò)處理器(NetworkProcessorUnit，NPU)上的高效實現(xiàn)。 TrieC算法利用改進(jìn)的壓縮前綴擴(kuò)展(ModifiedCompactPrefixExpansion，MCPE)技術(shù)構(gòu)造固定高度為5的IPv6TrieC查找樹，在減少搜索次數(shù)提高查找性能的同時，消除了由傳統(tǒng)前綴擴(kuò)展引入的冗余信息存儲。通過仔細(xì)研究分析算法設(shè)計和實現(xiàn)之間的關(guān)系，TrieC將網(wǎng)絡(luò)處理器的體系結(jié)構(gòu)特征融入了

3、算法設(shè)計之中。 根據(jù)IPv4地址前綴分布特征、IPv6地址分配特點和現(xiàn)有IPv6路由表的統(tǒng)計特性，本文采用了三組不同前綴分布特征、每組各包含200K、300K和400K三個不同規(guī)模的共計九個IPv6路由表，對TrieC算法在IXP2800網(wǎng)絡(luò)處理器上進(jìn)行了性能模擬。實驗表明TrieC算法可以在IntelIXP2800網(wǎng)絡(luò)處理器上支持OC-192線速的IPv6路由查找，此外算法接近線性的加速比表明TrieC還可以獲得更高的查找速度

4、。 基于多核多線程體系結(jié)構(gòu)的NPU編程是一項具有挑戰(zhàn)性的工作，本文通過研究并行算法設(shè)計和體系結(jié)構(gòu)映射之間的關(guān)系，在網(wǎng)絡(luò)處理器上高效地實現(xiàn)了TrieC算法。本文詳細(xì)討論了在這種多核多線程體系結(jié)構(gòu)上設(shè)計實現(xiàn)網(wǎng)絡(luò)處理程序和算法的六個關(guān)鍵問題：內(nèi)存空間壓縮、指令選擇、數(shù)據(jù)分配、任務(wù)切分、長延遲隱藏和線程同步，并以TrieC算法實現(xiàn)為例提供了在網(wǎng)絡(luò)處理器上設(shè)計高性能算法和應(yīng)用程序、有效開發(fā)NPU體系結(jié)構(gòu)特性以克服算法實現(xiàn)中的性能瓶頸、以及