广西大学
硕士学位论文
基于博弈论的P2P服务质量差异激励模型的研究
姓名：
陈志琦
申请学位级别：
硕士
专业：
计算机应用技术
指导教师：
苏德富

        P2P网络是一种自组织、没有中央职权和基础设施的分布式系统，因为其参与的自发性和自治性，使P2P网络中资源的可用性有着极高的变数和不可预知性。且实际应用中，由于大多数自主的参与者因缺乏激励而不共享资源，传统的P2P系统(比如Napster, Gnutella等)广泛地出现Free-Riding问题，严重阻碍了P2P技术和应用的发展。由此引发了许多关于P2P激励机制方面的理论研究课题和商业计划。本文在对近年来使用经济学模型分配分布式系统资源的相关研究进行分析比较的基础上，借用经济学中的博弈均衡理论，提出一种基于服务质量差异的激励模型来提高P2P系统性能和效率。
本课题研究的主要内容包括以下几个方面:
一、 研究P2P网络底层架构，以Gnutella为原型，引入对等网专用
设备(Peer Server)，为激励模型提供良好的底层网络平台。
二、 构建对等网文件共享系统的激励机制。这一部分首先分析了P2P网络中参与者之间对网络资源的竞争关系，并在非合作博弈Nash均衡理论框架下构造一个基于服务质量(QoS)差异的P2P激励模型。然后在改进后对等网络底层模型上，通过仿真实验分析激励机制下不同性质的用户采取不同策略时的均衡状态。
三、 借用分布式微观经济理论，将网络资源系统看成是一个价格随供求关系浮动的竞争市场，网络用户需要购买网络资源以满足个人的服务质量(QoS)。利用Flow Control技术模拟网络资源的分配优化过程，给出其仿真试验的测试结果及评价。
关键词:对等网 描述符 博弈论 纳什均衡 服务质量
  P2P网络资源的特性：
l  异构性
l  动态性
l  自治性
Free-Riding问题
指用户只下载而不愿意上传文件的问题。Free-Riding定义为一个自私的个体有意识地拒绝为某个群体的共同利益自愿地贡献。
  由此引 发 了许多关于P2P激励机制方面的理论研究课题和商业计划，提出P2P激励模型，向系统贡献资源的用户能从网络中得到相应的回报，激励用户共享资源以消除Free-Riding现象。目前比较普遍应用的两种激励模式是支付虚拟/真实的货币(Micro Currency)和提供差异服务质量(QoS)。
而在服务质量模式下运用经济学中的市场经济理论来解决P2P的分配问题己成为众多研究者所探讨的一个重要方向。在经济学模型中，资源代理被分为生产者和消费者两类。生产者的目标是获取最大的利益，而消费者的目标则是在自己的一些约束条件下(例如完成时间、预算等)获取尽可能多且好的资源来满足自己的需求。这两者之间的动态关系就可以使用己经充分研究、具有高度可扩展性的经济学模型来进行描述。对于将一些基本的经济学理论引入到分布式系统的资源管理中主要着重于将具体的资源管理场景抽象成数学模型，然后依据基本的经济学理论，例如一般均衡理论、Nash均衡、边际效用、用户偏好等，进行分析和模拟。
网络服务质量(Quality Of Service，简称QoS)定义为网络于用户之间以及网络上互相通信的用户之间关于信息传输与共享的质的约定。即指能够提供持续的、可预测的数据递交服务，满足用户需求。QOS要求应用、主机、网关等互相协调，网络各层自上而下以及从发送方到接收方沿途每个网络要素都有质量保证机制。
P2P网络对服务质量的要求
     带宽
    延时
     延时抖动
     包丢失率
n  访问和下载优先级
在P2P网络中提高QoS需要考虑以下方面：
     QoS的分类和定义
     准入控制和协商
    资源预约
     资源调度与管理
  使用博弈论优化资源分配的策略
