基于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).

作者单位:山东安丘市第三中学