Extending the Collaborative Online Visualization and Steering Framework for Computational Grids with Attribute-based Authorization

使用基于属性的授权机制对计算性网格的协作在线可视化和引导框架进行扩展

摘要

合作在线可视化和引导（COVS）已经成为了引导一个并行仿真实验并动态改变其参数或者仅仅通过可视化来给地理分散的合作者共享仿真结果的一项重要技术，特别是在由高性能计算（HPC）驱动的网格基础设施中。在较前的工作中，我们已经给出了一个基于UNICORE网格中间件（DEISA中使用此中间件）的COVS框架的参考实现。本文列出了COVS在框架设计和实现上的现有限制，包括不具有细致授权的能力等，而这种授权能力在合作COVS会话中是必需的。这些能力使用终端用户的诸如角色、项目成员关系或者参与专有虚拟组织（VO）等个人信息。我们概述了解决方案并且给出了一个使用属性授权机制的扩展框架的设计与实现，如最近广泛使用的基于安全断言标记语言（SAML）的虚拟组织成员关系服务（VOMS）等属性授权机制。

1. 简介

世界范围内的网格基础设施如DEISA、EGEE、OSG和TeraGrid提供了各种各样的网格服务，以实现用于e-science的大规模资源共享。虚拟组织允许跨越组织边界共享这些资源，并且能够有效的利用提供的诸如超级计算机或集群等网格计算资源。许多虚拟组织和网格基础设施内部的科学研究程序着力于物理、生物、化学或其他特定领域过程的仿真。现有的许多网格基础设施如DEISA或TeraGrid，由于高性能计算的驱动，通常使用并行计算技术（MPI[24]，OPENMP[10]）运行网格程序来仿真上述过程。这些仿真的结果通常有一个分离的后续处理步骤，例如，在可视化程序中查看仿真结果等。基于这些中间结果，可以在另一个计算周期中改变仿真参数。

为了提高e-scientists的有效性，合作在线可视化和引导（COVS）技术尝试同步仿真过程和仿真结果可视化。在线可视化意味着e-Scientists可以立即观察到仿真过程中的处理步骤,进而允许计算性引导在超级计算机运行时引导仿真的计算。在此上下文中，在较前的工作中，我们已经给出，当在诸如DEISA等UNICORE网格中使用一个COVS框架[22]，e-scientists的有效性能够通过改变强安全环境和协作的基于web服务的特性来获得长远的提高。在本文中，我们讨论了地理分散的可视化会话中面临的挑战，引出了对细致授权机制的需求。在现有的网格中，终端用户的诸多属性如VO、组成员关系、不同的角色和能力等都是可用的，但COVS框架仅限于基于身份标识的授权认证机制（如使用X.509证书），本文给出了一个允许基于属性的授权认证机制的扩展。

本文组织方式如下，在回顾计算性网格的可视化和指引能力后，第二部分介绍了COVS框架在UNICORE中的实现并且列出了该实现对细致授权机制的限制。第三部分描述了哪些技术符合基于属性的授权认证机制并且能够在现有的网格环境中使用。基于这些技术，我们在第四部分给出了我们对COVS架构的扩展，第五部分描述了两个科学程序作为这个新特性的用例。最终，在第六部分回顾了相关工作，第七部分给出了我们的结论。

2. 协作在线可视化和指引框架的限制

协作在线可视化和计算性指引（COVS）框架使得网格程序具备了交互能力（如计算性指引）和可视化反馈机制。在早期工作中[26]，我们给出了一个基于可视化接口工具包（VISIT）[13]的COVS技术实现原型和一个被称为计算资源统一接口（UNICORE）[28]的DEISA的网格中间件。此后，该方法被用于更广范围的COVS框架[23]，随后我们在Grid 2007会议上将之发表[22]，该方法具有较好的易用性和较高的性能。最近，我们深入研究了[21]在UNICORE中CVOS框架实现的计算性指引能力的影响[21]，该UNICORE常用于的大规模DEISA HPC系统（如IBM BlueGene/P JUGENE，共有65536个处理器）。