引入经济学：市场机制非常适合解决分布式资源配置问题。
引入博弈论：博弈是对战略相互作用的描述，它包括对参与人所能采取的行动的约束和参与人的兴趣，但不强调参与人实际采取的行动。解是对结果的系统描述，这种结果可能产生于一组博弈。博弈论给出各种博弈的合理解释并且考察他们的性质。
博弈论中一个代理被视为一个单体的、稳定的或者比较复杂的组织。博弈的重点在于参与者的竞价策略。参与者可以自行制定竞价策略，也可以参照其他参与者的价格来制定灵活多变的策略。换言之，博弈就是为了分析什么才是参与者的最佳选择。
博弈论的元素有参与者(players)、行动(action)、信,LA(information),策略(strategies),支付(payofs)、结果(outcome)和平衡(equilibria)。在给定参与者、行动和结果的前提下，各参与者根据可用信息选择自己的策略，该策略产生一个支付。
在博弈中，一个对策有以下几种基本要素:
(1 ) 参与者(players):参与者是博弈的决策主体行为。
(2) 策略(strategies):指每个参与者在对策中可以选择采用的行动方案，这个方案必须是一个完整的行动，而不是行动的某一步。每个参与者均有可供选择的多种策略。
(3) 支付或收益(payoffs):指一局博弈的得失。或者说是局中人从各种策略组合
中获得的效用，它是策略组合的函数。如果局中人得失的总和为零，则称这种对策为零和对策;否则，称为非零和博弈。
博弈和竞争均衡的区别在于:博弈论主要考虑决策主体在做出决策前企图获得其他参与人的行为信息，而竞争均衡假定每个参与任职对某些环境参数感兴趣(例如价格)，即使这些参数是被全体参与人的行为所决定的。
  纳什均衡是指博弈中的博弈方在策略选取时达到的这么一种状态:假设每一个博弈方都是理性人，已经选取了某策略的任一博弈方都不愿单独改变其策略，否则都只能是使得他的当前得益减少。
定义 1 :给定其它参与者的策略S，参与者i的最优反应记为，是指能给他带
来最大收益的策略，即(,)>=(,), != ；当每个参与者都选择了自己的最优反应策略，并且这些最优反应形成一个策略组合，便形成了纳什均衡。
定义 2 :一个策略组合=(，，?，)被称为纳什均衡是指：对于所有的i，有(,)>=(,), != 。
纳什均衡的思想就是，博弈的理性结局是这样一种策略组合，其中每个参与者选择的策略都已是对其它参与者所选策略的最优反应，所以，谁也没有积极性去选择其它策略。因为每一个参与者均不能因为单方面改变自己的策略而获利，于是谁也没有兴趣主动打破这种均衡。
P2P网络中的博弈论: 每个参与者都希望最大限度地从系统中获益，博弈双方对系统资源的竞争结果是稳定的，即Nash均衡。
Nash贡献：定义每个用户贡献的资源量。
价值矩阵：表示节点i的贡献对于节点j的价值。
差异服务概率函数：每个节点都根据其
他节点贡献了多少来回报它们。因此有一个服务概率函数。
效用函数：刻画用户对所得的服务质量的满意程度。

摘要
    近几年来 ，计算机支持的协同工作作为一个重要的研究领域越来越受到人们的重视，目前正处于蓬勃发展之中。本文研究cscw的一个分支一一实时协同文本编辑系统。实时协同文本编辑系统允许多人协作实时地完成对同一个文档的编辑。协同编辑系统要解决许多技术问题，特别是在出现并发操作的情况下维护文档的一致性的问题。本文在研究了现有的并发控制算法的基础上，提出了一种新的一致性维护算法一一折叠式操作变换(FOPT)算法，并在该算法的基础上构建了一个基于Eclipse的实时协同编辑件，该插件可以对分布式虚拟结对编程提供支持。
    FOP T算法包含三个部分，因果关系维护、操作变换和垃圾操作回收。因果关系维护使用熟知的基于状态向量的技术，通过使用状态向量来捕获操作之间的因果关系，并保证只有满足因果顺序的操作才能调度去变换和执行。操作变换是我们的主要关注和贡献，其主要思想是通过合理地组织操作历史缓冲记录使之与文档本身形成一种映射关系，并在操作变换的过程中采用隐藏/恢复并发操作的机制来解决并发冲突。垃圾操作回收将对操作变换来说无用的操作从历史缓冲区中去除，从而减少内存的消耗。文中我们对算法进行了详细描述并给出了具体的例子加以说明。
    Eclipse实时协同编辑插件的设计与实现是我们关注的另外一个重点。我们分别从通信层、会话管理、协同感知、一致性维护及与Eclipse集成这几个方面对系统的设计与实现问题进行了考察。在通信层，我们采用了Jabber作为通信平台，并在此基础上设计了一个可进行消息恢复的可靠传输机制。会话管理机制对于组织一群用户参与的协作来说是非常重要的，我们设计了一个基于发起人模式的会话管理协议，该会话管理协议能够支持一种特定的协作编程模式，并且允许站点中途加入会话。在协同感知方面，我们利用了Jabber作为即时通信平台所拥有的一些固有特性，简化了系统的开发。在设计插件的过程中，我们也对Eclips。技术进行了研究，开源的、高度可扩展的Eclipse平台大大方便了我们的开发。

