第１８卷 Ｖ０１．１８ 第２期 Ｎｏ．２ 电子设计工程 Ｅｌｅｃｔｒｏｎｉｃ Ｄｅｓｉｇｎ Ｅｎｇｉｎｅｅｒｉｎｇ ２０１０年２月 Ｆｅｂ．２０１０
Ｋａｄｅｍｌｉａ协议的分析与改进
张齐．劳炽元
（华南理工大学计算机科学与工程学院，广东广州５１０００６）
摘要：针对Ｋａｄｅｍｌｉａ协议存在的路由表更新迟缓、负载失衡和网络拓扑失配的缺陷，提出一种基于节点综合性能的
Ｋ桶（Ｋ—ｂｕｃｋｅｔ）构建方法，以改进Ｋａｄｅｍｌｉａ协议的性能。并通过模拟实验，证明了在恰当的更新策略下该方法的有
效性。
关键词：对等网（Ｐ２Ｐ）；Ｋａｄｅｎｄｉａ协议；Ｋ桶；负载失衡；拓扑失配；综合性能 中图分类号：ＴＰ３９３．０ 文献标识码：Ａ 文章编号：１６７４—６２３６（２０１０）０２—０１２５—０３
Ａｎａｌｙｓｉｓ ａｎｄ ｉｍｐｒｏｖｅｍｅｎｔ ｏｆ Ｋａｄｅｍｌｉａ ｐｒｏｔｏｃｏｌ
ＺＨＡＮＧ Ｑｉ，ＬＡＯ Ｃｈｉ—ｙｕａｎ
（Ｓｃｈｏｏｌ ｏｆＣｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｏｕｔｈ Ｃｈｉｎａ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＴｅｃｈｎｏｌｏｇｙ，Ｇｕａｎｇｚｈｏｕ ５１０００６，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇ ａｔ ｔｈｅ ｄｅｆｅｃｔｓ ｓｕｃｈ ａｓ ｒｏｕｔｉｎｇ ｔａｂｌｅ ｕｐｄａｔｅ ｄｅｌａｙ，ｌｏａｄ ｉｍｂａｌａｎｃｅ，ｎｅｔｗｏｒｋ ｔｏｐｏｌｏｇｙ ｍｉｓｍａｔｃｈ ｅｘｉｓｔｉｎｇ ｉｎ
Ｋａｄｅｍｌｉａ ｐｒｏｔｏｃｏｌ，ａ Ｋ—ｂｕｃｋｅｔ ｃｏｎｓｔｒｕｃｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｔｈｅ ｎｏｄｅ’Ｓ ｃｏｍｐｒｅｈｅｎｓｉｖｅ ｐｅｒｆｏｒｍａｎｃｅ ｉｓ ｐｒｅｓｅｎｔｅｄ ｉｎ ｔｈｉｓ
ｐａｐｅｒ，ｉｎ ｏｒｄｅｒ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ Ｋａｄｅｍｌｉａ ｐｒｏｔｏｃｏ１．Ｗｉｔｈ ａｎ ａｐｐｒｏｐｒｉａｔｅ ｕｐｄａｔｅ ｓｔｒａｔｅｇｙ，ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ
ｔｈｉｓ ｍｅｔｈｏｄ ｉｓ ｐｒｏｖｅｄ ｂｙ ｓｉｍｕｌａｔｉｏｎ．
Ｋｅｙ ｗｏｒｄｓ：ｐｅｅｒ—ｔｏ—ｐｅｅｒ（Ｐ２Ｐ）；Ｋａｄｅｎｄｉａ ｐｒｏｔｏｃｏｌ；Ｋ—ｂｕｃｋｅｔ；ｌｏａｄ ｉｍｂａｌａｎｃｅ；ｔｏｐｏｌｏｇｙ ｍｉｓｍａｔｃｈ；ｃｏｍｐｒｅｈｅｎｓｉｖｅ ｐｅｒ－ ｆｏｒｍａｎｃｅｓ
Ｋａｄｅｍｌｉａ是一种典型的结构化对等网Ｐ２Ｐ（Ｐｅｅｒ．ｔｏ—Ｐｅｅｒ）
协议，该协议以分布式的应用层全网方式存储和检索信息…。
在众多Ｐ２Ｐ协议中，Ｋａｄｅｍｌｉａ是应用最为广泛、原理和实现
最为实用和简清的一种。当前主流的Ｐ２Ｐ软件（如ｅＭｕｌｅ、
Ｂｉｔｃｏｍｅｔ、Ｂｉｔｓｐｉｒｉｔ和Ａｚｕｒｅｕｓ等）都采用Ｋａｄｅｍｌｉａ作为其辅助 检索协议
但随着Ｐ２Ｐ应用规模的不断增长，Ｐ２Ｐ用户急剧增加，
Ｋａｄｅｍｌｉａ协议同有的缺陷就越显突 ．如节点负载失衡、Ｋ桶 （Ｋ—ｂｕｃｋｅｔ）更新迟缓以及逻辑拓扑与物理拓扑失配等。为了
适应Ｐ２Ｐ应用规模的不断增长．改善Ｋａｄｅｍｌｉａ协议的性能．
本文将对Ｋａｄｅｍｌｉａ协议进行分析并提出相应的优化策略。
１ Ｋａｄｅｍｌｉａ协议的缺陷
１．１ Ｋ桶更新迟缓 在Ｋａｄｅｍｌｉａ覆盖网中，每个节点都保存有一些其他节点
的位置信息，以便本地节点进行寻址查询。根据Ｋａｄｅｍｌｉａ协
议的规定，这些位置信息一般由ＩＰ地址、ＵＤＰ端口．节点ＩＤ
等数据组成，并分为１６０个组。用单链表将组内节点连接起
来，组成一个Ｋ桶。每个Ｋ桶有至多ｋ个位置信息，这些位置
信息所代表的节点与本地节点的距离（异或距离）都在同一
个范围内。比如第ｉ个Ｋ桶只保存与本地节点相距［２‘，２ｉ＋１】范
围内的节点信息。Ｋ桶的逻辑结构如图ｌ所示。
一般来说，当ｉ值很小时，Ｋ桶通常是空的（即无足够多
收稿日期：２００９—０８—３１ 稿件编号：２０ＨＤ９０８０７ｌ ｋ－ｂｕｃｋｅ ｔ【０］ ｋ－ｂｕｃｋｅｔ【１］ ｋ－ｂｕｃｋｅｔ［２］
ｋ－ｂｕｃｋｅｔ［ｉ１ Ｅ ．｛＝三 …．Ｅ日．｛＝三 ｎｕＩ １ ■ 距离：ｆ１，２） 距离：【２，４）
距离：【４，８）
距离：【２ ，２ ）
ｋ－ｂｕｃｋｅｔ ｆｌ ５９】 日 三｜卜．［三 …・ 日．＿［三 ｎ１．１ｌＩ距离： ，２ ） Ｌｅａｓ ｔ—Ｒｅｃｅｎｔ ｌｙ Ｍｏｓ ｔ—Ｒｅｃｅｎｔ ｌｙ
图１ Ｋ桶的逻辑结构 的节点，比如当 ０时，该Ｋ桶只能保存ｌ项）；而当ｉ值很大
时，其对应Ｋ桶的项数又很可能超过ｋ个。这里参数ｋ是为
平衡系统性能和网络负载而设置的一个常数．但必须是偶
数，比如在ＢｉｔＴｏｒｒｅｎｔ的实现中，ｋ取值为８ 。
在标准Ｋａｄｅｍｌｉａ协议中，Ｋ桶的更新比较迟缓。假设有
３个节点Ａ、Ｂ、Ｃ，只要节点Ｂ持续在线，则无论其计算性能
和网络带宽如何低劣，节点Ｂ的信息将一直保存在节点Ａ的
某个Ｋ桶里。而对于性能和带宽都更佳的节点Ｃ，却只有代
表Ａ、Ｃ距离的那个Ｋ桶没有填满ｋ个节点信息时．才能填 上节点Ｃ的信息。
将在线时间长的节点留在Ｋ桶可增加Ｋ桶中的节点在
下一时间段仍然在线的概率．提高网络的稳定性并减少网络
维护成本（无需频繁更新节点的Ｋ桶）。此外，这种机制能在
一定程度上防御ＤＯＳ攻击。因为只有当原来的节点失效后．
本地节点才会更新Ｋ桶的信息．从而避免由于新节点的加入 而泛洪路由信息【 。但这种机制不及时更新Ｋ桶。将性能和带
作者简介：张齐（１９６３一），男，山西太原人，硕士，副教授。研究方向：智能控制、嵌入式网络系统、信息处理。
．．１２５－
日 电子设计工程）２０１０年第２期
宽更佳的节点拒于门外，不利于提升Ｋａｄｅｍｌｉａ的搜索效率和
降低等待时间。随着Ｋａｄｅｍｌｉａ用户增加，共享的数据、文件更
多。这种缺陷会更加明显。
１．２节点的负载失衡
Ｋａｄｅｍｌｉａ协议基于如下假设：所有节点的能力是相当
的；资源在覆盖网中的分布是随机的、均匀的；所有节点都可
以和其他任何节点连接。而在实际情况中，各节点的计算能
力、通信带宽和活动时间都是极端异构的。平等看待各节点 的能力将会导致节点负载失衡．造成网络的性能瓶颈Ｉ 。同样
数量的请求包，带宽大的节点可以轻松应对，但会造成带宽
浪费：而对于带宽较小的节点，则会造成网络堵塞。
对等网（Ｐ２Ｐ）指各节点地位平等而不是能力相同圈。通常
引入超级节点（Ｓｕｐｅｒ ｎｏｄｅ）概念以区分系统中的节点，使计 算能力强、存储容量大、高带宽、低延迟的节点成为超级节
点，充当一个区域的服务器，而性能较差的节点作为叶子节
点１４１，如图２所示。但这种策略需要一种复杂的算法来处理超
级节点的选择、退出、失效和其他异常情况，因此会增加系统
的额外开销。
●普通主机终端（ｓｃＪ ●超级节点（ｓＮ）
图２混合拓扑结构
１．３网络拓扑失配 Ｋａｄｅｍｌｉａ协议是利用ＩＰ网络上的一个覆盖网络实现寻
址的。覆盖网络只是一个采用分布式哈希表（ＤＨＴ）构建的逻
辑概念上的网络。相当于应用层协议。覆盖网络通过哈希值
决定网络中资源的映射位置，这种方式可提高系统可扩展性
和资源定位速度。而覆盖网络的寻址是建立在逻辑概念上
的，由覆盖网络中的逻辑跳（ｈｏｐ）￣１成，根据各节点保存的路 由信息选择一条逻辑跳数（ｈｏｐｓ）最少的路径作为最优路径。
由于覆盖网络并未过多考虑底层物理拓扑结构．因而会造成
逻辑拓扑与物理拓扑失配。覆盖网络中逻辑最近的２个节点 往往在物理层并不是最近，因此造成很多不必要的路由．降
低了资源定位效率Ｉ５１。
针对网络拓扑失配．当前的一种解决方法是地理布局
（ｇｅｏｇｒａｐｈｉｃ ｌａｙｏｕｔ）。该方法是利用收集的邻居信息（物理位
置）决定本地节点的逻辑位置．使得在逻辑空间相邻的２个
节点在物理层也相近旧。但这种方法同时会导致节点在逻辑 空间分布不均，加重负载的不均衡性。另外，这种策略使得邻
居节点只能保存在前几个Ｋ桶里，则本地节点搜索某些关键
字（该关键字经哈希转换后与本地节点的ＩＤ相似）速度很
快。而大部分关键字的搜索速度都比较慢。
－１２６－ ２泛洪搜集邻居节点
采用Ｋａｄｅｍｌｉａ协议原有策略构建覆盖网，即使用一致性
哈希函数（ｃｏｎｓｉｓｔｅｎｔ Ｈａｓｈ ｆｕｎｃｔｉｏｎ）将数据和节点都均匀映射
到一个逻辑空间，使性能优良的节点均匀分布于１６０个Ｋ
桶，从而避免搜索性能的不均匀。另外，为了降低网络拓扑失 配造成的影响，提高系统的搜索性能，本文的改进策略是对
邻居节点作 丌Ｌ一３（３个物理跳数范围内）泛洪，找出所有
１ＴｒＬ一３邻居节点并把它们加入Ｋ桶里（邻居节点也均匀分布
在１６０个Ｋ桶里）。对新节点进行１ＴｒＬ一３泛洪操作也可使老
节点在泛洪中了解到有新邻居产生，并及时更新其Ｋ桶。
３基于节点综合性能的Ｋ桶
３．１节点的综合性能１３１
在负载平衡方面，考虑到节点的异构性，本文从节点的
计算能力、存储能力、网络带宽、在线时间、物理跳数ＴｒＬ
（Ｔｉｍｅ Ｔｏ Ｌｉｖｅ）等因素量化出节点综合性能，综合性能高的节
点将承担更多的访问负载，存储和提供更多信息。这里
提出模型Ｃ￣ｆ（Ｍ，Ｕ，Ｂ， ， ）来计算节点的综合性能，其中
Ｃ是综合性能的量化值，∞是常数， 为存储能力，Ｕ为计算
能力，Ｂ为带宽， 为在线时间， 为消息传递所消耗的物理 跳数。 厂（肘， ，曰， ， ）根据节点各方面的性能计算出一个数 值，该数值越大则表示综合性能越高。
３．２调整后Ｋ桶的结构
为了依据节点的综合性能来选择下一跳节点。本文对Ｋ
桶的结构进行调整。首先，为Ｋ桶中每个结点都增加一个综 合性能成员数据。然后将所有结点按照综合性能从高到低排
序。并将Ｋ桶头结点的结构体修改如下：
ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ ｆ
ｄｏｕｂｌｅ ｓｕｍ；
能值总和
ｄｏｕｂｌｅ ｒａｉｎ；
ｉｎｔ ｃｏｕｎｔ： ｎｏｄｅ￣ｎｅｘｔ；
｝Ｈｅａｄ； ／／ｓｕｍ记录当前Ｋ桶里所有结点的综合性
／／ｍｉｎ记录当前Ｋ桶里最小的综合性能值
／／ｃｏｕｎｔ记录当前Ｋ桶已保存的节点数 ／／ｎｅｘｔ是指向下一个结点的指针
３．３节点的选择
为避免每次搜索都集中在少数几个综合性能优异的节
点上，造成节点负载过重，这里是根据概率随机选择节点。这 样虽然综合性能高的节点被选中的概率高。但不会每次都被
选中，从而在一定程度上避免了系统热点（Ｈｏｔ Ｐｏｔ）的产生。 根据概率选择节点的步骤如下：首先把各个节点的综合
性能值在数轴上相叠加．如图３所示。则某节点综合性能值
越大，该节点在数轴上占据的长度就越长：然后利用随机函
数ｒａｎｄ（）所产生的随机数是均匀分布的。令ｃｈｏｏｓｅ＝ｓｕｍｘ
ｒａｎｄ（），看ｃｈｏｏｓｅ落在哪个区间内就选择其对应的节点。比 如Ｃ￣＜ｃｈｏｏｓｅ＜ ＋Ｃｂ，这样ｃｈｏｏｓ
ｅ就落在第２个区间内，于是