Hash table & DHT

先附上定义：In computer science, a hash table, or a hash map, is a data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key (e.g. a person’s name), find the corresponding value (e.g. that person’s telephone number). 

从上述定义来看，hash表完成的主要功能是查找。 

举例说明：

假设某人爱好音乐，有N张CD。为了管理这些CD。此人设计了一个软件。该软件用HT实现查找，存储形式为数组array[N]。此人输入“SHE”，想得到的是和SHE相关的专辑放在什么位置，比如“第三层抽屉第一个CD包”

这里，关键字key是“SHE”，和关键字相关的value是“第三层抽屉第一个CD包” 

假设使用的hash函数为Fhash。

（1）Fhash(SHE)=1011   ；hash函数将key变换成一个值，通常是一个数字串

（2）1011对应的数组位置为array[10]，；确定了数字串的存储位置，完成了地址的定位。

（3）程序将array[10]中的结果返回。查找结束。

在DHT里面，某个nodeQ(0010)节点（上面的应用程序）查找“SHE”，和SHE相关的专辑放在什么位置（哪个机器上nodeP(?)）？也就是查询返回的value应该是“nodeX有SHE”

假设nodeQ的路由表只有以下3项。

nodeF1 <-> (0011)

nodeF2 <-> (0111)

nodeF3 <-> (1010)

nodeF3的路由表由以下两项

nodeF4 <-> (1011)

nodeF5 <-> (1100)

nodeF4上面存的信息是“node1（192.168.10.1）和node2（192.168.44.8）存有SHE”

注意。NodeF4并不等价于node1或者node2。它可能是其中某一个节点，也可能不是。

（1）Fhash(SHE)=1011   ；hash函数将key变换成一个值，通常是一个数字串

（2）nodeQ并不知道1011对应哪个节点。它按照距离最近的原则，将查询分组requestSHE（1011）发送给nodeF3

（3）nodeF3收到requestSHE（1011）后，查找自己的路由表，发现nodeF4的ID为1011，将查询分组转发给nodeF4

（4）nodeF4收到requestSHE（1011）后，查找自己的缓冲区（或者硬盘…），将“node1（192.168.10.1）和node2（192.168.44.8）存有SHE”作为reply发送给nodeQ。

（5）nodeQ收到reply，得到想要查找的信息，查找完成。

对比两个查找过程。

HT:  Fhash(SHE)->1011           ->a[10] ->“第三层抽屉第一个CD包”

DHT:Fhash(SHE)->1011->nodeF3 ->nodeF4 ->“node1（192.168.10.1）和node2（192.168.44.8）”

从上面的过程可以看到，Hash或者DHT提供的接口都是输入一个关键字，给出关键字对应的value，这个Value就是存储在DHT中的HT或者DHT用户（这个用户可能只是一个应用程序）所关心的信息。 

那么，为什么节点nodeQ没有ID（1011）对应的节点IP地址呢？

从查找效率上来说，如果nodeQ具有所有在线的节点的IP地址和节点ID的映射，每次查找都只需要一步就能完成。不需要其他节点转发查询消息。效率最高。但是，这在动态变化的DHT中是不可能做到的。因为存储那么多节点ID和IP的映射需要存储开销，更重要的是，要维护路由表的正确性，需要大量的通信开销。这是任何节点和链路都无法承受的。所以，每个节点都只能维护一部分路由表。至于节点选择维护多大一部分（how much），选择维护哪一部分（which），不同的DHT协议有不同的见解，基本上是在DHT网络的通信开销和查询效率上折中。 

那么，回到上次讨论的问题，路由表是不是hash表的一部分呢？

我自己的见解是，这个问题本身是不合适的。如果狭义的将hash表理解为就是静态的数组array[N]的地址，以及array[N]中所存的内容。那么路由表显然不是hash表。HT中Array[x]的地址是节点对应的ID，或者说，是Fhash(nodeX)所得到的值。array[x]中的下标x，对应的是节点的IP地址。而array[x]中保存的内容，是nodeX中保存的内容（或者是一部分内容）。 

但是，我所理解的HT，是一种完整的算法，包括查询在内。而DHT，则是这种算法的分布式实现。

所以，路由表是完成DHT查找功能的重要的一部分。是hash算法的分布式实现的重要的一部分。

