一个基于超级节点覆盖拓扑的健壮协议----实验分析

1、A Robust Protocol for BuildingSuperpeer Overlay Topologies（建立在超级节点覆盖拓扑之上的健壮协议）（建立在超级节点覆盖拓扑之上的健壮协议）实验结果及总结实验结果及总结实验实验所有图都是使用20次独立的实验绘制的。所有参数都是固定的：网络规模是100000节点，最大容量是500；newcast中使用的局部视图s的大小是30。这些值都可以适用于现实情况，实验结果图4展示随着时间的推移算法的执行情况。初始化配置下，我们选择一个与目标拓扑差距最大的情况：一个随机的拓扑结构，所有的节点都充当超级节点，任何一个都不负责任何客户节点。需要几个周期达到

2、目标拓扑结构（最坏55），已经是相当快的速度了。不考虑分布情况：在至少15周期后，实验结果的拓扑结构已经与目标拓扑非常相近了。实验结果实验结果图6和7显示通过NEWCAST交换的最大容量Cmax和局部视图s的信息是如何影响算法的性能的。在两种情况下，结果都达到了预期效果。容量越大，目标拓扑结果所包含的超级节点越少，算法达到这样的拓扑结构所需要的周期数就越大。另一方面，用于随机选择的节点样本越大，就会有更好的性能，但是需要更大的通信开销。实验结果算法总的通信消耗通过系统多层交换的信息数量总和给出。NEWCAST管理的三个集合，继承了协议良好的属性。在NEWCAST中，每个节点每周期交换量可以通过

3、随机变量1+ ， 为参数为1的泊松分布。因此，平均的，每个节点有两个交换（一个是初始的一个来自另一节点），这两个差异很小。这意味着这些层都是民主的（公平），所有节点每轮需要收发成百比特的数据。第四个，client集合，只由超级节点管理。考虑到两方面的通信消耗：在RandomPeer方法中发送的探针总数；执行转移的客户节点的总数。图8展示了不同规模网络的耗费情况。图表展示每个节点平均只有两个探针发送，然而每个客户节点转移了约9次。后者可被认为是一个相对高的值，总的来说，耗费主要与转移相关。实验结果为了完成通信消耗的评估，我们测量出在一个周期中一个超级节点完成操作的最大量，以容量区分相应的节点。图

4、9证明了没有任何一个结点因为通信消耗而超载。实验结果最后的图展示了协议的鲁棒性。图10表示一个灾难性情况：第30周期，50%的超级节点被移除。在初始化阶段后当所有的客户端的超级节点崩溃了而自己成为了超级节点，协议表现的还跟正常一样，从剩下的节点中选择新的超级节点修复覆盖拓扑。实验结果算法已经运行了几周期了，每一轮替代一定百分比的节点，产生了一个摆动的超级节点数。为了完成通信消耗的评估，我们测量出在一个单轮中一个超级节点完成操作的最大数量，除以相应的节点的容量。图9证明了没有任何一个结点因为通信消耗而超载。图7显示了加入和稳定化的伪代码，它取代图6来处理并发加入的情况。/ n加入网络，只设置自己

5、的后继，简单 n.join(n) predecessor = nil; successor = n.find_successor(n); / RPC / 周期性检查后继，告诉后继自己的存在 n.stabilize() x = successor.predecessor; / RPC查询 if(x IN (n, successor) successor = x; successor.notify(n); / RPC / n认为它应该是n的predecessorn.notify(n) if(predecessor IS nil OR n IN (predecessor, n) predecesso

6、r = n; / 周期性的刷新finger table n.fix_fingers() / finger_t1.node就是后继，不需要在这里刷新 i=random index 1 IN finger tables; finger_ti.node = find_successor(finger_ti.start); 一个简单的例子，假设节点n加入系统，并且ID在np和ns之间，n将会选择ns作为它的后继。节点ns在收到n的通知时将会把前驱指针更新为n。接下来当np运行stabilization时，它将向ns询问它的前驱结点（现在是n），【注：np并不知道n的加入，所以它的后继指针仍然指向ns】

7、np将会选择n作为后继。最终np将会通知n，并且n将会选择np作为它的前驱。到此为止，所有前趋和后继指针都正确了。定理定理4 一旦一个节点可以成功的解决一次查询，那么它以后也都能成功的解决。定理定理5 从最后的节点加入网络经过一段时间以后，所有的后继指针都将是正确的。定理的证明依赖于不变性和终止性论证。不变性陈述了一旦节点n可以通过后继指针到达r，那么它永远都可以。为了证明终止性，我们假设两个节点都认为它们有相同的后继s的情况。这种情况下，每一个都会通知s，s最终会选择两个中离它较近的（或者其它的更近的节点）作为它的前驱。于是将来通过联系s，它们能知道一个比s更合适的后继。这表明，随着时间的前

8、进，每个节点也都是朝着更好的后继在前进。这种进展将最终停止在一个状态上，每个节点都被另外的唯一一个节点选为后继，这就定义了一个环（或一组环，但是不变性保证了最多只有一个环）。定理定理6 如果我们有一个N节点的稳定网络，另外有N个没有正确fingers的节点（但是有正确的后继）加入到网络中，在很大概率上查询时间依然是O(logN)。加入并不会从根本上破坏fingers的性能。如果一个节点每个区间都设置了一个finger，即使在有节点加入之后这些finger依然是可用的。距离的1/2递减论据从根本上没有改变，表明O(logN)跳已经足够到达一个查询的目标节点了。在网络扩充一倍的情况下，查询时间依然是O(logN)，因此，除非大量节点加入，对查询影响都是不大的。5.2 失效和恢复失效恢复的关键步骤在于维护正确的后继指针，为此，每个Chord节点都为在Chord环上距离最近的r个后继维护一个“successor-list”（后继列表）。如果节点n发现它的后继失效了，它将从successor-list中取出第一个活动后继来代替。定理7 如果我们在一个具有稳定初态的网络中使用长度r=O(logN)的successor-list，且每个节点失效的概率为1/2，那么在很大