分布式哈希表(DHT)^[1-4]是一种分布式查询系统，具有查询扁平化、良好的可扩展性和可靠性^[5]等优点，因此DHT得到了广泛的应用^[6-14]。与此同时，较低的查询效率(logN，N为系统节点)是DHT的缺点，因此，如何提高DHT的查询效率一直是研究的热点，在众多的解决方法中，层次化方法^[15-22]不仅能提高查询效率，同时能减轻节点及链路上的流量负载，因而得到广泛的关注。一般来讲，层次化DHT结构分为2层：顶层和底层，其中，底层由所有分组构成，分组的构建主要遵循以下2个原则，其一是根据网络拓扑结构，将物理位置相近的节点放在一个分组内；其二是按照“语义(semantic)”来创建分组，这里所谓语义是指节点上所存储数据的类型，将存储相同类型数据(.mp3或者.avi等)的节点放在一个分组内。每个分组选出一个代理节点(proxy node)构成顶层结构(顶层拓扑一般仍然采用DHT连接)，通常来讲，代理节点比组内其它节点具有更高的带宽和更强的处理能力，因此，代理节点又称为管理节点或者超级节点，在文章后面部分统称为管理节点。为了减轻管理节点的处理压力，同时避免单点失效问题(single point problem)，一个分组需要多个管理节点。因此，这样的分层DHT结构可以类似看成Internet网络架构，每个分组可以看成是一个自治域(autonomous system, AS)，顶层结构可以近似地看成是Internet的核心网络，因此管理节点可以看成是每个自治域(分组)的网关，负责域内域外节点的通信。分层DHT的查询首先在分组内进行，如果查找目标不存在于分组内，则通过管理节点到其它分组进行查找。

Ratnasamy^[3]最早提出利用分层思想来提高CAN的查询效率，Ratnasamy提出利用网络标志(network landmark)测算的方法来计算系统节点到测试节点的时延，将具有相似时延结果的节点划分为一组。Garces^[15]借助IP网络的路由方式实现了2层DHT结构，顶层和底层均通过Chord连接，每个分组由一个管理节点管理。管理节点负责组内节点与外部节点的通信。对于每个分组拓扑结构，作者提出可以根据节点数目的规模来选择星型连接、集中式连接和DHT连接，当分组内节点数目较少时，可以采用集中式或者星型连接方式，当节点数目较大时，可以采用DHT连接方式。HIERAS^[16]利用(distributed binning scheme, DBS)方法将物理拓扑上距离相近的节点划分为一个分组，与其它分层结构不同的是，HIERAS的每一个节点同时属于所有的分组，查询采用从下至上的方式进行，如果在所有分组内均未查找到目标则在顶层全局进行查找，HIERAS虽然提高了查询效率，但同时也增加了每个节点的开销。Canon^[18]采用类似域名解析系统(domain name system, DNS)的分层结构，底层由系统所有节点构成，每个中间层节点为一个分组并采用DHT连接方式，除了查询本地化优之外，这种基于树形的分层结构能够有效利用缓存和多播技术来提高系统的查询效率。Cyclone^[19]虽然与Canon具有相同的树形分层结构，但是Cyclone具有垂直和平行2个平面的层次化结构，同时为了实现负载均衡，Cyclone对节点ID的定义采用与IP地址命名相同的规则，对于一个n比特的节点ID，前p个比特表示节点的ID，后面n-p的比特表示节点所在分组的ID。

然而，对分层DHT的传统研究多数集中在分层结构的构建和流量分析方面，极少关注在多管理节点结构下分层DHT查询效率和节点负载均衡问题，因此，提出了基于DHT的多管理节点分层结构，在多管理节点结构下针对分层DHT结构的查询效率和节点负载均衡做了一些研究。

1 多管理节点模型及出口选择策略

为了避免单点失效问题和减轻分组管理节点的压力，提高系统的可靠性和健壮性，一个分组应该具有多个管理节点。图 1给出了多管理节点分组结构，如图所示，分组i有3个管理节点，分别为MN1、MN2和MN3。这里需要特别说明的是，多管理节点分层模型的底层和顶层拓扑均采用Chord结构。对分组内部的节点来说，多个管理节点意味着当它们与外部节点通信的时候，有多个出口可以选择。特别的，对于图 1分组i中的节点来说有3个出口可供选择，而采用何种出口选择策略对系统的性能会产生不同的影响，研究将从“查询效率”、“最小化系统流量”和“负载均衡”3个维度来考察不同的出口选择策略对系统性能的影响。注意，为了描述方便，“管理节点”和“出口节点”将交替出现。

1.1 最短路径选路算法