Url排重Bloom Filter 算法、误差及其他

fly with me , in the perfect world — 题记

最近看了一些书，公式和算法，用一个词把他们窜起来的话，这就是：误差。说起误差，这让我想起了小时候的一个故事。小时候有个朋友他家在二级路旁开了家小商店。有一天客户拿着刚买的散装油对他说：分量不够。他告诉客户：这是误差。客户很生气说分量不够就是不够，怎么是误差？我这个朋友还真有办法，拉客户到隔壁，把油放到地秤上，说：你看把这壶油有放在地秤（称汽车的地称）上，地秤没显示，这就是误差。

小时候的事情，印象很深。

现在想起来，对误差的理解也更多了一些。不同的标准，不同的场合，不同的期望，这些通通构成了误差。可以说我们时时刻刻都被误差包围着。甚至在管理上，方兴东在博客上也总结说：对误差的极度容忍是一个管理者的必备素质。我自己也总结了一下：医学是对模糊的精确控制，管理是对精确的模糊管理。

我这里说说误差和效率的一点关系。误差和效率是一对矛盾共同体，生活中有对误差和效率的关系描述：“萝卜快了，不洗泥”；“慢工出细活”等等，都精辟的说出了误差和效率的辨证关系。对软件工程师来说，特别是编写算法的时候，对于“空间换时间”和“时间换空间”已经耳熟能详了；我想还应该加上一句：误差换效率。

误差换效率

google黑板报上一片文章，讲Url排重用到的一个技巧：把平均长度较长的Url转换成平均长度较短的GUID来节省空间。在Url排重方面还有一个常用的算法：Bloom Filter 算法。Bloom Filter 算法是查看元素E是否在集合S中存在的快速算法，典型的应用就是拼写检查spellcheck时，查看某个单词是否在字典中存在。关于查询的算法有很多种了，排序折半、B-Tree、Hash-Code 等等。Bloom Filter 的优点是什么呢？
1、Bloom Filter不存储key-value值，Bloom Filter 用一组Hash算法把集合S中的元素E换算成位表示；
2、查询速度快。

我们知道Hash算法一般都有冲突，在Bloom Filter中的冲突就表现为误差了。

Bloom Filter 是一种常见的算法，现在已经有了 Java , C++ , C# , ruby 等各个版本的算法。当然也有很多变种出现以适应更多的需求。
Bloom Filter 是有误差的，但误差在可控制的程度内。换句话说，大多数的误差的恼人之处在于我们无法衡量它。

参考阅读：

http://blog.likeshow.net/article.asp?id=34
http://blogs.msdn.com/devdev/archive/2006/01/23/516431.aspx
http://en.wikipedia.org/wiki/Type_I_and_type_II_errors
http://en.wikipedia.org/wiki/Bloom_filter
http://jaspell.sourceforge.net/javadocs/index-files/index-2.html
http://blogs.msdn.com/devdev/archive/2005/08/17/452827.aspx
http://www.cc.gatech.edu/fac/Pete.Manolios/research/bloom-filters-verification.html
http://homepages.inf.ed.ac.uk/s9902505/specksim/doc/index-files/index-2.html
http://weblogs.asp.net/dfindley/archive/2004/08/19/217485.aspx
http://www.darkridge.com/~jpr5/archive/dads/HTML/bloomFilter.html
http://loaf.cantbedone.org/

下面列举几个基于标准Bloom Filter的小技巧：

 

1.         求两个集合的并。假设有两个Bloom Filter分别表示集合S₁和S₂，它们位数组的大小相同且使用同一组哈希函数，那么要求表示S₁和S₂并集的Bloom Filter，只要将S₁和S₂的位数组进行“或”操作即可得到结果。

 

2.         将Bloom Filter“对折”。 如果想将一个Bloom Filter的大小缩小一半，那么只需将Bloom Filter的位数组分成两半进行“或”操作，得到的结果即为所求。在查找某一元素时，需要将哈希后的索引地址的最高位屏蔽掉。

 

3.         通过0的数目估计集合元素个数。在第一篇文章Bloom Filter概念和原理中，我们提到过：位数组中0的比例非常集中地分布在它的数学期望值m (1 - 1/m)^kn的附近，其中m为位数组的大小，k为哈希函数的个数，n为Bloom Filter所表示集合的元素个数。根据上式，知道了0的个数就可以很容易推断n的大小。

 

