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

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

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

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

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