蒋卓轩-开题报告原稿再改版(定稿)

《蒋卓轩-开题报告原稿再改版(定稿)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

毕业设计(论文)开题报告（全日制本科生）课题名称支持节点异常离开的P2P分布式系统Chord算法的实现课题类别设计■论文□专业、班级软件工程2006级05班学生蒋卓轩学号20061610510指导教师林亚平二○○九年十二月 一、本课题设计（研究）的目的：P2P技术起源于1995年５月由ShawnFanning和SeanParker共同创办的文件共享社区网站——Napster。起初，该网站最主要的服务是为其用户提供一种便捷、易用的界面以实现媒体文件的搜寻及共享，同时还为音乐迷们提供相互交流的论坛，以及实时讯息、聊天室、用户书签等产品。它的诞生在互联网世界产生了不小的震动，而之后因它而起的一系列沸沸扬扬的版权官司，更将人们的目光聚焦到了一项新的网络技术——P2P（peer-to-peer）上。此后，P2P技术的商业化取得了长足的发展，并且各国都掀起了如火如荼的研究热潮。目前,在学术界、工业界对于P2P没有一个统一的定义，下面列举几个常用的定义供参考：1)Peer-to-peerisatypeofInternetnetworkallowingagroupofcomputeruserswiththesamenetworkingprogramtoconnectwitheachotherforthepurposesofdirectlyaccessingfilesfromoneanother'sharddrives.2)Peer-to-peernetworking(P2P)isanapplicationthatrunsonapersonalcomputerandsharesfileswithotherusersacrosstheInternet.P2Pnetworksworkbyconnectingindividualcomputerstogethertosharefilesinsteadofhavingtogothroughacentralserver.3)P2P是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源（处理能力、存储能力、网络连接能力、打印机等），这些共享资源需要由网络提供服务和内容，能被其它对等节点(Peer)直接访问而无需经过中间实体。在此网络中的参与者既是资源（服务和内容）提供者（Server），又是资源（服务和内容）获取者（Client）。P2P已迅速成为计算机界关注的热门话题之一，财富杂志更将P2P列为影响Internet未来的四项科技之一。对于P2P应用来说，最基本最核心的问题就是如何高效准确的在网络中定位节点，从而找到相应的资源以及进行各种信息数据的交互。在MIT，开展了多个与P2P相关的研究项目：Chord，GRID和RON。Chord项目的目标是提供一个适合于P2P环境的分布式资源发现服务，它通过使用DHT 技术使得发现指定对象只需要维护长度的路由表。在DHT技术中，网络结点按照一定的方式分配一个唯一结点标识符(NodeID)，资源对象通过散列运算产生一个唯一的资源标识符(ObjectID)，且该资源将存储在结点ID与之相等或者相近的结点上。需要查找该资源时，采用同样的方法可定位到存储该资源的结点。因此，Chord的主要贡献是提出了一个分布式查找协议，该协议可将指定的关键字(Key)映射到对应的结点(Node)。从算法来看，Chord是相容散列算法的变体。MIT的GRID和RON项目则提出了在分布式广域网中实施查找资源的系统框架。本课题的目的在于实现一种Chord算法的典型P2P分布式解决方案，通过对每个节点标识符HASH来确定节点在环上的位置。通过实现P2P网络模型中的Chord算法，构建一种性能较好的P2P原型。建立P2P的Chord环，能够通过HASH节点标识符将节点加入到Chord环中，并支持节点的正常和异常离开，节点加入和离开后Chord环状态能够及时更新。二、设计（研究）现状和发展趋势：点对点技术（peer-to-peer，简称P2P）又称对等互联网络技术，是一种网络新技术，它依赖网络中参与者的计算能力和带宽，而不是把依赖都聚集在较少的几台服务器上。其核心思想就是要解决如何在P2P网络中找到存有特定数据的节点，是一种基于DHT的路由模型。目前，在网络电视、文件共享、分布式计算、网络安全、在线交流甚至是企业计算与电子商务等应用领域P2P都显露出很强的技术优势。图一:P2P体系结构的发展第1代P2P应用的是集中控制；第2代P2P是一种完全的无中心的分布式网络；第3代P2P是一种混合式的体系结构，同时具备前两代体系结构高效性和容错性的优点。 目前最新的研究成果体现在采用分布式散列表（DHT）的完全分布式结构化拓扑网络。DHT类结构能够自适应结点的动态加入/退出，有着良好的可扩展性、鲁棒性、结点ID分配的均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构，DHT可以提供精确的发现。只要目的结点存在于网络中DHT总能发现它，发现的准确性得到了保证，最经典的案例是Tapestry，Chord,CAN,和Pastry。DHT类结构最大的问题是DHT的维护机制较为复杂，尤其是结点频繁加入退出造成的网络波动（Churn）会极大增加DHT的维护代价。DHT所面临的另外一个问题是DHT仅支持精确关键词匹配查询，无法支持内容/语义等复杂查询。Chord算法是一种典型的P2P分布式解决方案，通过对每个节点标识符HASH来确定节点在环上的位置。Chord使用一致性哈希作为哈希算法，将其算法规定为SHA-1。Chord算法在节点经常增加和离开的网络中，可以以很小的代价运行，并且支持节点异常离开和正常离开，在节点频繁增减变化时也能保持高效的查询。图二:基于Chord的分布式存储系统基于Chord算法的系统中，所有节点在逻辑上按照标识的大小组成一个环（图三），数据同样有标识并且存放在和自己标识最近的节点上。当在某一个节点上输入查询请求的时候，如果节点的标识小于数据的标识，则向该节点知道的下一个节点传递请求，下一个节点如果拥有该文件则返回结果，否则按前面的方式继续转发给下一个节点。其中每个Chord节点只需要知道关于部分节点和到达它们的路由信息（指向表）。Chord路由查找过程有两个重要特性：每个节点都只需要知道一部分节点的信息，而且离它越近的节点，它就知道越多的关于它们上面的数据信息；每个节点的路由表只有部分节点的路由信息并且不能确定任意一个关键字的确切位置，只能知道下一跳的节点。图三所示为Chord节点维护的指向表，其中0、1、3的位置上有节点。每个节点上维护一张表，以顺时针方向，会在内找到任何一个节点。 图三:一个P2P系统的简单例子，包括节点及其指向表三、设计（研究）的重点与难点，拟采用的途径（研究手段）：本课题的重点在于Chord环的构建以及节点的正常加入和异常离开。包括以下几点：1用Java实现Chord基本算法，实现构建Chord环解决这个问题，需要熟悉的Java编程基础，以及根据系统的预设，需要确定一个合理的系统规模，分析构建Chord环所需要的资源。然后根据算法建立一致性哈希表（SHA-1）。定义如下数据结构：NotationDefinitionFinger[k].start(n+)mod,1<=k<=m.interval[finger[k].start,finger[k+1].start).node大于等于n.finger[k].start的第一个节点Successor在环上的下一个节点predecessor在环上的前一个节点表1：节点上的变量及定义实现时，全局变量的定义、类和方法之间的耦合度、架构的良好设计、健壮性、可扩展性等等都是需要考虑并解决的问题。2节点的正常加入和离开功能。这里，根据Chord算法的思想，需要实现代码。算法运行的异步性和稳定性至关重要。当一个节点需要加入时，Chord算法应当完成以下三个步骤：1)初始化这个节点以及建立这个节点的指向表2)更新与这个节点相关的前后节点的前驱、后继和指向表3)通知上一层结构这个节点已经加入环并且可以被查找 3在节点中加入数据项，实现数据项的查找和定位。首先根据关键字用一致性hash函数查找，对关键字哈希之后，根据哈希的结果再用SHA-1哈希定位节点。节点的查找实现后，需要在这个节点中定位并查找需要的数据和处理相应事务，如文件上传下载、网络通信、远程过程调用、信息交互等等。需要实现接口、远程过程调用以及服务等监听程序。4在实现基本Chord环的基础上实现节点的异常离开，且节点离开后Chord环可以自动的更新。需要提供灾难容错的处理机制。当节点发生异常（断电、断网等），系统需要能及时发现并且自动更新，自动以节点正常离开的算法处理。其中需要有一个机制，以防止当一个节点异常离开时，如何能获取该节点上本身储存的信息。一个设想是每一个节点要另外建立维护一个successor-list后继表，以保存r（r>1）个successor（下一个节点）。这样，当一个节点发生异常时，依然可以通过successor-list找到这个节点的successor虽然有了这样的机制，但仍有两个问题存在：1)r定为几才算合适呢？这要根据系统平均的稳定历史来测算获得，如何测算也是个问题。2)在发现某个节点发生异常之前和发现该节点异常离开后系统正在更新的这两个期间里，若要发生与该节点有关的路由和计算的情况时，该如何处理？需要进一步思考解决。还有一个问题是如何发现节点已经异常离开？目前有一个不成熟的思路：1)可以在间隔一定的时间之后，节点向其后继发送消息确认存在，若连续发送几个消息后继都没有响应，就可以认为他已异常离开。2)或者可以设置一个中央节点，每个节点加入环后都向中央节点报告，中央节点定时询问每个节点是否在环上，若没得到某个响应，可以认为其异常离开。使用哪种策略，还需要进一步考虑，在实践中摸索和实现。四、设计（研究）进度计划：03月01日起到06月11日止，共计14周。具体安排如下： 1、开题阶段（搜集资料、方案确定）3月1日－3月7日2、初期阶段（设计、实验、研究、初稿）3月8日－5月8日3、修改定稿阶段5月9日－5月30日4、答辩及成绩评定5月31日－6月11日五、参考文献：[1]IonStoica,RobertMorris,DavidKarger,M.FransKaashoek,HariBalakrishnan.ChordAScalablePeer-to-peerLookupServiceforInternetApplications.ACMSIGCOMM2001.SanDiego,CA,USA,ACM.2001:149-160[2]J.Cichon,K.Cichon,P.Kobylanski.NodeEvaluationintheChordP2PSystems.FourthInternationalConferenceonDependabilityofComputerSystems,6/30-7/2,2009:168-175[3]熊伟，谢冬青，焦炳旺，刘洁.一种结构化P2P协议中的自适应负载均衡方法.软件学报.20(3),2006:660-670[4]戴彬，王芙蓉，刘见.一种基于邻居路由表的Chord改进算法.华中科技大学学报（自然科学版）.37(2),2009:49-52[5]邱仲潘.JAVA网络编程指南.电子工业出版社.[6]ZhaoBenY,KubiatowiczJ,JoscphA.D..Tapestry:aninfrastructureforfault-tolerantwide-arealocationandrouting.TechnicalReportUCB-CSD-OI-I141,U.C.Berkeley.April2001.[7]彭丽媛，刘杰，赵霞，许庆平.结构化P2P网络Chord算法研究.北京工商大学学报(自然科学版).2008,26(2):59-62[8]邱彤庆，陈贵海.一种令P2P覆盖网络拓扑相关的通用方法.软件学报.2007,18(2):381-390[9]Che-LiangLiu;Chih-YuWang;Hung-YuWei.MobileChord:EnhancingP2PApplicationPerformanceoverVehicularAdHocNetwork.DGLOBECOMWorkshops,2008IEEE.2008,30(4):1-8[10]Cichon,J.,Cichon,K.,Kobylanski,P..NodeEvaluationintheChordP2PSystems. FourthInternationalConferenceonDepCos-RELCOMEX'09.2009,6:168-175[1]罗杰文.PeertoPeer(P2P)综述.中科院计算技术研究所网站http://docs.huihoo.com/p2p/1/index.html.2005,3(11)[2]李红玉.基于Chord协议的P2P网络模型及其搜索技术研究[D].中国优秀硕士学位论文全文数据库,2007,(05) 指导教师意见签名：月日教研室（学术小组）意见教研室主任（学术小组组长）（签章）：月日院（系）意见院长（教学主任）（签章）：月日