 Computer Science and Application 计算机科学与应用, 2012, 2, 47-50 http://dx.doi.org/10.12677/csa.2012.21009 Published Online March 2012 (http://www.hanspub.org/journal/csa) Fault-Tolerant Method in P2P Information Management Systems* Lu Cai1, Jian Zhao2 1School of Information Management and Information Systems, Chang’an University, Xi’an 2School of Basic Education, National University of Defense Technology, Changsha Email: Centaur_Laurel@hotmail.com, zhaojian@nudt.edu.cn Received: Jan. 2nd, 2012; revised: Jan. 19th, 2012; accepted: Feb. 3rd, 2012 Abstract: FissionE is a Kautz graph based infrastructure of P2P information management systems. It has the optimal network diameter given node degree d = 2. In order to address the problem of degraded routing performance caused by node failures, in this paper we propose a fault-tolerant routing algorithm for the FissionE system. The basic idea is to bypass failed node or link with some certain mechanism, so that FissionE can achieve better routing performance. Keywords: P2P Information Management System; Kautz Graphs; Fault-Tolerance P2P 信息管理系统中的容错方法* 蔡 璐1，赵 舰2 1长安大学经济管理系，西安 2国防科技大学基础教育学院，长沙 Email: Centaur_Laurel@hotmail.com, zhaojian@nudt.edu.cn 收稿日期：2012 年1月2日；修回日期：2012年1月19 日；录用日期：2012年2月3日 摘 要：FissionE 是一种基于Kautz 图的 P2P信息管理系统网络架构，在给定节点度数(d = 2)下具有最优的网络 直径。针对结点失效导致的 FissionE 路由性能较差的问题，本文对 FissionE 的容错路由算法进行研究，其基本 思想是：如果下一跳结点失效或网络连接失效，那么将采用某种方法“绕过”失效的结点或连接，从而获得较 好的路由性能。 关键词：P2P 信息管理系统；Kautz 图；容错 1. 引言 近年来，P2P 技术作为一种新型的网络计算技术蓬 勃兴起，已经被广泛地应用于信息管理系统领域，具 有广阔的发展前景[1-3]。P2P 信息管理系统中各结点的 地位平等，每个结点既是客户机又是服务器，不依赖 于任何中央服务器，可以充分利用各个结点上的资源， 极大地丰富了网络中的资源，各个结点可以直接进行 交互和协作，因而有效地提高了资源 的利用率[4-6]。 然而，现有的P2P 信息管理系统难以应用于结点 状态不稳定的环境[7]。这是由于一方面网络拓扑变化 频繁，另一方面P2P信息管理系统中没有中央控制， 各结点的状态信息无法进行汇聚，进而导致路由性能 较差。 FissionE 是一种基于 Kautz 图的信息管理系统网 络架构。FissionE 创造性地提出了许多新型的规则和 算法，例如 Kautz_hash 命名算法、邻居关系不变量拓 扑构造规则和局部优化动态维护机制，并且详细地分 析和证明这些机制的正确性。在给定节点度数(d = 2) *资助信息：本文研究成果受到国家自然科学基金(批准号： 60903205)和博士点基金(批准号：20094307110008)的资助。 Copyright © 2012 Hanspub 47  P2P 信息管理系统中的容错方法 下FissionE 具有最优的网络直径。 针对节点失效导致的 P2P 信息管理系统性能较差 的问题，本文对FissionE 的容错方法进行研究，其基 本思想是：如果下一跳结点失效或网络连接失效，那 么将采用某种方法“绕过”失效的结点或连接，从而 获得较好的性能。模拟实验表明，本文提出的方法能 够在存在节点失效的情况下实现高效的FissionE 信息 管理系统网络架构。 2. 相关研究 本节将对 FissionE 的基本设计(包括 Kautz 图拓扑 结构、FissionE 路由算法等)进行回顾。 Kautz串[2]是指在由k个字符组成的字符串中，如 果每个字符只能取从0到d的整数且相邻的两个字符 不同，那么就称这个字符串是基底为 d、长度为 k的 Kautz串。Kautz 空间KautzSpace(d, k)是指所有基底为 d、长度为 k的Kautz 串的集合。Kautz 图[2]K(d, k)是 每个结点的出度和入度都是d且网络直径是 k的有向 图，Kautz 图K(d, k)中每个结点的标识都是Kautz 空 间KautzSpace(d, k)中的一个Kautz串，Kautz 图K(d, k) 中任意一个结点都有 d条到结点 12 ,, k UU uuu 23 ,,VV uukk uaa u的出边(记作U)。图 1给出了 Kautz 图K(2, 3)的示例。 V 根据 Kautz 串的定义，Kautz 图K(d, k)中共有 个结点，在目前所有的拓扑图中最接近 Moore 界 ，并且在k = 2 时，Kautz 图中共有个结点，只比Moore界 少 一个，可见Kautz 图是结点数目最多的拓扑图。Kautz 图K(d, k)的网络直径达到了由 Moore 界推出的网络直 径下界，可见 Kautz 图具有 最优网络直径。Kautz 图的连接度为 d，即在Kautz 图的任意两个结点之间存在d条互不相交的路径，可 见Kautz 图的容错性非常好。 1kk dd lo 2 1k dd d 2 dd g1 1 dNd 2 1dd 1 在静态 Kautz 图中采用长路径路由算法，如果 ，那么从结点 U到结点 V的路由路径为：U 1k uv 如果uv那么从结点 U 到结点 V的路由路径为：Uu 12 uu u 231 3412kk k uu uvuu uvvu 112kk vvvvV；1k， 12 23 u uuu 12 vv 2kk uv k 232 1kkkk uvvuvv vV 。 34 uu 由此可见，Kautz 图K(d, k)中任意两个结点之间 的路由路径长度为 k或，平均路由路径长度为1k 1111 1ddk dkk d1 。例如在 Kautz 图K(2, 3)中从结点101 到结点 212的路由路径 为101→012→121→212，如图 1所示。 FissionE 中每个结点的标识都是一个基底为 2的 Kautz 串。最初 FissionE 与静态 Kautz 图相同，但是随 着结点的动态加入和退出，结点标识的长度也在动态 变化， FissionE 针对此提出了邻居关系不变量拓扑 构造 规则，使 FissionE 中邻居结点的标识长度相差始终不 超过 1，维护了良好的拓扑结构。FissionE 中每个结点 的路由表中都记录了两种邻居的信息，即出边邻居和 入边邻居，结点 12 ,, k Uuu u km q 的出边邻居是结点 23 1 Vuu uq 0m 23 1k uu uq 2 (是基底为2的 Kautz 串且 m q 12 uu )；结 点的入边邻居 是结点Wa 12 u,, k uUu i u 12 i au uu k (是基底为 2的Kautz 串且 2ki )。图 2给出了一个 FissionE拓扑示例。 Figure 1. Routing path from source node 101 to destination node 212 in K(2, 3) 图1. K(2, 3)中从源结点 101 到目的结点 212 的路由路径 Figure 2. Routing path from source node 121 to destination node 2020 图2. 从源结点 121 到目的结点 2020 的路由路径 Copyright © 2012 Hanspub 48  P2P 信息管理系统中的容错方法 FissionE 中消息路由的过程和Kautz 图的长路径 路由算法相似，设 X为当前结点的标识，T为目标 Kautz 串，M为X和T的前后匹配位数， X 为X的 长度，消息路由算法为重复进行 ,LXMXT 和 直至 。例如在上述拓扑示例中从结点 121 到结点2020 的消息路由路径为121→212→120→ 2020，如图 2所示。 1LL 0L 3. FissionE的容错路由算法设计 3.1. Kautz图容错路由 为降低失效结点对消息路由的影响，本文提出在 Kautz 图中采用如下兄弟结点容错机制。 结点 12 ,, k X xx x的两个出边邻居 23 Bxx k x y(y = 0, 1, 2 且b xk)互为兄弟结点，当结点 X处理 路由消息 Routing(T, L, P)时，如果路由消息要转发到 的出边邻居 已经失效，那么将路由消 息转发给 W的兄弟结点 ，之后按照长 路径路由算法，路由至目的结点。例如在 Kautz 图K(2, 3)中，理想情况下从源结点 102 到目的结点 120 的路 由路径为 102→021→212→120。当结点 212失效后， 路由路径变为102 →021→210→101→012→120，如图 3所示。 23 k Wxxxa 23 k Bxx xb 3.2. FissionE容错路由 在现有 FissionE设计中，结点被动退出后路由消 息很有可能还会被转发给已经失效的结点，为增加消 息路由的鲁棒性，一种选择是仿照Kautz 图容错路由 算法进行路由。但是，由于在 FissionE中结点的出边 邻居个数可能为 1，因此我们提出如下改进的 FissionE 容错方法。 标识为 21kj Wuux x 02j 和23 Vuu 2 ,, k u 2 (与相对于 互补，0)的结点互 为容错结点。当路由消息路由至Uu 时，假 设下一跳结点Wu () 已经失 效，那么U将把消息转发至 W的容错结点(即 )，然后从V再路由至目的结点。 1k uq q 23 Vuu m2 u 2 u1 u 2 ux 1km uq q m 12 u 1kj x0j 例如在图 2所示的 FissionE拓扑中，212 和012 互为容错结点，理想情况下从源结点 121 到目标 Kautz 串120 的路由路径为 121→212→120，如图4所示。 当结点 212失效后，路由路径变为 121→210→10→012 →120，如图5所示。图 6给出了FissionE 容错机制。 Figure 3. Routing path after node 212 fails in K(2, 3) 图3. K(2, 3)中结点212 失效后的路由路径 Figure 4. Ideal routing path from source node 121 to destination node 120 图4. 从源结点 121 到目的结点 120 的理想路由路径 Figure 5. Routing path after node 212 fails 图5. 结点 212 失效后的路由路径 Copyright © 2012 Hanspub 49  P2P 信息管理系统中的容错方法 Copyright © 2012 Hanspub 50 Figure 6. Fault tolerant rouging in FissionE 图6. FissionE的容错路由机制 4. 模拟评估 Figure 7. Fault tolerant performance 我们通过修改 FissionE模拟器对容错路由的性能 (平均路径长度)进行评估。在模拟过程中，首先通过 Kautz_hash 算法随机产生一个目标 Kautz 串，并随机 选择一个结点作为消息发起结点。消息采用标准 FissionE 路由算法进行路由。在每个消息的路由过程 中，随机选择一个结点作为失效结点，当消息遇到失 效结点时将启用如图6所示的容错路由算法。结点数 从256 变化到 32 K。模拟结果如图7所示。 图7. 容错性能 有效地提高 FissionE 的容错性能。 参考文献 (References) [1] 李东升. 基于对等模式的资源定位技术研究[D]. 国防科技大 学, 2005. [2] 彭兰. P2P 技术与网络传播的未来[URL], 2004. http://news.xinhuanet.com/newmedia/2004-12/01/content_2282 285.htm 图中也包括了没有失效结点时标准 FissionE 的平 均路由路径长度。从图中可以看出，发生结点失效时 的容错路由延迟仅比正常情况下的 FissionE 路由延迟 高50%左右，从而说明我们的容错路由算法是有效的。 [3] I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, et al. Chord: A scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Transactions on Networking, 2003, 11(1): 17-32. [4] M. Bawa, F. B. Cooper, A. Crespo, N. Daswani, et al. Peer-to-Peer research at Stanford. SIGMOD Record, 2003, 32(3): 23-28. [5] Napster Website, 2001. http://www.napster.com [6] S. Rhea, D. Geels, T. Roscoe and J. Kubiatowicz. Handling churn in a DHT. USENIX Annual Technical Conference, General Track, 2004. 5. 结论 [7] 刘敏. 结构化P2P 系统容错机制研究[D]. 国防科技大学, 2008. 本文对结构化 P2P 信息管理系统 FissionE 的容错 方法进行研究。模拟实验表明，本文提出的方法能够 |