今天在改论文的时候，仔细想了想论文里的原型系统实现，觉得论

文里没有写清楚具体如何将科研社会网络实用化，因此我自己又想

了想，决定自己改一改。

我首先用FreeMind画了个图，在这里ssn.rar可以下载到，大致是这样的。

科研社会网络的实用化或者说比较简单的部署和实现方案是这样的：

这是实现方案上的。还有待进一步细化，我个人在开发网站方面的能力并不是很强，希望可以有人合作。

另外，关于市场方面，就是这个网站和客户端工具有没有用户，我想是有很多的用户的，这个东西主要面向科研人员这个群体，详细的内容请见我的硕士论文（初始版本,后面再贴）。

广西大学
硕士学位论文
基于博弈论的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部分 评估
达到了设计目标，即：哈希表中邻近的两个节点在底层网络中也邻近。

下载：

这两天在阅读这篇文章File Consistency Maintenance Through Virtual Servers in P2P Systems（提供下载），因此简单的翻译了一下，将翻译稿贴出来，希望能被需要的人看到，呵呵，不过话说回来，水平有限，翻译的文章难免有点问题，希望能够多多谅解，同时也希望能多提建议：dolf.cao@gmail.com http://www.dolf.cn

下面是翻译的摘要部分：

摘要——随着P2P应用的巨大增长，与之相关的文件一致性问题也成为一个亟待解决的问题。在这篇论文里，提出了一个应用于无结构化、分布式P2P系统中的文件一致性维护算法（CMV），此算法基于虚拟服务器。在CMV中，通过虚拟服务器来维护动态文件的一致性。文件的更新必须通过VS才能进行，从而确保一个备份的串行性（即不会被随意修改）。

一个文件的VS是指：一个由所有拥有这个文件的复制节点（RPs）组成的逻辑网络。我们使用数学分析来确定最优的参数，从而使得维护文件一致性所花费的控制消息最少。

结果表明CMV能够有效的维护P2P系统中文件的一致性。

下载地址：doc：

pdf：

在阅读对等网：结构、应用和设计时，看到一些好的东西，记录一下。

• P2P专业国际会议

1. IPTPS——International Workshop on Peer-to-Peer Systems，国际P2P系统讨论会

P2P领域最高级的专业国际会议，2002年第一次召开，每年召开一次，其赞助方有Microsoft、Intel、IBM等国际著名计算机公司。IPTPS虽然到目前为止只举办了四届，但对P2P的影响是巨大的，比如发表在IPTPS‘02上的Kademlia模型、IPTPS’03上发表的Koorde模型。IPTPS发表的文章实际上引领着P2P领域的发展方向。

2. IEEE P2P——IEEE International Conference on Peer-to-Peer Computing，IEEE国际P2P计算会议

IEEE举办的P2P专业国际会议，2001年开始，每年召开一次。

• P2P相关国际会议

1. SIGCOMM——ACM数据通信特别兴趣组年会

网络通信领域最高层次的会议，每年召开一次，SIGCOMM会议上发表的论文，基本上都是网络通信领域的经典、权威之作，对整个网络通信领域有深远的影响，Chord和CAN模型就发布在SIGCOMM‘01上。

2. SPAA——ACM并行算法和体系研讨会

SPAA 1989年创办，是由ACM举办的并行算法和体系方面的高层会议。Plaxton等人在SPAA’97上提出了Plaxton Mesh结构，成为Tapestry和Pastry的基础。

3. PODC——ACM分布式计算原理讨论会

最早的常数度P2P模型 Viceroy发表于PODC。

4. ICNP——国际网络协议会议

ICNP是IEEE举办的网络协议高层次会议。

5. INFOCOM——IEEE计算机通信会议

INFOCOMM是IEEE举办的计算机通信领域高层次会议，每年召开一次，开始于1982年。

6. NOSSDAV——ACM数字音频和视频的网络和操作系统支持讨论会

7. SOSP——ACM操作系统原理讨论会

8. OSDI——USENIX操作系统设计和实现讨论会

9. USITS——USENIX因特网技术和系统讨论会

SkipNet模型发表在USITS‘ 03上。

10. ICDCS——国际分布式计算系统会议

11. ICPP——国际并行处理会议