为了最大化系统的查询效率，提出了最短路径选择算法(shortest path selection, SPSA)，SPSA是一种贪婪算法，总是选择距离目的地址最近的出口节点，如图 2所示，分组i中有节点对k₁、k₂发出查询(注意，此时查询目标k₁、k₂不存在于本地分组内)，此时，基于SPSA算法思想，由于距离k₁最近的出口节点为出口2，距离k₂最近的出口节点为出口3，因此，分组内对k₁进行查询的所有节点都将选择出口2，对k₁进行查询的所有节点将选择出口3，代码见表 1。

1.2 基于热土豆模型的最小化组内流量算法

在业务量工程相关问题程中，“hot-potato^[23-24]”路由算法的基本思想是通过对比一系列对等条件，把去往域外的流量从最近的出口导出域外，从而减轻域内各链路上的流量负载，达到提高链路利用率和网络性能的目的。图 3所示为“hot-potato”模型，A、B和C分别代表 3个路由器，其中B和C为边界路由器，路由器A和B之间的代价为9，A和C之间的代价为12，因此，在hot-potato模型下，通过A去往域外的流量将选择边界路由器B。

根据“Hot-potato”模型思想，笔者提出“基于热土豆的最小化组内流量”算法：MIT_HP (minimum intra-group traffic based on hot potato algorithm)。算法的基本思想：分组内的每个节点在其路由表中维护到所有出口节点的路由代价(hops)，当存在去往分组外的查询是，当前节点总是选择距离自己最近(路由代价最小)的出口节点。由于查询的突发性和随机性，可能导致某些出口节点在短时间内收到大量的查询，大量的突发流量将导致查询排队队列的增加，甚至阻塞出口节点，降低网络吞吐量。因此，每个出口节点都将设置一个负载门限值，节点在选择出口节点时首先判断出口节点是否过载，如果判断所选择的出口节点过载，就选择除了当前出口节点之外，路由代价最小的出口节点。MIT_HP算法如图 4所示，代码如表 2。

1.3 出口节点负载均衡选择算法

在某种意义上，系统具有较好的负载均衡意味着系统公平性越好。基于此，从系统负载均衡和出口节点公平性角度出发，提出了2种算法：LBGS_1(Load balancing with gateway selection_1) 和LBGS_2(Load balancing with gateway selection_2)，LBGS_1算法思想很简单，节点转发消息时，在本地路由表中随机地选择一出口节点，为了保证管理节点的公平性，LBGS_2算法在每一次选择出口的时候，选择负载最小的出口节点(可以统计节点消息计数来计算节点负载的高低)，代码如表 3。

为了比较2种算法的公平性，采用公式(1) 来考察。

$FI = \frac{{{{\left| {\sum\limits_{j = 1}^{M\_{\rm{list}}} {{\rm{Coun}}{{\rm{t}}_j}} } \right|}^2}}}{{n\sum\limits_{j = 1}^{M\_{\rm{list}}} {{\rm{Coun}}{{\rm{t}}_j}^2} }},$

(1)

函数FI(jain’s fairness index)是一个被广泛认同用来衡量系统公平性的函数，从公式(1) 可以得到，FI的取值范围为(0, 1]，当FI的值为1时，说明系统具有最好的公平性，反之FI值越小，表明系统公平性越差。

2 仿真结果与分析

对于传统分层结构，平均查询效率为

$1/2{\rm{log}}\;N + 1/2{\rm{log}}\;S + 1/2{\rm{log}}\;N = {\rm{log}}\;N + 1/2{\rm{log}}\;S,$

(2)

而多节点分层结构的平均查询效率为

$1/2{\rm{log}}\;N + 1/2{\rm{log}}\;\left( {S/r} \right) + 1/2{\rm{log}}\;N = {\rm{log}}\;N + 1/2{\rm{log}}\;\left( {S/r} \right),$

(3)

式(2) 和(3) 中，N为分组中节点数目，S为顶层节点数目，r为分组出口节点数目，由此可见，多出口分层模型的查询效率要高于传统分层模型。

研究侧重分析了在多出口模型下3种算法在查询效率、负载均衡和节点公平性3个维度考察算法的差异。

前面分别给出了最短路径选择算法、基于热土豆模型的最小化组内流量算法和出口节点负载均衡选择算法，3种算法从不同的角度考察分层系统的性能。研究给出3种算法的性能分析。实验仿真环境如下：分层拓扑结构分组节点数分别为2 000和4 000，分组数量为100，每个分组的管理节点数目分别为3, 4, 5，查询服从Zipf分布。仿真数据分别考察了系统的查询效率、分组内流量和出口节点负载均衡。

