• / 11
  • 下載費用:30 金幣  

一種基于多重布隆過濾器的ICN網絡信息名字查找方法.pdf

摘要
申請專利號:

CN201510635608.6

申請日:

2015.09.30

公開號:

CN105260429A

公開日:

2016.01.20

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||實質審查的生效IPC(主分類):G06F 17/30申請日:20150930|||公開
IPC分類號: G06F17/30 主分類號: G06F17/30
申請人: 河南科技大學
發明人: 張明川; 鄭瑞娟; 吳慶濤; 魏汪洋; 趙海霞; 白秀玲; 寧召宇; 劉婷婷; 馬超
地址: 471000河南省洛陽市澗西區西苑路48號
優先權:
專利代理機構: 洛陽公信知識產權事務所(普通合伙)41120 代理人: 羅民健
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510635608.6

授權公告號:

||||||

法律狀態公告日:

2019.04.26|||2016.02.17|||2016.01.20

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

本發明公開一種基于多重布隆過濾器的ICN網絡信息名字查找方法,包括以下步驟:首先確定路由節點的是興趣包還是數據包,若為是興趣包,按照遞進關系在CS、PIT、FIB中查找興趣包所需的信息,若是數據包,按照遞進關系在CS、PIT查找興趣包所需的信息;本發明利用ICN網絡信息名字分段的特點,以段為單位進行并行名字查找,在每個段內,基于多重布隆過濾器實現信息名字的快速查找,提高信息名字檢索的效率,為名字路由快速轉發提供支持。

權利要求書

1.一種基于多重布隆過濾器的ICN網絡信息名字查找方法,其特征在于:包括以下步驟:步驟1、確定路由節點接收到的是興趣包還是數據包,其中,興趣包用來發送信息請求,數據包用來向請求節點返回所需信息;步驟2、若路由節點接收到興趣包時,按照下列步驟進行處理:步驟201:首先在CS中查找興趣包所需的信息,如果存在,則銷毀興趣包,并生成一個數據包沿興趣包的反方向發送給請求節點;步驟202:如果CS中不存在所請求信息,則在PIT中查找,如果存在,說明該路由節點已經轉發過相同的內容請求,則銷毀興趣包,并將接收到興趣包的接口記錄在PIT相應行后邊;步驟203:如果PIT中不存在,則在FIB中查找,如果存在,則將興趣包按照FIB的接口轉發,并將信息記錄在PIT中;如果FIB中不存在,則說明本路由節點不知道該興趣包的路由,銷毀該興趣包;步驟3、若路由節點接收到數據包時,按照下列步驟進行處理:步驟301:首先在CS中查找數據包所需的信息,如果存在則直接丟棄該數據包;步驟302:如果CS中不存在,則在PIT中查找,如果存在,則按照PIT記錄的接口進行轉發后,刪除PIT記錄,然后按照相應策略緩存數據包到CS中;步驟303:如果PIT中不存在,則直接丟棄該數據包;其中,在PIT、FIB和CS中查找信息名字包括以下步驟:將信息名字進行編碼,然后將編碼后的名字分段進行哈希計算,以計算后獲得的縱橫哈希值為下標,查找對應的布隆過濾器,如果所有的下標對應的值都不小于1,則表示PIT、FIB和CS中存在對應的名字信息,如果存在一個布隆過濾器對應位置值為0,則表示不存在該信息。2.如權利要求1所述的一種基于多重布隆過濾器的ICN網絡信息名字查找方法,其特征在于:所述步驟203和步驟302中的信息記錄包括以下步驟:向隆過濾器中插入信息時,根據相應哈希函數組對每段信息編碼進行哈希計算,獲得一個橫向哈希函數值,一個縱向哈希函數值,以這兩個值為布隆過濾器的縱橫下標,將對應位置的布隆過濾器元素值加1。3.如權利要求1所述的一種基于多重布隆過濾器的ICN網絡信息名字查找方法,其特征在于:所述步驟302中的刪除記錄包括以下步驟:當從布隆過濾器中刪除信息時,需要根據相應哈希函數組對擬刪除信息的每段編碼進行哈希計算,獲得一個橫向哈希函數值,一個縱向哈希函數值,以這兩個值為布隆過濾器的縱橫下標,判斷對應位置的布隆過濾器的元素值,如果該位置元素值大于等于1,則將該元素值減1,否則不做處理。