现有COVS框架的架构如图1所示，图中给出了一个有两个地理上分散的参与者（如客户A和客户B）合作的情景。两者都运行一个科学可视化程序，外加一个COVS网格组件插件，该插件用于扩展GPR UNICORE网格客户端[25]。网格客户端用于访问两个COVS服务，该服务用UNICORE的Web服务资源框架（WS-RF）[1]的实现的工厂模式实现。因此，客户端是用来调用COVS工厂服务，该工厂服务创建了可以通过COVS服务访问的COVS会话资源。一个会话资源的实例代表一个管理不同参与者的合作可视化会话，对不同参与者的管理通过控制VISIT合作服务器和VISIT复用器来实现。VISIT合作服务器用于在参与者之间交换信息，交换通过使用SSH的专用连接完成，VISIT复用器负责通过SSH专用连接将仿真的结果分发给n个参与者。这些连接实用UNICORE网格中间件的强安全特性创建，在[26]中有关于这些连接的详细描述。总的来说，仿真实验的科学数据通过二进制加密的安全专用连接传输以达到令人满意的性能，使用Web服务的仿真工作的提交和合作会话的管理的开销就整体性能而言并不是主要的。

图1 UNICORE网格中间件中COVS框架实现

尽管我们的框架实现已经广泛使用，在提及细致的授权认证能力时，我们最近发现了该框架的一些限制，正是这些限制驱使我们提出了本文中的方法。在典型的场景中，COVS服务常用于一个虚拟组织内部，而不是用于许多地理分散的虚拟组织成员之间，在一个COVS会话中，这些成员通常有不同的角色并且拥有不同的能力。更详细地，如果一个人使用我们的框架并且与其他n-1个人共享一个并行仿真实验的可视化视图，那么我们称此人扮演一个participator角色。当一部分人扮演参与者角色时，另一部分人可能同时扮演若干个角色。这意味着我们的框架对某一个角色提供的功能不同于对另外其他角色提供的功能。例如，只有master角色的participator能够使用框架来提交或者控制一个运行在计算性网格资源上并行仿真。因此，其他参与者不需要（也不应该被允许）提交一个仿真，因为一个已经提交的并行仿真的结果将会被共享给其他参与者。 为了避免任何终端用户都可以加入一个会话，我们定义了approver角色，该角色决定哪些参与者可以加入到可视化会话中。approver角色基于候选人的不同角色和预定义的能力来决定谁能够加入到会话中。此外，在一次合作会话中,引导并行仿真的技术能力产生了在指引过程中对参与者互斥的需求。指引过程需要仿真领域的知识，因此，只有小部分参与者能够扮演领域专家的角色，并且只有这一小部分人被允许改变仿真的行为。由此得出，在同一时间，在一个COVS会话中只能有一个参与者扮演steerer的角色并控制并行仿真，这样才能保证仿真的

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

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

了想，决定自己改一改。

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

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

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

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

用户兴趣矢量的计算方法

用户模型的定义：

用户模型的定义用户模型不仅仅是对用户兴趣的准确描述，作为以计算机平台为依托的个性化服务系统，可计算性是它对用户模型的基本要求。也就是说，个性化服务系统中的用户模型不是对用户个体的一般性描述，而是一种面向算法的，具有特定数据结构的形式化的用户描述。

用户间的兴趣相似度的定义：

用户兴趣相似度是衡量2个用户兴趣矢量之间近似程度的一个指标。用户兴趣相似度是一个数值，取值范围在[0,1].规定:一个用户与其自身的兴趣相似度为1.

用户模型：

【1】用户兴趣建模方式

现有方法综述

A．基于模板的用户建模方法

是将用户的个人信息划分为一些模板。并通过这些模板帮助系统预见用户的行为的用户建模方法。应用模板可以为具有不同背景知识的用户分类进而为用户提供合适的信息和建议。尽管这种方法对于快速生成系统中的用户模型是一种很有效的技术，但也存在着明显的问题：模板的工作是寻求用户特征与数据库中项目的描述的匹配。如果这样的描述本身有同题的话，就可能导致系统建模的错误。实际上，这种描述往往是设计者人为进行的，难以避免主观性和片面性。因此，为了使模板技术具有更加广泛的实用性，这种描述必须是自动生成的。

B．基于机器学习的用户建模方法