关键字:计算机支持的协同工作，协同编辑，并发控制，一致性维护，FOP
第一章 绪论
    自从20世纪80年代计算机支持的协同工作(CSCW:Computer SupportedCooperative Work)这一概念正式提出以来，CSCW受到了来自各个领域的研究人员广泛的关注，发展到今天已经具有相当的规模和影响力，大量的研究成果开始运用到实际应用中。可以说现在CSCW这一理念己经是无处不在，它的研究、发展和应用正在影响和改变人们的工作和生活方式。
    新技术的出现加速了CSCW发展，互联网社会化也成为一种新的趋势。近年来，随着大量新兴技术(如网格技术，Web服务技术，P2P技术，语义与知识处理技术、)(XML等)的出现，CSCW的研究领域得到进一步的扩展和充实。Internet在最近的十多年中得到了长足的发展，已经深入到我们的日常生活中， 目前正呈现出一种社会化的趋势，许多研究者认为人类社会正在互联网络空间中形成一种新的心理空间或社会性与认知过程的空间。社会科学的一些理论开始运用于软件设计中，出现了所谓的“社会软件”的概念，该术语通常用来描述允许群体进行通讯、交互和合作的软件，广义上讲，包括了在线共同体、计算机协同工作平台以及新出现的群体类软件，如网络游戏，博客(Blog)，维基(Wiki).即时通信(工M)和其他多对多社群系统等，可以算作是CSCW的自然的扩展。有人认为社会化是一场正在到来的互联网革命，社会软件的崛起是一个明显的技术标志，互联网应用模式开始从传统的“人机对话”逐渐转变为“人与人对话”。从即时通信和文件共享等协同软件的流行上我们可以发现，人们对于能够促进人与人之间信息共享和交互的程序具有非常浓厚的兴趣，毕竟人是社会的人，交流和协作可以促进人际关系的发展，同时也能促进工作效率的提高。
     计算机支持的协同工作的定义为:地域分散的一个群体借助计算机及其网络技术，共同协调与协作来完成一项任务。其本质是通过计算机技术使处于不同地理位置的人们能够互相协作，并且感觉不到地理位置上的差异。
     CSCW可以分成几种不同的模式。按照人们合作的方式的不同和协作者的地域分布从时间和空间将CSCW分四种不同的模式:同步模式、分布式同步模式、异步模式和分布式异步模式。
     协同编辑系统，又称计算机支持的协同编著(CSCA:C omputerS upportedCooperative Authoring)系统是CSCW中的一种非常有用的工具仁3]，它允许不同时间不同地点的用户协作完成文档的编辑，从而大大提高群体工作的效率。协同编辑可以应用于计算机会议系统，远程协作学习，协同办公，协作编程等领域并与之集成。
     协同编辑按编辑的内容可分为:协同文本编辑、协同图形编辑和协同图像编辑等，按时间特性可分为实时(同步)的和非实时(异步)的。
     并发控制算法是协同编辑的核心，主要解决多人同时编辑同一文档时保证文档的一致性。一般区分为悲观的和乐观的并发控制两种，其中基于操作转换的乐观并发控制算法被认为是最有希望实现自由流畅交互的并发控制算法，研究者在这方面发表了大量的论文， 目前提出的大部分算法基于全复制结构和线性的文档模型，当前的并发控制机制在效率，控制的粒度以及应用于更复杂的文档模型等许多方面仍然需要改进。
第二章 协同编辑技术综述
     协同编辑(又称协同编著、协同写作)指的是由多人参与产生一个文档的过程。协同编辑器，又称为组编辑器(group editor)指的是支持协同编辑的应用程序，它允许一组地理位置分散的用户通过网络连接同步或者异步地对文档进行查看和编辑。
     按照协作模式的不同，可以将协同编辑系统划分为三种不同的类型:
     同步协同编辑器：典型代表如Grove,DistEdit，Reduce等。
     异步协同编辑器：典型例子包括通过E-mail进行协作(如LotusN otes)、文档批注系统(如Microsoft Word)和版本控制系统(如CVS, ClearCase)等。
    同时支持两种方式的编辑器：如 SE PI A超文本编著系统、RECIPE协作编程原型系统等。
       协同编辑系统的体系结构
    集中式体系结构：集中式体系结构将文档数据存放在一个中央服务器。
    全复制体系结构：P2P网络中采用的方式。全复制体系结构与集中式结构不同，每个参与站点分别保存共享文档的一个副本。
    混合式体系结构
    实时协同编辑系统的特性
    协作感知
    容错和快速响应
    并发控 制
    多用户Undo
    可以作为单用户编辑器使用
