史建焘，张宏莉

（哈尔滨工业大学计算机网络与信息安全技术研究中心 哈尔滨150001）

1 引言

分布式散列表(distributed Hash tables,DHT)技术的出现扩展了对等网络用户的规模，彻底释放了用户的共享下载需求。相比之前的P2P网络，DHT网络具有可扩展性好、可靠性高等优点，但是网络节点的异构性也给这一技术的发展提出了许多挑战。作为为数不多的在实际环境下实现的DHT系统，利用Kademlia协议[1]的eMule软件的KAD网络已经拥有了数以百万的用户群，在Internet上产生了一定的影响。KAD协议是基于二进制异或运算（XOR）度量距离的DHT协议，每个KAD节点拥有一个128位的唯一标识，所有节点构成一个二叉树结构。通过若干操作实现对数据项映射的存储和获取。一个健壮的DHT系统中，不同节点应该以很高的概率分配到相同数量的目标对象，从而保证系统的高可靠性和容错性。然而，由于应用环境的特殊性和网络节点的异构性，实际系统中并没有真正实现节点间负载的均衡性，KAD网络同样如此。本文通过测量实验发现由于关键词使用频率的差异，导致KAD网络中以关键词作为键值的文件索引负载在不同节点上的分配是不均衡的，这严重限制了KAD网络的扩展性和可用性。如何提高KAD网络这方面的负载均衡性是本文的研究重点。

负载均衡作为DHT系统重要的性能评价指标已经成为了当前研究的热点，大多数研究工作都是以ID空间作为研究对象的[2]。认为理想状态下，DHT系统的负载均衡是指每个节点负责管理的ID空间应该根据其软硬件承载能力按比例分配。……