P2PCenter节点选择机制的分析及改进
2011-09-07郭永平孙一潇
庄 雷,郭永平,孔 燕,孙一潇
(郑州大学信息工程学院,河南郑州450001)
0 引言
随着宽带互联网的迅速发展,P2P流媒体技术逐渐成为流媒体应用领域的研究热点,节点选择更是P2P流媒体系统中的一项关键技术,在节点选择方面笔者已做过相关研究[1-2].为了深入研究P2P流媒体技术,笔者选取国内的一个P2P流媒体开源项目——P2PCenter为研究对象.P2PCenter在节点选择方面运用简单的随机选择策略,协议简单且健壮性好,但却容易造成拓扑失配问题,并且不能保证系统的服务质量.笔者在对P2PCenter流媒体系统分析研究的基础上,针对该系统在节点选择机制上的不足进行改进,提出了基于IP地址库及节点能力的节点选择机制.该机制在保证系统健壮性的基础上,较好地解决了拓扑失配问题,并且能为用户提供更好的服务质量.
1 节点选择机制与分析
在P2P流媒体系统中,请求节点获取资源的过程大致分为三步:资源搜索定位、节点选择与资源获取.笔者的主要工作在第二步.
当前P2P流媒体系统的节点选择机制主要有以下3种.
(1)简单的随机选择策略[3]:该方法对候选的源节点进行随机选择,其特点是协议简单,能够保持系统的网络负载均衡性和健壮性.
(2)针对节点能力的节点选择策略[4]:该方法主要为提高流媒体软件的服务质量,在节点能力方面用到的主要参数有带宽、延迟、丢包率等.
(3)基于位置信息的节点选择策略[5]:该方法主要用于解决P2P网络中的拓扑失配问题.北京大学的Maze系统[6]在节点选择方面就采用该方法.
以上3种节点选择方法的缺点是针对系统某一方面的优化,不能达到整体优化.因此,笔者通过对P2PCenter在节点选择方面的研究,并综合已有节点选择机制提出一种改进的节点选择机制.
2 改进的节点选择机制与分析
在改进的节点选择机制中,综合运用基于位置信息的节点选择策略和针对节点能力的节点选择策略两种方法,在服务器端主要采用类似Maze系统的基于IP地址库的节点选择机制,并作适当的改进,在请求节点端采用针对节点能力的节点选择机制.
2.1 服务器端节点选择机制的实现
服务器端采用基于IP地址库的节点选择策略,目标是对候选节点进行选择筛选后,将节点返回给请求节点端,在返回节点的数目上根据文献[7]返回20个以满足请求节点端的需求.
IP地址库包含了IP地址段及与之对应的地域信息和运营商信息,地域信息可以用来估算网络距离,而运营商信息本身就是一种网络拓扑信息.从IP地址段的地域信息选出底层网络临近的节点作为邻居,而且尽量选择在同一运营商网络内的节点作为请求节点的邻居节点,以方便为用户提供更高的QOS保证.服务器端改进的节点选择机制如下:
(1)请求节目的客户端向服务器发送请求包,其中包含所请求节目的ID以及客户端IP;
(2)服务器接到请求包并对该包解析,从中提取节目ID和客户端IP;
(3)查询存放在服务器上的IP地址库(格式如表1),确定该客户端所属的网络运营商和所处地域信息,将该客户端连同网络运营商和所处地域信息放入所请求节目的源节点列表当中.IPStart和IPEnd表单中的数据分别代表经过编码转换的一个IP段的起止IP.IPIsp表单中的数据代表IP段所属的网络运营商编码,如1代表电信,2代表网通.IPAddress是IP段所在省市编码,例如:福建省厦门市用(52;0851)来表示,上海市用21来表示等.
表1 IP地址库中部分IP段Tab.1 IP database
(4)计算该请求客户端与候选节点列表中所有节点之间的舒适度,把舒适度较小的节点作为更合适的节点.候选节点列表中的节点B与请求节点A之间的舒适度C(A,B)计算公式如式(1):
式中:Cn(A,B)表示两个节点之间网络类型的舒适度,A,B处在同一网络取0,否则取1;Cp(A,B)表示两个节点之间省/州的舒适度,A,B处在同一省/自治区/直辖市取0,否则取1;Cc(A,B)表示两个节点之间城市的舒适度,A,B处在同一城市取0,否则取1.Cn(A,B)也可根据特殊网络运营商情况而定,比如中国联通的网络与教育网之间的接口带宽,比中国电信与教育网之间的大,这种情况下,规定教育网与联通网之间的网络类型距离为 0.8.wn、wp、wc、wpr分别表示 Cn(A,B)、Cp(A,B)、Cc(A,B)、Cpr(A,B)在求取 C(A,B)时所占的比例,四者相加等于1.在中国,由于不同网络运营商之间的网络带宽都较窄,相较于地理位置,相同的网络运营商之间的节点更容易实现良好的网络连接,在改进的机制中规定 wn=55%,wp=20%,wc=10%,wpr=15% .
与Maze系统中的公式比较,本公式主要添加了省间距离Cpr(A,B),表2是部分省/自治区的省间距离的取值.表中取值主要参考两省/自治区之间的实际的物理距离和网络运营商.
表2 部分省/自治区的省间距离CprTab.2 Cprof converted distance between provinces
具体取值时,同省之间的省间距离值为0.不同省之间取值时分两步:第一步,用两省之间所隔的省数乘以0.1得到第一步结果;第二步,若两省间网络运营商相同,则直接以第一步结果作为省间距离值,若不同则在第一步结果的基础上再加上0.1作为最终的省间距离值.
添加Cpr(A,B)能够进一步的减少覆盖网的压力,选择临近节点.比如当前观看节目的分别有3 个节点是:A(河南,联通)、B(黑龙江,联通)、C(河北,联通).其中节点A作为请求节点,如果不添加 Cpr(A,B),通过计算得知 C(A,B)=C(A,C),即节点B和C对于节点A来说舒适度相等,而实际上,节点C在物理位置上要更加接近节点A.添加 Cpr(A,B)后可以计算得知 C(A,B)<C(A,C),从而选择节点C作为节点A的邻居节点进行流媒体数据传输.
(5)将计算所得的舒适度用快速排序法作升序排序,然后选取舒适度较小的前20个节点作为候选节点发给请求节点,如果当前观看该节目的节点不够20个,在排序后就全部返还给请求节点.
2.2 请求节点端节点选择机制的实现
请求节点端接收经过服务器筛选后的节点,在请求节点端主要通过比较节点能力来进一步对这些节点进行优化选择,最终挑选出一组最优的服务节点.在节点能力方面主要参考节点可用带宽B(即当前候选节点可上传的速率)、候选节点在数据传输中的丢包率L以及候选节点与请求节点间的网络延迟T.为了综合运用这3个度量,定义候选节点j对请求节点i的优良度Hi(j)为:
此外,为了尽量避免单点失效问题以及尽量保证最大的网络传输率,系统采取并行传输策略,从备选的20个节点中选出m个节点使其优良度之和最大.假定流媒体播放速率为v0,m的选取可由公式(3)来确定,从而保证流媒体的播放流畅性.
3 可行性分析
在理论方面,由于对P2PCenter系统在节点选择上的一个改进,且节点选择在该系统中是一个独立的代码模块,因此笔者所提出的改进的节点选择机制完全可以在源代码基础上添加新的代码来实现.
在具体实现方面,该算法在服务器端主要需要计算出请求节点与源节点之间的舒适度并进行快速排序.时间复杂度方面,假设源节点列表中节点个数为n,运用快速排序该算法的时间复杂度为o(nlog2n),因此该机制的时间复杂度相对较小.在空间复杂度方面,只需添加节点的运营商信息和地域信息,对系统原来的空间复杂度影响很小.在请求节点端,求出可用带宽B、丢包率L及延迟T以得到节点优良度,因此该算法在请求节点端也是可行的.
4 结论
通过研究P2PCenter源代码,针对该流媒体系统在节点选择方面的不足提出了基于IP地址库和节点能力的双重节点选择机制.该机制的实现主要分两步:首先,在服务器端,根据请求节点的IP查询IP地址库,确定该节点的物理信息,然后根据该物理信息求出节点舒适度,利用该舒适度从候选节点中选出一组在物理距离上与请求节点临近的节点.其次,在请求节点端,利用候选节点与请求节点间的优良度进行进一步筛选得出最终所需要的服务节点.
该节点选择机制从整体上解决了该系统在网络拓扑中的失配问题,可极大的降低系统网络延迟,保证了系统的健壮性.从服务质量上,减少了请求节点端与服务节点端的网络时延,使得请求节点端能够更快的得到想要的数据,同时由于考虑到了服务节点的服务能力,选择出一组节点能力强的节点,可以让用户得到更为稳定的服务.
[1]庄雷,陈鸿昶,黄建华,等.基于超级点划分区域的对等网络模型[J].计算机应用与软件,2005,3(9):10-11.
[2]侯得果,庄雷.基于随机性和文件块相似性的结点选择策略[J].计算机工程与设计,2010,59(6):1376-1378.
[3]郑洁,张松,齐洁,等.P2P流媒体节点选择机制的研究与仿真[J].计算机工程与设计,2007,28(22):5396-5399.
[4]MOHAMED H,AHSAN H,BOYAN B.PROMISS:peer-to-peer media streaming using Collectcast[C]∥Proceedings of MM Berkeley,California,USA,2003:45-54.
[5]XIAO Li,LIU Yun-hao.Improving unstructurdpeerto-peer systems by adaptive connection establishment[J].IEEE Trans on Computers,2005,54(9):1091-1103.
[6]杨志超.Maze中基于位置感知的邻居网络构造算法和P2P邻居搜索[D].北京大学信息科学技术学院,2004.
[7]MOHAMED H,AHSAN H,XU Dong-yan.Collectcast:a peer-to-peer serveice for mediastreaming [J].Mutimedia Systems,2005,11(1):68-81.