4.         通过内积估计集合交集元素个数。假设有两个Bloom Filter分别表示集合S₁和S₂，它们位数组的大小相同且使用同一组哈希函数，下面我们来看第i位在两个Bloom Filter同时被置为1的概率。要让某一位同时被置为1，只有两种可能：要么它是被S₁∩S₂中的元素设置的，要么分别是被S₁ – (S₁∩S₂)和S₂ - (S₁∩S₂)中的元素设置的。因此第i位在两个Bloom Filter同时被置为1的概率为：

|S|表示S中元素的个数，k表示哈希函数的个数，m表示位数组的大小。经过化简，再乘以m，得到两个位数组内积的数学期望值为：

如果不知道|S₁|和|S₂|，可以用3中的方法根据0的个数估计出它们的大小。最后，根据上式，我们在知道内积的情况下就可以很容易推断| S₁∩S₂|的大小。

 

5.         表示全集。很简单，将位数组设为全1就可以表示全集了，因为查找任何一个元素都会得到肯定的结果。

Compressed Bloom Filter

焦萌 2007年2月8日

 

在前面的讨论中，我们都只将Bloom Filter作为一种表示集合的数据结构。但在网络应用中，Bloom Filter经常被当作节点之间交换信息时传递的消息。从这个角度考虑，我们自然希望消息在传递之前能够被压缩。

 

那么Bloom Filter到底能不能被压缩？在Bloom Filter概念和原理一文中，我们知道当Bloom Filter的错误率最低时，位数组中任意一位是0的概率p = 1/2。也就是说，在错误率最低时位数组中0和1的概率各占一半。根据Claude Shannon 编码原理，位数组将不可能获得任何压缩的效果。

 

然而事实并不是这样，因为p = 1/2的结论是这样作出的：在已知位数组大小m和集合元素个数n的情况下，我们求出最优的哈希函数个数k，使得错误率降到最低。这样求出的k = (m/n) ln2，位数组中任意一位是0的概率p = 1/2。这个分析思路没有考虑压缩，而是把Bloom Filter作为一种内存中的数据结构，在分配的位数组大小固定的情况下求哈希函数个数的最优值。

 

从上面的分析可以看出，在不考虑压缩的情况下，Bloom Filter有三个重要的性能参数：错误率f、哈希函数个数k和位数组大小m。在引入压缩之后，性能参数变成了四个：错误率f、哈希函数个数k、未压缩的位数组大小m和压缩后的位数组大小z。在多了一个因素之后，整个分析的思路会大不一样，因此不能简单地延续前面的结论继续分析。

 

下面我们就分析一下引入压缩之后，如何选择各个性能参数以达到最优的结果。在不考虑压缩的情况下，我们考虑的问题是：给定m和n，求最优的k，使得f最小。在考虑压缩的情况下，压缩后的位数组大小z比压缩前的大小m更重要，因为它是我们实际在网络上传输的消息大小。基于这个原因，我们考虑的问题就变成了：给定z和n，求最优的k和m，使得f最小。

 

首先假设我们有一个最优的压缩算法，使得z = m H(p)，其中H(p) = -plog₂p – (1-p)log₂(1-p)是信息熵函数（p是位数组某一位为0的概率）。在Bloom Filter概念和原理一文中，我们知道p ≈ e^-kn/m，从而有k ≈ (-lnp) (m/n)。于是错误率f就可以写成p的函数

f = (1 - p)^k = (1 - p)^{(-lnp) (m/n)}

再将m = z / H(p)带入上式，可得

f = (1 - p)^{-(zlnp/nH(p))}

由于z和n固定，且z ≥ n，要求f的最小值，即求β = f^n/z的最小值。将H(p) = -plog₂p – (1-p)log₂(1-p)代入可得

要求β的最小值，即求指数的最小值，也等于求

的最大值。对上式求导，得

令dγ/dp = 0，得p = 1/2。并且可以发现当p < 1/2时dγ/dp小于0，当p > 1/2时dγ/dp大于0。因此当p = 1/2时γ取得最小值，即β和f取得最大值。这个结论非常有意思：当p = 1/2，即k = (ln2) (m/n)时，在不考虑压缩的情况下错误率最低，而在考虑压缩的情况下错误率反而最高。换句话说，压缩总是能够降低错误率。

 

