节点负载度的均衡控制算法研究PPT课件.ppt

P2P网络中负载平衡与控制算法研究 1 内容提纲 前言 内容摘要 基本概念 论文思想 仿真与结论 2 前言 3 P2P并不是一个新的概念 早在1969年因特网的前身ARPANET刚出现的时候 网络的应用模式就是P2P ARPANET的最初目的是在全美国范围内共享计算机资源 其所面临的挑战是如何集成当时各种不同的网络 使之成为一个通用的网络 并且使得各个主机成为网络上平等的成员 ARPANET是以一种平等的计算Peer的方式把这些计算机系统连接起来 而不是用Master Slave或者是Client Server的方式连接 由于文件共享和即时聊天等P2P应用程序的成功 越来越多的程序员在因特网上开发他们的P2P程序 越来越多的用户在使用P2P应用程序 4 内容摘要 本文首先介绍了P2P网络的定义 P2P技术的特点 P2P与C S的区别以及P2P技术应用现状等基本概念 然后在主要内容中 解释了集散节点的形成原因 由集散节点的问题引出解决该问题的资源调度策略 然后分类阐述了现有的解决集散节点问题的资源调度策略 如激励机制 博弈论 经济模型和蚁群智能算法 本文主要论述的资源调度策略是基于拓扑结构重构的资源调度策略 通过控制网络的拓扑结构来解决集散节点的问题 最后通过建模和仿真实现基于拓扑结构重构的资源调度策略 5 基本概念 P2P与C S模式的区别 6 P2P网络的概念与定义 P2P即peer to peer 而peer在英语里是 地位 能力等 同等者 同事 和 伙伴 的意思 这样一来 P2P也就可以理解为 伙伴对伙伴 的意思 或称为对等联网 7 P2P技术特点 非中心化 Decentralization 可扩展性 scalability 健壮性 Robustness 高性能 价格比 HighPerformance prices 8 搭便车与集散节点的产生 所谓搭便车是指对等网络中的节点仅从系统中获取其它节点提供的服务 而不为对等网络作贡献的行为 正是因为有了一些自私节点的存在 才使得一些 奉献节点 沦为了集散节点 9 P2P网络负载平衡现状及控制方法 1激励机制2博弈论的方法3社会网络和经济模型 10 2019 12 30 11 论文思想 12 基本概念 负载度 全局负载均值 轻 重载结点 本文是通过将结点负载度与此时的全局负载均值作比较来进行判别的 若前者大 则点为重载结点 否则为轻载结点 节点负载偏差 网络负载偏差 13 负载平衡算法思想在某一时刻 若P2P网络中结点的负载度大于此时网络总负载度的均值 就将其定为此时的重载结点 若此时有结点向结点发出文件请求 重载结点首先搜索下备用结点表 若能找到含有的备用结点 则直接将这一请求负载向备用结点转移 假如重载结点之前并未建立关于的备用结点 然后从结点出发 搜索与它相连并含有文件的结点 最后在所有返回的结点中挑选出负载度最小的两个结点 作为结点中关于文件的备用结点 当然可能出现结点无法找到备份结点或者找出的备份结点也均是重载结点而无法转移请求负载的情况 这时从结点已找到的备份结点起再寻找与备用结点相连并含有文件的结点 依次进行下去 直到找到可供转移的轻载结点 若最后在TTL之内仍然未找到 就返回查找失败信息 14 负载平衡算法实现 1 确定重载结点算法2 寻找备份结点并建立二叉树结构算法3 结点连接算法 15 实验与仿真 16 实验与仿真 17 参考文献 1 LIZhen Hua CHENGui Hai QIUTong Qing PartitionNodes Topologically CriticalNodesofUnstructuredPeer to PeerNetworks JournalofSoftware Vol 19 No 9 September2008 pp 2376 2388 2 ParetoOptimalRedistribution HaroldM HochmanandJamesD Rodgers TheAmericanEconomicReview Vol 59 No 4 Part1 Sep 1969 pp 542 557 3 GeZH FigueiredoDR JaiswallS KuroseJ TowsleyD ModelingPeer2PeerFilesharingsystem ProceedingsoftheIEEEINFOCOM2003 SanFrancisco 2003 18822198 4 QiuDY SrikantR ModelingandperformanceanalysisofBitTorrent2likePeer to Peernetworks ProceedingsoftheSIGCOMM2004 Portland 2004 3672378 5 VecianaGd YangXY Fairness incentivesandperformanceinPeer to Peernetworks ProceedingsoftheForty FirstAnnualAllertonConferenceoncommunication ControlandComputing Monticello 2003 6 SRatnasamy PFrancis MHandley etal1Ascalablecontentaddressablenetwork C 1SIGCOMM2001 SanDiego CA USA 2001 7 Stoica RMorris DKarger etal1Chord Ascalablepeer to peerlookupserviceforInternetapplications C 1SIGCOMM2001 SanDeigo CA USA 2001 8 ARowstron PDruschel1Pastry Scalable distributedobjectlocationandroutingforlarge2scalepeer2to2peersystems C Int ConfonDistributedSystemsPlatforms Middleware Heidelberg Germany 2001 9 BYZhao LHuang JStribling etal1Tapestry Aresilientglobal2scaleoverlayforservicedeployment J IEEEJournalonSelectedAreasinCommunications 2004 22 1 41 53 10 SSaroiu PKGummadi SDGribble1Ameasurementstudyofpeer to peerfilesharingsystems C 1MultimediaComputingandNetworking MMCN SanJose USA 2002 11 AdarE HubermanB FreeridingonGnutella FirstMon day 2000 5 10 32 35 12 KrishnanR SmithMD TangZL TelangR Theimpactoffree ridingonPeer to Peernetworks Proceedingsofthe37thHa