基于P2P的資源搜索算法探討

趙著堂

摘 要:服務器的不堪重負和分布在網絡中的閑置資源促使了一種新的網絡范例——對等計算(Peer-to-Peer,簡稱P2P)的出現。文章介紹了P2P的三種類型,提出了基于根服務器的P2P搜索算法的設計。

關鍵詞:P2P 搜索 根服務器

一、引言

隨著Internet的廣泛普及和網絡應用規模的不斷擴大,客戶機/服務器模式的存儲技術面對快速增長的網絡規模,由于自身模式的原因閑置浪費了大量的計算和存儲資源。更大規模的網絡對存儲服務器提出了更高的要求。服務器的不堪重負和分布在網絡中的閑置資源促使了一種新的網絡范例——對等計算(Peer-to-Peer,簡稱P2P)的出現。本文就基于P2P的資源搜索算法設計進行探討。

二、P2P概述

P2P中文稱為對等網絡,是指分布式系統中的各個節點是邏輯對等的,也就是說,對等網絡中每個IP點的地位是對等的,既可充當服務器為其他節點服務,也可充當客戶機消費其他IP點提供的服務。依據文件的檢索模型和機制,現有的P2P實現方式大致可以分為三種類型。它們分別是基于目錄服務器P2P,非結構化P2P和結構化P2P。

基于目錄服務器的P2P摒棄了傳統C/S模式由服務器負責一切的方式,用一個或多個中央目錄服務器存儲資源的實際存儲位置,并響應各P2P對等機的查詢請求;在非結構化的P2P中,網絡模型無需特別的設計,節點在網絡中完全對等,加入和退出網絡不會引起大量的維護消息;結構化的P2P多數采用基于DHT技術構造,具有明確的搜索目的性,具有較高的搜索效率。

三、基于根服務器的P2P搜索算法設計

1.數據結構

(1)根服務器上保存所有搜索樹根的列表:

structRootlst{

long KEY_Sector;

long ip;

}rootlst[LENGTH];

(2)物理節點(PN)所保存的本地邏輯節點列表:

struct LNlst{

longKEY_Sector;

long LNID;

}Inlst[LENGTH];

int LNnum;

(3)邏輯節點(LN)的路由表:

struct Lnroute{

longfather;

longchildren[4];

intchildren-count;

int Vln;

int Lin;

long Ext;};

struct LN{

long IP;

long KEY;

struct Lnroute Inroute;

}LNnew;

2.搜索樹根發現機制

所有LN維護一個僅存儲自己的父節點、所有子節點的位置信息的鄰居表,所有根節點的子節點均設置父節點為根節點的標識符口當一個LN需要獲得根節點的位置時,將發送一個根節點發現消息給自己的父節點,并逐級向上轉發,直到父節點為根節點時,返回響應消息。

3.空余度路由更新算法

子LN節點的空余度Vin或者空余度距離Lin發生改變時,將二者的值發給父LN,通知父節點執行空余度路由更新。

父節點更新自己存儲的該子節點的Vln和Lin,并根據新的子節點空余度路。

由狀況重新設置自己的空余度路由出口。

Vin為空余度,Lin為空余度距離,Ext為空余度路由出口。LN6下接4個節點之后,LN6的空余度路由發生改變,同時通知其父節點LN2,LN2將選擇Lin最小的子節點,而LN7.LN8.LN9的Lin均為0,因此LN6選擇這三個子節點中Vin最大者,即LN9作為自己的空余度路由出口。而LNl及其他兄弟節點并為受此拓撲變化的影響。

偽碼如下:

Route-update(child_Vln, child_Lln){

if (LN.Inroute.children_count<4){

LN.Inroute.Vln=4-LN.Inroute.children_count;

LN.Inroute.Lln=0;

LN.Inroute.Ext=localhost;}

else{

LN.Inroute.Ext=max_Lln(LN.children)

LN.Inroute.Vln=GetRemoteLN(LN.Inroute.Ext).InrouteVln;

LN.Inroute.tln=GetRemoteLN(LN.Inroute.Ext).InrouteLin+1}}

4.搜索樹創建算法

當一個物理節點上存儲的文件加入PZP網絡時,將執行一下步驟:

(1)計算出該文件各個關鍵字對應的哈希鍵值

