一种异构网络中的高效路由P2P覆盖网的设计

程志强

(武汉船舶职业技术学院实训中心,湖北武汉 430050)

目前的P2P覆盖网设计需要着力解决如下的问题,如节点加入、退出造成网络不稳定,节点负载不均衡造成网络运行效率低下,覆盖网与物理网拓扑不匹配而产生冗余消息流量。针对这些问题,P2P覆盖网设计广泛采用了层次化方法,从众多节点中选择若干能力较强的超级节点(SP),负责服务索引维护和路由,以提高查询效率。在SP节点的选择策略上,有基于网络拓扑[1,2]、基于节点兴趣[3]、基于节点能力[4,5]、及基于网络运行代价[6]的多种策略;在SP数目的选择上,分别有基于节点能力[7]和基于节点负载[8]的选取策略。以上提出的层次化覆盖网能显著改善系统的服务性能,但不足之处在于其中SP的负载均衡程度不一[8],容易产生系统的性能“瓶颈”,难以同时承担服务索引维护与消息路由的繁重任务,且在层次化结构设计过程中未考虑底层物理拓扑是否能和覆盖网的查询路径尽可能一致,一条查询消息可能通过一条链路或一个节点多次,造成不必要的开销。本文针对节点度数幂率分布的异构网络中的SP负载不均衡与网络拓扑不匹配这两个问题,在不同的SP上分离了路由和服务索引维护功能,实现了覆盖网结构与查询消息路由的优化。

1 系统的体系结构

1.1 覆盖网层次化设计

覆盖网包括三层:路由层、服务层、节点层,如图1所示。顶层为路由层,由稳定、高性能的节点(记为SuSP)构成,占节点总数的比例很小,形成一个很稳定的Chord环,起路由枢纽作用,每个SuSP负责维护一个由邻近的普通节点构成的簇(Cluster),并针对路由层建立路由表,不维护服务索引。中间层为服务层,由较稳定、性能较强的节点(记为OrSP)构成,每个OrSP选择并被绑定到最近的一个SuSP,负责维护一定数目的服务索引,及一个由邻近的普通节点构成的簇,每个SuSP绑定多个物理邻近的OrSP,每个OrSP从其绑定的SuSP中获取路由表,并维护记录着1跳距离内的所有SuSP信息的表(SuSPList),用以不经过路由层的Chord快速找到目标SuSP。底层为节点层,由普通节点构成,记为CP,每个CP连接到一个邻近的作为其簇首的SuSP或Or-SP,借助其进行快速的服务查询。

1.2 超级节点的选择

假设节点的能力强弱、稳定性高低与度数大小是一致的,设网络节点总数 N,SP包括SuSP和 OrSP,数目为 NSP,占总节点比例设为 αSP,αSP=NSP/N,SP最低度数Ksv也为OrSP的最低度数,基于复杂网络理论,节点的度分布可以表述为累积分布函数[9]:P(K)=CK1-γ,且在连通图中所有节点的度都不小于1:P(1)=1,因此可以认为 C=1,有 αSP=P(Ksv)=Ksv1-γ,规定 γ为常数,得 Ksv表示为

图1 覆盖网体系结构

设SuSP总数为Nrt,占总节点比例设为αrt,且αr t=αSP/Div,其中Div大于1,SuSP最低度数为Krt,基于度幂率分布累积概率公式

αrt=P(Krt)=Krt1-γ,得 Krt表示为

1.3 节点和服务的地址分配

采用二维编址方法,一维用于路由层,另一维用于服务层,采用2个不同的Hash函数计算节点或服务在两层对应的地址,分别得到路由层的UPID和服务层的DOWNID。路由层节点SuSPi的ID表示为UPIDi:00…00,其DOWNID永远为0;服务层节点OrSPj(假设绑定到SuSPi)的ID表示为UPIDi:DOWNIDj。在路由层各SuSP按UPID排列在Chord环上,设服务层最大地址值为V,绑定到SuSPi的m个OrSP将依照各自DOWNID的大小排列,并平均划分DOWNID地址空间,依次为:{V/m,2V/m,…,(m-1)V/m,V}。如图 2所示,纵轴代表 UPID,横轴代表DOWNID,DOWNID空间被绑定到同一个SuSP的各OrSP均分,如三个OrSP(a1-a3)绑定到UPIDi所对应的SuSP上,可将对应的ID空间(DOWNID∈[0,V],UPID∈(UPIDi-1,UPIDi])平分成三个矩形,各自对应一个OrSP。

服务的ID编址空间与以上相同,用 2个hash函数分别计算得到服务的UPID和DOWNID,该服务应被放置到的节点的ID应满足:节点UPID最小但不小于服务UPID,且DOWNID最小但不小于服务DOWNID。如果服务(UPIDs:DOWNIDt)对应的坐标(DOWNIDt,UPIDs)落在一个矩形内,则该服务应发布在此矩形对应的OrSP上,如图2中服务索引A、B置于a1上,C置于a2上。

图2 节点和服务索引的2维地址空间

2 系统性能分析

文献[4,5,8]提出了传统的层次化覆盖网设计思想,是以Chord为顶层的2层覆盖网,在结构上等同于本文提出的覆盖网中α rt=0、地址一维分布的情况。本文选定平均查询路径长度(QPL)、簇大小分布均匀度、节点负载均衡程度和查询成功率(QSR)这几个指标,以Div和α rt作为变参,展开性能分析和比较。其中QSR表示为成功查询的总数与查询总数之比。引入随机节点失效模型来描述节点动态加入、退出行为对网络的影响,其中节点失效的概率反比于其度数。

