论文部分内容阅读
摘 要： 分析现有P2P网络存在的安全问题，并针对这些问题提出新的解决方案，进行优化，并以Chord协议说明该模型的实现。实验证明，提出的方案是有效的，在具有一定比例恶意节点的P2P网络中，该方案对于信息窜改、信息窃听及路由功能失效等类型的恶意攻击有较好的抑制作用，不会降低网络的查询效率。
关键词： 路由表结构；网络节点；路由算法；chord
中图分类号：TP393.02 文献标识码：A 文章编号：1671－7597（2012）0210089－02
1 P2P概述
P2P是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源（处理能力、存储能力、网络连接能力、打印机等），这些共享资源需要由网络提供服务和内容，能被其它对等节点直接访问而无需经过中间实体。在此网络中的参与者既是资源（服务和内容）提供者，又是资源（服务和内容）获取者。P2P技术是一种用于不同PC用户之间、不经过中继设备直接交换数据或服务的技术。它打破了传统的Client/Server模式，在对等网络中，每个节点的地位都是相同的，具备客户端和服务器双重特性，可以同时作为服务使用者和服务提供者。
P2P路由模型分类：
目前，典型的P2P路由模型主要有如下几种：
1）集中式目录结构模型，它能提供较好的查找资源性能，但是存在服务质量无法提高和单点崩溃的问题。
2）洪泛请求模型，它是纯对等网络模型，不存在单点崩溃问题，但容易造成消息泛滥，系统的可扩展性难以提升。
3）结构化覆盖网路由模型，它能平衡负载，改善网络可扩展性，但是没有考虑网络的实际拓扑结构，邻近的节点也有可能散列到相隔很远处，要经过很长的搜寻路径才能获得数据，严重降低了路由的效率。将Chord、CAN、Pastry、Tapestry，4种结构化覆盖网络模型从拓扑结构、路由原理、路由性能几个方面进行比较可知，Chord具有简单性、可靠性和性能稳定
2 Chord环的构建
一致的SHA-1哈希函数赋予对等节点和数据关键字一个m位的标识符。一个对等节点的标识符由哈希函数计算对等节点的IP地址得到，而数据关键字的标识符则由哈希函数计算数据关键字得到。标识符的长度m必须足够长，保证用哈希函数计算数据关键字时不会得到两个相同的标识符。对等节点标识符（如N8）以2m为模顺序排列在标识符圆环上。关键字k被存储在标识符等于或大于k的第一个对等节点上。这个对等节点被称为关键字k的后续对等节点，用公式N=successor(k)表示。如果标识符用0到2m-1表示，那么successor(k)就是顺时针方向关键字k的第一个对等节点。这个标识符圆被称为Chord环。
3 基于信任概率的双向路由表模型
本文以Chord协议说明该模型的实现，基于信任概率的双向路由表模型：增加一张路由表保存初始chord反向环路由信息，并添加信任度项。数据结构如下表1所示。
Successor_R(n)：节点n的反向后继节点。节点n在逆时针方向上的下一个节点。
Trust(n)：节点n的信任度，具体算法见下一节。该项决定节点与其它节点的交互使能。
3.1 节点备份
在构造finger表的过程中使用2中不同的哈希函数将关键字散列在chord环上，也就是说每个关键字会出现在2个不同的随机节点上。Chord使用的是SHA-1，另一种哈希函数使用DJB hash function，俗称“Times33”算法。
times33的算法很简单，就是不断的乘33。nHash=nHash*33+*key++；实践证明times33比其他哈希算法都更快。
下面我们看一下节点在Chord算法中的实现示例。在例子中，我们采用对关键字进行2次不同哈希的方法得到2个不同的关键字关键字。图1是当m=6，10个节点的Chord节点空间示意图。我们资源K10的索引信息放到节点N15和N43上，而把K24的索引信息存放在N32和N57。
3.2 路由表精简
我们都知道在chord中，K是发布到successor(k)节点上，为了加速节点的定位，每个节点上保存一个finger表，将环空间的节点按照2的幂进行分割，finger[i]和finger[i+1]之间差距为2i-1个距离，在i<8的时候，finger[i]与finger[i+1]的间距比较小，很可能finger[i]与finger[i+1]的节点指向都相同，它的不足之处在于：在P的路由表中，随着i的增大，finger[i].interval呈2倍增长。而相对2m的标识符空间来说，节点是非常稀少的，这些点又基本上是均匀分布的（根据哈希散列函数），所以当i较小时，interval也较小，中间的节点数就很少，甚至没有，即前后相邻的两个或多个指针完全相同，造成不必要的重复存储，从而减少了路由表有价值的信息量的存储；相反，随着i的增大，interval越来越大，落于其中的节点数会越来越多。
4 模型实现
4.1 节点加入
每个节点在加入系统之前都将自己加入一个固定的多播组，以某个固定的TTL用组播发送加入消息，加入消息使用非对称密钥加密。如果在其报文TTL可达范围内存在已加入系统的节点，则节点返回消息，并将新加节点加入路由表。新节点收到消息后，同样将返回消息的节点加入其路由表。此外，收到信息的节点将新节点的加入信息广播到整个网络。
4.2 节点退出
节点退出之前首先在域内发送退出信息的组播报文，接收到信息的节点将路由表中该节点路由信息设置为不可达，同时将该节点的退出信息广播到整个网络。
4.3 节点查找
节点n查找关键字Key的算法：
如果k存储在本地，则返回k的信息与Trust值。Trust为1，查找成功；Trust为0，重新查找。
举例：节点3查找关键字51。
1）按照原查找方法：
关键字51在[35，4]之间，查询请求转发给节点37；节点37的路由表如图2所示；关键字51在[45，53]之间，查询请求转发给节点45，节点45的路由表如图3所示。
关键字51在[49，53]之间，查询请求转发给节点52；节点52上有关键字51，返回关键字51的信息。查找结束。查询路径：3→37→45→52。3跳。
2）按改进后的查找方法：
节点3的正向路由表中，关键字51在[35，4]之间；反向路由表中，关键字51在[59，51]之间。查询请求转发给节点45。节点45的路由表如图4所示。
查询路径：34552。由3跳变为2跳，比原来的方法减少了一跳。查找关键字的时间=查找关键字在P2P网络中的跳数（Hop）*每跳的平均时间。显然，双向路由表有更高的效率。
5 小结
虽然系统能够在具有一定比率恶意结点的情况下，可以保持原有的算法的查询效率。但是，新的方案在冗余缩引的存储和一致方面，还需要改进。在以后的工作中，一方面要改进冗余数据一致性方面的缺陷，另一方面要深入研究系统的维护机制和路由机制，尽量保证路由安全的基础上，降低维护代价和查询代价，同时寻找更有效的路由算法，以使在网络安全问题和性能效率问题找到一个最好的折衷方案。
参考文献：
[1]唐辉、李组鹏等，结构化覆盖网络模型Chord研究，计算机工程与应用，2005：41（1）.
[2]陈洪、刘双与、杨玉华，P2P技术发展与应用，计算机工程，2003，29（l9）：127-132.
[3]陈建华、黄道颖等，计算机对等网络P2P技术，计算机工程与应用，2003，33：162-165.
[4]陈宏亮、李杰、王桃，基于位置的层次式Chord模型，计算机工程，2009，35（21）.
作者简介：
张昊（1968-），女，辽宁省铁岭市人，硕士研究生，副教授，研究方向：计算机应用及多媒体教学。
关键词： 路由表结构；网络节点；路由算法；chord
中图分类号：TP393.02 文献标识码：A 文章编号：1671－7597（2012）0210089－02
1 P2P概述
P2P是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源（处理能力、存储能力、网络连接能力、打印机等），这些共享资源需要由网络提供服务和内容，能被其它对等节点直接访问而无需经过中间实体。在此网络中的参与者既是资源（服务和内容）提供者，又是资源（服务和内容）获取者。P2P技术是一种用于不同PC用户之间、不经过中继设备直接交换数据或服务的技术。它打破了传统的Client/Server模式，在对等网络中，每个节点的地位都是相同的，具备客户端和服务器双重特性，可以同时作为服务使用者和服务提供者。
P2P路由模型分类：
目前，典型的P2P路由模型主要有如下几种：
1）集中式目录结构模型，它能提供较好的查找资源性能，但是存在服务质量无法提高和单点崩溃的问题。
2）洪泛请求模型，它是纯对等网络模型，不存在单点崩溃问题，但容易造成消息泛滥，系统的可扩展性难以提升。
3）结构化覆盖网路由模型，它能平衡负载，改善网络可扩展性，但是没有考虑网络的实际拓扑结构，邻近的节点也有可能散列到相隔很远处，要经过很长的搜寻路径才能获得数据，严重降低了路由的效率。将Chord、CAN、Pastry、Tapestry，4种结构化覆盖网络模型从拓扑结构、路由原理、路由性能几个方面进行比较可知，Chord具有简单性、可靠性和性能稳定
2 Chord环的构建
一致的SHA-1哈希函数赋予对等节点和数据关键字一个m位的标识符。一个对等节点的标识符由哈希函数计算对等节点的IP地址得到，而数据关键字的标识符则由哈希函数计算数据关键字得到。标识符的长度m必须足够长，保证用哈希函数计算数据关键字时不会得到两个相同的标识符。对等节点标识符（如N8）以2m为模顺序排列在标识符圆环上。关键字k被存储在标识符等于或大于k的第一个对等节点上。这个对等节点被称为关键字k的后续对等节点，用公式N=successor(k)表示。如果标识符用0到2m-1表示，那么successor(k)就是顺时针方向关键字k的第一个对等节点。这个标识符圆被称为Chord环。
3 基于信任概率的双向路由表模型
本文以Chord协议说明该模型的实现，基于信任概率的双向路由表模型：增加一张路由表保存初始chord反向环路由信息，并添加信任度项。数据结构如下表1所示。
Successor_R(n)：节点n的反向后继节点。节点n在逆时针方向上的下一个节点。
Trust(n)：节点n的信任度，具体算法见下一节。该项决定节点与其它节点的交互使能。
3.1 节点备份
在构造finger表的过程中使用2中不同的哈希函数将关键字散列在chord环上，也就是说每个关键字会出现在2个不同的随机节点上。Chord使用的是SHA-1，另一种哈希函数使用DJB hash function，俗称“Times33”算法。
times33的算法很简单，就是不断的乘33。nHash=nHash*33+*key++；实践证明times33比其他哈希算法都更快。
下面我们看一下节点在Chord算法中的实现示例。在例子中，我们采用对关键字进行2次不同哈希的方法得到2个不同的关键字关键字。图1是当m=6，10个节点的Chord节点空间示意图。我们资源K10的索引信息放到节点N15和N43上，而把K24的索引信息存放在N32和N57。
3.2 路由表精简
我们都知道在chord中，K是发布到successor(k)节点上，为了加速节点的定位，每个节点上保存一个finger表，将环空间的节点按照2的幂进行分割，finger[i]和finger[i+1]之间差距为2i-1个距离，在i<8的时候，finger[i]与finger[i+1]的间距比较小，很可能finger[i]与finger[i+1]的节点指向都相同，它的不足之处在于：在P的路由表中，随着i的增大，finger[i].interval呈2倍增长。而相对2m的标识符空间来说，节点是非常稀少的，这些点又基本上是均匀分布的（根据哈希散列函数），所以当i较小时，interval也较小，中间的节点数就很少，甚至没有，即前后相邻的两个或多个指针完全相同，造成不必要的重复存储，从而减少了路由表有价值的信息量的存储；相反，随着i的增大，interval越来越大，落于其中的节点数会越来越多。
4 模型实现
4.1 节点加入
每个节点在加入系统之前都将自己加入一个固定的多播组，以某个固定的TTL用组播发送加入消息，加入消息使用非对称密钥加密。如果在其报文TTL可达范围内存在已加入系统的节点，则节点返回消息，并将新加节点加入路由表。新节点收到消息后，同样将返回消息的节点加入其路由表。此外，收到信息的节点将新节点的加入信息广播到整个网络。
4.2 节点退出
节点退出之前首先在域内发送退出信息的组播报文，接收到信息的节点将路由表中该节点路由信息设置为不可达，同时将该节点的退出信息广播到整个网络。
4.3 节点查找
节点n查找关键字Key的算法：
如果k存储在本地，则返回k的信息与Trust值。Trust为1，查找成功；Trust为0，重新查找。
举例：节点3查找关键字51。
1）按照原查找方法：
关键字51在[35，4]之间，查询请求转发给节点37；节点37的路由表如图2所示；关键字51在[45，53]之间，查询请求转发给节点45，节点45的路由表如图3所示。
关键字51在[49，53]之间，查询请求转发给节点52；节点52上有关键字51，返回关键字51的信息。查找结束。查询路径：3→37→45→52。3跳。
2）按改进后的查找方法：
节点3的正向路由表中，关键字51在[35，4]之间；反向路由表中，关键字51在[59，51]之间。查询请求转发给节点45。节点45的路由表如图4所示。
查询路径：34552。由3跳变为2跳，比原来的方法减少了一跳。查找关键字的时间=查找关键字在P2P网络中的跳数（Hop）*每跳的平均时间。显然，双向路由表有更高的效率。
5 小结
虽然系统能够在具有一定比率恶意结点的情况下，可以保持原有的算法的查询效率。但是，新的方案在冗余缩引的存储和一致方面，还需要改进。在以后的工作中，一方面要改进冗余数据一致性方面的缺陷，另一方面要深入研究系统的维护机制和路由机制，尽量保证路由安全的基础上，降低维护代价和查询代价，同时寻找更有效的路由算法，以使在网络安全问题和性能效率问题找到一个最好的折衷方案。
参考文献：
[1]唐辉、李组鹏等，结构化覆盖网络模型Chord研究，计算机工程与应用，2005：41（1）.
[2]陈洪、刘双与、杨玉华，P2P技术发展与应用，计算机工程，2003，29（l9）：127-132.
[3]陈建华、黄道颖等，计算机对等网络P2P技术，计算机工程与应用，2003，33：162-165.
[4]陈宏亮、李杰、王桃，基于位置的层次式Chord模型，计算机工程，2009，35（21）.
作者简介：
张昊（1968-），女，辽宁省铁岭市人，硕士研究生，副教授，研究方向：计算机应用及多媒体教学。