论文部分内容阅读
摘 要：Chord是基于覆盖网的典型分布式结构化P2P(Peer-to-peer)系统，其相邻节点在IP Network上可能相距很远，从而导致网络访问速度大大降低. 为此对Chord系统进行改进，提出一种新的P2P系统. 在该系统中，将同一地区的节点组织为一个局域P2P网络(Location Area P2P Network, LAPN)，使用指针连通这些局域P2P网络，可以很好地解决上述问题，使系统执行效率大大提高.
关键词：对等网络； 覆盖网； IP网； 多关键字查询
中图分类号：TP393.01
文献标志码：A
Decentralized structured P2P system grouped by location
SHEN Xinpeng， LI Zhanhuai
(College of Computer Sci. & Eng.,Northwestern Polytechnical Univ., Xi’an, 710072)
Abstract： Because Chord is a typical distributed structured peer-to-peer (P2P) system based on overlay network, the distance between two adjacent peers may be very far on IP network, and the network access speed is greatly reduced. To solve the problem, a new P2P system is proposed to improve the Chord system. The peers in the same location are connected in a Location Area P2P Network (LAPN) which is connected by pointers. The method can resolve the problem and improve the system efficiency.
Key words： peer-to-peer network; overlay network; IP network; query on several keys
0 引 言
随着计算机处理能力和存储容量的提高以及通信技术的进步，人们可以随时随地接入网络并通过直接交换共享计算机资源和服务，对等计算[1](Peer-to-peer Computing)因此应运而生.对等网[2](Peer-to-peer，P2P)是没有任何集中控制的分布式系统，系统中每个节点在功能上均等同，既是客户机又是服务器，没有主从之分.
以Chord为代表的分布式结构化系统是P2P系统结构的研究重点.[3]系统中没有集中目录服务器，但节点的组织是结构化的.这里的结构是指系统对P2P网络拓扑和文件放置都精确地加以控制，仔细将文件均匀地分布在参与的节点中.该系统的优点是易于扩展，查询效率高，支持稀少文件的查询；缺点是对节点的不断加入和离开需要频繁地进行额外工作，不能有效支持多样化查询.而且由于该系统是在IP网(IP Network)上建立覆盖网(Overlay Network)，结果出现在覆盖网上的两个相邻节点在IP网上却相距很远的情况，于是，理论上只需要很少的延迟(比如一个Hop)，反映到实际IP网络上却需要很大的延迟，导致网络的实际访问速度大大降低.
为了解决这些问题，本文在分布式结构化P2P系统Chord的基础上进行改进，提出基于地域分组的分布式结构化P2P(Decentralized Structured P2P System Group by Location，DSPSGL)系统，它可以很好解决以上问题，是对P2P系统的一次有益改进.
1 DSPSGL系统介绍
在结构化P2P系统中，节点之间的访问路径长度一般都根据Overlay Network上的距离进行计算.但是Overlay Network上相邻的节点在IP Network上可能相距很远，从而造成数据访问的理论速度与实际速度差别很大.
为此，对分布式结构化P2P系统进行改进，提出DSPSGL系统.在DSPSGL系统中，处于同一地域的节点构成分布式结构化的局域P2P网络(Local Area P2P Network，LAPN)，这些LAPN的相互连通形成完整的DSPSGL网.
1.1 系统拓扑结构
在DSPSGL系统中，采用一致性哈希(Consistent Hashing) 算法[4]将网络中每个节点的标志映射成一个长度为M 位(bit)的二进制序列：节点标志符(pID)，并将其唯一分配给该节点.它表示1到2M-1间的数，在一维环空间(模2M)上由小到大按顺时针排列，选择合适的M值，可以保证两个节点的pID相同概率接近0.
在Chord 模型中，节点标志符(pID)通过哈希IP地址得到，但是该方法存在明显不足.现在国内很多用户使用ADSL方式上网，他们每次登入网络的IP地址都是变化的，因此同一节点两次登入系统的节点标志符不同.这就违反了节点标志符的唯一性原则，可能会造成同一节点在存储文件和查找文件时的节点标志符不一致的情况，失去定义节点标志符的意义.这里使用哈希机器CPU的ID来生成节点标志符.每台机器CPU的ID是唯一不变的.使用该方法可以保证节点多次接入系统时，其pID保持不变.
同时，每个节点还有一个N(N 这样，DSPSGL系统中所有的节点都有一个节点标志符和一个地区标志符，组成一个 M×N 的二维圆环.坐标(pID，aID)决定节点在该圆环中的位置.
图1显示一个8×4的网络.其中aID为01和10的节点各有两个，aID为11的节点有4个，没有pID相同的节点.
图 1 节点环空间
具有相同地区标志符(aID)的节点按节点标志符从小到大顺时针排列组成一个小的LAPN.每个LAPN都是一个小的Chord网络.但是一个节点同时只能属于一个地区，因此这些LAPN是相互孤立的，见图2.
图 2 LAPN
为了使这些网络可以相互联通，对网络中的某些节点增加一个或多个地区指针.每个地区指针指向某个LAPN的任意一个节点.
将节点标志符(pID)的前N位称为节点的伪地区码(fake area ID，简称nfaID).由于LAPN网中的节点按节点标志符从小到大顺时针排列，故LAPN网上各节点的伪地区码也就从小到大顺时针排列成一个环.
如果一个节点的伪地区码(nfaID)为n1，其前继节点(指在LAPN环空间上从这个节点出发逆时针方向的第一个节点)的伪地区码(nfaID)为n2，若n1=n2，则该节点没有地区指针；若n1>n2，则该节点有n1-n2个地区指针，分别指向地区标志符为(n2+1, n2+2, …, n1-1, n1)的LAPN中的任意一个节点.若n1
例如，图1所示的DSPSGL系统中，地区标志符为11的LAPN 网的各个节点的地区指针见表1所示.
在表1所示的地区指针中，节点001的所有地区指针均为NULL，若连续多个节点的地区指针都为NULL，将使系统的算法复杂度大大提高.为此，对地区指针的算法进行修正.若一个节点(其伪地区码是n1)的所有地区指针都为NULL，就再给它增加若干个指针，直至有一个非空指针，即增加分别指向地区标志符为(n1+1, n1+2, …, n1+n3-1, n1+n3)的LAPN指针，其中前n3-1个指针都为NULL，最后一个指向n1+n3的地区指针非空.这样经过修正后每个有地区指针的节点都至少有一个非空的地区指针.
图1所示的DSPSGL系统的地区指针经修正后，其他节点的地区指针不变，节点001增加一个指向aID=01的LAPN的地区指针.
增加地区指针后，DSPSGL系统中的节点就相互连通.图1所示的系统增加地区指针后见图3.
1.2 文件的加入和查找
文件是对系统中要存储的数据的统称.在系统中每个文件都有一个唯一确定的文件标志符(fID).它也是通过一致性哈希算法得到的.文件标志符(fID)表示为一个1到2M -1间的数.
在介绍文件的加入和查找算法之前，首先定义几个概念.图 3 连通后的DSPSGL系统
后继节点：文件标志符为f0的后继节点就是在LAPN环空间上节点标志符等于f0的节点或者从f0出发顺时针方向的第一个节点.
文件的伪地区码(ffaID)：称文件标志符(M位)的后N(N 后继LAPN：节点p0的地区标志符为a0的后继LAPN.它必须满足:(1)不是p0所在的LAPN；(2)地区标志符等于a0或者是在地区标志符环空间上从a0出发顺时针方向的第一个有效地区标志符.求节点p0的地区标志符为a0的后继LAPN算法如下：如果节点p0的地区标志符等于a0，将a0加1；然后在a0(N位)后面补M-N个0，构成一个M位的二进制数k，在p0所处的LAPN上查找k的后继节点p1，p1上必然有指向aID等于a0的LAPN地区指针.若此指针为NULL，说明该LAPN暂时不存在，就将a0加1，再次查找p1上的地区指针，如此反复直到找到一个非空的地区指针.该指针指向的LAPN就是节点p0的地区标志符为a0的后继LAPN.
从节点p0增加一个文件标志符为f0的文件到系统的算法：
(1)在节点p0所处的LAPN中查找f0的后继节点p1，将文件保存到p1上；
(2)确定文件f0的伪地区码为fa0；
(3)查找p0的地区标志符为fa0的后继LAPN；
(4)在此后继LAPN上查找文件f0的后继节点p2，并将文件保存到p2上；
(5)修改p0所处的LAPN的指向后继LAPN地区指针指向节点p2.
注意：文件的伪地区码取文件标志符的后N位，这与节点的伪地区码不同，原因是根据以上文件加入系统的算法，如果文件的伪地区码取文件标志符的前N位，将会使所有文件在后继LAPN中仅集中在少数几个节点上，即集中在伪地区码等于地区标志符的节点上.
从节点p0查找文件标志符为f0的文件算法：
(1)在p0所处的LAPN中查找f0的后继节点p1；
(2)在节点p1上若找到文件f0，将文件复制到节点p0上，查询结束，正常返回；
(3)若没有找到文件，确定文件f0的伪地区码为fa0；
(4)查找节点p0的地区标志符为fa0的后继LAPN；
(5)在后继LAPN上查找文件f0的后继节点p2；
(6)在节点p2上若找到文件f0，将文件同时复制到节点p0和p1中，成功返回，若找不到，异常返回.
1.3 基于多关键字的文件存储和查找
前面介绍简单的文件存储和查找算法，但有时需要基于关键字进行文件的存储和定位.为此在DSPSGL系统中增加称为索引的新实体.索引就是文件的多个关键字和文件名(文件标志符)一种对应关系.在系统中，每个索引也有一个唯一的索引标志符(iID)，该标志符是对索引进行一致性哈希运算得到的一个M位的二进制序列，它表示1到2M-1间的数.
为了使系统具有多关键字查询功能，在保存索引标志符k的节点n上建立索引信息表.表中每一项保存一个文件的所有索引和对应的文件标志符.例如关键字“网络”对应的索引信息见表2.
从节点p0增加一个具有多个关键字的文件算法如下：
首先按照1.2节中介绍的加入算法将文件(文件标志符为k)存储到节点p1(p0所在的LAPN上的节点)和p2(后继LAPN上的节点)上，然后在节点p0对每个关键字分别进行哈希运算，得到对应的索引标志符(k1,k2, … , kn).对每一个索引ki，再次使用第１.2节中介绍的加入算法选择合适的节点pki1(p0所在的LAPN上的节点)和节点pki2(后继LAPN上的节点)存储该索引信息.在节点pki1和pki2的索引信息表中保存该文件的所有关键字和文件标志符fID的对应关系.
当从节点p0使用一个或多个关键字搜索文件时，对其中的任意一个关键字进行哈希运算，得到索引标志符k；使用第1.2节中介绍的查找算法找到存储该索引的节点pk；然后在节点pk上打开其索引信息表，找到所有符合检索条件的文件对应的文件标志符，最后根据找到的文件标志符取得要查找的文件.
例如要查找具有关键字“算法，网络”的文件，可以对关键字“网络”进行哈希运算，得到索引标志符k，找到存储该索引的节点pk，读取其索引信息表，在其中查找同时具有“算法”和“网络”两个关键字的文件，发现有4个，对应的文件标志符分别是12，15，13，40. 最后再根据第1.2节介绍的算法，分别取得这4个文件.
1.4 节点的加入
在DSPSGL系统中，节点p0加入系统前，必须先知道系统中任意一个节点p1的信息；再根据自己的CPU ID值和IP地址计算节点的标志符(pID)为p0，地区标志符(aID)为a0.
若a0(节点p0的地区标志符)等于p1的aID，说明p0就在p1所处的局域P2P网络(LAPN)中.在此LAPN上查找p0的后继节点p2.将p0插入p2前面，先根据Chord算法更新信息(包括将后继节点的部分文件和索引信息移动到新节点上来)，然后再根据p0的后继节点p2以及前继节点p3的nfaID和地区指针更新p0和p2的地区指针.具体算法与前面确定地区指针的算法相同.
若a0不等于p1的aID，说明p0不在p1所处的LAPN上.在a0(N位)后面补M-N个0，构成一个M位的二进制数k，在p1所处的LAPN上查找k的后继节点p2，p2上必然有指向aID等于a0的LAPN的指针.
若指针不为空，就可以找到地区标志符等于a0的LAPN，然后在此LAPN上确定p0的位置，并更新它及其相邻节点的信息(包括Chord网络信息、文件及索引信息和地区指针等).
若指针为NULL，说明p0是该LAPN的第一个节点，此时要通知所有其他LAPN更新指向该LAPN的指针，并在节点p0上建立指向所有LAPN网的地区指针，然后确定节点p0的地区标志符为a0的后继LAPN(其地区标志符为a1)，从后继LAPN上把伪地区码小于等于a0的文件和索引复制到节点p0上(伪地区码大于a0且小于等于a1的文件和索引留在原LAPN上).
2 DSPSGL系统分析
根据以上介绍可以发现DSPSGL系统是对Chord系统的一种改进，具有稳定性高、响应迅速、支持多关键字查找等特点.下面对系统性能进行简单分析.
2.1 系统的健壮性分析
在系统中每个LAPN就是一个Chord网，因此节点失效不会引起LAPN瘫痪.同时每个LAPN网中都有指向所有其他LAPN的指针，若LAPN1的某个节点失效使得指向LAPN2的指针丢失，那么可以通过LAPN1上指向LAPN3的节点转到LAPN3上寻找指向LAPN2的指针.因此，任何一个或多个节点的失效都不会引起系统瘫痪，不存在单点故障问题.
2.2 算法复杂度分析
在P2P系统中，对系统性能影响最大的是访问节点，因此下面以访问节点的个数为依据，简单分析各主要算法的系统开销，前提是假定没有节点失效问题.假定系统中有M个节点，有N个LAPN，每个LAPN中最多有X个节点，因此在LAPN中查找节点的算法复杂度为logX.
首先分析查找节点p0的地区标志符为a0的后继LAPN的算法复杂度.由前面的介绍可知该算法就是先在a0后面补M-N个0构成M位的二进制数k，然后在p0所在的LAPN中查找k的后继节点p1，最后在节点p1上查找指向后继LAPN的指针，因此其复杂度为log X.
文件加入算法是同时将文件放入起始节点p0所在的LAPN和其后继LAPN中.放入p0所在的LAPN中需要一次查找文件的后继节点；放入后继LAPN需要一次查找后继LAPN和一次查找文件的后继节点，因此其复杂度是logX.
基于多关键字的文件加入算法相当于多个文件的加入，因此算法复杂度还是log X.
文件查找算法：若文件存在于起始节点p0所在的LAPN，只需查找一次文件的后继节点即可.若不在该LAPN，需要分别查找后继LAPN和文件的后继节点一次，因此它的算法复杂度为log X.
基于多关键字的文件查找算法相当于两次文件查找，因此算法复杂度还是log X.
节点p0已知节点p1加入系统时有3种情况:(1) p0和p1在同一LAPN中，即将p0加入p1所在的LAPN，算法复杂度为logX；(2) p0和p1不在同一LAPN中且p0所在的LAPN已经存在，此时需要在p1所在的LAPN上查找地区指针，然后在p0所在的LAPN上找到p0所在的位置，实际上是两次在LAPN上查找节点，算法复杂度是logX；(3) p0和p1不在同一LAPN中且p0所在的LAPN不存在，首先需要在p1所在的LAPN上查找地区指针(算法复杂度log X)，然后更新所有LAPN中指向这个新LAPN的地区指针(算法复杂度N·log X)，最后要访问其后继LAPN上的所有节点并进行文件迁移(算法复杂度X).因此其算法复杂度为N·log X+X.
3 结 论
从以上分析可以看出DSPSGL系统的健壮性很好，其文件加入和查找的算法复杂度均为log X(X是LAPN中的节点数)，与Chord算法相比有一定的改进.节点加入时，除了建立新的LAPN时复杂度较高外，其他时刻的算法复杂度也比Chord算法低.
DSPSGL系统在系统总体性能有所改进的前提下实现节点访问与IP网的关联，可使大部分操作在同一地域的IP网中完成，从而大大提高对等网的效率，同时实现基于多关键字的文件索引功能.因此，DSPSGL系统是一种有前途的新型P2P系统.
参考文献：
[1] FOX G. Peer-to-peer networks [J]. Computing in Sci & Eng, 2001,3(3): 75-77.
[2] MILOJICIC D S, KALOGERAKI V, LUKOSE R, et al. Peer-to-peer computing [R]. Hewlett-Packard Company, 2002.
[3] STOICA I，MORRIS R，NOWELL D L，et al.Chord:a scalable peer-to-peer lookup protocol for Internet applications [J].IEEE/ACM Transactions on Networking,2003,11(1): 17-32.
[4] MATEI R, LAMNITCHI A, FOSTER I. Mapping the Gnutella network [M]. IEEE Internet Computing, 2002.
(编辑 廖粤新)
“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”
关键词：对等网络； 覆盖网； IP网； 多关键字查询
中图分类号：TP393.01
文献标志码：A
Decentralized structured P2P system grouped by location
SHEN Xinpeng， LI Zhanhuai
(College of Computer Sci. & Eng.,Northwestern Polytechnical Univ., Xi’an, 710072)
Abstract： Because Chord is a typical distributed structured peer-to-peer (P2P) system based on overlay network, the distance between two adjacent peers may be very far on IP network, and the network access speed is greatly reduced. To solve the problem, a new P2P system is proposed to improve the Chord system. The peers in the same location are connected in a Location Area P2P Network (LAPN) which is connected by pointers. The method can resolve the problem and improve the system efficiency.
Key words： peer-to-peer network; overlay network; IP network; query on several keys
0 引 言
随着计算机处理能力和存储容量的提高以及通信技术的进步，人们可以随时随地接入网络并通过直接交换共享计算机资源和服务，对等计算[1](Peer-to-peer Computing)因此应运而生.对等网[2](Peer-to-peer，P2P)是没有任何集中控制的分布式系统，系统中每个节点在功能上均等同，既是客户机又是服务器，没有主从之分.
以Chord为代表的分布式结构化系统是P2P系统结构的研究重点.[3]系统中没有集中目录服务器，但节点的组织是结构化的.这里的结构是指系统对P2P网络拓扑和文件放置都精确地加以控制，仔细将文件均匀地分布在参与的节点中.该系统的优点是易于扩展，查询效率高，支持稀少文件的查询；缺点是对节点的不断加入和离开需要频繁地进行额外工作，不能有效支持多样化查询.而且由于该系统是在IP网(IP Network)上建立覆盖网(Overlay Network)，结果出现在覆盖网上的两个相邻节点在IP网上却相距很远的情况，于是，理论上只需要很少的延迟(比如一个Hop)，反映到实际IP网络上却需要很大的延迟，导致网络的实际访问速度大大降低.
为了解决这些问题，本文在分布式结构化P2P系统Chord的基础上进行改进，提出基于地域分组的分布式结构化P2P(Decentralized Structured P2P System Group by Location，DSPSGL)系统，它可以很好解决以上问题，是对P2P系统的一次有益改进.
1 DSPSGL系统介绍
在结构化P2P系统中，节点之间的访问路径长度一般都根据Overlay Network上的距离进行计算.但是Overlay Network上相邻的节点在IP Network上可能相距很远，从而造成数据访问的理论速度与实际速度差别很大.
为此，对分布式结构化P2P系统进行改进，提出DSPSGL系统.在DSPSGL系统中，处于同一地域的节点构成分布式结构化的局域P2P网络(Local Area P2P Network，LAPN)，这些LAPN的相互连通形成完整的DSPSGL网.
1.1 系统拓扑结构
在DSPSGL系统中，采用一致性哈希(Consistent Hashing) 算法[4]将网络中每个节点的标志映射成一个长度为M 位(bit)的二进制序列：节点标志符(pID)，并将其唯一分配给该节点.它表示1到2M-1间的数，在一维环空间(模2M)上由小到大按顺时针排列，选择合适的M值，可以保证两个节点的pID相同概率接近0.
在Chord 模型中，节点标志符(pID)通过哈希IP地址得到，但是该方法存在明显不足.现在国内很多用户使用ADSL方式上网，他们每次登入网络的IP地址都是变化的，因此同一节点两次登入系统的节点标志符不同.这就违反了节点标志符的唯一性原则，可能会造成同一节点在存储文件和查找文件时的节点标志符不一致的情况，失去定义节点标志符的意义.这里使用哈希机器CPU的ID来生成节点标志符.每台机器CPU的ID是唯一不变的.使用该方法可以保证节点多次接入系统时，其pID保持不变.
同时，每个节点还有一个N(N
图1显示一个8×4的网络.其中aID为01和10的节点各有两个，aID为11的节点有4个，没有pID相同的节点.
图 1 节点环空间
具有相同地区标志符(aID)的节点按节点标志符从小到大顺时针排列组成一个小的LAPN.每个LAPN都是一个小的Chord网络.但是一个节点同时只能属于一个地区，因此这些LAPN是相互孤立的，见图2.
图 2 LAPN
为了使这些网络可以相互联通，对网络中的某些节点增加一个或多个地区指针.每个地区指针指向某个LAPN的任意一个节点.
将节点标志符(pID)的前N位称为节点的伪地区码(fake area ID，简称nfaID).由于LAPN网中的节点按节点标志符从小到大顺时针排列，故LAPN网上各节点的伪地区码也就从小到大顺时针排列成一个环.
如果一个节点的伪地区码(nfaID)为n1，其前继节点(指在LAPN环空间上从这个节点出发逆时针方向的第一个节点)的伪地区码(nfaID)为n2，若n1=n2，则该节点没有地区指针；若n1>n2，则该节点有n1-n2个地区指针，分别指向地区标志符为(n2+1, n2+2, …, n1-1, n1)的LAPN中的任意一个节点.若n1
在表1所示的地区指针中，节点001的所有地区指针均为NULL，若连续多个节点的地区指针都为NULL，将使系统的算法复杂度大大提高.为此，对地区指针的算法进行修正.若一个节点(其伪地区码是n1)的所有地区指针都为NULL，就再给它增加若干个指针，直至有一个非空指针，即增加分别指向地区标志符为(n1+1, n1+2, …, n1+n3-1, n1+n3)的LAPN指针，其中前n3-1个指针都为NULL，最后一个指向n1+n3的地区指针非空.这样经过修正后每个有地区指针的节点都至少有一个非空的地区指针.
图1所示的DSPSGL系统的地区指针经修正后，其他节点的地区指针不变，节点001增加一个指向aID=01的LAPN的地区指针.
增加地区指针后，DSPSGL系统中的节点就相互连通.图1所示的系统增加地区指针后见图3.
1.2 文件的加入和查找
文件是对系统中要存储的数据的统称.在系统中每个文件都有一个唯一确定的文件标志符(fID).它也是通过一致性哈希算法得到的.文件标志符(fID)表示为一个1到2M -1间的数.
在介绍文件的加入和查找算法之前，首先定义几个概念.图 3 连通后的DSPSGL系统
后继节点：文件标志符为f0的后继节点就是在LAPN环空间上节点标志符等于f0的节点或者从f0出发顺时针方向的第一个节点.
文件的伪地区码(ffaID)：称文件标志符(M位)的后N(N
从节点p0增加一个文件标志符为f0的文件到系统的算法：
(1)在节点p0所处的LAPN中查找f0的后继节点p1，将文件保存到p1上；
(2)确定文件f0的伪地区码为fa0；
(3)查找p0的地区标志符为fa0的后继LAPN；
(4)在此后继LAPN上查找文件f0的后继节点p2，并将文件保存到p2上；
(5)修改p0所处的LAPN的指向后继LAPN地区指针指向节点p2.
注意：文件的伪地区码取文件标志符的后N位，这与节点的伪地区码不同，原因是根据以上文件加入系统的算法，如果文件的伪地区码取文件标志符的前N位，将会使所有文件在后继LAPN中仅集中在少数几个节点上，即集中在伪地区码等于地区标志符的节点上.
从节点p0查找文件标志符为f0的文件算法：
(1)在p0所处的LAPN中查找f0的后继节点p1；
(2)在节点p1上若找到文件f0，将文件复制到节点p0上，查询结束，正常返回；
(3)若没有找到文件，确定文件f0的伪地区码为fa0；
(4)查找节点p0的地区标志符为fa0的后继LAPN；
(5)在后继LAPN上查找文件f0的后继节点p2；
(6)在节点p2上若找到文件f0，将文件同时复制到节点p0和p1中，成功返回，若找不到，异常返回.
1.3 基于多关键字的文件存储和查找
前面介绍简单的文件存储和查找算法，但有时需要基于关键字进行文件的存储和定位.为此在DSPSGL系统中增加称为索引的新实体.索引就是文件的多个关键字和文件名(文件标志符)一种对应关系.在系统中，每个索引也有一个唯一的索引标志符(iID)，该标志符是对索引进行一致性哈希运算得到的一个M位的二进制序列，它表示1到2M-1间的数.
为了使系统具有多关键字查询功能，在保存索引标志符k的节点n上建立索引信息表.表中每一项保存一个文件的所有索引和对应的文件标志符.例如关键字“网络”对应的索引信息见表2.
从节点p0增加一个具有多个关键字的文件算法如下：
首先按照1.2节中介绍的加入算法将文件(文件标志符为k)存储到节点p1(p0所在的LAPN上的节点)和p2(后继LAPN上的节点)上，然后在节点p0对每个关键字分别进行哈希运算，得到对应的索引标志符(k1,k2, … , kn).对每一个索引ki，再次使用第１.2节中介绍的加入算法选择合适的节点pki1(p0所在的LAPN上的节点)和节点pki2(后继LAPN上的节点)存储该索引信息.在节点pki1和pki2的索引信息表中保存该文件的所有关键字和文件标志符fID的对应关系.
当从节点p0使用一个或多个关键字搜索文件时，对其中的任意一个关键字进行哈希运算，得到索引标志符k；使用第1.2节中介绍的查找算法找到存储该索引的节点pk；然后在节点pk上打开其索引信息表，找到所有符合检索条件的文件对应的文件标志符，最后根据找到的文件标志符取得要查找的文件.
例如要查找具有关键字“算法，网络”的文件，可以对关键字“网络”进行哈希运算，得到索引标志符k，找到存储该索引的节点pk，读取其索引信息表，在其中查找同时具有“算法”和“网络”两个关键字的文件，发现有4个，对应的文件标志符分别是12，15，13，40. 最后再根据第1.2节介绍的算法，分别取得这4个文件.
1.4 节点的加入
在DSPSGL系统中，节点p0加入系统前，必须先知道系统中任意一个节点p1的信息；再根据自己的CPU ID值和IP地址计算节点的标志符(pID)为p0，地区标志符(aID)为a0.
若a0(节点p0的地区标志符)等于p1的aID，说明p0就在p1所处的局域P2P网络(LAPN)中.在此LAPN上查找p0的后继节点p2.将p0插入p2前面，先根据Chord算法更新信息(包括将后继节点的部分文件和索引信息移动到新节点上来)，然后再根据p0的后继节点p2以及前继节点p3的nfaID和地区指针更新p0和p2的地区指针.具体算法与前面确定地区指针的算法相同.
若a0不等于p1的aID，说明p0不在p1所处的LAPN上.在a0(N位)后面补M-N个0，构成一个M位的二进制数k，在p1所处的LAPN上查找k的后继节点p2，p2上必然有指向aID等于a0的LAPN的指针.
若指针不为空，就可以找到地区标志符等于a0的LAPN，然后在此LAPN上确定p0的位置，并更新它及其相邻节点的信息(包括Chord网络信息、文件及索引信息和地区指针等).
若指针为NULL，说明p0是该LAPN的第一个节点，此时要通知所有其他LAPN更新指向该LAPN的指针，并在节点p0上建立指向所有LAPN网的地区指针，然后确定节点p0的地区标志符为a0的后继LAPN(其地区标志符为a1)，从后继LAPN上把伪地区码小于等于a0的文件和索引复制到节点p0上(伪地区码大于a0且小于等于a1的文件和索引留在原LAPN上).
2 DSPSGL系统分析
根据以上介绍可以发现DSPSGL系统是对Chord系统的一种改进，具有稳定性高、响应迅速、支持多关键字查找等特点.下面对系统性能进行简单分析.
2.1 系统的健壮性分析
在系统中每个LAPN就是一个Chord网，因此节点失效不会引起LAPN瘫痪.同时每个LAPN网中都有指向所有其他LAPN的指针，若LAPN1的某个节点失效使得指向LAPN2的指针丢失，那么可以通过LAPN1上指向LAPN3的节点转到LAPN3上寻找指向LAPN2的指针.因此，任何一个或多个节点的失效都不会引起系统瘫痪，不存在单点故障问题.
2.2 算法复杂度分析
在P2P系统中，对系统性能影响最大的是访问节点，因此下面以访问节点的个数为依据，简单分析各主要算法的系统开销，前提是假定没有节点失效问题.假定系统中有M个节点，有N个LAPN，每个LAPN中最多有X个节点，因此在LAPN中查找节点的算法复杂度为logX.
首先分析查找节点p0的地区标志符为a0的后继LAPN的算法复杂度.由前面的介绍可知该算法就是先在a0后面补M-N个0构成M位的二进制数k，然后在p0所在的LAPN中查找k的后继节点p1，最后在节点p1上查找指向后继LAPN的指针，因此其复杂度为log X.
文件加入算法是同时将文件放入起始节点p0所在的LAPN和其后继LAPN中.放入p0所在的LAPN中需要一次查找文件的后继节点；放入后继LAPN需要一次查找后继LAPN和一次查找文件的后继节点，因此其复杂度是logX.
基于多关键字的文件加入算法相当于多个文件的加入，因此算法复杂度还是log X.
文件查找算法：若文件存在于起始节点p0所在的LAPN，只需查找一次文件的后继节点即可.若不在该LAPN，需要分别查找后继LAPN和文件的后继节点一次，因此它的算法复杂度为log X.
基于多关键字的文件查找算法相当于两次文件查找，因此算法复杂度还是log X.
节点p0已知节点p1加入系统时有3种情况:(1) p0和p1在同一LAPN中，即将p0加入p1所在的LAPN，算法复杂度为logX；(2) p0和p1不在同一LAPN中且p0所在的LAPN已经存在，此时需要在p1所在的LAPN上查找地区指针，然后在p0所在的LAPN上找到p0所在的位置，实际上是两次在LAPN上查找节点，算法复杂度是logX；(3) p0和p1不在同一LAPN中且p0所在的LAPN不存在，首先需要在p1所在的LAPN上查找地区指针(算法复杂度log X)，然后更新所有LAPN中指向这个新LAPN的地区指针(算法复杂度N·log X)，最后要访问其后继LAPN上的所有节点并进行文件迁移(算法复杂度X).因此其算法复杂度为N·log X+X.
3 结 论
从以上分析可以看出DSPSGL系统的健壮性很好，其文件加入和查找的算法复杂度均为log X(X是LAPN中的节点数)，与Chord算法相比有一定的改进.节点加入时，除了建立新的LAPN时复杂度较高外，其他时刻的算法复杂度也比Chord算法低.
DSPSGL系统在系统总体性能有所改进的前提下实现节点访问与IP网的关联，可使大部分操作在同一地域的IP网中完成，从而大大提高对等网的效率，同时实现基于多关键字的文件索引功能.因此，DSPSGL系统是一种有前途的新型P2P系统.
参考文献：
[1] FOX G. Peer-to-peer networks [J]. Computing in Sci & Eng, 2001,3(3): 75-77.
[2] MILOJICIC D S, KALOGERAKI V, LUKOSE R, et al. Peer-to-peer computing [R]. Hewlett-Packard Company, 2002.
[3] STOICA I，MORRIS R，NOWELL D L，et al.Chord:a scalable peer-to-peer lookup protocol for Internet applications [J].IEEE/ACM Transactions on Networking,2003,11(1): 17-32.
[4] MATEI R, LAMNITCHI A, FOSTER I. Mapping the Gnutella network [M]. IEEE Internet Computing, 2002.
(编辑 廖粤新)
“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”