由于压缩总能降低错误率，因此对比标准的Bloom Filter，Compressed Bloom Filter性能更加出色。而且由于Compressed Bloom Filter增加了一个性能参数，它在各个性能参数的权衡上更加灵活。例如，用同样的位数表示集合元素，Compressed Bloom Filter的错误率更低，所用的哈希函数个数更少：

上表中的第一列就是标准的Bloom Filter，没有压缩（m/n = z/n），每一个元素用8位表示。后两列是经过压缩的Bloom Filter，同样每一个元素用接近8位表示，但用的哈希函数个数更少，错误率更低。又例如，达到同样的错误率，Compressed Bloom Filter每一个元素所占位数更少，哈希函数个数也更少：

 

总之，在网络应用环境下，按( m/ n) ln2选择最优k 值不会获得任何的传输压缩率。相反，若增大本地节点表示信息的位数和选择较小的k值，不仅可以获得好的传输压缩率同时还能获得更小的错误率。

 

参考论文：Compressed Bloom Filters

ppPhone—基于Kademlia协议的P2P VoIP系统设计与实现

dolf cao(dolf.cao@gmail.com)

摘 要：点对点（P2P）技术和基于IP的语音VoIP（Voice Over IP）技术是当前Internet应用技术研究的两个热点，将二者相结合的P2P VoIP技术已经成为VoIP技术发展的一个趋势。本文从分析传统VoIP系统的不足入手，讨论了未来VoIP系统的发展趋势，提出了一种基于Kademlia协议的纯P2P的P2P VoIP架构，并在此基础上实现了一个P2P VoIP系统——ppPhone。

关键词：Kademlia；DHT；P2P VoIP；G.729；对等网；分布式哈希表

ppPhone—A Kademlia Based P2P VoIP System Design And Implementation

dolf cao(dolf.cao@gmail.com)

Abstract：Peer-to-Peer and Voice Over IP are the research hotspot in current Internet application technology. P2P VoIP Technology that combine the P2P and VoIP is a trend of VoIP development. This paper analysis the shortage of current P2P VoIP systems at first, then discuss the development trend of future VoIP system, and based on previous analysis, we put forward a kademlia protocol based pure P2P VoIP architecture, then we implement our kademlia based P2P VoIP system—ppPhone.

Key words：Kademlia；DHT；P2P VoIP;G.729
 

1 引言

点对点P2P（peer to peer）技术和基于IP的语音VoIP(Voice Over IP) 技术是当前互联网应用技术研究的两个热点。最近几年发展起来的P2PVoIP系统更是这两种技术融合后的一个重要发展方向。它通过利用P2P技术的高扩展性和健壮性的特点，给传统VoIP产业带来了更高效的沟通模式。P2P VoIP系统是指将P2P技术与VoIP技术相结合,P2P技术用于资源的查找定位及共享,来共同完成语音通信过程的系统。

当前，以Skype为代表的P2P VoIP系统发展迅速,已经成为人们日常生活中不可或缺的一种重要的联系手段。另外,诸如HeadCall， Gizmo， WengoPhone等P2P VoIP系统也拥有广大的用户群。相对于传统的C/S模式的VoIP系统，P2P VoIP系统具有稳定性好、部署简单及易用性好等优点；就目前的发展趋势来说，传统VoIP系统正逐渐的向基于P2P技术的方向发展。

但是由于目前的P2P VoIP系统多为商用系统，其核心技术是私有的，没有公开，而且多为国外系统，并且当前的P2P VoIP系统还有许多问题需要解决，因此有必要研究P2P VoIP系统，尤其是考虑到军队等国家重要部门的特殊性，更有必要研究自己的P2P VoIP系统。

Kademlia协议是一个广泛应用的基于分布式哈希表（DHT）的P2P协议，当前的许多P2P文件共享软件如Emule，BitTorrent，BitSprit，BitComet等都使用Kadmelia协议来实现底层的网络拓扑。协议的广泛应用证明，Kademlia协议是一个简单高效的P2P协议。