說明書

一種基于多重布隆過濾器的ICN網絡信息名字查找方法

技術領域

本發明涉及信息網絡技術領域,具體的說是涉及一種基于多重布隆過濾器的ICN網絡信息名字查找方法。

背景技術

隨著互聯網上應用的不斷發展變化,基于TCP/IP的現有互聯網也逐漸暴露出許多的不適應,比如,不安全、移動性差、可靠性差、靈活性差等問題。用戶在進行網絡訪問的時候,更多是關心“需要什么”,而不是關心“需要的東西在哪里”。但是現有互聯網是基于主機的通信模型,必須關注“在哪里”的問題。這種基于主機的通信模型已經不適合當前網絡發展的需要。

因此,如何從網絡中“拉”回用戶所需信息無疑成為ICN網絡需要解決的關鍵核心問題。對這一問題的研究必須改變理念,從傳統以主機為中心的通信模型轉換為以信息為中心的通信模型,建立支持信息“拉”式訪問的ICN網絡智慧路由機制。

所謂的信息中心網絡,就是網絡中的一切都可以看作是信息,可以說是一個信息互聯的網絡,而非主機互聯,其核心對象是信息,通過信息的名字標識每一個信息。ICN網絡采用面向信息的通信模型取代傳統面向主機的通信模型,以主機到網絡的“拉”式信息訪問取代傳統主機到主機的“推”式信息訪問,以緩存轉發路由取代傳統存儲轉發路由,可以從根本上解決當前網絡存在的問題。

對ICN網絡來說,其中流動的都是有名字的信息,整個網絡及其終端就在各種信息的驅動下運行起來了。網絡中存在海量的信息,網絡系統需要區別每一個信息。因此,如何從海里信息名字中找到所需信息,是ICN網絡研究的一種關鍵問題。因為,ICN網絡中信息的名字比較隨意(不像IP網絡中IP地址長度、格式固定)、信息名字數量巨大(遠大于IP網絡IP地址的數量),因此,對ICN網絡信息名字查找的效率要求更高。

發明內容

本發明為了解決上述技術問題,提供一種基于多重布隆過濾器的ICN網絡信息名字查找方法。該方法利用ICN網絡信息名字分段的特點,以段為單位進行名字查找。在每個段內,基于多重布隆過濾器實現信息名字的快速查找,提高信息名字檢索的效率,為名字路由快速轉發提供支持。

本發明所采用的技術方案是:一種基于多重布隆過濾器的ICN網絡信息名字查找方法,包括以下步驟:

步驟1、確定路由節點接收到的是興趣包還是數據包,其中,興趣包用來發送信息請求,數據包用來向請求節點返回所需信息;

步驟2、若路由節點接收到興趣包時,按照下列步驟進行處理:

步驟201:首先在CS中查找興趣包所需的信息,如果存在,則銷毀興趣包,并生成一個數據包沿興趣包的反方向發送給請求節點;

步驟202:如果CS中不存在,則在PIT中查找,如果存在,說明該路由節點已經轉發過相同的內容請求,則銷毀興趣包,并將接收到興趣包的接口記錄在PIT相應行后邊。

步驟203:如果PIT中不存在,則在FIB中查找,如果存在,則將興趣包按照FIB的接口轉發,并將信息記錄在PIT中;如果FIB中不存在,則說明本路由節點不知道該興趣包的路由,銷毀該興趣包;

步驟3、若路由節點接收到數據包時,按照下列步驟進行處理:

步驟301:首先在CS中查找數據包所需的信息,如果存在則直接丟棄該數據包;

步驟302:如果CS中不存在,則在PIT中查找,如果存在,則按照PIT記錄的接口進行轉發后,刪除PIT記錄,然后按照相應策略緩存數據包到CS中。

第三步:如果PIT中不存在,則直接丟棄該數據包。

