一種NDN數據名查找方法及系統與流程

2023-06-04 04:04:31 3

本發明涉及gpu應用的名字查找領域，特別是一種ndn數據名查找方法及系統。

背景技術：

ndn是相對於如今的tcp/ip網絡架構提出來的一種新型的網絡架構，它關注的是我們希望轉發的內容而不是轉發的地址。在ndn網絡中存在兩種類型的數據包：興趣包和數據包。在這兩種數據包裡均包含內容的名字，也即是數據名，它也是我們在查找轉發數據包時的核心所在。因此在ndn網絡中數據名的查找變得十分關鍵，但是由於數據名的複雜，長度不定且大多數情況下都較長等特性，使得數據名的存儲空間開銷變得十分之大，進而也導致數據名查找的時間開銷變得很大，所以想要實現快速且存儲開銷不大的數據名查找具有重要的實際應用價值。

gpu作為一種高效的並行處理的機制已經越來越受到大家的關注，相比於cpu，它在計算密集，高度並行等情況下都具有更大的優勢。因此，通過對gpu的利用從而來解決數據名查找問題就成為熱點問題，但是目前沒有有效的處理方案。

技術實現要素：

本發明所要解決的技術問題是，針對現有技術不足，提供一種ndn數據名查找方法及系統，同時兼顧高查找性能與低存儲消耗的平衡問題。

為解決上述技術問題，本發明所採用的技術方案是：一種ndn數據名查找方法，包括以下步驟：

1）設計並實現基於gpu的數據結構候選對齊遷移數組cata（candidate-alignedtransitionarray,cata）；

2）在cpu上運行cata的構建算法和更新算法；

3）將cata從cpu端傳輸到gpu端；

4）在gpu上運行基於cata的數據名查找算法；

5）不斷調整gpu的運行參數，使得查找性能達到最優。

步驟1）的具體實現過程包括：

1）將ndn數據名表進行劃分，變成以斜槓為分割的多組件形式；

2）將新得到的多組件形式的數據名表以組件為單位構建有限狀態機fsm；

3）將有限狀態機fsm中的每個狀態的所有分支分配兩個候選位置，兩個候選位置分別由兩個哈希函數得到；

4）依次將每個狀態的所有分支存入同一個對齊遷移數組，每個分支的存儲過程為：首先查詢當前分支的第一個候選位置是否為空，如果為空則將該分支存入；如果不為空，表示該候選位置已被使用，則查找第二個候選位置是否為空，如果為空則存入；如果不為空，說明兩個候選位置該分支均無法存入，則在兩個候選位置的基礎上增加某一偏移量形成新的候選位置再次按照剛剛的方法重新進行存儲。如果嘗試所有偏移量後均不能無衝突的存儲該狀態的所有分支，則選擇新的對齊遷移數組進行存儲；

5）重複步驟4），直至所有狀態的所有分支均已存入對齊遷移數組，所有的對齊遷移數組構成了cata。

步驟4）的具體實現過程包括：

1）設置每一個對齊遷移數組的大小均為素數，將每個狀態的所有分支存儲在同一個對齊遷移數組；

2）當某個狀態的分支與別的狀態的分支發生衝突時，則將其中分支數較少的一個狀態進行遷移；每個對齊遷移數組均記錄當前空餘位置的總數，當某個狀態選擇對齊遷移數組進行存儲時，預先判斷該對齊遷移數組的空餘位置是否足夠存儲該狀態的所有分支，如果不足則需要換一個新的對齊遷移數組進行判斷，直至該對齊遷移數組滿足空餘位置總數大於等於當前準備存儲的狀態的總分支數的要求為止。

相應地，本發明還提供了一種ndn數據名查找系統，包括：

對齊遷移數組cata；

cpu：用於運行對齊遷移數組cata的構建算法和更新算法；

傳輸單元：用於將對齊遷移數組cata從cpu端傳輸到gpu端；

gpu：用於運行基於對齊遷移數組cata的數據名查找算法；

調整單元：用於不斷調整gpu的運行參數，使得查找性能達到最優。

與現有技術相比，本發明所具有的有益效果為：本發明提供了一種根據多哈希機制設計出來的候選對齊遷移數組的數據結構與算法，使得解決數據名查找問題時，能夠同時兼顧高查找性能與低存儲消耗的平衡問題，具有重要的實際應用價值；在ndn數據名查找領域，提供了一種基於gpu的進行數據名查找的高查找性能與低存儲消耗模型，對網絡設備的輕量級實現具有重要的實用價值。

附圖說明

圖1是基於gpu的ndn高效數據名查找流程圖；

圖2是ndn數據包轉發過程圖；

圖3是本發明的cata方法與另一同類型數據名查找方法多對齊遷移數組（mata）的存儲消耗對比圖；

圖4是cata與mata的存儲利用率對比圖；

圖5是cata與mata的查找延時對比圖；

圖6是cata與mata的查找吞吐率對比圖。

具體實施方式

參考圖1，本發明包括以下步驟：

步驟1，開始基於gpu的數據名查找任務，並初始化運行環境。cpu的編程環境為codeblocks-c++；gpu的編程環境為nvidia-cuda。

步驟2，設計並實現數據結構cata。其中，cata的原理是根據多哈希得到的多候選位置來進行對齊遷移數組的存儲。

步驟3，在cpu端實現cata的構建與更新算法。

步驟4，將cata的存儲數據從cpu端傳輸到gpu端。

步驟5，在gpu端運行基於cata的數據名查找算法，並不斷調整gpu運行參數使得查找性能最優化。其中，調整參數有gpu多線程數，多流數量等。

步驟6，將查找結果從gpu端傳輸回cpu端。

參考圖2，是ndn數據包轉發過程圖，解釋了ndn中數據包轉發的具體過程。在ndn的兩種數據包：興趣包和數據包裡均包含了數據名，並且實際查找中也是以數據名作為轉發的關鍵。

圖3是cata方法與另一同類型數據名查找方法多對齊遷移數組（mata）的存儲消耗對比圖，表示隨著數據規模的不斷擴大下cata與mata的存儲消耗增長的過程。首先橫坐標的k的含義是：我們把3m的總實驗數據分成相等大小的10份，每次選擇前k份作為第k次的實驗數據，然後進行數據名查找實驗。縱坐標則是存儲消耗的大小，從實驗結果可以看出我們的cata在隨著數據規模的增大下是線性增長的，並且最大存儲消耗為50m左右，是mata的五分之一左右，這足以說明我們在存儲消耗上的優勢。

圖4是cata與mata的存儲利用率對比圖，從圖中可以看出cata在存儲利用率達到了90%左右，對比於mata的低存儲利用率，可以發現cata的多候選位置原理的優點所在了。

圖5是cata與mata的查找延時對比圖。從圖中看出，cata的平均查找延時在100us左右，只是略高於mata，說明在降低了存儲開銷的同時查找性能也並未下降。

圖6是cata與mata的查找吞吐率對比圖。可以發現cata的吞吐率也和mata持平，也再次證明了cata在查找性能上依舊錶現不俗。