一种基于节点聚类的网络坐标系统

摘要:网络坐标可通过较少的测量预测出节点间的网络距离,因此可帮助P2P流媒体直播系统进行节点选择。但是目前尚未有针对P2P流媒体直播系统的网络坐标系统。针对该问题,本文提出了一种将节点聚类的网络坐标系统DDNCNC,采用两层式的结构,将GNP与PCoord方法结合,并利用GNP计算出的网络坐标将节点重新聚类,使PCoord的参考节点选择更加精确,实验证明系统具有很好的抗扰动性和较好的精度。

关键词:P2P流媒体;网络坐标;节点选择;聚类

中图分类号:TP393 文献标识码:A文章编号:1007-9599 (2010) 06-0000-02

Network Coordinate System Based on Node Clustering

Yang Bin 1,2,Zhou Bing 1,2

(1.Henan Information Network Lab of Key Disciplines,Zhengzhou450052,China;2.School of Information Engineering,Zhengzhou University,Zhengzhou450052,China)

Abstract:Network coordinates can be predicted by measuring small network distance between nodes,it can help P2P live streaming system’s node selection.However,there is not yet network coordinate for live streaming system.For the problem,this paper gives a network coordinate system based on node clustering-NCNC with a two-layer structure,in this system the method of GNP and PCoord were combined,the coordinates calculated by GNP were used to make nodes cluster,so that reference nodes in PCoord were selected more precisely,experimental results show the system has good disturbance rejection and better precision.

Keywords:P2P live media streaming;Network coordinate;Node selection;Clustering

一、介绍

随着互联网的发展,基于P2P技术的流媒体系统得到了普及。商用的P2P视频系统得到长足的发展,国内目前常见的有PPLive[1],PPStream[2]等,这些软件在丰富人民生活的同时,也带来诸如浪费带宽等问题。

P2P流媒体的流量过高与P2P流媒体的节点选择机制有很大的关系。目前主流的节点选择机制是利用网络坐标系统提供的网络距离信息来帮助整个系统进行合理的节点选择,目前没有网络坐标系统针对P2P流媒体直播系统的特点做出合理的设计。

针对上述问题,本文设计了一种将节点聚类的网络坐标系统NCNC(Network coordinate based on node clustering)。

二、相关技术

(一)GNP

GNP[4]的核心思想是把因特网嵌入到一个欧几里得空间,因特网中的任何节点都作为该欧式空间的一个点。任何节点都可通过路标节点来计算自己的网络坐标。

GNP中有两类节点,一种被称为路标节点,路标节点按照一定准则首先被选择出来,在路标节点被选择出来后,它们之间首先测量各自到对方的RTT值,跟据测得的RTT值,采用Simplex downhill method方法来得到路标节点的网络坐标,

在上述公式中, 表示两个节点之间的实际网络距离,一般用RTT来衡量, 表示两个节点在欧几里得坐标系中计算所得的值。然后用 函数表示二者之间的误差。

另一类节点是普通节点,在上一步中已计算出各个路标节点的网络坐标,假设有N个普通节点,测出节点对每个路标节点的RTT值,然后按照下式进行计算。

(二)PCoord

PCoord[5]的设计目标是设计一种完全分布式的基于P2P的网络坐标系统,在此系统中,节点只需根据自己对任意少数节点的RTT值即能计算自己的坐标。

PCoord系统主要采用了三种机制来使整个系统达到稳定,以及快速收敛的目的。

样本衡量机制:为了避免精度不高的参考节点对计算坐标的影响,引入了样本衡量机制。节点i有一个相对估计误差,定义节点i的相对估计误差 =MIN(1, ),将节点i的 定义为 =1- 。样本中节点j的权重为

摩擦力机制:在更新节点i的坐标时,将 加入到丢失函数中,作为阻止i的新节点移动的阻力因素。对一个新加入的节点而言,摩擦系数被设为0,节点i的摩擦系数为 ,j节点的坐标更新过程变为寻找节点i的新坐标 ,来最小化下式的 ,

阻尼机制:阻尼机制是为了减小坐标精确度不高的样本空间对计算坐标的影响。根据现在的一组样本的吻合度指数,采用阻尼机制可以决定坐标的移动距离,即坐标的更新程度。

三、设计方案

(一)NCNC系统的结构

由于层次性的网络坐标系统能降低距离较低时的相对误差[6],并且由文献5得知,在PCoord系统中,样本节点中最理想的方式是包括一部分的距离预测节点较近的样本节点,也要包括一部分较远的节点,在分布式系统中,样本节点的选取无法达到如此精确。因此本系统采用了如下结构。