所述在PIT、FIB和CS中查找信息名字包括以下步驟:將信息名字進行編碼,然后將編碼后的名字分段進行哈希計算,以計算后獲得的縱橫哈希值為下標,查找對應的布隆過濾器,如果所有的下標對應的值都不小于1,則表示PIT、FIB和CS中存在對應的名字信息,如果存在一個布隆過濾器對應位置值為0,則表示不存在該信息。

所述步驟203和步驟302中的信息記錄包括以下步驟:向隆過濾器中插入信息時,根據相應哈希函數組對每段信息編碼進行哈希計算,獲得一個橫向哈希函數值,一個縱向哈希函數值,以這兩個值為布隆過濾器的縱橫下標,將對應位置的布隆過濾器元素值加1。

所述步驟302中的刪除記錄包括以下步驟:當從布隆過濾器中刪除信息時,需要根據相應哈希函數組對擬刪除信息的每段編碼進行哈希計算,獲得一個橫向哈希函數值,一個縱向哈希函數值,以這兩個值為布隆過濾器的縱橫下標,判斷對應位置的布隆過濾器的元素值。如果該位置元素值大于等于1,則將該元素值減1,否則不做處理。

本發明的有益效果:本發明利用ICN網絡信息名字分段的特點,以段為單位進行并行名字查找。在每個段內,基于多重布隆過濾器實現信息名字的快速查找,提高信息名字檢索的效率,為名字路由快速轉發提供支持。

附圖說明

圖1為本發明中信息命名的格式;

圖2為本發明中提供者的格式;

圖3為本發明中分類段的格式;

圖4為本發明中直接命名法的格式;

圖5為本發明中屬性值對命名法的格式。

具體實施方式

如圖所示,一種基于多重布隆過濾器的ICN網絡信息名字查找方法,包括以下步驟:

步驟1、確定路由節點接收到的是興趣包還是數據包,其中,興趣包用來發送信息請求,數據包用來向請求節點返回所需信息;

步驟2、若路由節點接收到興趣包時,按照下列步驟進行處理:

步驟201:首先在CS中查找興趣包所需的信息,如果存在,則銷毀興趣包,并生成一個數據包沿興趣包的反方向發送給請求節點;

步驟202:如果CS中不存在,則在PIT中查找,如果存在,說明該路由節點已經轉發過相同的內容請求,則銷毀興趣包,并將接收興趣包的接口記錄在PIT相應行后邊。

步驟203:如果PIT中不存在,則在FIB中查找,如果存在,則將興趣包按照FIB的接口轉發,并將信息記錄在PIT中;如果FIB中不存在,則說明本路由節點不知道該興趣包的路由,銷毀該興趣包;

步驟3、若路由節點接收到是數據包,按照下列步驟進行處理:

步驟301:首先在CS中查找數據包所需的信息,如果存在則直接丟棄該數據包;

步驟302:如果CS中不存在,則在PIT中查找,如果存在,則按照PIT記錄的接口進行轉發后,刪除PIT記錄,然后按照相應策略緩存數據包到CS中。

步驟303:如果PIT中不存在,則直接丟棄該數據包。

所述在PIT、FIB和CS中查找信息名字包括以下步驟:將信息名字進行編碼,然后將編碼后的名字分段進行哈希計算,以計算后獲得的縱橫哈希值為下標,查找對應的布隆過濾器,如果所有的下標對應的值都不小于1,則表示PIT、FIB和CS中存在對應的名字信息,如果存在一個布隆過濾器對應位置值為0,則表示不存在該信息。

所述步驟203和步驟302中的信息記錄包括以下步驟:向隆過濾器中插入信息時,根據相應哈希函數組對每段信息編碼進行哈希計算,獲得一個橫向哈希函數值,一個縱向哈希函數值,以這兩個值為布隆過濾器的縱橫下標,將對應位置的布隆過濾器元素值加1。

所述步驟302中的刪除記錄包括以下步驟:當從布隆過濾器中刪除信息時,需要根據相應哈希函數組對擬刪除信息的每段編碼進行哈希計算,獲得一個橫向哈希函數值,一個縱向哈希函數值,以這兩個值為布隆過濾器的縱橫下標,判斷對應位置的布隆過濾器的元素值。如果該位置元素值大于等于1,則將該元素值減1,否則不做處理。