&#16
0;   丰富的文档结构
    一致性维护算法
    存在两种类型的并发控制算法，悲观的(pessimistic)和乐观的(op timistic)。悲观的算法要求任何更新操作都必须事先获取合适的互斥锁，从而阻止冲突的出现，保证拷贝之间不会出现不一致。乐观的并发控制不阻止不一致性的发生，但是通过使用某种机制来检测和纠正出现的不一致。
    定义 1： 一致性模型定义:如果一个协同编辑系统总是能维护下面的条件的话就说它是一致的:
    操作结果收敛(Convergence):当同样的一系列操作在所有的站点都执行后 ，共享文档的各个拷贝保持一致;
    因果关系一致(Casualityp reservation):对任何一对操作Op1,和Op2，如果Op2在因果关系上依赖于Op1，那么在任何站点Op1都先于Op2执行 ;
    操作意愿一致(Intentionp reservation):对任意操作Op，在任何站点执行的效果都与Op的操作意愿(即Op在生成它的站点的执行效果)相同,并且Op的执行不影响其他并发操作的操作效果。
    本质上，操作结果收敛条件保证了在协作编辑会话结束时最终结果的一致性;因果关系一致性条件保证了在协同编辑会话中存在因果关系的操作执行顺序的一致性;操作意愿一致条件保证了操作在远程站点执行的效果与在本地站点执行的效果一致，并且并发操作之间互不影响。
    传统的并发控制算法
    加锁方法:加锁方法是一种悲观的并发控制策略
    时间戳串行化方法:时间戳串行化方法为每个操作赋予一个时间戳，这个时间戳定义了该进程在实际操作中的次序，来自不同用户的操作请求可以根据它们的时间戳进行全排序，然后执行。
    发言顺序协议(foor based turn-taking):每次只允许一个用户编辑共享文档.
    Undo/Redo方法:Undo/Redo。方法是一种乐观的并发控制算法，当接收到操作后立即执行，并将操作记录到历史，如果收到乱序的操作，则要将全局序在它之后的已执行操作Undo，然后执行这个操作，再将Undo了的操作Redo。
    基于操作转换的并发控制算法
    文档标注算法
    多版本算法
    协作感知技术
    协同感知的目的是模拟现实世界的协作过程，让参与协作的人员在计算机环境下了解其他人的活动，从而为自己的活动提供一个上下文(context)环境，消除由于空间上的分布而带来的割裂感，更好的发挥个体的主动性和积极性。要求根据应用的需求，提供多层次的感知信息，使得协作过程更自然。
    会话管理
    会话(Session)指的是开始、结束、加入、退出以及浏览一个协作场景的过程。会话管理也可以称之为群组管理。在会话管理中要确定会话的过程并设计相应的协议来处理。会话管理的两种通用做法分别是基于发起人的(initiator-based)和基于参与者的(joiner-based)，它们的区别在于用户结合的方式:前者由初始用户邀请其他人员加入到协作会话中，而后者由初始用户创建会话，其他人主动加入。