目前较成熟的适用于VoIP系统的P2P协议主要有Chord，Pastry，Tapestry，CAN和Kademlia。相比较于另外四种协议，Kademlia协议具有实现简单、查找效率高、资源定位准确以及更加成熟等优点，因此我们选用Kademlia协议作为底层协议来实现P2P VoIP系统——ppPhone。
 

2 Kademlia协议简介

P2P技术按照节点信息存储与搜索方式的不同，主要分为非结构化和结构化的P2P。

非结构化P2P系统中，每个节点存储自身的信息或信息的索引(如指针和IP地址)。当用户需要在P2P系统中获取信息时，他们预先并不知道这些信息(如某个文件)会在那个节点上存储。因此，在非结构化P2P系统中，信息搜索的算法难免带有一定的盲目性，例如最简单的泛洪式查找(类似于广播)和扩展环查找(从最近的n个节点开始，层层转发直到找到目标或超出了跳数的上限为止)。典型的非结构化P2P系统主要有：Gnutella，Napster等。非结构化系统的优点在于实现结构简单：无须中央服务器，节点之间完全平等，网络的层次是单一的，而且节点之间无需维护拓扑信息。

结构化P2P系统中，每个节点只存储特定的信息或特定信息的索引。当用户需要在P2P系统中获取信息时，他们必须知道这些信息(或索引)可能存在于那些节点中。由于用户预先知道应该搜索哪些节点，避免了非结构化P2P系统中使用的泛洪式查找，因此提高了信息搜索的效率。但是，结构化P2P也引入了新的问题：

首先，既然信息是分布存储的，那么如何将信息分布存储在重叠网中的节点上。

其次，由于节点动态的加入和离开重叠网，如何将拓扑的变更信息通知其它节点。

DHT（分布式哈希表）的引入基本解决了上述问题，因此自从DHT协议出现以后，结构化P2P的应用得到了快速的发展。目前已经有很多较为成熟的DHT协议被提出并且得到了应用。其中比较有代表性的有：缓冲阵列路由协议(CARP)；一致性哈希；Chord；内容寻址网络（CAN）；Pastry；Kademlia；P-Grid。

2.1 DHT

DHT（Distributed Hash Table），分布式哈希表技术使用分布式哈希算法来解决结构化的分布式存储问题。分布式哈希算法的核心思想是通过将存储对象的特征(关键字)经过哈希运算，得到键值(Hash Key)，对象的分布存储依据键值来进行。在不需要服务器的情况下，每个客户端负责一个小范围的路由，并负责存储一小部分数据，从而实现整个DHT网络的寻址和存储。

DHT能够容纳数量巨大的节点数目，并且能不断处理新加入的节点，同时能够妥善地处理节点离开，具有很好的容错性。

将DHT作为应用层拓扑，可以构建更加复杂的应用，例如分布式文件系统，点对点文件共享，内容分发系统，协同web缓存，应用层组播，分布式域名解析以及即时消息服务。

2.2 Kademlia协议

Kademlia协议是美国纽约大学的PetarP. Maymounkov和David Mazieres在2002年发布的一项研究结果《Kademlia: A peerto -peer information system based on the XOR metric》。Kademlia通过独特的以异或算法（XOR）为距离度量基础，建立了一种全新的DHT 拓扑结构，能够以比较快的速度执行路由查询。

Kademlia协议的每个节点保持一个哈希值、关键字对，并且将这个对保存在DHT中若干距节点逻辑距离在一定范围内的最“近”的节点上。

异或运算提供了一种在Kad网络上进行可靠距离度量的方法。由于异或运算的非负性、对称性、单向性、传递性以及三角不等性，从而能够保证距离与节点的一一对应的特性。

Kademlia协议实现了K-Bucket来实现节点查询。K-Bucket中保存以用户ID哈希值、对方IP地址和对方UDP端口这样的数据结构为单元的列表，列表首部保存最近最少访问的节点，尾部是最近最多访问的节点。当DHT接收到新节点加入请求时，如果此时K-Bucket没有满，那么就把新节点加入尾部；如果此时K-Bucket已经满了，就先对首部的节点发送消息，手部节点有响应的话那么忽略新节点加入请求，同时把首部有反馈的节点移动到尾部，如果首部节点没有反馈，则删除就删除尾部节点，加入新节点。这种新节点加入的处理方式能够很好的解决拒绝服务攻击，即使有很多节点同时到达要求加入网络，K-Bucket用自己的更新机制处理节点加入请求，而不会过载，从而避免了拒绝服务攻击的影响。

