容错网络的资源配置算法研究

《容错网络的资源配置算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得云津互些丞鲎或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。学位论文作者签名：王旭签字日期：知心年3月1日学位论文版权使用授权书本学位论文作者完全了解云洼王些太堂有关保留、使用学位论文的规定。特授权云洼王些太当兰可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印

2、或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。(保密的学位论文在解密后适用本授权说明)学位论文作者签名：王旭新繇获肋)签字日期：知心年3月7日．签字日期：2口“；弓,El7日万方数据学位论文的主要创新点一、从提高客户服务质量角度考虑，提出了一系列快速的副本放置和更新算法：1)最大重用算法，2)请求覆盖算法，3)局部最优算法，4)禁忌搜索算法。在保证较低的网络运行和更新成本的同时，大大降低了客户获得所需服务的响应时间。实验结果表明，本文提出的时间复杂度最高的禁忌搜索算法与已有的动态规划算法相

3、比，在运行时间上提升了87．97％。二、从整个网络的容错性考虑，在设计副本放置和更新算法时，将服务器故障的情况纳入考虑中。当网络中的某些服务器出现故障后，客户的服务质量仍然能够得到保障。三、从整个网络的稳定性考虑，针对部分客户请求数发生变化的情况，提出了局部更新算法。局部更新算法可以保证数据访问请求没有发生变化的客户受到较小的影响，从而在减少更新时间、确保服务质量的同时，增强了网络的稳定性。万方数据摘要网络信息资源与经济资源一样，只有通过运用一定的管理手段对其进行合理配置，才能最大限度地为人类提供服务。为了提高网络性能，通常将同一数据的

4、多份副本分布在网络的不同节点处，从而提高数据的可用性，降低访问延迟，实现负载均衡。网络中的副本放置问题是国内外学术界较为关注的一个研究领域，并且已经产生了一些重要的研究成果，然而对于副本更新问题的研究却并不充分。本文针对网络中的副本放置和更新问题提出了一系列算法，并且在算法设计的过程中，考虑网络的容错性。为了保障客户服务质量，降低服务请求的响应时间，本文提出了四个快速的副本更新算法：1)最大重用算法，2)请求覆盖算法，3)局部最优算法，4)禁忌搜索算法。其中，时间复杂度最高的禁忌搜索算法与已存在的动态规划算法相比，执行时间加速了87．9

5、7％，同时，整个网络的运行和更新成本不超过最优解的2．49％。当网络中的服务器节点出现故障时，最大重用算法，请求覆盖算法和局部最优算法均能够在线性时间内快速对网络中的副本进行重新部署，以保证整个网络有效运行。对于网络中部分客户的请求数发生变化的情况，本文提出了局部更新算法。在局部更新策略中，仅对变化的客户重新配置副本，减小对其他客户及服务器的影响。当网络中10％的客户请求发生变化时，实验结果表明该算法可在O．01秒内得到新的可行解，且额外代价不超过最优解的2．25％。关键字：树形网络；副本；更新策略；算法；禁忌搜索万方数据Abstrac

6、tNetworkinformationresourceiSsimilartotheeconomicresourceinsocietyresource．TheinformationresourceCallprovideserviceforhumanbeingsthroughacertainmanagemem．Inordertoimprovethenetworkperformance，itusuallycopiessomereplicasofthedataobjectandplacesthereplicasinthenetwork，SOas

7、toimprovetheavailabilityofdma，reduceaccesslatencyandloadbalancing．Thereplicaplacementproblemisoneoftheimportantresearchtopics，andithasproducedsomesignificantresearchresults．Inthispaper,weproposesomealgorithmstosolvethereplicaplacementanditsupdatingproblem．Inaddition，thef

8、aulttoleranceisconsideredforthenetwork．Inordertoensurethequalityofserviceandreducetheresponsetime，weint