第三章 Eclipse技术
第四章 一致性维护算法研究
    本章介绍FOPT(Folding OperationT ransform)算法.综合文档标注算法和操作转换算法两者的优点，采用线性文档模型，只对操作本身进行变换。对操作位置进行变换时，不是采用转换函数对操作进行两两转换，而是通过维护一个特殊的操作历史记录，使用文档标注算法中的隐藏/恢复机制来计算并发操作在本地文档上执行的正确位置，从而维护用户的操作意愿。因为状态消隐时的隐藏/恢复操作类似于折扇的折叠和展开操作，我们形象地称之为折叠式操作变换，即Folding OperationTransformation(简称FOPT)。
    一致性维护算法
    实时文本编辑系统的形式化定义如下：实时协同编辑系统G用一个二元组<D,M >表示，其中D表示此系统所处理的文档，D=<Cl,C2,……,Cn>, Ci,i belongs to {1,……,n}为字符，D由一系列基本操作的集合M={OP1,OP2,……,OPn}操纵。基本操作op, i belongs to { 1,……,n} 可以是插入和删除一个字符的操作，插入用ins(p ,c) 表示，删除用del(p ,c) 表示，p为文档中的位置，c为字符。
    站点集合 S=(S1,S2,……,Si,……,Sn},n是G中结点的个数，每一站点用它的下标i惟一的标识，每一个结点Si相应有一个Di，它是D在Si上的实例。为了维护各个拷贝的一致性，每个操作OPi，都需要在所有的参与站点的文档对象Dj上执行，任一站点的动态行为可以抽象为下面四个方面:
    操作生成:将用户界面的操作转化为针对D，的操作。
    操作传播:将操作op传送到G中的其他站点。
    操作接收:接收来自其他站点的操作。
    操作执行:在本地文档Di上执行接收到的操作op(可以是变换后的)。
    本地操作生成后直接执行，然后再传播到其他站点，远程操作接收下来后，要先保证其符合因果关系，然后经过一致性维护算法的处理后再执行。
    每个站点Si，维护一个本地状态向量LSVi和一个操作历史记录表HBi =(EO1,EO2,……,EOn}, EO是执行了的操作记录。EO可以由三元组<op,S op,Vop>来表示，其中op为基本操作，Sop为生成该操作的站点号，Vop为生成该操作的站点的当前的状态向量。Vop 包含n个分量，表示为<V1,V2,……,Vn >， 每个分量Vi, i belongs to { 1,……,n} 表示的是本地站点已执行的来自第i个站点的操作的个数。
    一致性模型
    采用上面定义一中定义的一致性模型。FOPT算法分成两部分，一个是因果关系维护，另外一个是维护用户意愿，在维护用户意愿的过程中， 同时也保证了内容的收敛。
    因果关系的维护
    操作变化与集成
    垃圾回收机制
    本章在研究文档标注算法和操作算法的基础上，提出了一种新的FOPT一致性维护算法。首先介绍了协同编辑系统的形式化描述及一致性模型，然后分别对因果关系维护和用户意愿维护做了描述。着重介绍了FOPT维护用户意愿的方法，从文档初始状态为空的情况入手，再到文档初始状态不为空的情况，逐渐深入，对算法的细节做了详细的描述，并给出了具体的例子加以说明。
第五章 基于Eclipse的协同编辑插件的设计与实现
第六章 结论与进一步工作
关

Fissione: A Scalable Constant Degree and Low Congestion DHT Scheme Based on Kautz Graphs

摘要：

分布式哈希表（DHT）已经成为许多大规模P2P网络的核心组件。度、直径和拥塞是DHT中很重要的评估标准。现有的DHT机制多基于传统的互相联络技术，其中具有代表性的是Kautz图；Kautz图具有最理想的直径，最佳的容错性和低拥塞。

在这片论文中，我们提出了FISSIONE——第一个基于Kautz图的有效的DHT机制。FISSIONE是常量度的，直径是O(logN)，拥塞不会超过（1+O（1））。FISSIONE说明了一个常量度和常量拥塞的DHT机制仍然能够保持O（logN）的直径，这个直径比以前的直径下界要低。FISSIONE的平均度是4，直径小于2logN，维护消息的开销少于3logN。平均路由长度约为logN，在同样度情况下，FISSIONE的路由长度比CAN或者Koorde都要小。同时，FISSIONE还拥有较好的负载均衡、高性能、低拥塞；FISSIONE的这些特性将通过论文后续部分的理论证明和仿真来实现。

关键词：

对等网,分布式哈希表,DHT,Kautz graph,congestion-free。

第一部 Introduction and Related Work

DHT有两个重要的评估标准：度和直径。前者是指每一个节点维护的路由表的大小；后者是指查询过程在最坏情况下的路由跳数。

使用静态的Kautz图构建动态的P2P网络有以下三个问题：

1. 节点的ID应该是Kautz字符串，但是目前还没有能够在Kautz名字空间中生成独一无二的Kautz的算法，因此我们提出了一个Kautz_hash算法来实现Kautz字符串的生成。

2. 修改路由最短路径算法以适应于动态P2P网络。

3. FISSIONE提出了一个拓扑规则 neighborhood invariant 来均衡负载以及获得更小的直径。

第二部分 Kautz Graph and Low Congestion

A. 静态Katuz图

定义1：长度为k基为d的Kautz String ks 定义为一个string ,其中是集合{0,1,2,……,d}中的一个元素，并且（1<= i <= k-1)。

定义2：Kautz名字空间KautzSpace(d,k)定义为包含所有长度为k基为d的Kautz string的集合。KautzSpace(d,k)={is a Kautz string}。在KautzSpace(d,k)中共有N=个字符串。

