论文部分内容阅读
[摘要] 本文根据chord网络的结构和缺点,提出了一种基于反馈评价机制的节点价值评价算法和控制chord网络由于节点频繁进出而造成的网络波动的策略,对chord网络进行了改进。
[关键词] chord 价值评价算法 节点控制
0 引言
P2P技术中,P2P网络查找策略和网络波动问题一直是P2P技术研究的热点和焦点问题。 P2P网络中,最关键的是如何高速和有效的定位查找资源问题,因为P2P分为很多种结构。所以,每一种结构对应的查找的策略也不尽相同,根据拓扑结构可以将P2P研究分为4种类型。
1.集中式拓扑(Centralized Topology):如Napster。采用的是集中式的查找方法。
2.全分布式非结构化拓扑(Decentralized Unstructured Topology):如Gnutella。采用的是广播“泛洪”的方法。
3.全分布式结构化拓扑(Decentralized Structured Topology,也称作DHT网络):如Chord、CAN、Tapes时、D2B、CRN。采用的是用分布式哈希表(DHT)来查找的方法。
4.半分布式结构(Partially Decentralized Topology):如Kazaa。采用的是中心化拓扑和全分布式非结构化拓扑相互结合的查找策略,设置超级节点的一种分层的结构。
在以上的四种类型中,由于全分布式结构化拓扑结构(DHT)的可扩展性、可靠性、维护性以及发现算法效率高等的特点,所以成为目前研究的热点。
1 Chord 模型
Chord网络是一种基于全分布式结构化拓扑(DHT)的路由模型。Chord使用一致性哈希算法,该模型不去考虑整个网络的拓扑结构,即网络中的节点在逻辑上的一致,在网络中节点存储m个其他节点的信息,存储这些信息的表的叫做Finger Table(查询表)。网络的结构使用一维的环形拓扑结构,关键字和节点在同一标识空间中表示,关键字和节点都用m bits的标识符表示,表示范围为0…2m-1(如图1)。
1.1Chord 模型的优点
Chord网络的利用Finger Table加快了查询过程。且可以随着系统的规模的增加而增加。故Chord网络可以应用在大规模的网络系统中。并且由于chord网络是全分布式结构化不存在中央服务器,故拥有很好的鲁棒性。
1.2 Chord模型的缺陷
但是,chord网络在实际应用中,也存在的一些缺陷,在实际的网络中,节点之间存在差异。而chord认为网络中所有节点实体的地位相同,而忽视了网络节点能力的差异,这是不现实的。
且节点的频繁进入会导致finger table表的频繁更新,造成网络的极大波动,造成了很大的维护开销,直接导致了网络性能下降
如何有效控制节点的加入和离开,是控制chord网络波动的关键问题,在chord网络中,节点的加入步骤可分为三个步骤:
(1)假设某新节点m1,加入网络之前通过某种方法或者策略指导网络中的节点m,m1通过m来初始化自己的指针表。
(2)将m1的信息更新入其他节点的指针表,将m1的信息加入网络。
(3)把所有的节点中,后续节点是m1的关键字转移到m1上,时间复杂度为0(log2n),而节点失效或者离开chord网络的时候,所有的指针表中包括了节点m的节点都要把m替换成m的后续节点。
故当节点频繁的变动的时候,指针表必须不停的更新,造成了网络的不断的波动,影响了查询性能,另一方面,某一些节点由于自身能力不足(比如带宽小,负载能力弱,在线时间断)并不能够负载起节点的传输和查询作用,因此,如何控制节点加入,制定一套合适的节点加入规则,是控制chord网络波动,提高性能和负载能力和负载平衡的重要的手段。
2 节点的评价算法
2.1当前的一些节点评价算法的研究和应用状况
在已有的应用中,一些P2P软件对节点能力估值做出了一系列的研究,比如著名的软件emule中的highid和lowid,他主要是通过判断用户是否在内网,以及是否可以正常的进行NAT网络穿越来判断。
著名的混合型P2P VOIP通信软件skype将拓扑网络中的节点分为普通节点和超级节点两大类。其中超级节点除了具有普通节点的功能外,还负责数据的转发。其超级节点是根据其内存,上线时间,带宽为条件进行选择的。
但上述的几种节点估值的算法都是根据节点的自我评价来进行鉴别的。这样,就有可能出现这种情况,节点自身的网络存在一定得限制(如节点的本身或者网络限制了对P2P协议或者ip连接数进行了限制),导致其他节点连接存在着不确定性。或者节点用户做出了一定得限制(如上传限制和下载限制)。
故针对这种情况,本文提出了另外一种基于反馈的节点的重要性和能力估值算法。这个算法对节点的能力评价并不是由节点根据自身的能力(如带宽,机器性能)等进行自我评价,而是由连接他的其他节点来做出。这样就很好地解决了节点自我评价可能导致的问题。
2.2算法描述
典型的P2P网络中传输过程如下:
在P2P网络传输中,典型的传输过程如下:
A:接受者 B:传输者1 C:传输者2
A发出一个查询请求,DHT网络返回 B和C
A尝试连接B和C
尝试成功,B和C开始向A传输数据
传输结束
为了实现反馈估值,在传输过程顺利的完成后,A向B和C发送出一组数据D1(包括传输的起始和结束时间,平均速度)当BC接受到传输的数据以后,与自己本身的已经存在的节点的评价值D进行价值评估算法的运算,生成新的节点评价值D。
在评价算法中,有三个参数:成功的次数C,节点的有效时间T,以及节点的平均速度S。
成功的次数C:当每一次节点返回一次评价参数的时候,节点成功次数C加1。当连接上却不能够传输的时候,节点成功次数减一。
节点的有效时间T=T2-T1:节点自身保存有当前第一次加入到chord网络的时间T1,当接收到到评价参数结束时间T2后,用T2减去T1,即是节点的有效时间。
节点的平均速度S=(S1*C+S2)/(C+1):S1节点自身纪录的传输平均速度,S2指通过新传入评价参数中的平均速度傳输速度,当S2的值小于传输节点自身当前下载速度的70%时候,视为无效,由于S2和S1可能具有较大的不同,所以为了平滑和减少S值的波动,我们引入C,用C来平滑S的值,以求取得精确性。
节点的评价值D2:D2=
其中,D1是保存在节点自身信息中的上一次的评价值。
为了防止出现吸血节点和节点过载,我们还需要设定两个参数Dmax和Pmax,且定义如下两条规则,
规则一:设定一个评价值最大值Dmax,当D的计算值大于Dmax的时候,令D=Dmax;
规则二:设定最大任务连接数P,当节点A本身连接数大于P的时,节点A向临界节点发出过载信息,不再接受新的任务。
规则三:当查询返回的数个节点拥有同样的评价值D,优先连接连接数P最小的节点
设定了这样的三条规则以后,就可以有效的避免出现高评价值节点过载和防止出现吸血节点。
3 节点的加入策略
为了控制节点的加入,在目录服务器中维护一队列A和一个队列B,队列A保存这欲加入队列的节点的信息,包括地址,评价值等,并且按照评价值的大小进行降序排列,数组B中保存了当前已经加入chord的节点的最低评价值,并按照升序排列。当一个节点进入chord网络,先将自身的评价值同B进行比较,如果大于B,则直接加入chord网络环,并且跟新队列B,如果小于B申请加入chord网络环的时候,我们先将其置入一个节点加入等待队列中,当chord网络环中的某一个节点失效或者网络节点负载过重的时候,需要更高性能的节点的时候,系统就像等待队列中发送消息,从目录服务器中取出最顶端的节点(暨评价值最高的节点),加入chord网络,并且更新队列B。
队列A的结构如下表:
在目录服务器中,我们应该加入一个程序段,用于队列A和队列B的控制。
Peerqueue()
{
new QuequeMember q1=receive(message);
If q1>quequ2.first;
{q1.addtochord;
Updatebysort(queue2,q1);
}
Else
Updatebysort(queque1,q1);
}
为了控制这个过程,我们应当在chord网络中节点中,运行一个程序段,控制着节点的加入,监视节点的状态,
Monitor()
{if ((peer(i).status=fails)||message>Peer(i).ability)
{newpeer n1=getnewpeer(queue);
……..
n1.add();
}
}
改进后的结构模型如图:
4 实验结果
我们使用MatLab作为仿真工具,用来模拟当高评价值和低评价值的节点频繁进入chord网络情况下网络波动情况和性能。
查询性能和网络的流量波动性能是P2P网络中衡量网络性能的重要的指标
我们模拟100个节点,其中n个节点定义为一半高评价值一半低评价值节点的混合。
试验结果如下:
由图可以看出,当低评价值节点频繁进出的时候,未改进的节点收到的影响明显大于改进以后的节点所受到的影响,并且可以推断出,当频繁进出网络的节点为低评价值节点时候,所带来的差异将更加明显。
可以看出,当节点频繁进出的时候,原始的chord网络和改进以后的chord网络相比,原始的chord网络的流量的波动明显大于改进后的网络。
我们模拟100个节点,下载带宽限制为55k/s,不停的重复下载一个100m的文件。下载平均传输性能如图所示:
在传输中,开始的时候,改进型网络速度稍微逊于原始的chord网络,但是当时间逐渐延长,反馈评价机制发挥作用,改进型chord网络中的节点之间的网络开销小于原始的网络开销,故速度反而快于原始的chord网络,故可以推断出,网络存在的时间越长,改进型网络的性能越优。
综合上述实验结果可以看出,改进后的chord网络在节点频繁进出的时候,节点的查询性能要明显好于未改进的网络且网络波动也要明显优于未改进的网络,而两者的传输性能方面,chord网络存在时间越长,则性能越优。
5 结论与展望
本文针对chord网络的特点和缺陷,提出了一种基于评价反馈机制的节点价值评价算法和并根据这一算法提出了chord网络中节点控制的策略。有效地改善了节点频繁进出造成的网络波动和查询波动问题。如何进一步改進节点控制算法和评价算法,使之更加智能和有效,是下一步研究的重点。
参考文献:
[1]马毅.一种新的P2P节点路由优化算法RGAAC[J].小型微型计算机系统,2009.10.
[2]黄道颖.基于主动网络的分布式P2P网络模型[J].软件学报,2004,15 (7) : 1081- 1089.
[3]黄道颖.利用Gnutella网络的拓扑特性改进其可扩展性[J].计算机工程与应用,2003, 39(26):58-60.
[4]陈贵海,李震华.对等网络:结构,应用与设计[M].北京:清华大学出版社,2007.83-93.
[5]陈欣.结构P2P网络Chord模型研究及其动态分析[J].福建电脑,2006,(04):18-19.
[关键词] chord 价值评价算法 节点控制
0 引言
P2P技术中,P2P网络查找策略和网络波动问题一直是P2P技术研究的热点和焦点问题。 P2P网络中,最关键的是如何高速和有效的定位查找资源问题,因为P2P分为很多种结构。所以,每一种结构对应的查找的策略也不尽相同,根据拓扑结构可以将P2P研究分为4种类型。
1.集中式拓扑(Centralized Topology):如Napster。采用的是集中式的查找方法。
2.全分布式非结构化拓扑(Decentralized Unstructured Topology):如Gnutella。采用的是广播“泛洪”的方法。
3.全分布式结构化拓扑(Decentralized Structured Topology,也称作DHT网络):如Chord、CAN、Tapes时、D2B、CRN。采用的是用分布式哈希表(DHT)来查找的方法。
4.半分布式结构(Partially Decentralized Topology):如Kazaa。采用的是中心化拓扑和全分布式非结构化拓扑相互结合的查找策略,设置超级节点的一种分层的结构。
在以上的四种类型中,由于全分布式结构化拓扑结构(DHT)的可扩展性、可靠性、维护性以及发现算法效率高等的特点,所以成为目前研究的热点。
1 Chord 模型
Chord网络是一种基于全分布式结构化拓扑(DHT)的路由模型。Chord使用一致性哈希算法,该模型不去考虑整个网络的拓扑结构,即网络中的节点在逻辑上的一致,在网络中节点存储m个其他节点的信息,存储这些信息的表的叫做Finger Table(查询表)。网络的结构使用一维的环形拓扑结构,关键字和节点在同一标识空间中表示,关键字和节点都用m bits的标识符表示,表示范围为0…2m-1(如图1)。
1.1Chord 模型的优点
Chord网络的利用Finger Table加快了查询过程。且可以随着系统的规模的增加而增加。故Chord网络可以应用在大规模的网络系统中。并且由于chord网络是全分布式结构化不存在中央服务器,故拥有很好的鲁棒性。
1.2 Chord模型的缺陷
但是,chord网络在实际应用中,也存在的一些缺陷,在实际的网络中,节点之间存在差异。而chord认为网络中所有节点实体的地位相同,而忽视了网络节点能力的差异,这是不现实的。
且节点的频繁进入会导致finger table表的频繁更新,造成网络的极大波动,造成了很大的维护开销,直接导致了网络性能下降
如何有效控制节点的加入和离开,是控制chord网络波动的关键问题,在chord网络中,节点的加入步骤可分为三个步骤:
(1)假设某新节点m1,加入网络之前通过某种方法或者策略指导网络中的节点m,m1通过m来初始化自己的指针表。
(2)将m1的信息更新入其他节点的指针表,将m1的信息加入网络。
(3)把所有的节点中,后续节点是m1的关键字转移到m1上,时间复杂度为0(log2n),而节点失效或者离开chord网络的时候,所有的指针表中包括了节点m的节点都要把m替换成m的后续节点。
故当节点频繁的变动的时候,指针表必须不停的更新,造成了网络的不断的波动,影响了查询性能,另一方面,某一些节点由于自身能力不足(比如带宽小,负载能力弱,在线时间断)并不能够负载起节点的传输和查询作用,因此,如何控制节点加入,制定一套合适的节点加入规则,是控制chord网络波动,提高性能和负载能力和负载平衡的重要的手段。
2 节点的评价算法
2.1当前的一些节点评价算法的研究和应用状况
在已有的应用中,一些P2P软件对节点能力估值做出了一系列的研究,比如著名的软件emule中的highid和lowid,他主要是通过判断用户是否在内网,以及是否可以正常的进行NAT网络穿越来判断。
著名的混合型P2P VOIP通信软件skype将拓扑网络中的节点分为普通节点和超级节点两大类。其中超级节点除了具有普通节点的功能外,还负责数据的转发。其超级节点是根据其内存,上线时间,带宽为条件进行选择的。
但上述的几种节点估值的算法都是根据节点的自我评价来进行鉴别的。这样,就有可能出现这种情况,节点自身的网络存在一定得限制(如节点的本身或者网络限制了对P2P协议或者ip连接数进行了限制),导致其他节点连接存在着不确定性。或者节点用户做出了一定得限制(如上传限制和下载限制)。
故针对这种情况,本文提出了另外一种基于反馈的节点的重要性和能力估值算法。这个算法对节点的能力评价并不是由节点根据自身的能力(如带宽,机器性能)等进行自我评价,而是由连接他的其他节点来做出。这样就很好地解决了节点自我评价可能导致的问题。
2.2算法描述
典型的P2P网络中传输过程如下:
在P2P网络传输中,典型的传输过程如下:
A:接受者 B:传输者1 C:传输者2
A发出一个查询请求,DHT网络返回 B和C
A尝试连接B和C
尝试成功,B和C开始向A传输数据
传输结束
为了实现反馈估值,在传输过程顺利的完成后,A向B和C发送出一组数据D1(包括传输的起始和结束时间,平均速度)当BC接受到传输的数据以后,与自己本身的已经存在的节点的评价值D进行价值评估算法的运算,生成新的节点评价值D。
在评价算法中,有三个参数:成功的次数C,节点的有效时间T,以及节点的平均速度S。
成功的次数C:当每一次节点返回一次评价参数的时候,节点成功次数C加1。当连接上却不能够传输的时候,节点成功次数减一。
节点的有效时间T=T2-T1:节点自身保存有当前第一次加入到chord网络的时间T1,当接收到到评价参数结束时间T2后,用T2减去T1,即是节点的有效时间。
节点的平均速度S=(S1*C+S2)/(C+1):S1节点自身纪录的传输平均速度,S2指通过新传入评价参数中的平均速度傳输速度,当S2的值小于传输节点自身当前下载速度的70%时候,视为无效,由于S2和S1可能具有较大的不同,所以为了平滑和减少S值的波动,我们引入C,用C来平滑S的值,以求取得精确性。
节点的评价值D2:D2=
其中,D1是保存在节点自身信息中的上一次的评价值。
为了防止出现吸血节点和节点过载,我们还需要设定两个参数Dmax和Pmax,且定义如下两条规则,
规则一:设定一个评价值最大值Dmax,当D的计算值大于Dmax的时候,令D=Dmax;
规则二:设定最大任务连接数P,当节点A本身连接数大于P的时,节点A向临界节点发出过载信息,不再接受新的任务。
规则三:当查询返回的数个节点拥有同样的评价值D,优先连接连接数P最小的节点
设定了这样的三条规则以后,就可以有效的避免出现高评价值节点过载和防止出现吸血节点。
3 节点的加入策略
为了控制节点的加入,在目录服务器中维护一队列A和一个队列B,队列A保存这欲加入队列的节点的信息,包括地址,评价值等,并且按照评价值的大小进行降序排列,数组B中保存了当前已经加入chord的节点的最低评价值,并按照升序排列。当一个节点进入chord网络,先将自身的评价值同B进行比较,如果大于B,则直接加入chord网络环,并且跟新队列B,如果小于B申请加入chord网络环的时候,我们先将其置入一个节点加入等待队列中,当chord网络环中的某一个节点失效或者网络节点负载过重的时候,需要更高性能的节点的时候,系统就像等待队列中发送消息,从目录服务器中取出最顶端的节点(暨评价值最高的节点),加入chord网络,并且更新队列B。
队列A的结构如下表:
在目录服务器中,我们应该加入一个程序段,用于队列A和队列B的控制。
Peerqueue()
{
new QuequeMember q1=receive(message);
If q1>quequ2.first;
{q1.addtochord;
Updatebysort(queue2,q1);
}
Else
Updatebysort(queque1,q1);
}
为了控制这个过程,我们应当在chord网络中节点中,运行一个程序段,控制着节点的加入,监视节点的状态,
Monitor()
{if ((peer(i).status=fails)||message>Peer(i).ability)
{newpeer n1=getnewpeer(queue);
……..
n1.add();
}
}
改进后的结构模型如图:
4 实验结果
我们使用MatLab作为仿真工具,用来模拟当高评价值和低评价值的节点频繁进入chord网络情况下网络波动情况和性能。
查询性能和网络的流量波动性能是P2P网络中衡量网络性能的重要的指标
我们模拟100个节点,其中n个节点定义为一半高评价值一半低评价值节点的混合。
试验结果如下:
由图可以看出,当低评价值节点频繁进出的时候,未改进的节点收到的影响明显大于改进以后的节点所受到的影响,并且可以推断出,当频繁进出网络的节点为低评价值节点时候,所带来的差异将更加明显。
可以看出,当节点频繁进出的时候,原始的chord网络和改进以后的chord网络相比,原始的chord网络的流量的波动明显大于改进后的网络。
我们模拟100个节点,下载带宽限制为55k/s,不停的重复下载一个100m的文件。下载平均传输性能如图所示:
在传输中,开始的时候,改进型网络速度稍微逊于原始的chord网络,但是当时间逐渐延长,反馈评价机制发挥作用,改进型chord网络中的节点之间的网络开销小于原始的网络开销,故速度反而快于原始的chord网络,故可以推断出,网络存在的时间越长,改进型网络的性能越优。
综合上述实验结果可以看出,改进后的chord网络在节点频繁进出的时候,节点的查询性能要明显好于未改进的网络且网络波动也要明显优于未改进的网络,而两者的传输性能方面,chord网络存在时间越长,则性能越优。
5 结论与展望
本文针对chord网络的特点和缺陷,提出了一种基于评价反馈机制的节点价值评价算法和并根据这一算法提出了chord网络中节点控制的策略。有效地改善了节点频繁进出造成的网络波动和查询波动问题。如何进一步改進节点控制算法和评价算法,使之更加智能和有效,是下一步研究的重点。
参考文献:
[1]马毅.一种新的P2P节点路由优化算法RGAAC[J].小型微型计算机系统,2009.10.
[2]黄道颖.基于主动网络的分布式P2P网络模型[J].软件学报,2004,15 (7) : 1081- 1089.
[3]黄道颖.利用Gnutella网络的拓扑特性改进其可扩展性[J].计算机工程与应用,2003, 39(26):58-60.
[4]陈贵海,李震华.对等网络:结构,应用与设计[M].北京:清华大学出版社,2007.83-93.
[5]陈欣.结构P2P网络Chord模型研究及其动态分析[J].福建电脑,2006,(04):18-19.