SCDN在P2P网络中的动态内容管理应用研究

张攀东

【摘 要】本文首先介绍了 SCDN 基础的拓扑结构，然后提出了基于需求的资源发现机制，混合 Push/Pull 的更新发布机制，节点加入离开相关的处理机制以及节点类型管理机制，最后对 SCDN 进行了理论分析和仿真实验。

【关键词】SCDN；P2P；动态内容

1 SCDN 的双层结构

SCDN 的目标是在 P2P 网络中构建稳定的内容分布网络，可以在参与节点频繁动态变化的情况下定位所需的内容，并对内容及其副本进行有效的管理。所以，SCDN 包括两层：节点层和内容层。根据 CAN 协议，路由信息在节点层构成一个d 维协作空间，同时每个内容通过 DHT 被映射到键值最接近的节点上，如图 1所示。

图1 SCDN 的双层结构

我们之所以选择 CAN 作为基础拓扑是因为：首先，通过使用 d 维协作空间，CAN 可以支持多关键字查询；其次，CAN 的路由表是节点基于局部信息构建的，所以节点的加入离开仅会造成该节点周围少数节点的路由表变化；此外，CAN 具有良好的鲁棒性。虽然相对于其他 DHT 模型而言，CAN 的平均查询路径较长，但我们可以通过使用基于节点需求构建的远程连接有效提高查询速度。

2 基于需求的资源发现

由于每个节点不仅存储了邻居节点的信息，还存储了若干通过远程连接相连的远程节点作为“捷径”，所以 SCDN 可以通过将捷径和 CAN 路由结合提高资源发现的性能。

每个节点通过搜索自己所有的邻居连接和远程连接进行资源发现，并将查询请求转发给和目标内容键值最接近的节点，直到找到目标内容的 CP。和 CAN 网络中渐进式的路由不同的是，SCDN 使用跳跃式的路由。假设节点 P5需要寻找内容 A，如果是在 CAN 网络中，查询路径会沿着 P5→P4→P3→P1前进，直到抵达内容 A 的 CAN 负责节点 P1节点，如图 2 所示；如果是在 SCDN 网络中且节点 P4和 P1之间存在一条远程连接，则查询路径会沿着 P5→P4→P1前进，如图 3所示。

图 2 CAN 的查询路径示意图

图 3 SCDN 的查询路径示意图

通过使用远程连接提供的捷径，SCDN 可以提高资源发现的速度。内容越流行，则需要该内容的节点越多，这就会产生越多连向该内容 CP 的远程连接，资源发现的速度也会越快。

3 混合 Push/Pull 的更新发布

由于每个复制节点都存储了一个内容的副本，所以网络存在多副本。SCDN使用一种混合的 Push/Pull 的机制实现对内容的更新和更新的发布，从而保证每个节点都可以在较低的通信成本下获得最新版本的内容并对内容进行更新。

为了降低系统的通信量，节点的类型是根据节点访问内容的速度决定的。频繁访问内容的节点会成为内容的 CRP，而访问内容的节点则会成为内容的IRP。如何管理 CRP 和 IRP，我们将在后面详细介绍。每个内容都使用版本号区别不同的版本，并在每一次 VS 更新内容之后对版本号进行修改。

内容的更新和更新的发布可以分为三个阶段：更新请求、更新检测、更新发布。

SCDN 根据节点访问内容的频率决定节点更新内容和更新发布的方式。VS 主动向所有的 CRP 发送更新信息，从而避免了频繁的版本检测；IRP 在使用副本之前主动检测版本信息，从而避免了频繁接收到更新消息。通过使用这种方式，SCDN 可以在较低的通信量之下对内容进行管理和更新，同时保证了所有的节点在它们需要使用或更新内容时，可以获得最新版本的内容信息。

4 理论分析

通过对 SCDN 中远程连接的个数和平均查询路径的长度这两者之间的关系进行推导分析。

4.1 基于 Markov 链的分析

资源发现的过程可以形式化成为 Markov 链的一个吸收过程，如文[1]所示。每个节点仅根据自身当前的状态决定查询请求需要被转发的下一个节点。最后，在不考虑节点失效的情况下，查询请求被转发到目标节点，成为一个吸收态。

假设一个系统中共有 N 个节点，所有的节点被从 0 到 N-1 进行命名。不失一般性，我们将节点 0 作为查询的目标节点，而其他的所有节点都是查询源节点。我们将查询请求从节点 i 转发到节点 j 的概率定义为转移概率 pi，j，则整个转移矩阵为P =（pi，j ） N* N。

我们使用hi，j记录一个查询请求从节点i被成功转发到节点j的查询路径长度，则：

h■=1+■p■h■（1）

此后可以获得从迁移态 i（i=1，2，…，N-1）到吸收态 j（j=0）的平均查询路径长度。

5 实验和分析

使用仿真实验测量了 SCDN 资源发现的性能，内容和副本的一致性，以及在参与节点频率动态变化下资源发现协议的鲁棒性。

5.1 资源发现的性能

为了测量 SCDN 网络中资源发现的性能，首先对比了在不同网络规模下SCDN，CAN，SWOP 三种网络的查询效率，然后测量了在不同的网络维数下，不同的最大存储内容数量下的查询效率，最后对比了 CAN 路由和捷径路由两种路由方式对 SCDN 的影响。

实验 1：在不同网络规模下 SCDN、CAN、SWOP 三种网络的查询性能