定义3：Kautz图K(d,k)是指一个所有节点的ID都是由KautzSpace(d,k)中的Kautz String给定的有向图。显然，K(d,k)中的每个节点的出度和入度都是d，K(d,k)中共有N=个节点。节点U和节点V之间有一条边(U->V)当且仅当V能够通过U左移一位得到,例如，节点U=有一条边指向V=（对U是出度，对V是入度），当且仅当x!=并且x{0,1,2, ……,d}。

Kautz图和de Bruijn图的唯一区别是：de Bruijn图的节点ID是普通的字符串，而Kautz图的节点ID是Kautz串。

证明Kautz图有最短直径。

给定度d和直径k，图中节点数目的上限N由Moore定理给出：N=1+d+。Kautz图中的节点数目K(d,k)=，非常接近Moore定理的上界。考虑k=2,那么一个图中节点的最大数量是d+d*d，此时Kautz图是完备的（K(d,2)，N=d+d*d）。根据Moore定理，容易计算出一个有N个节点的图的直径的下界是，此时直径为k的Kautz图K(d,k)达到了这个下界。（因为 = k+1-1=k，即二者相等）。

B. 低拥塞路由

Kautz图选择长路径路由算法(Long Path Routing algorithm)。

定义4：长路径路由算法：Kautz图K(d,k)中节点U=到节点V=的路由路径是一个如下所示的长度为k的路径：

U==V （）

U==V（）(此时长度为k-1)

这样可以计算出Long path routing algorithm的平均路径长度h=（d/(d+1))*k+(1/(d+1))*(k-1)=k-(1/(d+1))。这个长度比shortest path routing算法要长一些，但是long path routing algorithm算法负载均衡性更好。

定义5：P2P网络中的c-congestion-free（c是常数且c>=1）是指：在all-to-all通信的情况下，此P2P网络既是c-node-congestion-free，也是c-edge-congestion-free的。c-congestion-free指网络中只有c个拥塞或者常数个拥塞。c-node-congestion-free是指每个节点处理的平均通信数量不会超过c个，c-edge-congestion-free是指每条边处理的平均通信数量不会超过c个。

uniform all-to-all communication（完全all-to-all通信）是指：对于每一对节点U，V（U！=V），在U和V之间有且只有一个单元的通信量。静态P2P网络是指，假定名字空间中所有节点都存在且在线。

在uniform all-to-all 情况下，网络中共有N*（N-1）个路由消息，假设路由路径平均长度是h，那么每个节点将处理（N-1）*h个路由消息，而每条边将处理N*（N-1）*h/|E| (E是指网络中边的条数)条消息。

定理1：采用long path routing算法，Kautz图K(d,k)是(1+O(1))-congestion-free的。

通过5个定义和1个定理，我们从理论上分析了FISSIONE的特性，FISSIONE具有常量度，最优直径，最好的容错特性。在网络足够大的时候，FISSIONE是congestion-free的。

Fissione Design

A. Overview

Fissone使用度为2的Kautz图K(2,k)作为其静态拓扑。Fissione中多有节点共同组成二维笛卡尔坐标空间，每个节点拥有一个区域。初始时，所有节点的ID长度相同，且共同组成Katuz空间。当有新节点加入或离开时，Kautz空间会被划分（分割大区域原则，合并小区域原则），节点ID的长度有可能改变。出于维护性能的需要