以下結合具體實施里進一步闡述本發明。

ICN網絡中有兩類數據包:興趣包和數據包。興趣包用來發送信息請求,數據包向請求節點返回所需信息。每個路由器節點需要維護三個數據結構——PIT、FIB和CS。

PIT(待定請求表,PendingInterestTable):用于記錄經過本路由節點尚未回傳的請求信息,以便相應信息返回時傳回請求節點。

FIB(前向轉發表、ForwardingInformationBase):用于記錄經過本路由節點的請求應該向那個出口(face)轉發才能到達目的節點。

CS(內容存儲器,ContentStore):記錄經過本路由節點的信息內容,以便供其它請求該信息的節點使用。

當路由節點接收到一個興趣包時,首先在CS中查找興趣包所需的信息,如果存在,則銷毀興趣包,并生成一個數據包沿著興趣包的反方向發送給請求節點;如果CS中不存在,則在PIT中查找,如果存在,說明該路由節點已經轉發過相同的內容請求,則銷毀興趣包,并將接收興趣包的接口記錄在PIT相應行后邊;如果PIT中不存在,則在FIB中查找,如果存在,則將興趣包按照FIB的接口轉發,并將信息記錄在PIT中;如果FIB中不存在,則說明本路由節點不知道該興趣包的路由,銷毀該興趣包。

當路由節點接收到一個數據包時,首先在CS中查找,如果存在則直接丟棄該數據包;如果CS中不存在,則在PIT中查找,如果存在,則按照PIT記錄轉發后刪除PIT記錄,并按照相應策略緩存數據包到CS中;如果PIT中不存在,則直接拋棄該數據包,或按照相應策略緩存數據包。

因此,ICN網絡中,信息的命名和查找是影響網絡性能至關重要的因素。對PIT、FIB、CS三個數據表都涉及頻繁的查找、插入和刪除操作,其中查找是最關鍵的操作。本發明基于多重布隆過濾器,發明一種高效的信息命名查找方法。

(一)信息命名

根據網絡信息命名的需求和信息訪問的特點,我們發明信息的命名包括4個組成部分,每個部分稱為一個段。也就是說ICN網絡中每一個信息的名字由4段組成,如圖1所示,

1.提供者

提供者是一個長度固定的段(比如8字節),細分為兩個域:域名和提供者,分別用來表示該信息的提供者域名和提供者名稱,如圖2所示。

(1)域名:域名是一個固定長度的域(如4字節),由上“通用頂級域”(Generictop-leveldomain,gTLD)和“國家和地區頂級域名”(countrycodetop-leveldomains,ccTLD)中的一個組成,如“.org”、“.com”、“.cn”等。

(2)提供者:提供者也是一個固定長度的域(如4字節),表示該信息提供的主體,如sohu、sina、google、baidu等。

規定域之間用從屬分割符(這里用“.”)連接起來,這樣提供者段就可以表示為“域名.提供者”,如“com.baidu”,“com.sina”等。

有些情況下,信息的名字中也需要用到從屬分隔符(比如這里用的“.”),這時采用計算機領域常用的轉義字符“/”區分,即在分隔符前加上轉義字符“/”。

2.分類

分類是一個長度不固定的段,由多個域組成,域的個數也不固定,但每個域的長度固定,其格式如圖3所示。

圖3中每一個子分類的長度固定(如4字節),用來表示信息的一種子類別。分類段的子分類個數不確定,即有的信息分類層次多,有的信息分類層次少。因此,整個分類段的長度不固定。

規定分類中域之間用從屬分割符(這里用“.”)連接起來,按照這種方式,一個信息的分類段就可以表示為“子分類1.子分類2.子分類3.….子分類n”,如“娛樂.視頻.電視劇.歷史”。

3.名稱

名稱是一個長度不固定的段,有兩種不同的命名方法。

(1)直接命名法

直接命名法主要針對信息意義比較明確或不需要名稱字段表示信息意義的情況,其格式如圖4所示。

