论文部分内容阅读
中图分类号：TP3 文献标识码：A 文章编号：1671－7597（2011）0210168－01
1 Kademlia在搜索中存在的问题
因为Kademlia是基于DHT构造的，而基于DHT的P2P系统利用某种哈希函数操作某些参数（例如IP地址）为每个网络节点产生一个m位的ID值，为网络节点产生ID值时，没有考虑到实际网络情况，Kademlia在构建overlay层面的过程中没有考虑与物理层面匹配的问题，导致overlay层面的邻居节点在物理层面可能会相距很远，这样在搜索过程中会出现许多不必要的路由，甚至超时导致搜索失败，大大降低了搜索效率。
2 基于区域划分的改进Kademlia模型
2.1 区域划分与节点归属
为了避免上述问题，本文提出以下方法，逐步精确的为节点确定位置，并且易于在现有网络中实现。
因特网结构错综复杂，但是一般的，可以认为地域上相邻或相近的节点在网络中也是相邻或相近的。因此考虑将地图划分为多个区域，单个区域视为一个区域点，再将这些点连接成为一个网络，这样的网络看作是一个有向连通图G=(V,E)，任意两个节点Va到Vb是否直接连通由实际地理位置决定，当然也关系到这两个区域点的网络的连通程度。然后再为这些区域点编码。编码所遵循原则是：保证实际相邻（相近）区域編号的编号距离相邻（相近）的，实际距离较远的区域的编号也是相应的编号距离较远的。这样的区域划分是很好实现的。一种计算区域a和区域b的编号距离D的方法，其中Sa、Sb表示区域a和区域b的编号。
Da2b=Sa⊕Sb
在实际操作中，需要为区域选择具有代表性的节点作为区域界点，以便于新加入节点判断自己所属的区域。可以选择多个区域中靠近网络中心的稳定的节点作为区域界点，选择多个是为了冗余保持区域界点总是有效的。
现在需要为新加入网络的用户节点确定其所属的区域。用户节点首先对各个区域点进行N次RTT（round trip time）探测，计算到每个区域点的平均延迟间Tavg。比较后得到最小延迟，将该节点归入获得最小延迟的区域点所代表的域。由此一来，用户节点所处的网络位置就粗略的确定了，并且用户与用户之的远近关系可以由所属区域编号很清晰的表示。稍后介绍一种具体的实现过程
2.2 进一步精确定位
上面为用户节点粗略的确定了其所处的网络位置。下面将进一步将节点位精确化。通过对IP地址分配的研究发现，地理位置相近的节点的IP地址有很可能也是相近的。根据上述的结论，可以将节点公网IP地址作为进一步定位节点的参数。而公网IP地址分配并非完全依据地理位置分配，有可能出现的情况是：两个点公网IP相近，然而地理位置上他们相距较远。例如210.012.010.*是在广东而与之相近的IP地址210.012.011.*处于吉林省。虽然这样的情况并不普遍，公网IP地址仍只能作为辅助定位的参数，可以给其赋一个较小的权值，使其节点定位影响不那么大。按照上述两点，下面将给出一个具体节点定位过程。
2.3 具体的算法过程
本节以一个新的节点加入网络的过程以及节点搜索文件的过程来阐述算法前面提到过一种计算区域a和区域b的距离Da2b的方法，节点的距离同样采用异或的方法计算：
d(x,y)=x⊕y
采用异或计算节点间距离的好处在于，计算简单耗时小，并且节点编号的越高拥有越高的权值。例如，最高位相异的两个节点，异或后得到的距离很大，于可以将权重较重的因素编码放在编号的较高位，权重较低的因素编码放在较低位。
在现普遍应用于edonkey、emule等P2P软件的Kademlia算法中，新节点入时，将随机分配给一个160位的编号。现以改进Kademlia协议为例阐述本算法。
节点A想要加入P2P网络，其过程可描述如下：
第一步，A对系统选定的m个区域点N1到Nm各发送探测包k次。对每一个区域点计算这k次的平均值如下所示：
k取一个经验值，使其能够保证RTT计算误差尽量小又不至于花费太多时间。找到这m个平均RTT的最小值，设该最小值是节点A到区域点Nj的RTT平均值，那么将Nj
做为节点A所处的区域。设Nj二进制编号为SNj，其位数为t1，那么m的取值范围如下所示。
2t1-1 将SNj作为节点A的编号SNA的高t1位。现在A的编号为SNj……。这样一来，节点A在实际网络的大概位置就确定了。
第二步，找到A的公网IP地址，这里需要强调的是公网IP地址，而不是虚拟的内网IP地址。因为只有公网IP地址是符合论文第三部分所提出的第二个结论的。在同一个内网中，节点间的网络延时相对来说可以忽略不计的，因此不需要将内网IP地址作为节点网络定位的一个因素。一定程度上，节点公网IP地址反应了其所处的网络位置，因此，将节点A的公网IP地址IP作为编号SNA的第二部分，占32位。经研究，在一定范围内，公网IP地址的差别主要体现在IP地址的后面24位，因为公网IP地址只是用于进一步的精确定位，此步骤建立在节点位置已经大致确定的基础上，因此，完全可以将前8位忽略。设节点A的IP后24位为IPA24，则现在节点A的编号为SNjIPA24……，已经确定的一共是t1+24位。第三步，按照某种随机散列算法生成160-(t1+24)位的随机序列。这样就为节点A生成了一个160位的编号。前面t1+24位是用于保证节点的物理定位，而后面的t2=160-(t1+24)位由节点随机生产，保证任意两个节点编号重复的机率很小，几乎为0。至于为什么要一共是160位，这是借鉴的Kademlia协议的做法，根据统计学规律，160位的SHA1散列值可以唯一的确定一份特定数据内容的文件。因此，节点编号也暂时相应的采用160位了。
参考文献：
[1]Robert F M A.Java P2P技术内幕[M].高龄、刘红、周兆确译，北京：人民邮电出版社，2003.
[2]赵科军、刘洋、仇一鸿等，基于异或运算对等网模型Kademlia研究[J].山东科学，2007（6）：68-71.
[3]张建伟、连卫民，P2P对等网络路由模型特性分析[J].河南科学，2007，25（5）：827-830.
[4]庄雷、郭永强、潘春健，基于Gnutella协议与划分技术的P2P网络模型的设计与实现[J].计算机应用研究，2004，21（9）：253-255.
作者简介：
赵娟娟（1979-），南昌陆军学院科文教研室讲师。
1 Kademlia在搜索中存在的问题
因为Kademlia是基于DHT构造的，而基于DHT的P2P系统利用某种哈希函数操作某些参数（例如IP地址）为每个网络节点产生一个m位的ID值，为网络节点产生ID值时，没有考虑到实际网络情况，Kademlia在构建overlay层面的过程中没有考虑与物理层面匹配的问题，导致overlay层面的邻居节点在物理层面可能会相距很远，这样在搜索过程中会出现许多不必要的路由，甚至超时导致搜索失败，大大降低了搜索效率。
2 基于区域划分的改进Kademlia模型
2.1 区域划分与节点归属
为了避免上述问题，本文提出以下方法，逐步精确的为节点确定位置，并且易于在现有网络中实现。
因特网结构错综复杂，但是一般的，可以认为地域上相邻或相近的节点在网络中也是相邻或相近的。因此考虑将地图划分为多个区域，单个区域视为一个区域点，再将这些点连接成为一个网络，这样的网络看作是一个有向连通图G=(V,E)，任意两个节点Va到Vb是否直接连通由实际地理位置决定，当然也关系到这两个区域点的网络的连通程度。然后再为这些区域点编码。编码所遵循原则是：保证实际相邻（相近）区域編号的编号距离相邻（相近）的，实际距离较远的区域的编号也是相应的编号距离较远的。这样的区域划分是很好实现的。一种计算区域a和区域b的编号距离D的方法，其中Sa、Sb表示区域a和区域b的编号。
Da2b=Sa⊕Sb
在实际操作中，需要为区域选择具有代表性的节点作为区域界点，以便于新加入节点判断自己所属的区域。可以选择多个区域中靠近网络中心的稳定的节点作为区域界点，选择多个是为了冗余保持区域界点总是有效的。
现在需要为新加入网络的用户节点确定其所属的区域。用户节点首先对各个区域点进行N次RTT（round trip time）探测，计算到每个区域点的平均延迟间Tavg。比较后得到最小延迟，将该节点归入获得最小延迟的区域点所代表的域。由此一来，用户节点所处的网络位置就粗略的确定了，并且用户与用户之的远近关系可以由所属区域编号很清晰的表示。稍后介绍一种具体的实现过程
2.2 进一步精确定位
上面为用户节点粗略的确定了其所处的网络位置。下面将进一步将节点位精确化。通过对IP地址分配的研究发现，地理位置相近的节点的IP地址有很可能也是相近的。根据上述的结论，可以将节点公网IP地址作为进一步定位节点的参数。而公网IP地址分配并非完全依据地理位置分配，有可能出现的情况是：两个点公网IP相近，然而地理位置上他们相距较远。例如210.012.010.*是在广东而与之相近的IP地址210.012.011.*处于吉林省。虽然这样的情况并不普遍，公网IP地址仍只能作为辅助定位的参数，可以给其赋一个较小的权值，使其节点定位影响不那么大。按照上述两点，下面将给出一个具体节点定位过程。
2.3 具体的算法过程
本节以一个新的节点加入网络的过程以及节点搜索文件的过程来阐述算法前面提到过一种计算区域a和区域b的距离Da2b的方法，节点的距离同样采用异或的方法计算：
d(x,y)=x⊕y
采用异或计算节点间距离的好处在于，计算简单耗时小，并且节点编号的越高拥有越高的权值。例如，最高位相异的两个节点，异或后得到的距离很大，于可以将权重较重的因素编码放在编号的较高位，权重较低的因素编码放在较低位。
在现普遍应用于edonkey、emule等P2P软件的Kademlia算法中，新节点入时，将随机分配给一个160位的编号。现以改进Kademlia协议为例阐述本算法。
节点A想要加入P2P网络，其过程可描述如下：
第一步，A对系统选定的m个区域点N1到Nm各发送探测包k次。对每一个区域点计算这k次的平均值如下所示：
k取一个经验值，使其能够保证RTT计算误差尽量小又不至于花费太多时间。找到这m个平均RTT的最小值，设该最小值是节点A到区域点Nj的RTT平均值，那么将Nj
做为节点A所处的区域。设Nj二进制编号为SNj，其位数为t1，那么m的取值范围如下所示。
2t1-1
第二步，找到A的公网IP地址，这里需要强调的是公网IP地址，而不是虚拟的内网IP地址。因为只有公网IP地址是符合论文第三部分所提出的第二个结论的。在同一个内网中，节点间的网络延时相对来说可以忽略不计的，因此不需要将内网IP地址作为节点网络定位的一个因素。一定程度上，节点公网IP地址反应了其所处的网络位置，因此，将节点A的公网IP地址IP作为编号SNA的第二部分，占32位。经研究，在一定范围内，公网IP地址的差别主要体现在IP地址的后面24位，因为公网IP地址只是用于进一步的精确定位，此步骤建立在节点位置已经大致确定的基础上，因此，完全可以将前8位忽略。设节点A的IP后24位为IPA24，则现在节点A的编号为SNjIPA24……，已经确定的一共是t1+24位。第三步，按照某种随机散列算法生成160-(t1+24)位的随机序列。这样就为节点A生成了一个160位的编号。前面t1+24位是用于保证节点的物理定位，而后面的t2=160-(t1+24)位由节点随机生产，保证任意两个节点编号重复的机率很小，几乎为0。至于为什么要一共是160位，这是借鉴的Kademlia协议的做法，根据统计学规律，160位的SHA1散列值可以唯一的确定一份特定数据内容的文件。因此，节点编号也暂时相应的采用160位了。
参考文献：
[1]Robert F M A.Java P2P技术内幕[M].高龄、刘红、周兆确译，北京：人民邮电出版社，2003.
[2]赵科军、刘洋、仇一鸿等，基于异或运算对等网模型Kademlia研究[J].山东科学，2007（6）：68-71.
[3]张建伟、连卫民，P2P对等网络路由模型特性分析[J].河南科学，2007，25（5）：827-830.
[4]庄雷、郭永强、潘春健，基于Gnutella协议与划分技术的P2P网络模型的设计与实现[J].计算机应用研究，2004，21（9）：253-255.
作者简介：
赵娟娟（1979-），南昌陆军学院科文教研室讲师。