机器学习是智能系统不断地积累经验以改善系统性能的过程，主要的学习方法有归纳学习方法和分析学习方法。早期使用机器学习的用户建模方法，主要是用来捕获用户行为所隐含的认知过程和普通用户与专家之间技能的差异；目前的研究重点则是放在了对用户行为本身的模式和偏好上。机器学习是用户模型隐式获取方法中最常用的一种。它的目的在于减少用户的直接干预，并且增强用户模型的话应性。统计相关分析法是用户建模过程中机器学习的主要方法，它将用户的行为和上下文关联起来。以后通过上下文就可以检索到对应的行为，从而起到预测用户行为的作用。机器学习的优点在于不需要用户的干预，适合于对用户模型进行定期的动态更新。其存在的同题主要包括：需要大量的数据集合；需要标定的数据；概念漂移；计算复杂等等。

C．基于贝叶斯网络的用户建模方法

在用户建模的过程中，常常会有一些不确定的因素。因此就需要一些能在不确定因素下还能够进行推理的方法。概率技术，尤其是贝叶斯网络是解决上述问题的有效方法。贝叶斯网络又称为概率推断网和信度网。是用来表示变量同连接概率的图形模式，是一个有向无环图。它基于如下假设：人们感兴趣的变量值受概率分布的控制。结合观察数据，对退些概率进行推算便可做出最优的决策。以前贝叶斯网络大多用于对静态数据进行处理，近年来将贝叶斯网络用于动态变化的不确定性领域的兴趣正在增加。此方法正在以其独特的不确定性知识表达形式、丰富的概率表达能力、综合先验知识增量学习特性等成为目前用户建模众多方法中最为引人注目的焦点之一。

D．基于神经网络的用户建模方法

神经网络是反映人脑结构及功能的一种抽象数学模型，一个神经网络是由大量神经元节点互连而成的复杂网络。用以模拟人类进行知识的表示与存储以及利用知识进行推理的行为。一个基于神经网络的用户建模系统是通过学习获取知识后建立的。从本质上讲，神经网络的学习是一种归纳的学习方式，它通过大量实例的反复学习，由内部自适应过程不断修改各

神经元之间相互的权值，最终使神经网络的权值分布收敛于一个稳定的范围。

E．基于逻辑的用户建模方法

是指能够建立一个具有推断有关用户假设的用户模型的建模方法。

F．基于模糊集的用户建模方法

是指应用模糊数学的处理方法进行用户建模的方法。

使用不同技术的建模方法比较：在上述用户建模的方法中，基于逻辑的方法、基于贝叶斯网络的方法、基于神经网络的方法和基于模糊集的方法都涉及到用户建模过程中的具体知识表示方法，其中贝叶斯网络的方法最常用。例如微软的Office助手就采用了这种方法(贝叶斯推理算法)来推断用户的意图。基于机器学习的方法和基于模板的方法实际上并不是知识表示方法。而是知识获取和利用的方法，但是它们必须以具体的知识表示为基础。基于模糊集和基于神经网络的方法都是为了表示与处理用户模型中不确定性知识丽引入的方法，但两种方法从概念到技术都不相向。基于模糊集的方法是模仿入脑的逻辑思维，而基于神经网络的方法是模仿入脑的结构来映射输入特征与输出结论的非线性关系。两种方法可以结合起来，各取所长，互相补充。

方法

基于VSM、基于神经网络、基于逻辑、基于贝叶斯、基于模糊集、基于机器学习

：使用VSM（Vector Support Machine）来建立用户模型

1) 在VSM中，用户兴趣模型由兴趣特征及其相应的权重对组成，能够表示每个兴趣特征在用户兴趣模型中的重要程度，而不只是对该特征存在与否的描述。这样有利于在对用户的多种兴趣进行描述时，各种兴趣之间的比较以确定用户当前的真正兴趣。

2) 由于VSM广泛应用于特征表示，在本文实现的原型系统中，也使用了VSM作为文本和领域类别的类向量的表示方法。用VSM 表示用户兴趣模型，有利于文本、领域类别和用户兴趣模型之间的分析与计算。

3) 使用VSM表示用户兴趣模型，可以利用向量间的余弦距离来计算用户兴趣模型的相似度，其运算速度相当快，有利于比较用户间的兴趣相似度 。