命名類型:是一個固定長度的域(比如1字節),表示名稱段是采用“直接命名法”命名還是采用“屬性值對命名法”命名。其中,1表示采用直接命名法,2表示采用屬性值對命名法。

規定名稱段中域之間用從屬分割符(這里用“.”)連接起來,這樣名稱段就可以表示為“命名類型.名稱”,如“1.2014感動中國十大人物”,“1.afsdfasl/.jpg”等。這里的“/”是轉義字符,用于限定“.”不是從屬分隔符。

(2)屬性值對命名法

屬性值對命名法主要針對要清楚的表達信息的意義需要有較多的屬性描述的情況,其格式如圖5所示。

命名類型:是一個固定長度的域(比如1字節),表示名稱段是采用“直接命名法”命名還是采用“屬性值對命名法”命名。其中,1表示采用直接命名法,2表示采用屬性值對命名法。

屬性值對:每一個屬性值對是一個固定長度的域(比如8字節),用來表示信息的一個屬性及其值,從一個側面對信息進行描述,其格式為“屬性名.屬性值”,比如“內存.4G”。多個屬性值對之間用并列分隔符(這里用“:”)連接起來,這樣信息的屬性值對格式為“屬性1.屬性值1:屬性2.屬性值2:…:屬性n.屬性值n”,比如“大小.14吋:顏色.銀灰:CPU.I5-1/.8GH:內存.4G:硬盤大小.120G””。

核心名:核心名段是一個長度不固定的域,用來表示屬性值對修飾的主體。

規定命名類型、屬性值對和核心名之間用從屬分割符(這里用“.”)連接起來,這樣名稱段就可以表示為“命名類型.屬性值對.核心名”表示,進一步表示為“命名類型.屬性1.屬性值1:屬性2.屬性值2:…:屬性n.屬性值n.核心名”,比如“2.大小.14吋:顏色.銀灰:CPU.I5-1/.8GH:內存.4G:硬盤大小.120G.筆記本”。

4.驗證碼

驗證碼是一個長度不固定的段,主要用于對提供者、分類、名稱三個段信息的完整性、不被冒充性、提供者不可抵賴性、信息不被篡改性提供保障。驗證碼可以采用摘要算法、公鑰密碼體制RSA等公用的數字簽名算法,將信息的提供者、分類、名稱三個段組成的信息作為輸入,生成一個驗證碼序列。

規定信息名字的段之間用段分隔符(這里采用“/”)連接起來,這樣一個完整的ICN網絡信息名稱為:

“域名.提供者/子分類1.子分類2.子分類3.….子分類n/命名類型.名稱/驗證碼”

如“com.sohu/新聞.國內.人物/1.2014感動中國十大人物/8D34D566EF23EA09”,“com.百度/圖片.卡通圖片/1.99bOOOPIC77/.jpg/6D24C521BC21D402”

或“域名.提供者/子分類1.子分類2.子分類3.….子分類n/命名類型.屬性1.屬性值1:屬性2.屬性值2:……:屬性n.屬性值n.核心名/驗證碼”

如“com.jd/電腦、辦公.電腦整機.筆記本/2.大小.14吋:顏色.銀灰:CPU.I5-1/.8GH:內存.4G:硬盤大小.120G.MacBook/3FECC54B709AC476”

(二)查找方法

在ICN網絡中,涉及對PIT、FIB和CS的查找、插入、刪除操作。其中查找操作是基礎,插入和刪除操作都要先進行查找。此外,PIT、FIB和CS的查找都是根據信息的名字查找,其操作的本質是一樣的。因此,本發明利用多重布隆過濾器,實現名字的快速查找。

1.多重布隆過濾器的形態

一個布隆過濾器是一個N×N的二維數組(N是常數),每個元素的初始值為0。

在路由器節點中,每個PIT、FIB和CS需要3K個布隆過濾器,即3K個N×N的二維數組,分別用BS1i,BS2i和BS3i表示,其中i=1,2,3,…,K表示第i個布隆過濾器。BS1,BS2和BS3分布存儲段1、段2和段3經過K對正交哈希函數計算后獲得的位置下標信息。段4是驗證碼,用于用戶獲取信息后對信息發布者的驗證,不需要存儲。