Kademlia协议定义了四种远程RPC 操作：PING、STORE、FIND_NODE、FIND_VALUE。

PING 操作的作用是探测一个节点，用以判断其是否仍然在线。

STORE 操作的作用是通知一个节点存储一个<key , value>对。

FIND_NODE 操作使用一个160bit 的ID 作为参数。本操作的接受者返回它所知道的更接近目标ID 的K 个节点的(IP address ,UDP port , Node ID)信息。

FIND_VALUE 操作和FIND_NODE 操作类似，不同的是它只需要返回一个节点的( IP address , UDP port , Node ID)信息。如果本操作的接受者收到同一个key 的STORE 操作，则会直接返回存储的value 值。

采用Kademlia协议实现P2P VoIP系统是一个尝试，因为现在比较成型的P2P VoIP系统如Skype等P2P协议是私有的，而且下一小节将会介绍到Kademlia协议当前的应用，证明Kademlia协议是一个成熟的协议，用于P2P VoIP系统能避免许多不成熟的协议可能遇到的问题。

2.3 Kademlia协议应用

Kademlia协议应用范围较广，主要是P2P文件共享程序底层使用Kademlia协议来搭建Overlay，实现资源的存储、搜索和定位。

采用Kademlia协议实现的P2P文件共享程序主要有Emule，BitTorrent，BitSiprit，BitComet等。经过实践证明Kademlia协议是简单可靠的。目前Internet上大约有一半的网络流量为P2P流量，其中大部分为P2P文件共享程序产生的流量，而目前Emule，BitTorrent，BitSprit，BitComet都是很流行的P2P文件共享软件，因此可以不夸张地说，采用Kademlia协议的网络产生的流量占了很大一块Internet的流量。
 

3 ppPhone系统设计

3.1 ppPhone功能需求

ppPhone作为一个VoIP系统，应能实现以下功能：

l 新用户注册：系统注册新用户以及新用户加入网络；

l 用户退出：用户退出网络；

l 用户发布：在用户注册了一个用户名之后，将用户名及用户相关信息（IP地址及端口）发布到DHT中逻辑距离相近的节点上。

l 用户检索：给定一个用户名，将用户名哈希后，在DHT中查找到用户相关信息（IP地址及端口），并且将用户相关信息（IP地址及端口）返回。

l 语音通信：根据查找得到的用户相关信息（IP地址及端口），建立起语音通信信道，并且实现语音呼叫信令及语音编解码（采用G.729）。

l NAT及防火墙穿越：当用户处于内网或者防火墙之后时，提供一种用户穿越NAT和防火墙的方法。

l 与传统电话网及移动电话网互联互通：通过公共交换电信网（PSTN）与传统电信网实现互联，从而使得用户可以呼叫传统电话以及移动电话。

3.2 系统设计

系统主要概念和术语定义如下：

l 用户：ppPhone的终端实体，拥有唯一用户名、密码、姓名、年龄、性别、好友列表等属性。

l 结点：用户的载体，是连接到P2P网络的个人PC。

l 引导结点：一个P2P网络结点，为要加入P2P网络的结点提供一些联系人组成它的路由表。

l 注册服务器：为用户提供注册和认证功能，存储用户的用户名、密码、好友列表等信息，用户登录时对用户进行身份认证。注册服务器还保证用户名的全球唯一性。

l PSTN服务器：提供ppPhone网络节点与传统电话网及移动电话网通信的接口。

3.2.1 系统体系结构

在ppPhone中，所有的节点共同组成Overlay，注册（认证）服务器主要用于新用户的注册以及用户登录时的验证。用户通过PSTN服务器与传统电话网及移动电话网进行通信。ppPhone的体系结构不同于Skype，ppPhone中并没有超级节点（Super Node），所有的节点是完全对等的，实现完全相同的功能。因此ppPhone是一个纯P2P的VoIP系统。ppPhone系统体系结构如图1所示。

图1 ppPhone系统体系结构

3.2.2 系统模块设计