这篇文章主要提出了一种适用于传感器网络和ad-hoc网络中的结合网络底层拓扑结的DHT：T-DHT。采用T-DHT作为基础来实现以数据为核心的存储、信息处理以及ad-hoc和传感器网络中路由。T-DHT不依赖于位置信息，并且即使在规模非常小的网络也能很好的工作。根据底层网络的拓扑结构构件了一个分布式的DHT。T-DHT中邻近的两个节点在物理网络中通常会有一个直接的链接。相比较于最短路径路由，T-DHT在路由时发送的路由消息更少。
第一部分 介绍
文章主要讲述了如何基于底层网络物理拓扑构建DHT，以达到：哈希表中邻近的两个节点，在实际的物理网络中，通常有一个直接链接。
构建T-DHT包含两个步骤：（1）建立一个代表无力网络的虚拟坐标空间；（2）以虚拟坐标空间为基础，构建一个二维的哈希表，其中每个节点维护和其虚拟位置邻近的节点信息。
第二部分 轻量级的虚拟坐标空间
首先随机选择3个参照节点，其他的每个节点根据这3个参照节点计算出其自身的坐标位置。然后参照节点以两个节点之间的跳数为距离，洪泛整个网络，这样每个节点就能得到节点到参照节点的距离。根据节点自身到参照节点的距离，每个节点都能计算出其在虚拟坐标空间中的位置。
第三部分 面向拓扑的哈希表
坐标空间被所有参与节点分开，每个节点负责其邻近的一部分区域。同时每个节点维护一个路由表，该路由表包含其在虚拟坐标空间中的邻居节点信息，和每个邻居节点维护的区域信息。在二维哈希空间中的路由是很直观的，节点使用贪心算法向其路由表中的节点发送消息，直到返回结果。
加入T-DHT包含3个步骤：（1）想加入T-DHT的节点，首先必须找到一个已经存在于T-DHT中的节点。（2）通过T-DHT路由来找到当前正在维护它的位置区域的节点。然后将这个区域等分成两份。（3）新加入的节点通知邻居节点自身的存在。
为了自举，在最初的时候第一个参照节点维护整个哈希表。当有新的节点加入时，第一个参照节点通知新节点：“我是T-DHT的成员。”然后邻居节点之间相互通知成员关系和邻居关系的存在。
第4部分 评估
达到了设计目标，即：哈希表中邻近的两个节点在底层网络中也邻近。

下载：

今天记录两件事情，一个是老婆的司考成绩出来了，刚刚过分数线2分，362，呵呵，这下我不用挨骂了，回家也不会不敢面对岳父母了。

第二件事是72pines问题多多，终于狠了一下跑到yo2.cn绑定了域名，36.5，不算贵，还可以接受。

今天还买了本书，南大陈贵海写的《对等网络：结构应用与设计》，作者都是牛人，书的组织结构也很好。

研究kademlia有1年半了，中间搜集过很多的资料，只是都被我不小心删除掉了，这里发布一些经典的资料。

KadC：一个比较经典的C实现的kademlia协议KadC：http://kadc.sourceforge.net/ 下载链接，不过目前这个库已经很久没有人更新了，这个库实现了kademlia协议几乎全部的内容，但是有一个关键的部分没有实现，就是存储发布信息，即发布信息是可以成功的，但是目标节点并没有存储这些信息，因此在成功发布之后不能搜索到发布的内容，这个实现运行于Linux平台，windows下可以用cygwin或者mingw模拟运行。

emule:电骡是我研究时间比较长的一个东东，开源的，软件下载地址，源码下载地址，目前最新版本是0.48a，我看得主要是0.47c的源码，然后前一阵 verycd除了一个easyemule，easyemule源码，算是emule的mod吧，还比较适合国内用，加入了反吸血，不过我还没有怎么仔细看源码，对于emule这个东东，我也发布过几篇学习的文章：emule中节点加入Kad网络过程（源代码详解） emule中kad网络深入解析。与emule（windows平台）类似的有linux下的amule。sharaza实现了多种P2P协议，其中包括kademlia协议。

revconnect：这个东东也很厉害，也是p2p的文件共享基于DC++，但是结果呈现的方式和emule的完全不同，第一次看到它的呈现方式时觉得确实不错（相比较于emule），这个东东相当于是internet上的网络邻居，呵呵，不过在国内不太流行，用户不太多，国外用户还是很多的，源码写的也很不错，底层同样是基于kademlia协议。

我主要就是看了这三个项目，其中前两个的源码仔细研究过，不过emule的代码确实有点复杂，到现在我只能说能够将kademlia模块弄出来做些应用。

另外，2007年夏天我自己做了一个基于kademlia的p2p voip系统——ppPhone，详细介绍可以在这里看到。

下面共享一些我机器里的资源：

Kademlia: A Peer-to-peer Information System Based on the XOR Metric，这是kadmelia协议提出者发表的论文，呵呵

kademlia协议原理简介：这是国内一个高人写的，不错

emule 0.47a source：0.47a vc8的源码，已经包含相关的库了。

revconnect中kademlia库的源码

revconnect 0.674p的源码

A performance evaluation of the kad-protocol.pdf：这是法国的一篇硕士论文，对emule中的kademlia协议做了比较详细的分析。

An Analysis of BitTorrent’s Two Kademlia-Based DHTs.pdf：分析bt中使用的kademlia协议的缺点，并提出了一些改进方法。

Analytical Study on Improving Lookup Performance of Distributed Hash Table Systems under Churn.pdf：分析了在churn（即网络拓扑动态变化较大）情况下DHT的查询性能，以kademlia协议为代表。

Improving lookup performance over a widely-deployed dht .pdf：对kademlia协议进行优化的文章