2.哈希函數組

為了在多重布隆過濾器中表示一個信息的名字,首先需要將名字以段為單位進行編碼,編碼方式可以采用多種方式,如CRC32。然后,為每段編碼選擇2組正交的哈希函數,實現對編碼的哈希計算。

這里哈希函數的選擇可以采用哈希函數常用的方法,也可以自行設計特殊的哈希函數,但要求哈希函數能夠將名字編碼映射成值為[0,n)的整數。最終,可以獲得3組正交的哈希函數,分別表示為:H_S1x(i,str),H_S1y(i,str),H_S2x(i,str),H_S2y(i,str)和H_S3x(i,str),H_S3y(i,str)。其中,H_S1x,表示信息名字段1的橫向哈希函數通用名,H_S1y,表示信息名字段1的縱向哈希函數通用名,i=1,2,3,…,K表示第i個哈希函數,str表示段1的編碼字符串。

3.向布隆過濾器中插入信息

當需要向布隆過濾器中插入信息時,需要根據相應哈希函數組對每段信息編碼進行哈希計算,獲得一個橫向哈希函數值,一個縱向哈希函數值,以這兩個值為布隆過濾器的縱橫下標,將對應位置的布隆過濾器元素值加1。假設需要插入信息的名字經過CRC32編碼后為:344BC4DB/455EF43AD/BF445AD34,則插入步驟為:

第一步:建立段1的布隆過濾器

H_S1x(1,344BC4DB)=5;H_S1y(1,344BC4DB)=6;則表示BS11[5,6]的值加1。

H_S1x(2,344BC4DB)=4;H_S1y(2,344BC4DB)=8;則表示BS12[4,8]的值加1。

……………………………………

H_S1x(K,344BC4DB)=255;H_S1y(K,344BC4DB)=361;則表示BS1K[255,361]的值加1。

第二步:建立段2的布隆過濾器

H_S2x(1,455EF43AD)=2;H_S2y(1,455EF43AD)=1;則表示BS21[2,1]的值加1。

H_S2x(2,455EF43AD)=7;H_S2y(2,455EF43AD)=2;則表示BS22[7,2]的值加1。

……………………………………

H_S2x(K,455EF43AD)=55;H_S2y(K,455EF43AD)=241;則表示BS2K[55,241]的值加1。

第三步:建立段3的布隆過濾器

H_S3x(1,BF445AD34)=9;H_S3y(1,BF445AD34)=7;則表示BS31[9,7]的值加1。

H_S3x(2,BF445AD34)=11;H_S3y(2,BF445AD34)=3;則表示BS32[11,3]的值加1。

……………………………………

H_S3x(K,BF445AD34)=121;H_S3y(K,BF445AD34)=324;則表示BS3K[121,324]的值加1。

在當前高性能計算機中,可以利用多處理器對上述三個步驟進行并行化處理,提高計算速度。

4.從布隆過濾器的刪除信息

當需要從布隆過濾器中刪除信息時,需要根據相應哈希函數組對擬刪除信息的每段編碼進行哈希計算,獲得一個橫向哈希函數值,一個縱向哈希函數值,以這兩個值為布隆過濾器的縱橫下標,判斷對應位置的布隆過濾器的元素值。如果該位置元素值大于等于1,則將該元素值減1,否則不做處理。假設擬刪除信息的名字經過CRC32編碼后為:344BC4DB/455EF43AD/BF445AD34,則刪除信息步驟為:

第一步:刪除段1的布隆過濾器值

H_S1x(1,344BC4DB)=5;H_S1y(1,344BC4DB)=6;則判斷BS11[5,6]的值,如果大于等于1,則將BS11[5,6]的值減1。

H_S1x(2,344BC4DB)=4;H_S1y(2,344BC4DB)=8;則判斷BS12[4,8]的值,如果大于等于1,則將BS12[4,8]的值減1。

……………………………………

H_S1x(K,344BC4DB)=255;H_S1y(K,344BC4DB)=361;則判斷BS1K[255,361]的值,如果大于等于1,則將BS1K[255,361]的值減1。

第二步:刪除段2的布隆過濾器值