2.1 查询路径长度分析

在2层覆盖网中,发自CP的查询的QPL为CP到其簇首SP的跳数(为h=1)加Chord上的跳数,发自SP的查询的QPL为Chord上的跳数,故总的QPL表示为

在本文的覆盖网中,发自CP的查询的QPL为:CP到其SP的跳数(为h=1),加Chord上的跳数,加目的SuSP到目的OrSP的跳数(为1),发自SP的查询的QPL为:Chord上的跳数,加目的SuSP到目的OrSP的跳数,故总QPL为

在理论上,2层覆盖网中Chord上的节点数是本文的覆盖网的Div倍,当 Div＞2时,有QPL3＜QPL2,此时本文的覆盖网的查询性能超过2层覆盖网。

2.2 负载均衡程度分析

假设各节点的服务请求特性是一致的,理想的负载平衡应实现节点的负载正比与其能力,可通过簇中的CP数目的分布程度来衡量,体现服务请求的平衡程度。求各SP的簇大小与其度数的比值,定义为 Rclsi=Nclsi/ki,其中Nclsi为该SP的簇的大小,ki为该 SP的度,记平均值为,用归一化标准差表示的平衡程度如(5),其值越小,表明簇大小及查询请求的分布越合理。

3 仿 真

3.1 仿真设置

在Windows环境下基于C++开发仿真程序,实现成簇、覆盖网构建、服务发布、失效节点随机选择、查询事件生成、查询执行等过程。在6000个节点构成的节点度数幂率分布的网络拓扑下,设原先每个节点平均提供6个服务,生成5000个随机查询事件并执行查询,记录各指标在不同参数下的平均值,这些参数规定为:αSP分别取值0.01,0.02,0.03,0.04,0.05,Div分别取值4,12,20,探索各性能指标随参数变化的规律。

3.2 仿真分析

依据(1)和(2),获得不同参数下SuSP和Or-SP节点数目,结果显示在表1的二元组中。可以看出,3层覆盖网的路由层节点数仅为几十到上百,且它们之间彼此直接连通或距离很近,能形成稳定高效的路由层。获取不同参数下的QSR如图3,在2层覆盖网中由于Chord上失效节点多,该指标随α SP增大而显著降低,而本文覆盖网中该指标随α SP增大仅略有下降,但均保持在90%以上。值得注意的是,QSR与前述几个指标在α SP的选择上存在性能折中。

表1 不同参数下SuSP和OrSP节点数目

图3 不同参数下查询成功率

平均QPL如图4,可以发现,本文的覆盖网的平均QPL绝大部分在4跳以内,而2层覆盖网的平均QPL都在5跳以上。

图4 不同参数下的平均查询路径长度

在仿真中记录每个簇的大小,依(5)得到不同参数下的σ cls,结果如图5。从中看出本文的覆盖网各Div参数下的σ cls值要显著小于2层覆盖网的,故本文的覆盖网的簇大小与SP能力对应分布较均匀。且随着α SP减小,σ cls值将不断增大,簇大小的分布变得更不均衡。

图5 簇大小比值分布

4 结 语

本文提出了体现拓扑意识、运行稳定的覆盖网体系、地址分配方案,针对P2P覆盖网的负载均衡与拓扑匹配问题进行了专门优化,仿真结果证明了本文提出的方法的优越性。未来的工作包括设计动态控制节点负载的算法,基于节点行为特征和服务内容设计内容复制方法,以改进另一个体现负载均衡的指标,即超级节点上的服务分布平衡程度。

1 乐光学,李仁发,周祖德.基于Region多层结构P2P计算网络模型[J].软件学报,2005,6(6):1140～1150.

2 JESI G P,MON TRESOR A,BABAOGLU O.Proximity-aware superpeer overlay topologies[J].IEEE T ransactions on Network and Service Management,2007,4(2):74～83.

3 ZOELS S,EICHHORN M,TA RLANO A,etc.Contentbased hierarchies in DHT-based peer-to-peer sy stems[C]//IEEE Computer Society.Proceedings of 2006 Symposium on Applications and the Internet Workshops,Phoenix.Arizona.USA,2006:105～108.

4 夏启志,谢高岗,闵应骅,等.IS-P2P:一种基于索引的结构化P2P网络模型[J],计算机学报,2006,29(4):602～610.

5 M IN S H,HOLLIDA Y J,CHO D S.Optimal super-peer selection for large-scale P2P system[C]//Proceedings of 2006 International Conference on Hybrid Information Technology,Jeju Island.Korea,2006:588～593.

6 WAT ANABE K,HAYASHIBARA N,T AKIZAWA M.A superpeer-based two-layer P2P overlay network with the CBF strategy[C]//IEEE Computer Society.First International Conference on Complex,Intelligent and Software Intensive Systems,Vienna.Austria,2007:111～118.

7 HAN S Y,PARK S Y.Adapting superpeer size using particle swam optimization for self-organizing superpeer ring with loosely-consistent DHT[C]//Proceeding of 7th IEEE International Conference on Computer and Information Technology,Fukushima.Japan,2007:463～468.

8 XIAO Li,ZHUANG Zhen-yun,LIU Yun-hao.Dynamic layer management in superpeerarchitectures[J].IEEE Transactions on Parallel and Distributed Systems,2005,16(11):1078～1091.

9 FALO UTSOS M,FALO UTSO P,FALO UTSO C.On Power-Law Relationships of the Internet T opology[C]//Proceedings of ACM SIGCOM M,Cambridge.Massachusetts.USA,1999:251～262.