4) 对兴趣特征的权重进行调节就可以改变该特征在用户兴趣模型中的重要程度，这样对于分辨长期兴趣和短期兴趣以及它们之间的互相转换是相当方便的。

例二

使用了用户感兴趣的领域类别、用户感兴趣的关键词和信息来源这三个方面作为用户的兴趣特征。

用户兴趣模型I可以表示为：

IC表示科研用户感兴趣的领域类别的特征向量，ni为用户感兴趣的领域类别的序号，实际对应于第ni个领域类别的类向量Cni；IK表示科研用户感兴趣的关键词的特征向量，Ki为用户感兴趣的关键词；IS表示科研用户经常访问的信息来源的特征向量。

IC从粗粒度描述了用户的兴趣，它表示了用户兴趣的一个范围和方向。

IK从细粒度描述了用户的兴趣，它以关键词或关键词的组合来表达用户对信息的查询或者用户想获取的信息的特征。

方法二：基于贝叶斯网络模型的用户兴趣联合推送

1） 目标表示：是指从目标信息（如用户兴趣或文档）中选取一些特征项（如术语等），用这些特征项及其在目标信息中的重要性来代表目标信息。

VSM方法：

（1） 选取一组适合于表示目标信息的术语（T1，……， Tn）

（2） 对于目标信息F，根据术语Ti在F中的重要程度求出权值Wi，i=1，……，n，然后把目标信息F用术语特征矢量（W1，……，Wn）表示出来，Wi表示Ti在F中的权重。我们根据术语在文档中的属性及其文件频度和反频度将文档表示为术语特征矢量。如果术语Ti出现在文档的标题或作者中，那么其权重为1。如果术语出现在文档F的正文中，则根据术语的文件频度和反频度计算其权重，计算公式为：

其中，tf(i)为术语Ti在文档F中出现次数，df(i)是包含术语Ti的文档数，n是全部文档数目，tfmax是文档F中出现最多的术语的出现次数。

2） 用户兴趣建模

（1） 通过用户主动提供自己的兴趣来得到用户的初始兴趣模型

（2） 通过用户对搜索结果的反馈信息来更新用户的兴趣模型

（3） 在用户没有明确参与的情况下，系统通过观察用户行为来更新用户的兴趣模型，并将用户阅读过的信息元数据保存起来。

方法三：基于神经网络的方法（参见文献 基于动态自组织映射的用户兴趣建模方法）

(1) 分词提取关键字；

(2) 采用词频——逆向文档频率(Term Frequency-Inverse Document Frequency, TF-IDF)术从经过切词、还原或停词处理后的文本中提取表征文本的特征。具体做法是，将每一篇文本文档表示成向量空间中的一个向量，向量的每一维由文档d中的一个单词wi和其权重组成。每个单词的权重值di通过式(1)计算产生:

其中,TF(w;,d)是词频，表示单词wi在文档d中出现的次数; |D|是文档总数量; DF (w;)是文档频率，表示单词wi至少在其中出现一次的文档的数量; log(|D| /D F(w,))是单词wi的逆向文档频率，表示包含单词wi的文档数量越多，wi在区分文档中的作用越小。

经过上述步骤后，文本信息集中的每一篇文档都能够用一个以单词为特征的向量来表示。由于一篇长文档转化成向量后可能导致很高的维数，出于有效性和计算性的双重考虑，通常选用80^-120个具有最高TF- IDF权重的单词作为关键词来表征一篇文档，即表征用户偏好特征。

DS OM 神经网络以成长型单元结构(Growing Cell Structures, GCS)为基础。GCS是一类网络结构可变的自组织映射(Self – Organizing Map, SOM)神经网络。DS OM 方法将用户兴趣建模过程看成是一个增量聚类过程。该过程起始于输出层为一个三角形的网络互连结构，即初始类别数为3。对于用户感兴趣的每一篇文档，网络计算其特征向量与所有输出神经元权向量之间的欧氏距离。如果存在某些距离值小于预先给定的一个距离闭值0，则网络根据基本SOM的竞争规则，将文档归人与其距离最小的神经元(获胜神经元)所代表的类中，同时调整获胜神经元及其直接相邻神经元的权向量，使与该输入相似的模式再次出现时，这些神经元更加容易获胜。

