P2P系统中一种负载均衡的超级节点选择策略

朱永琼

摘要 传统的分层P2P网络拓扑构造存在超级节点服务能力偏低的问题，特别是在对时延要求高的应用中，超级节点的服务能力偏低将不能满足应用的需求。本文研究一种超级节点负载均衡的层次化网络拓扑构造方法，该方法在选择超级节点时不仅考虑节点的容量还将节点的剩余负载作为重要参考指标。在同等条件下，本方法可提高网络呑吐量，减少网络流量开销，为P2P网络的大规模应用提供了实用基础。

【关键词】P2P网络 负载均衡 超级节点

1引言

P2P技术已经发展了16年，成为互联网上最主要的应用。随着P2P用户激烈的增长，P2P网络己经呈现海量化、分散化、动态化的特征。那么，在巨大的P2P网络中如何进行高效的资源定位是P2P领域亟需解决的关键难题之一。2004年Liu在Infocom会议上指出，优化拓扑是提高P2P系统搜索效率的一种有效途径。在P2P网络结构中，层次化P2P网络是最主流、研究最多并且应用最广的一种网络结构，最早由Yang，J在2003年提出[1]。后来在该思想体系下发展出了众多具有典型特点的网络模型。2007年，Gian等人提出了SG2[2]，一种延时受限的超级节点选择算法，将节点间延时小于系统阈值的能力强的节点选出作为超级节点来保证数据的同步。2009年，Hung-Chang Hsiao在[3]中指出P2P网络无论在网络拓扑结构还是通讯机制方面都具有小世界SW模型特征，它依据特征路径长度和聚类系数选择超级节点，但是此方法不可避免地具有与结构化P2P系统类似的缺点。2010年，Jung-Shian Li使用完美差异图模型对层次化P2P网络进行优化[4]，2013年，Shreyas提出了一种自适应的超级节点选择算法[5]，选择超级节点依据节点的响应距离。国内也早己开展了此方面的研究。如2006年中科院计算所的夏启志提出一种基于索引的P2P网络模型IS2P2P[6]。2007年东北大学的张骞给出了基于领域的P2P信任模型的定义，然后在此基础上提出了一种针对无结构化P2P网络的自适应拓扑进化协议[7]。

传统的分层拓扑构造存在筛选出的超级节点服务能力偏低的问题，特别是在对时延要求高的应用中，超级节点的服务能力偏低将不能满足应用的需求。因此，本文拟研究一种超级节点负载均衡的层次化网络拓扑构造方法，研究的内容包括：超级节点选择模型、节点加入和退出方法等。该方法可使选出的超级节点在同等条件下，提供更短的搜索长度，更少的网络流量开销，为P2P网络的大规模应用提供了实用基础。

2拓扑构造

在层次化网络拓扑构造过程中，超级节点和普通节点的划分仅仅依赖系统提供的阈值，将系统中超过阈值的所有节点都设定为超级节点，普通节点随机连到超级节点上。每当超级节点收到一个叶子节点的连接请求，只要不超过其最大连接数就立即连接，而没有考虑到添加该叶子节点的连接就必须承担该叶子节点的查询工作量，增大了该超级节点的查询负载。事实上，网络中往往存在“热区”，大量的查询请求都被转发到少数容量大的节点，导致节点间的负载极度不均衡，降低了网络吞吐量。因此，建立超级节点负载均衡模型是层次化P2P网络拓扑构造必须解决的关键问题。

2.1系统模型

给定一个P2P系统，初始状态下节点根据现有的网络协议如Internet相互连在一起，每一个节点能和其他节点通信，每一个节点都知道自己的IP地址和端口号。网络是动态变化的，节点可以自由的加入和离开。

每一个节点都有个邻居节点列表，记录的是该节点所有的邻居信息。节点邻居是网络节点的子集，邻居列表的内容定义着整个网络拓扑。邻居列表的动态变化，网络拓扑也不断变化。