Improving the Performance and Robustness of Kademlia-based Overlay Networks.pdf：kademlia协议优化

PDF下载

    这几天看了若干篇博士论文，尽量将它们都贴出来吧，后面会陆续贴一些读书笔记。 
    近年来，基于对等结构（Peer-To-Peer，P2P）的分布式系统在互联网上广泛的流行起来，成为了当前占据 Internet 主要流量的应用之一。基于分布哈希表（Distribute Hash Table，DHT）的结构化系统是 P2P 系统的重要组成部分，系统中的各个节点通过某种规则相互链接形成具有一定拓扑结构的网络，具有较高的查询效率。常量度 P2P 系统作为一种新型的结构化系统，具有邻居节点个数为常数而查询效率为 O(LogN)的特性。常量度 P2P 系统能有效地减小系统维护开销，简化系统结构，但同时也面临着容错、数据负载平衡、路由负载平衡等方面的问
题。如何解决常量度系统所面临的这些问题，是一个值得深入研究的课题。此外，由于 P2P 系统中往往具有着巨大的节点规模和节点在地理上广泛分布的特点，因此在大规模 P2P 环境下的资源搜索面临着两个重要的性能指标：搜索效率和网络负载。高效的搜索有利于减小搜索的延时，提高用户的满意度；而较低的网络负载有利于减轻网络流量，减小营运商的成本。特别是在 P2P 环境下进行复杂搜索时，面临着搜索效率和消息开销的性能折衷问题：优化其中一个往往使得另一个表现出较差的性能。进行复杂搜索时，如何在保持搜索效率的同时减
小网络的消息开销将对网格系统、服务组合等应用具有现实的推动作用。
     针对上述问题，本文首先拓展了 CCC[1]网络结构，为每个节点增加 3 个邻居节点，从而形成新的常量度 P2P 重叠网络，它在负载平衡、路由效率等方面表现出新的特性。在该系统的基础上，本文围绕复杂搜索中的区间搜索和 Top-K 搜索两个问题展开研究，提出了针对这两个问题的搜索算法，对算法进行的理论分析和实验模拟表明这两种算法具有较高搜索效率和较低的网络负载。论文的主要贡献主要包括：
（1）本文在 CCC（Cube-Connected-Cycle）网络结构的基础上，提出了一种新的常量度 P2P 网络—Cactus。该系统中每个节点的邻居节点数为 6，而在节点规模不超过 d×2d的情况下，查询效率为 O(d)，其中 d 是 CCC 网络的维度。本文阐述了 Cactus 的拓扑构造、路由算法以及容错机制，并对相关实验及其结果进行了分析。实验表明 Cactus 在查询效率、负载平衡、容错性等方面均不逊于现有的常量度数的 P2P 统。特别是与已有的容错算法相比，在节点非正常离开系统的情况下，Cactus 采用了“反馈式”容错算法，使节点恢复邻居关系的消息个数从 log2N
减小到 3logN，时间开销从 logN 减小到 2 步，从而使得系统具有较强的容错能力。
（2）本文在 Cactus 常量度系统基础上，设计了一种 Smart-Broadcast 算法。该算法根据被搜索区间的范围，动态建立一棵虚拟搜索树。该搜索树的结构与 Cactus 系统的底层拓扑结构相匹配，并使得被搜索的节点都聚集在根节点附近，从而使得单值区间搜索的消息开销为 O(d)，而平均路由开销不超过 O(d)+(1＋3/d)m，其中 m 是被搜索区间内所有映射到的节点。本文描述了 Smart-Broadcast算法，并在该算法的基础上设计了多属性区间搜索算法。对算法进行理论分析和模拟实验证实 Smart-Broadcast 算法在大规模节点的情况下，具有较小的消息开销和路由开销。
（3）本文在 Cactus 系统和区间搜索算法的基础上，提出了一种 Top-K 搜索算法—IES（Iterative Estimate Range-size）。算法根据资源属性，将资源看作是 m 维空间中的点，而 Top-K 搜索就转换为在 m 维空间中搜索距离查询点最近的 k 个点。该算法根据 Agrawal 发现的资源密集现象，在 m 维空间中确定搜索区间大小，并利用 Cactus 的多区间搜索算法，迭代地在多个区间中搜索资源，使得算法同时保持了高效和低负载的特点。本文证明了算法的正确性并分析了它的性能。分析和实验表明，该算法在高属性维度、低查询维度的情况下，具有较好的查询效率和较低的网络负载。

PDF下载