DSOM方法分别通过网络权重调整、增加新神经元和删除旧神经元3种类型的操作，学习并跟踪用户的多种兴趣及兴趣变化。

我的选择：采用支持向量机模型，采用TF-IDF函数来计算关键词的权重

词频——逆向文档频率(Term Frequency-Inverse Document Frequency, TF-IDF)（见文献Automatic Text Processing 1989）

考虑三个层面：

用户的多兴趣（用户的兴趣是多种多样的，模型通常只能反映出用户的主要兴趣，因此如何选择和决定哪些兴趣是用户的主要兴趣需要考虑）

用户的长期兴趣和短期兴趣

【3】用户兴趣的更新

用户的兴趣和信息需求在一定时间内具有相对的稳定性，但又不是一成不变的。当用户兴趣及信息需求发生改变时，便需要相应的对已有的用户模型进行优化和更新。

P2P知识共享网络研究与实现

一．课题名称、来源、选题依据

1.1 课题名称

P2P知识共享网络研究与实现

1.2 课题来源

实验室自主研发

1.3 选题依据

1.3.1 知识共享的需求

知识是通过实践、研究、联系或调查获得的关于事物的事实和状态的认识，是对科学、艺术或技术的理解，是人类获得的关于真理和原理的认识的总和^[1]。知识是对事实或思想的一套系统的阐述提出合理的判断或者经验性的结果，它通过某种交流手段，以某种系统的方式传播给其他人^[2]。总之，知识是人类积累的关于自然和社会的认识和经验的总和。

知识共享可以定义成：知识从一个人、群体或组织转移或传播到另一个人、群体或组织的活动。个体知识、组织知识通过各种交流手段为组织中其他成员所共享， 同时，通过知识创新， 实现组织的知识增值。知识只有通过相互交流、学习、共享才能得到发展， 知识的共享范围越广， 其利用、增值的效果越好。知识只有被更多的人共享， 才能使知识的拥有者获得更大的收益。知识共享包括两个方面的内容，分别是知识生成和知识的重复使用^[3]。人类社会传承的数千年历史中，知识的共享一直是人类社会得以发展和进步的源动力。知识的共享对于促进人类社会的进步无疑更具有重要的意义。

1.3.2 传统知识共享的不足

知识的共享是如此的重要，以至于人类社会几乎每次重大的进步都与知识共享手段的进步有直接的关联。从最初的造纸术的发明，到现在互联网的发明，知识共享的手段越来越进步。但是我们仍然能够看到，当前的一些知识共享手段仍然是有局限的。

现在和未来我们需要的知识共享模式必须具备以下特点^[4]:

(1 )不受地域 (地理的和网络的)、时间和其他任何条件的限制;

(2)共享机制中的每个人既是知识获得者，也是知识发布者，同时还是知识收集者;

(3)不需要耗费更多资源即可实现知识共享;

(4)知识的形式是不限的，可以是文字、数据或文件等等;

(5)机制是开放的，只要遵从共享规范，每个人都可以有自己的发布方式。

我们希望能够有一种随时随地允许人们共享自己的经验、想法等知识并且将人们的知识永久保存下去的一种方法或者工具，从而能够使得人类文明得以更好的传承，人类社会得以更好的发展。人们的视野总是受当时社会发展的程度所制约的，我们也不例外。在现有的技术基础上， P2P知识共享网络能够很好的实现上面提到的目标，即允许人们在任何时候任何地点共享自己的经验、想法，并且将被保存。

1.3.3 P2P知识共享网络优势

P2P的本质即为共享，P2P模式将计算机网络和分布式计算结合起来，网络的参与者共享他们所拥有的部分资源，这些共享资源由网络提供服务和内容，能被其它对等节点(Peer)直接访问而无需经过中间实体^[5]。在此网络中的参与者既是资源（服务和内容）提供者（Server），又是资源（服务和内容）获取者（Client）。P2P具有非中心化、可扩展性、健壮性、高效性、隐私性和负载均衡等特性，这些特性能很好的避免传统的知识共享系统的一些问题。采用P2P模式来实现知识共享系统，真正的体现了共享的本质，人们能够直接的交流知识，随时将知识存储到网络中，而不用关心知识具体存放到哪里，在任何时候都能够将知识取回来，而且知识的继承性也能被很好的维护，用户的私密性也得以保证，系统的可用性很好。

