基于GPU動態(tài)IP查找架構(gòu)的分析與研究.pdf

1、隨著社會信息化步伐的加快,信息通訊的重要性正在逐步突顯。作為信息通訊形式之一的網(wǎng)絡(luò)通訊扮演著重要角色。當前,光纖技術(shù)的出現(xiàn),使得點對點的信息傳輸速度達到了幾百Gbps,這信息傳輸帶寬已經(jīng)能夠滿足現(xiàn)在的信息傳輸量。然而,作為網(wǎng)絡(luò)中轉(zhuǎn)站的路由器限制了網(wǎng)絡(luò)的整體速度。目前,實際路由速度才幾十個Gbps,遠遠無法滿足信息通訊的帶寬要求。因此,研究快速、高效的路由架構(gòu)及相應(yīng)的更新算法在路由表的查找、刪除、插入/更新等技術(shù)中具有重要的意義。本文著力

2、于研究快速、有效的路由架構(gòu)及對應(yīng)的算法,主要工作有:
　　1)針對軟件路由速度慢和硬件路由擴展性弱、內(nèi)存小、價格昂貴等缺點,提出一種基于GPU并行多Hash動態(tài)IP查找架構(gòu)。該架構(gòu)包含兩部分,第一部分是Host端與Device端的數(shù)據(jù)傳輸,其中包括將CPU預(yù)處理的IP數(shù)據(jù)包頭部信息傳給GPU和返回處理完后的結(jié)果給CPU兩部分;第二部分是GPU對IP數(shù)據(jù)包頭部信息的處理。首先,CUDA提供了Host端與Device端的數(shù)據(jù)傳輸模塊;

3、另外,我們依據(jù)IP地址前綴長度的分布特性對相同長度的IP地址Hash索引后,存儲于相應(yīng)的數(shù)組。同時,我們用另外一個表順序存儲沖突的IP地址。在采用AdaptiveOptimalXORHash函數(shù)后,保證沖突率低于1％。這也意味著,該架構(gòu)結(jié)合GPU硬件強大的并行處理能力能夠保證99%以上的查找訪存度為O(1),從而使得該架構(gòu)獲得十倍于軟件路由的查找速度,以及百倍于現(xiàn)有基于GPU路由的更新速度。
　　2)針對上述架構(gòu),我們在已有Has

4、h理論的基礎(chǔ)上,提出了構(gòu)造AdaptiveOptimalXORHash的理論。該理論基于比特之間的異或操作,統(tǒng)計樣本數(shù)據(jù)比特之間0和1的差值,依據(jù)差值進行比特的異或操作達到壓縮位數(shù)的效果。雖然該算法的時間復(fù)雜度是O(n3),但由于規(guī)則的更新是線下處理,所以這個時間復(fù)雜度可以被接受。實驗結(jié)果表明,該方法使得IP地址的沖突率低于1%,能夠大幅度提高架構(gòu)的查找速度。
　　3)針對企業(yè)的實際工程需求,設(shè)計和實現(xiàn)了一個基于GPU并行多Has