法律状态公告日
法律状态信息
法律状态
2016-11-16
未缴年费专利权终止 IPC(主分类):H04L12/54 授权公告日:20110914 终止日期:20150928 申请日:20070928
专利权的终止
2011-09-14
授权
授权
2010-02-24
实质审查的生效
实质审查的生效
2009-04-01
公开
公开
技术领域
本发明涉及计算机网络技术领域，特别涉及一种在基于分布式哈希表(Distributed Hash Table，DHT)的对等(Peer to Peer，P2P)网络中查找数据的方法和系统。
背景技术
区别于传统的客户端(Client)/服务器(Server)模式的网络，P2P网络中的每一参与的节点都是对等的，每一节点共享其拥有的一部分硬件资源(如处理能力、存储能力、网络链接能力、打印机等)，这些共享资源通过网络提供的服务和内容能被其它对等节点直接访问而无需经过中间实体。也就是说，在P2P网络中的参与节点既是资源(如服务和内容)提供者(相当于服务器)，又是资源获取者(相当于客户端)。
在新一代的P2P技术中，采用DHT构建P2P网络。DHT是一种分布式存储方法。DHT中每个节点负责存储一小部分数据，并负责一个小范围的路由，从而实现整个DHT网络的存储和寻址。
DHT中，首先将需要存储的数据通过散列函数得到定长的数据键值(Key)，同时，为组成Overlay网络中的节点也利用散列函数分配一个节点键值。特定键值的节点上负责一部分键值的数据的存储。各个节点间可以查找某键值的数据所在的节点。
现有技术中，可以采用多种算法实现DHT，例如有Chord、Pastry、CAN及Bamboo等。以下以Chord算法为例，介绍基于DHT的P2P实现方式。
Chord中每个数据关键字和节点都分别拥有一个m比特的标识符。数据V的关键字标识符设为K，可以通过哈希算法得到。节点标识符设为N，可以通过节点的IP地址由哈希算法得到。上面的哈希函数可以选用安全散列算法1(Secure Hash Algrithom-1，SHA-1)，或其它哈希函数。所有节点按照其节点标识符后其特征在于从小到大沿着顺时针方向排列在一个逻辑的标识圆环上(称为Chord环)。Chord的映射规则是：关键字标识为K的(K，V)对存储在这样的节点上，该节点的节点标识等于K或者在Chord环上紧跟在K之后，这个节点被称为K的后继节点，表示为successor(K)。因为标识符采用m位二进制数表示，并且从0到2m-1顺序排列成一个圆圈，successor(K)就是从K开始顺时针方向距离K最近的节点。
图1示出了一个m＝6的环。该m＝6的环中最多可以包括26个节点，这里以该m＝6的环中分布了10个节点，存储了5个关键字为例进行说明，节点标识前加上N而关键字前加上K以示区别。如图中10个节点分别表示为N1、N8、N14、N21、N32、N38、N42、N48、N51、N56；5个关键字分别表示为K10、K24、K30、K38、K54。因为successor(10)＝14，所以关键字为K10的数据存储到节点N14上。同理，关键字为K24和K30的数据存储到节点N32上，关键字为K38的数据存储到节点N38上，关键字为K54的数据存储到节点N56上。
仍以图1中所示的Chord算法中数据存储和节点关系的原理图为例，图2示出了Chord的查询原理图。图中每个节点维护一个路由表，称为指针表(finger table)。每个数据关键字和节点标识符用m位二进制数表示，那么，每个节点的指针表中最多含有m个表项。节点N的指针表中第i项的节点是圆环上标识大于或等于n+2i的第一个节点(比较是以2m为模进行的)。例如若s＝successor(n+2i)，0≤i≤(m-1)，则称节点s为节点N的第i个指针。另外，当查找的数据关键字大于指针表中的最大范围时，对应指针表中的最后一个节点，即下表中的数据关键字大于N8+16时，对应指针表中的节点N42。指针表中每一项既包含相关节点的标识，又包含相关节点的IP地址(和端口号)。如图中的节点N8可以维护下面所示的指针表：
表1.节点N8维护的指针表
上表给出了节点8的指针表，例如节点14是环上紧接在(8+20)mod 26＝9之后的第一个节点，所以节点8的第一个指针是节点14；同理，因为节点21是环上紧接在(8+23)mod 26＝16之后的第一个节点，所以节点8的第3个指针是节点21。其它指针和其它节点维护的指针表可以以此类推。上述维护指针表使得每个节点只需要知道网络中一小部分节点的信息，而且离它越近的节点，它知道的信息越多。
这样，任何一个节点收到查询关键字为K的数据V的请求时，首先检查关键字K是否落在该节点标识和它的后继节点标识之间，如果是，这个后继节点就是存储目标(K，V)对的节点。否则，节点将查找自身维护的指针表，找到表中节点标识符不超过K的最大的节点，并将这个查询请求转发给该节点。通过重复这个过程，最终可以定位到K的后继节点，即存储有目标(K，V)对的节点。
本领域技术人员知道，叠加(Overlay)网络是应用层网络，它是面向应用层的，不考虑或很少考虑网络层、物理层的问题。具体的，Overlay网络是指建立在一个网络上的网络。很多P2P网络就是Overlay网络，因为它运行在互连网的上层。
实际中，可以有多种不同层次的Overlay网络共同构成P2P网络。图3示出了具有两个层次Overlay网络的P2P网络拓扑图。两个层次的Overlay分别为上层(top-level)Overlay和下层(bottom-level)Overlay。bottom-level Overlay中包括若干普通节点，且每个bottom-level Overlay通过一个普通节点与top-level Overlay传递数据，这时，这个用于在不同层次叠加网络中传递数据的普通节点称为超级节点，该超级节点同时属于bottom-level Overlay网络和top-level Overlay网络。如图3中分层次的Overlay网络中查询数据的方法可以举例如下：
步骤A：top-level Overlay中的一个超级节点接收查询请求，按照该查询请求中的长度为m比特的数据关键字K查询top-level Overlay中的超级节点。
步骤B：当在top-level Overlay中查询到最接近的超级节点时，在该超级节点所在的bottom-level Overlay中继续按照长度为m比特的数据关键字K查找。
上述步骤中的查询可以是前面提到的Chord方式。
例如，如图3中，环D为top-level Overlay，其上包括三个超级节点，关键字分别为010101，110110和101001。环A、环B和环C都是bottom-levelOverlay，其中，环A上包括与环D共有的关键字为010101的超级节点，还包括节点010001和011000。当环D中收到一个查询关键字为010001的数据查询请求时，首先在环D中以该关键字逐个查询。之后，在环A上也以关键字010001的继续查询。
在对现有技术的研究和实践过程中，发明人发现现有技术中存在以下问题：
由于在一个环内，仅需要查询关键字的某些位即可得到查询结果，而现有技术在不同层次的环内进行查询时始终采用同一长度的关键字进行查询，查询效率不高。例如上述过程中，在环D内的超级节点，如果不同超级节点的头两位不同，那么，只需查找关键字的头两位即可判断是否找到对应的超级节点，如果此时仍按照6位长度查询，效率不是很高。同样，在环A内的普通节点，如果不同普通节点的后四位不同，那么，只需查找关键字的后四位即可判断是否找到对应的普通节点，如果此时仍按照6位长度查询，效率也不高。
发明内容
本发明实施例的目的是提供一种在基于分布式哈希表的对等网络中查找数据的方法和系统，以克服现有技术中始终采用同一长度的关键字进行查询而导致的查询效率不高的缺点。
为解决上述技术问题，本发明实施例提供一种在基于分布式哈希表的对等网络中查找数据的方法和系统是这样实现的：
一种在基于分布式哈希表的对等网络中查找数据的方法，所述对等网络包括至少两层叠加网络，每层叠加网络中包括至少一个节点，所述节点的节点标识包括区域标识和本地标识，相邻的两层叠加网络通过超级节点传递数据，该方法并包括：
上层叠加网络中的第一超级节点接收查询请求；所述查询请求中包含待查找数据的区域标识和本地标识；
在所述上层叠加网络中从第一超级节点开始，查找与所述查询请求相同区域标识的第二超级节点；
在所述第二超级节点所在的下层叠加网络中以所述查询请求中的本地标识查找数据所在节点。
一种在基于分布式哈希表的对等网络中查找数据的系统，所述对等网络包括至少两层叠加网络，每层叠加网络中包括至少一个节点，所述节点的节点标识包括区域标识和本地标识，相邻的两层叠加网络通过超级节点传递数据，其中，
上层叠加网络中的第一超级节点用于接收查询请求，并在所述上层叠加网络中查找与所述查询请求相同区域标识的第二超级节点；所述查询请求中包含待查找数据的区域标识和本地标识；
所述超级节点所在的下层叠加网络，用于以所述查询请求中的本地标识在所述下层叠加网络中进行查找。
一种在基于分布式哈希表的对等网络中查找数据的节点，位于上层叠加网络中，所述上层叠加网络中包括至少一个节点标识为包括区域标识和本地标识的所述节点，且所述节点包括：
查询请求接收单元，用于接收查询请求，；所述查询请求中包含待查找数据的区域标识和本地标识；
查找单元，用于在所述上层叠加网络中查找与所述查询请求相同区域标识的超级节点。
一种在基于分布式哈希表的对等网络中查找数据的节点，位于下层叠加网络中，所述下层叠加网络中包括至少一个节点标识为包括区域标识和本地标识的所述节点，且所述节点包括：
查询请求接收单元，用于接收查询请求；所述查询请求中包含待查找数据的区域标识和本地标识；
查找单元，用于以接收到的查询请求中的本地标识在所述下层叠加网络中进行查找。
由以上本发明实施例提供的技术方案可见，接收到查询请求后，在上层叠加网络中查找相同区域ID的超级节点，在该超级节点所在的下层叠加网络中以所述查询请求中的本地ID进行查找，这样，在不同层次的叠加网络中进行查询时采用不同的关键字，而不需要采用全部字段的关键字进行查询，也就是说采用全部关键字中的部分字段进行查询，从而提高了查询效率。
附图说明
图1为现有技术Chord算法中数据存储和节点关系的原理图；
图2为现有技术Chord算法的查询原理图；
图3为现有技术中包含上层和下层叠加网络的对等网络拓扑图；
图4为本发明方法实施例的流程图；
图5为本发明方法一个完整实施例的网络拓扑图；
图6为本发明方法一个完整实施例中上层叠加网络的节点图；
图7为本发明方法一个完整实施例中下层叠加网络的节点图。
具体实施方式
本发明实施例提供一种在基于分布式哈希表的对等网络中查找数据的方法，上层叠加网络中的第一超级节点接收查询请求，在所述上层叠加网络中查找与所述查询请求相同区域标识的第二超级节点，在所述第二超级节点所在的下层叠加网络中以所述查询请求中的本地标识进行查找。
为了使本技术领域的人员更好地理解本发明方案，下面结合附图和实施方式对本发明实施例作进一步的详细说明。
本方法实施例中提供一种在基于分布式哈希表的对等网络中查找数据的方法，所述对等网络包括至少两层叠加网络，每层叠加网络中包括至少一个节点，所述节点的节点标识包括区域标识和本地标识，相邻的两层叠加网络通过超级节点传递数据。所述区域ID是节点所属区域的标识，不同区域的节点其区域ID不同。所述本地ID是节点在所属区域内的标识，同一区域内的不同的节点其本地ID不同。如图4所示，该方法实施例包括下面步骤：
步骤401：上层叠加网络中的第一超级节点接收到查询请求；所述查询请求中包含待查找数据的区域标识和本地标识。
该步骤中，查询请求最初可以是直接发送到所述第一超级节点，也可以是通过下层叠加网络传递到所述上层叠加网络。如果是后一种情况，则可以包括下面步骤A和B：
步骤A：下层叠加网络中的第一普通节点接收到查询请求后，判断查询请求中的区域ID是否与自身区域ID相同。
该步骤中，首先通过查询请求中的区域ID判断是否需要在接收查询请求的第一普通节点所在叠加网络中查找。首先通过区域ID的判断，可以预先排除不需要查找的叠加网络，这样可以避免无效的查找，从而提高查找效率。
步骤B：当所述查询请求中的区域ID与所述接收查询请求的第一普通节点的区域ID不同时，将查询请求通过所述第一普通节点所在下层叠加网络与上层叠加网络连接的所述第一超级节点定向到所述上层叠加网络。
另外，当所述查询请求中的区域ID与所述下层叠加网络的区域ID相同时，以查询请求中的本地ID在所述接收查询请求的第一普通节点所在层次的叠加网络中查找。
步骤402：在所述上层叠加网络中查找与所述查询请求相同区域ID的第二超级节点。
具体查询过程可以采用前述提到的Chord方式，当然也可以采用其它可行的方式。
这样，可以保证后续查找过程在区域ID相同的情况下查找，而不会在不同区域ID的叠加网络中查找，提高了查找效率。
步骤403：在所述第二超级节点所在的下层叠加网络中以所述查询请求中的本地ID进行查找。
该步骤中，所查找的范围在与查询请求中相同区域ID的下层叠加网络中，即将查找范围锁定在合理有效的较小范围内，从而提高了查找效率。
上述查找过程中，可以预先将节点的区域ID设置为与该节点的物理位置相关。例如，对于国内的不同省市的节点来说，可以将同在北京的节点设置为相同的区域ID，将同在天津的节点设置为另一相同的区域ID。这样，查找过程中，尽可能的在同一区域上查找，避免跨区域查找引起的延时长的问题。
可以采用静态配置的方式实现将节点的区域ID设置为与该节点的物理位置相关，即将物理位置相同的节点的区域ID设置为相同。例如，设北京的区域ID为010，则可以将同在北京的节点设置为相同的区域ID(即010)。
也可以采用扩展动态主机配置协议(Dynamic Host Configuration Protocol，DHCP)消息的方式实现。具体的，节点加入网络时，采用DHCP分配IP地址。则，分配地址的DHCP消息中，可以增加区域ID的标识给请求加入的节点，且物理位置相同的节点其区域ID相同。例如，当某一节点加入网络时，由网络通过DHCP分配IP地址，该网络所在区域为天津，设其区域ID为022，则在分配IP地址的DHCP中增加天津对应的区域ID(即022)，这样，所述加入该网络的节点相同的天津对应的区域ID(022)。依此类推，任一加入该网络的节点都具有天津对应的区域ID，即具有相同的区域ID。
还可以采用网际协议版本6(IPv6)中的路由通告(Router Advertisement，RA)的方式实现。具体的，不同节点加入同一路由器以下的网络时，路由器将自身的前缀(prefix)通过RA消息通告给所述节点的同时在RA消息中携带区域ID扩展字段。这样，所述路由器以下网络中的所有节点具有相同的区域ID。也可以将多个位置接近的路由器设置相同的区域ID，他们在RA消息中携带相同的区域ID。
另外，上述过程中，不同层次的叠加网络可以用不同的ID来组织路由，即设置和存储每个节点的路由表项。如top-level Overlay可以采用区域ID组织路由，而bottom-level Overlay可以采用本地ID组织路由。其中，超级节点既是上层叠加网络的节点，也是下层叠加网络的节点，超级节点同时支持上述两种路由组织方式。这里的组织路由，即设置节点上存储的路由表，与现有技术不同的，这里对节点上存储的路由表的设置，在top-level Overlay采用区域ID设置，在bottom-level Overlay采用本地ID设置。换句话说，是采用全部ID中的部分来设置，而不是现有技术中的采用全部ID设置，这样，相对于现有技术中组织路由的方式，可以节省路由表项的体积。在采用Chord的查询方式中，这里的路由表即指针表，具体可以如下面例子中所示。
相应地，所述在所述上层叠加网络中查找与所述查询请求相同区域标识的第二超级节点，在所述超级节点所在的下层叠加网络中以所述查询请求中的本地标识查找数据，由以下方式实现：
在所述上层叠加网络节点上存储的由区域标识组织的路由表项中查找与所述查询请求相同区域标识的第二超级节点；
在所述第二超级节点所在的下层叠加网络中的普通节点上存储的由本地标识组织的路由表项中，以所述查询请求中的本地标识进行查找。
上述实施例以两层overlay为例进行说明，而本发明完全可以扩展到多层overlay，例如将区域ID进一步细分为国家ID，地区ID，然后依据上述原则进行层次化的查找。
以下以图5所示的网络为例，例举一个本发明方法的完整实施例。
为了说明方便，将每个节点的区域ID和本地ID之间加“.”以区分。由图5可见，环A、环B和环C为bottom-level Overlay，环D为top-level Overlay。环A上节点都处于同一物理位置，且区域ID都为001，环B上节点都处于同一物理位置，且区域ID都为010，环C上节点都处于同一物理位置，且区域ID都为110。环A与环D通过超级节点A8/D1相连，环B与环D通过超级节点B1/D2相连，环C与环D通过超级节点C1/D6相连。
则包括以下流程：
步骤a：A1收到查找关键字为110.1100的数据的请求。
步骤b：A1判断查询请求中的区域ID(110)与自身的区域ID(001)不同。
步骤c：A1将查询请求定向到环A的超级节点A8/D1上。
步骤d：D1在环D上根据区域ID查找到与所述查询请求区域ID(110)相同的超级节点C1/D6。
步骤e：C1在环C上根据查询请求中的本地ID查找所在节点，最终找到关键字为110.1100的数据在节点C13上。
可以按照前面提到的Chord方法在每个环中进行查找。举例如下：
节点D1中存储有如下所示的指针表：
表2.节点D1维护的指针表
当D1接收到查询关键字为110.1100的数据的请求，在环D上的查找可以如图6所示。数据关键字的区域ID十进制为6，按照上面表中，大于D1+2(3)，因此定位在对应节点D6上。此时，数据关键字6正好等于D6的区域ID，这样，在D6(也就是C1)所在的下层叠加网络中继续查找。
节点C1中存储有如下所示的指针表：
表3.节点C1维护的指针表
当C1接收到查询关键字为110.1100的数据的请求，在环C上的查找可以如图7所示。节点C1中存储有如图所示的表，数据关键字的本地ID十进制为12，按照上面的表，定位到节点C9上。
节点C9中存储有如下所示的指针表：
表4.节点C9维护的指针表
而12大于C9+2(C11)，且12小于C9+4(C13)，按照上面的表，定位到节点C13上，在节点C13上查找到关键字为110.1100的数据。
在环A中的查找与上面过程类似，在此不再赘述。
当然，除了采用上面的Chord方式查找，还可以采用其它方式。
需要说明的是，上述完整实施例中，上层叠加网络中的每个节点上可以储存区域ID字长个数的表项，下层叠加网络中的每个节点上可以储存本地ID字长个数的表项。
由上述实施例可见，上层叠加网络中的第一超级节点接收到查询请求后，在上层叠加网络中查找相同区域ID的第二超级节点，在该第二超级节点所在的下层叠加网络中以所述查询请求中的本地ID进行查找，这样，在不同层次的叠加网络中进行查询时采用不同的关键字，即采用全部关键字中的部分字段进行查询，从而提高了查询效率。另外，预先将节点的区域ID设置为与该节点的物理位置相关，这样，在查找过程中，保证尽可能的在同一区域上查找，从而避免了不必要的跨区域查找引起的延时长的问题。
以下介绍本发明的系统实施例。
一种在基于分布式哈希表的对等网络中查找数据的系统，所述对等网络包括至少两层叠加网络，每层叠加网络中包括至少一个节点，所述节点的节点标识包括区域标识和本地标识，相邻的两层叠加网络通过超级节点传递数据，其中，
上层叠加网络中的超级节点用于接收查询请求，并在所述上层叠加网络中查找与所述查询请求相同区域ID的超级节点；
所述超级节点所在的下层叠加网络，用于以所述查询请求中的本地ID在所述下层叠加网络中进行查找。
所述下层叠加网络还用于：下层叠加网络中接收到查询请求的节点判断查询请求中的区域ID是否与自身区域ID相同；
当所述查询请求中的区域ID与所述节点的区域ID不同时，将查询请求通过所述节点所在下层叠加网络的第一超级节点定向到上层叠加网络。
所述下层叠加网络的区域ID与所述查询请求中的区域ID相同时，所述下层叠加网络还用于以查询请求中的本地ID查找。
所述下层叠加网络的区域ID与所述查询请求中的区域ID相同时，所述下层叠加网络还用于以查询请求中的本地ID查找。
所述上层叠加网络和下层叠加网络中的节点，其区域ID分别设置为与该节点的物理位置相关。
所述上层叠加网络中的节点采用区域ID组织路由，下层叠加网络中的节点采用本地ID组织路由，其中，超级节点既是上层叠加网络的节点，也是下层叠加网络的节点，超级节点同时支持上述两种路由组织方式；相应地，
所述上层叠加网络在其包含的节点上存储的由区域ID组织的路由表项中查找与所述查询请求相同区域ID的超级节点；
所述超级节点所在的下层叠加网络在其包含的节点上存储的由本地ID组织的路由表项中，以所述查询请求中的本地ID进行查找。
利用上述系统实施例实现查找数据的方法与前面方法类似，在此不再赘述。
以下介绍本发明的节点实施例。
一种在基于分布式哈希表的对等网络中查找数据的节点，位于上层叠加网络中，所述上层叠加网络中包括至少一个节点标识为包括区域标识和本地标识的所述节点，且所述节点包括：
查询请求接收单元，用于接收查询请求；所述查询请求中包含待查找数据的区域标识和本地标识；
查找单元，用于在所述上层叠加网络中查找与所述查询请求相同区域标识的超级节点。
一种在基于分布式哈希表的对等网络中查找数据的节点，位于下层叠加网络中，所述下层叠加网络中包括至少一个节点标识为包括区域标识和本地标识的所述节点，且所述节点包括：
查询请求接收单元，用于接收查询请求；所述查询请求中包含待查找数据的区域标识和本地标识；
查找单元，用于以接收到的查询请求中的本地标识在所述下层叠加网络中进行查找。
利用上述节点实施例实现查找数据的方法与前面方法类似，在此不再赘述。
由以上实施例可见，上层叠加网络中的第一超级节点接收到查询请求后，在所述上层叠加网络中查找相同区域ID的第二超级节点，在该第二超级节点所在的下层叠加网络中以所述查询请求中的本地ID进行查找，这样，在不同层次的叠加网络中进行查询时采用不同的关键字，即采用全部关键字中的部分字段进行查询，从而提高了查询效率。
虽然通过实施例描绘了本发明实施例，本领域普通技术人员知道，本发明有许多变形和变化而不脱离本发明的精神，希望所附的权利要求包括这些变形和变化而不脱离本发明的精神。
机译： 在基于分布式哈希表的对等网络中管理数据的方法，涉及在时间间隔到期之后在节点之间传输数据文件，其中节点的身份是从确定的身份值中得出的
机译： 在基于对等通信的面向服务的网络中动态数据发现的系统和方法
机译： 一种基于查找在内容中心网络中轻松传输数据包进行确定的方法和系统