节点是异构的，它们的计算能力和容量各不相同，网络连接的带宽都不同，所以每个节点能连接的节点的个数都有限制。假定节点的容量为Ci，代表节点ni的处理能力，假定每一个节点都知道它自己的能力。网络中任意两个节点ni，nj之间的RTT延迟就是节点间的延时距离，以（ni，nj）表示。

2.2超级节点的选择

在本文中，超级节点的选择不仅关注节点的容量还要关注节点的负载均衡。不是选择容量最大的节点作为超级节点，而是根据其剩余负载的能力和节点的容量，选出合适的节点作为超级节点，从而能提高网络的吞吐量。

假定N中存放的是延时范围内的所有节点，本文的目标是从N中选出一个容量大并且负载均衡的节点作为超级节点。假定系统定义的叶子节点和超级节点间的延时不能超过t，超级节点之间的延迟不能超过t+k。 是节点的平均容量值，Ri是节点的剩余容量。那么对于网络中的任意节点ni，nj和节点之间的延时d（ni，nj），问题描述为：

（1）每一个节点不是超级节点就是叶子节点；

（2）对于每一个叶子节点ni和超级节点Sm，有d（ni，Sm）≦t；

（3）对于任两个超级节点Sm和Sn，有d（Sm，Sn）≦t+k；

（4）对于任一个超级节点Sm，其容量超过 ，并保证其Ri是最小的。

节点的容量必须大于系统的平均容量值 才可能成为超级节点。而系统的平均容 是根据系统中节点容量的平均值的k倍。

假定有n个节点加入了网络，那么

k是系统参数，k≧1。

节点的负载主要由三部分组成：

（1）节点的维护负载。每个节点需要周期性的通过ping/pong消息对连接进行维护，处理节点的加入离开，和缓存表的维护。

（2）节点的查询负载。每个节点都能夠接收查询消息并处理它们。

（3）节点的响应负载。一旦节点命中查询，节点会发送响应消息沿原路返回。

表1给出超级节点的选取过程。

超级节点己经选出，需要对范围内的其他所有节点建立连接。叶子节点与超级节点的连接过程如表2所示。endprint

在超级节点与叶子节点的连接过程中，需要对已经建立连接的节点做标记，即将选出的超级节点将标记为超级节点sp，其他的节点标记为叶子节点。不管是超级节点还是叶子节点，只要是打标的节点，以后的探测消息均不会在该节点进行转发。由于节点的探测是广播的方式，因此对已建立连接的节点做标记，会明显的减少广播过程中的消息传递，从而减少网络开销。

3结束语

P2P网络的拓扑管理协议作为一个基础协议，为上层丰富的P2P应用提供了服务节点选择的支撑，是非常重要的一个研究方向。本文提出的超级节点选择算法，充分的考虑了节点的负载均衡，与传统方法相比，系统的服务能力明显提升。

参考文献

[1] Yang， J， An efficient interest-group based search mechanism in unstructured peer-to-peer networks， IEEE Computer Society，2003.

[2] Jesi， G.P.，"Proximity-aware superpeer over lay topologies"，Network and Service Management， IEEE Transactions on computer lecture p.74-83，2007.

[3] Hung-Chang， Hsiao，"Building Sma11-World Peer-to-Peer Networks Based on Hierarchical Structures"， IEEE Transact ions on Parallel and Distributed Systems， vol.20， pp.1023-1037，2009.

[4] Jung-Shian，Li，"An Efficient Superpeer Overlay Construction and Broadcasting Scheme Based on Perfect Difference Graph"，IEEE Transactions on Parallel and Distributed Systems，vol.21，pp.594-606，2010；

[5] Shah， Shreyas Shailesh，"Adaptive server selection in peer-to-peer networks"，San Diego State University，2013.

[6]夏啟志，谢高岗，闵应骅，李忠诚.IS2P2P：一种基于索引的结构化P2P网络模型[J].计算机学报，2006.

[7]张骞，张霞，刘积仁.一种有效的Peer-to-Peer自适应拓扑进化协议[J].软件学报，2007.endprint