12. IPDPS——国际并行和分布式处理讨论会

   搜索引擎能否提供实时有效的信息导航服务是用户使用搜索引擎时最为关心的事情。传统的搜索引擎依赖于服务器,而信息整理的速度远落后于网络信息的膨胀。备查信息收集到数据库与实际搜索发生存在时间差有可能导致搜索结果中出现网页缺失、错误链接以及过时信息等问题的产生。
      基于P2P的搜索引擎的出现，为互联网的信息搜索提供了全新的解决之道。与目前使用的其他各类搜索引擎相比，其最大优势在于应用先进的对等搜索理念，可不通过给定的中央服务器，也可不受信息文档格式和宿主设备的限制，对互联网络进行全方位的搜索。其在搜索深度上是传统搜索引擎所难以比拟的，原因很简单，传统的搜索引擎是主动去发现新的信息，难免有遗漏,而P2P的搜索引擎则主动提交新信息。另外，P2P网络模式中节点之间的动态、对等的互联关系使得搜索可以在对等点之间直接、实时地进行，从而保证了搜索的实时性。同时搜索深度也是传统搜索引擎所难以比拟的，其搜索范围可在短时间内以几何级数迅速增长。

    以Gnutella搜索原理为例：一台PC上的Gnutella软件可将用户的搜索请求同时发给网络上另外多台PC，如果搜索请求未得到满足,这多台PC中的每一台又会把该搜索请求转发给另外多台PC，这样,搜索范围将在几秒钟内以几何级数增长，几分钟内就可搜遍几百万台PC上的信息资源。理论上最终将包括网络上的所有开放的信息资源，采集到的信息将有更强的实时性和有效性。

Faroo ：Faroo 是运行于P2P网络上的web搜索引擎，目前处于private beta阶段，Faroo 的理念是由所有的用户提供搜索引擎所需的web站点数据库，比像google这种基于中心服务器的要好。用户首先需要下载一个P2P软件

P2PSeek：P2PSeek也是P2P的web搜索引擎，提供了最新的P2P技术，并且搜索到的音乐和视频都是合法的。P2P Seek涵盖了超过200个P2P，音乐和视频站点，包括P2P新闻门户，博客，论坛和公司。站点包含Distributed Computing Industry Association所有的成员。P2P Seek现在还很不成熟。

发一下今天看的小论文，国内的，虽然质量不太高，不过还可以看看：

基于Peer-to-Peer的搜索引擎的发展.pdf

基于Peer to Peer 模式的模糊搜索.pdf

P2P网络性能测度及监测系统模型研究.pdf

P2P技术的应用领域及潜在问题研究.pdf

今天上午在看对等网：结构、应用和设计的时候，出了一个想法，想做一个P2P的网络存储，因为前几天想做集中式的基于web的网络文件共享，就是提供给用户网络存储空间，然后将用户上传的文件共享。但是后来和老婆讨论的时候发现有侵权的问题，所以考虑改一个方向，因此出来了P2P网络存储的想法。

今天晚上在网上找些资料，看到了一个处于内测的alpha版本的P2P网络硬盘，叫做wua.la，发现我的想法和这个东东一摸一样的，看来我还是落后啊。

Wuala, your free online hard-disk
Share files with your friends, privately. Images, videos, music, documents, whatever you like.
All files encrypted. No file size limits. No traffic limits.
Fast downloads. Get as much storage as you like. Free and simple.
Sign up, see screenshots, or read more.
Read also what others say: Techcrunch, GigaOm, Download.com, etc.

现在提供给用户1G的空间，如果想要更多空间的话，需要用户共享一部分本机资源，呵呵。有必要详细研究一下，如果可以的话，我觉得可以引进到国内来，这个模式还算是比较先进的，在这个平台作共享的话就好多了。前一阵考虑的基于web的网络文件共享主要是因为我考虑想找一个东西迅速起步，快速入手比较好。

关于wua.la的介绍，这里还有一些http://www.wappblog.com/50226711/wualaiecaeae_120685.php

Wuala是一种新型的在线文件存储及分享服务，有别于传统的在线存储系统，它是一个分散型的，可以充分利用每台电脑的闲置资源，从而构建出一个大型的、安全且可靠的在线存储系统。它为用户提供了一个桌面客户端，分别支持windows和mac系统。

不管你在哪里，你都可以使用wuala来上传文件，即使你的电脑是离线。或者你可以用它来共享文件，如照片，录像，音乐，文件给朋友或是团体。而在公共区域内，你可以搜索或浏览别人发表的共享文件。Wuala对文件类型及尺寸没有任何限制，不过它提供给每个用户1GB的空间，当然如果你有需求的话还可获得更多。只是，目前该服务还处于Alpha内测阶段，你可到其主页上留下Email，等待注册邀请。

今天还和导师交流了一下，导师叫我研究深入，并且告诉我，只有在深入研究之后才能发现一些潜在的需求，呵呵，加油加油，为了更好的养活老婆。

Technorati 标记: P2P, 网络存储, 网络硬盘