H_S2x(1,455EF43AD)=2;則判斷BS21[2,1]]的值,如果大于等于1,則將BS21[2,1]的值減1。

H_S2x(2,455EF43AD)=7;H_S2y(2,455EF43AD)=2;則判斷BS22[7,2]的值,如果大于等于1,則將BS22[7,2]的值減1。

……………………………………

H_S2x(K,455EF43AD)=55;H_S2y(K,455EF43AD)=241;則判斷BS2K[55,241]的值,如果大于等于1,則將BS2K[55,241]的值減1。

第三步:刪除段3的布隆過濾器值

H_S3x(1,BF445AD34)=9;H_S3y(1,BF445AD34)=7;則判斷BS31[9,7]的值,如果大于等于1,則將BS31[9,7]的值減1。

H_S3x(2,BF445AD34)=11;H_S3y(2,BF445AD34)=3;則判斷BS32[11,3]的值,如果大于等于1,則將BS32[11,3]的值減1。

……………………………………

H_S3x(K,BF445AD34)=121;H_S3y(K,BF445AD34)=324;則判斷BS3K[121,324]的值,如果大于等于1,則將BS3K[121,324]的值減1。

在當前高性能計算機中,可以利用多處理器對上述三個步驟進行并行化處理,提高計算速度。

5.名字查找

當需要在PIT、FIB和CS中查找信息名字時,首先將名字經過CRC32進行編碼,然后將經編碼后的名字分段進行哈希計算,以計算后獲得的縱橫哈希值為下表,查找對應的布隆過濾器,如果所有的下標對應的值都不小于1,則表示PIT、FIB和CS中存在對應的名字信息,如果存在一個布隆過濾器對應位置值為0,則表示不存在該信息。

假設擬查找信息的名字經過CRC32編碼后為:344BC4DB/455EF43AD/BF445AD34,則查找步驟為:

第一步:查找段1的布隆過濾器值

H_S1x(1,344BC4DB)=5;H_S1y(1,344BC4DB)=6;則判斷BS11[5,6]的值,如果等于0,則查找失敗,否則,繼續1。

H_S1x(2,344BC4DB)=4;H_S1y(2,344BC4DB)=8;則判斷BS12[4,8]的值,如果等于0,則查找失敗,否則,繼續1。

……………………………………

H_S1x(K,344BC4DB)=255;H_S1y(K,344BC4DB)=361;則判斷BS1K[255,361]的值,如果等于0,則查找失敗,否則,段1查找成功。

第二步:查找段2的布隆過濾器值

H_S2x(1,455EF43AD)=2;則判斷BS21[2,1]]的值,如果等于0,則查找失敗,否則,繼續1。

H_S2x(2,455EF43AD)=7;H_S2y(2,455EF43AD)=2;則判斷BS22[7,2]的值,如果等于0,則查找失敗,否則,繼續1。

……………………………………

H_S2x(K,455EF43AD)=55;H_S2y(K,455EF43AD)=241;則判斷BS2K[55,241]的值,如果等于0,則查找失敗,否則,段2查找成功。

第三步:查找段3的布隆過濾器值

H_S3x(1,BF445AD34)=9;H_S3y(1,BF445AD34)=7;則判斷BS31[9,7]的值,如果等于0,則查找失敗,否則,繼續1。

H_S3x(2,BF445AD34)=11;H_S3y(2,BF445AD34)=3;則判斷BS32[11,3]的值,如果等于0,則查找失敗,否則,繼續1。

……………………………………

H_S3x(K,BF445AD34)=121;H_S3y(K,BF445AD34)=324;則判斷BS3K[121,324]的值,如果等于0,則查找失敗,否則,段3查找成功。

在當前高性能計算機中,可以利用多處理器對上述三個步驟進行并行化處理,當一個段查找失敗后,通知其它段停止查找,以提高計算速度。

關 鍵 詞:
一種 基于 多重 過濾器 ICN 網絡 信息 名字 查找 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:一種基于多重布隆過濾器的ICN網絡信息名字查找方法.pdf
鏈接地址:http://www.rgyfuv.icu/p-6345443.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
山东11选5中奖结果走势图