SWOP 也是一种知名的在结构化 P2P 网络上使用远程连接构建的改进 P2P 网络。在 SWOP 中，所有的节点根据它们的键值有序排成环形结构，并在环上形成聚类。每个聚类中有一个 head 节点，同一个聚类内的所有其他节点都和 head节点直接相连。不同聚类之间通过远程连接相连。当一个节点需要寻找某个内容时，查询请求先在聚类内转发，此后才会通过聚类中的远程连接转发给其他聚类，这个过程不断重复，直至找到所需内容。

我们将 SCDN 和 SWOP 相比，因为 SWOP 使用随机选择的远程连接，而 SCDN使用基于节点需求选择的远程连接，两个都是使用远程连接来提高查询性能。所以，我们可以通过构建相同数量的远程连接来对 SWOP 和 SCDN 进行公平的比较。我们将 SCDN 和 CAN 相比，是因为 SCDN 是构建在 CAN 的基础网络之上。

分别考虑网络规模为 N=1000 和 4096 两种情况下的连通图。每个节点发布一个内容，所以网络中总共有 N 个内容。每个节点进行 1000 次查找，查询目标在网络所有内容中随机选择。使用平均查询路径来衡量不同网络的查询性能。SCDN 使用 3 维键值空间，每个节点平均所需的内容为 12 个，上限为 24 个。为了公平起见，SWOP 的远程连接个数也设为 24 个，CAN 也使用 3 维键值空间。

查询路径长度

图 4 在网络规模 N=1000，网络维数 d=3 的情况下，

SWOP、CAN、SCDN 三种网络的查询路径长度分布图

查询路径长度

图 5 在网络规模 N=4096，网络维数 d=3 的情况下，

SWOP、CAN、SCDN 三种网络的查询路径长度分布图

网络规模N

图 6 在不同网络规模下，SWOP、CAN、SCDN

三种网络的平均查询路径长度

图4和图5给出了在网络规模N分别为1000和4096这两种情况下，SWOP、CAN 和 SCDN 三种网络的查询路径长度分布。图6则总结了当网络规模从 1000 增加到 10000 时，这三种网络的平均查询路径长度变化。从结果可以看出，SCDN 的平均查询路径长度始终低于 SWOP 和 CAN 两种网络。SCDN 的平均查询路径长度约为 SWOP 的 80.86%，仅为 CAN 的 30.69%。SCDN 的标准差也始终小于 SWOP 和 CAN 两种网络。

5.2 内容和副本的一致性

实验2：内容和副本的一致性

研究 SCDN 在内容被动态更新的情况下副本的正确率。假设内容的更新服从泊松分布，参数 T 从 0.5s 变化到 300s；每一跳的延迟也服从均值为 85ms的泊松分布[3]。

表 1 在网络规模 N=1000 和 4096，网络维数 d=3 的情况下，SCDN 的内容更新频率对副本正确率的影响

表 1 显示了 SCDN 在 N=1000 和 4096 这两种网络规模下，副本正确率随内容更新周期变化的情况。对于一般的文件共享系统而言，文件更新的周期一般大于等于 300s[4]。SCDN 在更新周期大于等于 10s 的时候总能保证副本正确率在 99%以上。即使对于内容更新周期可能达到 0.5s～1s 的大规模多人在线游戏[5]而言，SCDN 的副本正确率也始终能大于 83.06%。

6 分析和讨论

综上所述，证明了 SCDN 可以提高资源发现和更新发布的性能，同时提供了良好的数据一致性和系统鲁棒性。

1）SCDN 和 SWOP、CAN 相比具有更好的资源发现效率，当网络规模 N=4096，网络维数 d=3 时，平均查询路径长度仅为 3.71。查询性能可以通过增加网络维数和节点存储的最大内容数进一步提高。这是因为 SCDN 总是先使用所需内容提供的远程连接进行粗糙的全局搜索，再进行精确定位，从而降低了平均查询路径长度。

2）即使内容被频繁更新，内容和副本仍能保持良好的可用性和一致性。当更新周期在 10s 之上时，SCDN 可以保证 99%的副本都是正确一致的，这种更新频率对于一般的文件共享系统而言已经相当高了。

3）即使参与节点频繁动态加入离开网络，SCDN 仍能保持良好的查询性能。即使网络中的节点替换率保持在 20%，（下转第67页）（上接第15页）SCDN 仍能保证 98.83%的路由成功率和 4.77 跳的平均查询路径长度。

此外，在 SCDN 中使用双层结构进行资源发现和更新发布。内容和副本之间的拓扑结构形成了一种层次结构可用于更新发布，而这些内容和副本之间的远程连接还可以作为“捷径”被用于资源发现。不同于其他的 P2P 系统，比如SWOP为了资源发现专门构建远程连接，从而产生了额外的构建和维护的成本，SCDN 的远程连接是根据节点的需求在内容和副本之间自动构建的，并可以通过更新发布过程自动维护，所以 SCDN 不需要任何额外的成本用于构建和维护远程连接。

【参考文献】

[1]AZZOUNA N B， GUILLEMIN F. Experimental analysis of the impact of peer-to-peer applications on traffic in commercial IP networks [J]. European Transactions on Telecommunications： Special Issue： Special Issue on P2P Networking and P2P Services， 2004， 15（6）： 511-522.

[2]ZHANG M， JOHN W， CLAFFY M， et al. State of the Art in Traffic Classification： A Research Review： PAM 2009： proceedings of the 10th International Conference on Passive and Active Measurement， South Korea， April 1-3， 2009[C]// Berlin： Springer， 2009.

[3]STEINMETZ R， WEHRLE K. Peer-to-Peer Networking and Computing [J]. Informatik-Spektrum， 2004， 27（1）： 51-54.

[4]Napster [EB/OL]. [2014-02-19]. http：//music.napster.com.

[责任编辑：杨玉洁]