图 5所示为分组内部节点数目为2 000，管理节点数目为3，查询服从Zipf分布，当Zipf参数不同时，MIT_PH、SPSA和出口节点负载均衡选择算法(LBGS_1) 对系统查询延迟的影响。从图中可以看到，LBGS_1算法查询效率最低，MIT_HP算法的性能上要优于SPSA算法，似乎与算法分析预期不符合，但是通过对实验仿真环境和仿真数据仔细分析后不难得出结果，出现这种情况的原因是SPSA仅能保证在顶层取得查询延迟最小，底层(分组内)的情况较复杂，其查询延迟受到查询分布和节点数目二者的共同影响，在提出的实验环境中，分层拓扑结构组内的节点数目要远远多于顶层节点数(顶层节点数量为300~500，而分组内节点数目为2 000~4 000)，MIT_HP算法能保证底层分组内查询延迟最小，因此从查询效率贡献上来讲，MIT_HP算法要优于SPSA算法。

图 6所示为MIT_HP算法与SPSA算法流量对比，由于MIT_HP算法总是从最近的出口节点导出查询消息，因此较SPSA具有较低的流量，图中能清晰地反映这一规律。

表 4给出了3种出口选择算法下分组内流量比较，从表中可以看出，MIT_HP算法总是具有最小的分组内流量(count3表示)。

表 5给出了3种算法下管理节点的负载公平性的对比情况，其中，FI_1为LBGS_1公平性函数值，FI_2为SPSA算法得到的公平性函数取值，FI_3为最MIT_HP得到的公平性函数取值。可以看到，采用LBGS_1取得最好的公平性，FI取值接近于1，意味了每个管理节点上的负载几乎相同。这里特别要说明的是，在基于热土豆模型最小化组内流量算法下，由于组内每个节点的查询数量没有发生变化(仅仅是查询目标发生变化)，而算法选择出口总是选择距离自己最近的出口节点，因此，FI_3的值保持不变。

图 7所示为3种算法的查询效率对比，实验仿真环境为：分组节点数为4 000，管理节点数为5，查询分布服从Zipf分布(参数变化)。图中av_1、av_2和av_3分别表示LBGS_1、MIT_HP和SPSA 3种算法，从图中可以清楚地看到，LBGS_1算法具有最低的查询效率，MIT_HP和SPSA算法的查询效率相近，随着管理节点数目的增加，最短路径算法对整个系统的查询效率贡献越来越多，在这种情况下，SPSA算法较MIT_HP算法有较高的查询效率，这和前面的分析相符合。

图 8和图 9所示为3种算法下系统顶层流量和分组内部流量的分析对比，这里分组节点数为4 000，管理节点数为5，查询分布服从Zipf分布(参数变化)。图中T11、T22和T33分别表示SPSA、MIT_HP和LBGS_13种算法所产生的流量。从图中可清晰地看出，最短路径查询算法总能使得系统顶层产生最小流量，而对于底层来说，MIT_HP能取得最小流量。

图 10给出了传统查询算法和多出口模型下查询算法的一个对比，图中，S₁表示传统查询算法查询效率的理论值，S₂为其仿真值；S₃、S₄、S₅分别为出口节点为3, 4, 5的时候多出口模型下查询效率的仿真值。从图中可以清楚地看到，多出口模型下的查询效率要明显高于传统分层查询效率。

表 6对具有多出口分层DHT结构与传统分层DHT结构进行了一个简单的对比，在可靠性、出口节点负载、分组内部流量和查询效率方面，所提结构均优于传统分层结构。

3 结语

传统分层DHT结构以管理节点构成顶层，底层由各个分组构成。在此基础上，提出了具有多个管理节点(管理节点)的分层DHT模型。传统分层DHT结构在系统构建以及流量分析和查询效率上做了一定研究，但是忽略了对于多管理节点结构的相关研究。具有多出口分层DHT结构首先能够增加系统的可靠性，解决单点失效的问题，其次，多管理节点对于分组来说意味着有多个出口节点可以选择。研究提出具有多个管理节点的分层结构并分别从查询效率，负载流量和负载均衡3个方面进行了分析，进而提出了3种出口选择算法：最短路径出口选择算法、基于热土豆模型的最小化组内流量算法和出口节点负载均衡选择算法。

研究在不同实验条件下对3种算法进行了仿真分析。首先，将MIT_HP算法和SPSA算法与随机选择算法进行了对比分析，证明了所提出的2种算法在查询效率上要优于传统查询算法；其次，分析了MIT_HP算法和SPSA算法在性能上的差异；最后，对3种算法在负载流量和系统公平性做了分析对比。