二．本课题国内外研究现状及发展趋势

现有的知识共享模式主要有三种：

基于C/S模式：如图书馆，图书馆是一个服务器，用户是客户机，读者从图书馆取得资料，相当于从客户端从服务器获取数据。这种模式在现实社会中的例子如老师授课等。

基于C->C/S模式：如搜索引擎，搜索引擎从各处检索资料，客户端通过搜索引擎获取资料。这种模式在现实生活中的例子如购书者、图书发行商和作者形成的关系等。

基于P2P模式：所有的用户共享知识和资料，用户根据需要从P2P网络获取所需的内容。这种模式在现实生活中的例子如人们相互的探讨，交流等。

我们将前两种作为传统的知识共享模式来对待。人类社会知识共享的模式更倾向于第三种，所有需要知识的人之间相互交流。但是现有的技术手段限制了人们交流的方式。

目前传统的知识共享模式已经非常成熟，但是国内外还没有产品化的P2P知识共享网络，研究也处于初步的阶段。因此我就两个方面分析国内外现状，一部分是传统知识共享系统的国内外现状；一部分是P2P知识共享网络的国内外现状。

1. 传统知识共享系统

Internet诞生本身即是为了共享，从20世纪70年代末的BBS ^[6]到目前的博客（Blog）^[7]、维基（Wiki）^[8]、威客（Witkey）^[9]、百度知道^[10]、新浪爱问^[11]和Yahoo知识堂^[12]等等，出现了很多知识共享系统。

BBS：BBS全称Bulletin Board System（电子公告板），BBS能够发布内容，用户交流，是最初信息共享交流的雏形，我们认为BBS可以算作是最早的知识共享系统的雏形。目前已经有了基于P2P的BBS（Saku）^[13]，不需要类似于当前论坛的中心服务器，所有的数据分布存储于用户节点上。

Blog：中文名博客，是当前网络上流行一种信息表达形式。它顺序地记载一些想法、评论等，并且通过超级链接把相关的资源组织起来，从而形成一种对某一信息资源的小型信息库，使得信息以此为扩散地或集中点。博客通过Trackback的方式互相链接起来，组成一个类似于社会网络的知识网络。但是博客内容主要是个人思考之类，自有知识储存体现不多，可谓有思想而无知识；基于Web发布，不便于共享和交流。因而就其本质来说主要是一种基于Web的个人表达工具，而不是完善的知识共享机制。

Wiki：中文名维基，Wiki是一种多人协作的写作工具。Wiki站点可以有多人（甚至任何访问者）维护，每个人都可以发表自己的意见，或者对共同的主题进行扩展或者探讨。与大多数网络亚文化一样，Wiki也同样是体现开放、合作、平等、共享的网络文化。目前的Wiki多是基于中心服务器的。Wiki使用版本控制系统来维护数据的一致性。Wiki的版本控制系统能够保证内容被篡改之后回滚至以前正确的版本。Wiki更类似于创作共享模式，在共同创作一个文档的过程中，作者更多的在付出而非收获，无法实现真正意义上的知识共享。同BBS类似，目前已经有了基于P2P的Wiki系统^[14]，将写作过程中产生的内容分布存储于所有作者节点上，不需要中心化的服务器。

Witkey(威客)：通过互联网把自己的智慧、知识、能力、经验转换成实际收益的人，他们在互联网上通过解决科学，技术，工作，生活，学习中的问题从而让知识、智慧、经验、技能体现经济价值。威客模式也不是真正的知识共享的方式。

类似地，目前国内的百度知道、新浪爱问和Yahoo知识堂等都是以帮助解答问题的模式来共享

广西大学
硕士学位论文
基于博弈论的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的价值。
差异服务概率函数：每个节点都根据其
他节点贡献了多少来回报它们。因此有一个服务概率函数。
效用函数：刻画用户对所得的服务质量的满意程度。

这两天在阅读这篇文章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——国际并行和分布式处理讨论会

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

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

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

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

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

研究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下载