如图3.1所示,本系统是一种两层式的网络坐标系统,每个节点需采用GNP方法和PCoord方法分别计算节点的局部和全局坐标。在利用GNP计算时,选取P2P流媒体直播系统中的超级节点作为GNP的路标节点。每个在系统中的节点首先利用GNP方法计算的坐标为节点的全局坐标。节点计算出自己的全局坐标后,进入聚类过程。节点与自己聚类的路标节点联系,获得所有路标节点(超级节点)的坐标,通过与各超级节点的坐标比较,计算出网络距离,确定离自己最近的超级节点,并加入其所在的聚类。下一步计算节点的局部坐标,采用PCoord方法。节点将该聚类的若干节点选取为样本节点,在选取PCoord方法的K个样本节点时假设聚类的数量为n,选取 个内部节点,同时挑选 个其他的聚类,从每个聚类中随机挑选一个节点组成PCoord方法的样本节点。通过上述方法,PCoord的样本节点为近距离节点和远距离节点的集合。

图3. 1 NCNC系统节点的计算

(二)坐标的计算

由于每个在本系统中的节点的坐标包括两部分,整个节点坐标的获取过程分为两步,第一步,以每个超级节点为路标节点,采用集中式的方法首先得到初始坐标。第二部,采用一种分布式的摩擦力机制来更新坐标。

局部坐标的计算依靠PCoord方法,不同之处在于样本节点的选取。GNP是一种集中式的算法,坐标更新依赖于几个路标节点,在路标节点失效,或者同时请求的节点数过多情况下,GNP算法可能无法正常更新坐标,在这种情况下,我们从每个聚类中选取若干节点加入PCoord的样本节点。从而保证每个节点都能正常获取自己的网络坐标。

对于两个节点i和j,利用GNP方法计算出来的全局坐标分别为: 、 ,利用PCoord方法计算出来的局部坐标分别为: 、 。则在本系统中,两个节点之间的距离 由网络坐标计算得出,如果两个节点在同一聚类,则两个节点之间的距离用局部坐标之间的距离表示: =|| - ||。如果两个节点在不同聚类,则两个节点之间的坐标用全局坐标之间的距离表示: =|| - ||。

四、实验

本实验涉及到的数据都来自于king数据集[7],GNP系统的结果由GNP software[8]生成,PCoord系统和本文所提出的系统采用P2P Simulator D_P2P_SIM[9]模拟实现。

网络坐标系统的精确性采用相对误差RE来衡量,假设两个节点i和j,则其相对误差RE= ,其中 和 分别代表节点i和节点j的网络坐标, 表示实际测量值。设t为节点加入到系统到退出的时间,则用节点的平均预测误差的变化来衡量系统的稳定性。平均预测误差是在系统模拟的60秒内统计出的数据所计算出来的平均误差。

(一)NCNC系统的精确性

将NCNC系统与GNP和Vivaldi三种系统做出比较,从图4.1可以看出,三种系统中,本系统的精确度最高,GNP次之,Vivaldi系统的精度最低。由于NCNC系统中的GNP采用了性能较好的节点作为路标节点,PCoord方法中的样本节点选取更加精确,结合了远距离节点和近距离节点,所以整个系统的精确性略高于GNP。两层式的结构也有效的减小了距离较小时系统的相对误差。

图4.1 三种系统的精度对比

(二)NCNC系统的抗扰动性

从图4.2中可以看出,在比较极限的情况下,每个节点在系统的生存时间超过10秒后,平均预测误差就稳定在12ms到13ms之间。这说明节点的频繁加入或者退出对NCNC系统的影响不大。在NCNC系统中,节点的全局坐标是由GNP方法得出,节点的局部坐标是由PCoord方法得出,由于通过了节点聚类对样本空间进行了详细的划分,这些节点同时大量退出的可能性不大,所以节点的局部坐标受节点加入或退出的影响也不大。

图4. 2 NCNC系统在高扰动性下的平均预测误差

五、小结

本文提出了一种适用于P2P流媒体直播系统的基于节点聚类的网络坐标系统――NCNC。通过实验表明,NCNC具有较好的精度和抗扰动性。

参考文献:

[1]Y.Liu,X.Hei,C.Liang and K.W.ROSS."Insight into pplive:A measurement study of a largescale p2p iptv system".2007

[2]PPStream[EB/OL]./,2010

[3]Dabek F,Cox R,Kaashoek F,Morris R.Vivaldi:A decentralized network coordinate system.In:Proc.of the ACM SIGCOMM.New York:ACM Press,2004.15−26

[4]T.S.Eugene N,Hui Z.A Network Positioning System for the Internet.In:Pro of USENIX Annual Technical Conference 2004.Boston,MA.June,2004,424-438

[5]Lehman L,Lerman S.PCoord:Network position estimation using peer-to-peer measurements.In:Proc.of the 3rd IEEE Int’l Symp. on Network Computing and Applications,2004,15−24

[6]Chengbo Dong, Guodong Wang, Xuan Zhang,et al.Two-layer network coordinate system for Internet distance prediction

[7]Leonard D,Loguinov D.Turbo king: Framework for large-scale internet delay measurements.In:Proc.of the IEEE INFOCOM.Piscataway:IEEE Press,2008

[8]T.E.Ng.Global Network Positioning(GNP) software.www.cs.cmu.edu/∼eugeneng/research/gnp/,2003

[9]Simulator:D_P2P_SIM,/p/d-p2p-sim/