ppPhone系统主要包括用户界面、DHT模块、语音通信模块、注册服务器以及Bootstrap服务器共5个模块。系统模块与功能设计如图2所示。

图2 ppPhone系统模块图
 

4 ppPhone系统实现

基于上述设计，我们实现了ppPhone的原型系统，其中与传统电话网及移动电话网互联的部分由于条件限制还未能实现，其余各个功能均实现，系统运行良好，用户定位准确及时，语音通信质量较好。

4.1 系统平台

ppPhone在Windows XP上使用Visual Studio 2005开发，程序设计语言为C++，P2P模块基于Kademlia协议实现，语音编解码使用G.729的Codec，通信信令为自定义的信令。

4.2 系统具体实现

ppPhone流程主要有注册/认证、加入Kad网、发布用户ID、查找用户ID，呼叫的建立和释放、语音传输等。系统流程如图3所示。

图3 ppPhone系统流程图

用户在第一次启动时需到注册服务器注册，注册自己的用户名ID，密码等信息；若已注册，直接登录，到注册服务器进行身份认证。用户客户端注册/认证完毕后就可以加入Kad网，首先设置本地TCP、UDP端口，设置引导结点IP地址、端口号，然后就可以调用Kademlia协议模块加入DHT网络。用户节点在加入DHT网络时向整个网络发布用户ID，首先哈希用户ID，然后进行异或运算搜索与用户ID逻辑距离最近的一些结点，把用户ID，及所在的结点IP地址等信息存储到上面。为了保证这些结点的存活性和适应不断变化的网络拓扑结构，用户节点需要周期性的刷新发布信息。当用户节点试图呼叫某个用户时，需要在DHT网络上搜索该用户ID，找到该用户ID的发布信息，从而得到该用户ID所在结点的IP地址及端口号，即可建立语音通信信道。一旦用户查找到要呼叫的终端IP地址，就可以根据特定的信令协议向其发出呼叫请求，并随时可以终止呼叫。当呼叫建立后，语音数据就可以在两个终端间传送。

ppPhone系统主要有3个线程，其中一个DHT网络控制线程，一个DHT网络信息更新线程以及一个语音通信线程。网络底层通信链路Berkeley套接字。DHT网络控制线程初始化时，首先在端口20028开一个Listen Socket，不断侦听，在接受到DHT网络的数据包时进行处理；只要系统继续运行，此线程即一直在运行，不会退出。DHT网络信息更新线程是一个定时器，主要用于确认节点是否在线，此线程会周期性的向K-Bucket中的节点发送PING消息，没有响应的节点会被认为已经失效，从而保证K-Bucket中节点的有效性，当用户因为意外原因离开网络后，此线程也能及时发现。语音通信线程主要用于信令的传输以及语音数据的发送和接收。

5 总结

本文阐述了一个基于Kademlia协议的P2P VoIP系统的实现过程，初步实现了VoIP系统的功能；使用P2P来完成用户的查找与定位，能够有效的避免集中式服务器诸如单点故障等问题，并且能够以较好的速度来完成用户的查找和定位。相比较于传统的VoIP系统，P2P VoIP系统不需要配置即零配置、运营成本低、系统可靠性高，但是又有不便于管理等特点。在运营成本受限或者部署较大规模的VoIP系统时，P2P VoIP系统是一个很好的选择。
 

参考文献

【1】 Kademlia : A Peer-to-peer Information System Based on the XOR Metric. PetarP. Maymounkov, David Mazieres.

【2】 开源P2P文件共享项目BitTorrent www.bittorrent.com

【3】 开源P2P文件共享项目 Emule www.emule-project.net

【4】 开源P2P文件共享项目 BitSpirit http://www.bitspirit.com.cn/

【5】 开源P2P文件共享项目 BitComet www.bitcomet.com

【6】 基于混合结构P2P技术的IP电话软件原型与实现 汪亮宇硕士论文 北京航空航天大学

【7】 Skype www.skype.com

【8】 采用G.729的语言实时通信DLL(含测试源代码)

http://www.newasp.net/code/vc/2407.html

【9】 NetTalk http://nettalk.nwtbb.com/

【10】 Emule中Kademlia网络深入解析

http://dolfcao.spaces.live.com/

【11】 ppPhone系统实现 http://sourceforge.net/projects/ppphone