(2)檢查本節點上是否已經存在包含該哈希鍵值的LN,如果沒有,則創建該LNnew.

(3)檢查該物理節點上是否已存在的其他LN,如果不存在,則向根服務器發送新LN消息:如果存在則利用該LN的根LN發現消息找到其所對應的根LN,即對應另一哈希數值區間的搜索樹根,并由此確定LNnew本身所屬的哈希數值區間的搜索樹是否存在(步驟d確保每個搜索樹根LN均保有所有搜索樹根LN的信息),若存在,則轉向LN加入算法;若不存在,則向根服務器發送新LN消息。

(4)根服務器接收到新LN消息,在LNnew所對應的哈希數值區間上新建一棵搜索樹,即將該物理節點上的這個新創建的LN定義為該搜索樹的根添加到本地搜索樹根表中的對應行,隨即將這張搜索樹根表發給所有根LN進行更新。

新加入的邏輯節點LNnew僅在本地不存在其他LN的時候才向根服務器發起查詢請求,而根服務器也僅需返回對應于LNnew所在哈希值區段的搜索樹樹根地址即可。

偽碼如下:

CreatTree(KEY){

if(!existed(GetLocalLN)(KEY))

PN.CreateLN(KEY);

if(LNnum>0){

oot=getRoot(anotherLN);

if(Root=getRootLRoot,KEY)==null){

LNnew.send(Sever,msg_NEWLN,LNnew.KEY,LNnew.IP);

Server.Add(Server.getSector(KEY),LNnew.lP);

Server.Broadcast(Server.getRootListQ);}

else

LNnew.send(Root,msgNEWLN,LNnew.KEY,LNnew.IP);}

else

LNnew.send(Sever,msg_NEWLN, LNnew.KEY,LNnew.IP);}}

建立搜索樹的目的即是將同在一個關鍵字哈希值區間內的文件邏輯上聚合在一起,當產生搜索請求時,搜索消息即可在某個搜索樹內部進行,消除了盲目性,而搜索樹的結構也保證了不會有消息循環和冗余。每個節點僅需負責簡單的轉發消息和查找自己的文件列表,負載分布合理,具有很高的效率。

5.邏輯節點加入算法

當一個新的LN:LNnew加入網絡,并且由算法A中的c)步驟轉向LN加入算法時:

(1)LNnew通過同一PN的其他搜索樹節點獲得自己所在搜索樹的根LN節點。若該PN沒有其他的LN時,則向根服務器查詢根LN。

(2)LNnew向根節點LN發送新LN消息。

(3)從根節點開始,依照空余度路由轉發LN加入消息,直到到達路由出口指向自身的節點LNi,即完成搜索。

(4)LN將LNi作為LNnew的父節點,并通知該當前節點和LNnew,二者隨后更新自己的空余度路由表。

LNnew向其所屬的搜索樹的根節點LN1發出加入請求,根節點沿著空余度路由進行搜索,直到找到出u指向自己的邏輯節點LN9。

LNnew接入搜索樹,成為LN9的子節點,則LN9更新其空余度路由,并向父節點LN2發出更新消息,以此類推,LN2和根節點LNI均更新空余度路由,LNnew加入過程完畢。

偽碼如下:

Root.OnNEWLN(KEY, IP)

Node=Root;

while(node.Inroute.Ext!=node.IP){

node=GetRemoteLN(node.Inroute.Ext);}

LNi=node;

LNi.children[LNi.lnroute.children_count] =LNnew.IP;

LNnew.father=LNi.IP;}

采用空余度路由的理由是盡可能將新加入的節點往靠近根LN的地方放置,并且盡可能將各LN的子節點排滿,避免在搜索樹的各個LN間廣播空余度查詢消息時,造成對搜索樹的大面積遍歷,浪費網絡資源。

參考文獻:

1.詹春華,陳曉蘇.對等網絡搜索方法比較與分析.湖北工學院學報,2004.

2.陳志琦,蘇德富.基于P2P技術的Gnutella網絡搜索路由機制的改進.計算機工程與設計,2005.

3.周晉,路海明,盧增祥,李衍達.基于部分匹配方式的可擴展P2P搜索算法.清華大學學報:自然科學版,2004,44(10).

作者單位:山東安丘市第三中學