分布式应用程序到多个云佩德罗·保罗·德索萨·本托·达席尔瓦引用此版本：佩德罗·保罗·德·苏扎·本托·达席尔瓦。将分布式应用程序映射到多个云上。分布式、并行和集群计算。里昂大学，2017年。英语NNT：2017LYSEN089。电话：01708420HAL Id：tel-01708420https://theses.hal.science/tel-017084202018年2月13日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire全国论文集编号：2017LYSEN089里昂大学博士学位论文歌剧l’EcoleEcoleDoctoraleN° 512里昂信息与数学博士学校Spécialitédedoctorat：InformatiqueSoutenue publiquement le 11/12/2017，par：佩德罗·保罗·德索萨·本托·达席尔瓦分布式应用程序到多个云的映射Contributionsauplacementd'applicationsdistribuéessurmulti-clouds陪审团组成如下：波尔多因里亚研究主任特别报告员帕斯卡尔-斯托夫Blagnac国际大学联合会主任ELMROTH，ErikMesseur，Umén大学，Suède ExaminateurMORIN，Christine DirecteurdeRechercheInriaRennesExaminatricePEREZ，Christian DirecteurdeRechercheInriaGrenobleRhône-AlpesDirecteurdethèse弗雷德里克·德斯普雷因里亚·格勒诺布尔Co-encadrantdethèseiii鸣谢/Agradecimentos首先，我要感谢我的顾问Christian Perez和Frédéric Desprez，他们帮助我克服了这一科学旅程中的许多障碍我还要向评审团成员Christine Morin、Patricia Pascal-Stolf、Emmanuel Jeannot和Erik Elmroth表示最深切的感谢，我还要感谢本论文的审稿人Emmanuel Jeannot和Patricia Pascal-Stolf花时间阅读和评估本文，并与我分享他们非常重要的评论。这是一个愉快的经验，工作在LIP和在Inria所有这些年。我非常感谢提供的支持和基础设施，使我能够发展我的研究，并参加许多会议和研讨会。显然，如果没有LIP的助手Evelyne Bleslé、Marie Bozo、Chiraz Benamor、Laetitia Lécot、SylvieBoyer 、 Catherine Desplanches 和 Nelly Amsellem ， 以 及 （ 前 ） 工 程 师 LaurentPouilloux、Simon Delamare、Mathieu Imbert、Jean Christophe Mignot、Serge Torres和Dominique Ponsard组成的团队，这一切都不可能实现我也要感谢所有来自LIP的博士生。特别是，我要感谢那些成为亲密朋友的人，与他们分享了许多快乐的时刻（最终也有一些不那么快乐的时刻）。我开始感谢所有幸存下来与我分享同样经历的人。特别是，我要感谢ViolaineVV，Liovaine LV和Radu Carpa。感谢Violaine VV，我最亲爱的同事，2年之久，“Palme d 'or des Co-Bureau”的持有者，无论何时我需要，基本上，从第一天起，你就几乎帮了我所有的忙：搬家（是的，复数），电子邮件和报告审查，行政研究，滑雪板等。非常感谢，VV！！我还必须感谢Radu，感谢他与我就算法思想、Linux管理（不完全是讨论，因为他是个该死的黑客）和存在主义困境进行了长时间的讨论。也感谢您在里昂1号的教学中给予我的所有行政帮助。 我希望有一天我们能克服在比特币便宜的时候没有买比特币的问题。感谢Liovaine LV，为所有的私人法语课程和抱歉是这样一个坏学生。希望我现在有一个足够好的法国Laurent Pouilloux，感谢你教我如何开发一个运行我的经验的体面的环境，并向我介绍GridMarcos Assunção，感谢所有专业，哲学和存在主义的讨论。也非常感谢您对我所有的文章和本文的文本进行了审阅和修改。奥雷利安·卡维兰和马鲁阿·马雷杰，感谢你们和我一起参加这次会议-iv“Journée des Doctorants du LIP 2016”的组织委员会。这是一次非常好的经历。Fabrice Mouhartem，感谢您帮助保持博士研讨会的活力！安东尼，谢谢你给我介绍了法国音乐的“不可征服”。当我Helène Coullon，非常感谢您的讨论和建议！让我们拥抱布列塔尼！感谢Alexandre提供的关于流处理的所有有趣的相关工作，并抽出时间与我讨论谢谢你，奥瑞莉，谢谢你给我做的美味的奶奶做的杰德，谢谢你同意和我一起穿越法国搬家！再一次，让我也想感谢我在论文中遇到的许多了不起的人在里昂国立科学院的大门外。感谢Simon，Cécile和Gessel一直在那里，为美妙的旅行，烧烤和晚会！感谢我的邻居Ton-ton-thony和Seb，为我举办了许多野餐和晚会！芭芭拉，能再次和你分享同一个城市真是太酷了Adelha，Mayroquera，M，DJ Rodragson，Renata，Tiago，Rafa和Lina，感谢您举办的许多“voz e violão”派对，讨论和旅行。主要是，谢谢你的友谊和在那里！Christophe，Fanny，Pierre，Antoniette和Mo，当然，我不能忘记感谢那些留在巴西的老朋友（但他们仍然在我的生活中），以及四年后我在法国再次遇到的人我的高中朋友从CEFET-SP，谢谢你帮我保持道德！另外，感谢你在我的巴西之行中抽出时间陪我！爱你们“Caravana da Depressão”不会被遗忘！谢谢你Dani Mingatos（你今天喝了CBB吗？），Leo Takuno ，Renato Ramalho ，Cris Ikenaga ，Fábio Franco ，AndersonBorbulhas e Marcelo Hashimoto！Mylena和D.蒙塔纳，谢谢你一晚上的哲学和存在主义讨论！感谢您发送编修。卡琳，我感谢Fábio、Sato和Antoine，让我们在创业界度过了难忘的冒险！我们还有几年时间在35岁之前成为百万富翁，非常感谢Corinne，Arthur，Leonard和De Decker一家，特别是Antoine和Agnès，在我在法国逗留期间，特别是在假期期间，多次收养我。我永远不会忘记2014年的圣诞节！最后，我想感谢我的家人，我的学术生活的这部分案文将以葡萄牙文编写v第一次，我和佩德罗和玛琳在一起的时候，我的朋友们都很高兴，因为我的孩子们很重要，我很想和他们在一起。我非常喜欢你的成绩，但我不认为你有能力让那些不合格的教育者学习。我们要做的是让你的声音通过，让你的声音消失。我的舞伴是Luana和Mayra。我对纳塔莉亚特别有好感，因为她总是为我这样的孩子做榜样。你的学习和奉献总是给我灵感。Estendo（REF）meu agradecimento à todos os os os membros dafamília Souza，aos meus queridos tios e tias，primos e primas.我对马利的印象特别深刻，因为我是法国的第一位教授，我打算让他去法国。我们不能在第一和第二、第一和第一的时候就开始跳舞一家人的便当。特别是，我想知道Fia、Rosa和Márcia的名字，他们是Carinho的虚拟人，他们希望我经常去巴西，因为他们总是把我安排在巴西。因此，我必须特别向我的瓦纳公司表示感谢，因为我的第一步是向我表示支持和 鼓 励 。 Obrigado por responder com amor e companheirismo os meus frequentesepisódios de ausência，mau humor e frustação.我希望能和大田的家人一起，特别是和初代夫人和多娜·帕科夫人一起，因为我一直都觉得自己是这些家庭的一部分。vii摘要云已经成为部署分布式应用程序的一个非常流行的平台如今，几乎任何信用卡持有人都可以访问云服务。向客户提供云服务有许多不同的方式在这篇论文中，我们特别关注的基础设施即服务（IaaS），一个模型，通常，提出了虚拟化的计算资源，以虚拟机（VM）的形式向客户。由于其具有吸引力的按使用付费模式，客户（特别是中小型公司）更容易将托管基础设施外包，并节省与前期投资和维护成本相关的费用此外，客户可以访问可扩展性、可用性和可靠性等功能，这些功能以前几乎是大公司独有的。要将分布式应用程序放在云上，客户必须首先考虑其应用程序（或其部分）与目标基础设施之间的映射。 她需要考虑成本、资源和通信限制，从私有云和公共云提供商中选择最合适的虚拟机集。 然而，在大规模或时间受限的场景中，手动定义映射可能是一个挑战，因为可能的配置数量激增。市场上的云提供商数量庞大，以及在不同的云站点上部署应用程序的最终优势，例如冗余和可达性，使这一挑战变得更加复杂。此外，当自动化映射定义时，必须考虑可扩展性问题，因为这个问题是图同态问题的推广，这是NP完全的。在这篇论文中，我们解决的问题，计算初始和reconfiguration的地方，为分布式应用程序在可能的多个云。我们的目标是在满足应用程序的资源和通信限制的同时，最大限度地减少租用和迁移成本我们专注于应用程序和云基础设施之间的映射。使用增量的方法，我们将问题分为三个不同的部分，并提出了高效的算法，可以计算出良好的质量放置非常迅速的小型和大型的场景。首先，我们建模的问题作为一个通信不经意的问题，并提出向量包装的算法能够计算初始布局的解决方案。然后，我们通过引入通信约束扩展了我们的应用和基础设施模型，并提出了一种基于图同态的启发式算法来计算初始布局解决方案。在最后一部分中，我们将应用重构引入到我们的模型中，并提出了一个能够计算通信和重构感知的布局解决方案的启发式算法。这些算法已经针对最先进的方法（如MIP求解器和元算法）进行了广泛的评估。我们通过模拟表明，拟议的算法可以在几秒钟内计算出解决方案，而这需要花费数小时或更长的时间。viii用其他方法计算。ix简历Le Cloud est devenu une plate-forme très répandue pour le déploiement 今天，一张银行卡的虚拟化可以通过云提供的服务来实现。De plus en plus d'enterprises peuventsous-traiter leurs infrastructures d'hébergement et ， ainsi ， éviter les dépensesd'investissements initi- aux en infrastructures et de maintenance.尤其是，许多中小企业都面临着类似于通过l'échelle、la disponibilité和la fiabilité等功能的挑战，这些功能在云计算之前就已经为大型企业提供了服务。Son modèle attractif de coffetsLes services du Cloud sont o campaign aux utilisação de plusieurs facons.在这一点上，我们将重点放在服务形式下的基础设施模式上。Ce modèle permet aux utilisa-d'accéderPour placer une application distribuée sur le Cloud ，un client doit d'abord définirl'association entre son application（ou ses modules）et l'infrastructure. Il est nécessairede prendre en considération des constraintes de cobalt，de resources et de communicica-tion pouvoir choisir un ensemble de MV propioned d'opérafficient de Cloud（云提供商）publiques et privés le plus adapté.尽管如此，由于可能的配置名称，云的众多操作以及与云的多个站点上的应用程序分发相关的位置的优势，就像冗余和可访问性一样，这是一个巨大的挑战在外部，为了使该过程自动化，可以不使用关联算法的过程。因此，le problème de calculer une association entre uneapplication et une infrastructure est une generalisation du problème de homomorphismede graphes，qui est NP-complet.在这篇论文中，我们讨论了初始位置计算的问题et de recon figuration pour desapplications distribuées sur potentiellement de multiple Clouds.其目的是尽量减少地点和移徙的影响，以满足资源和通信的限制。为此，我们利用一种递增的方法，将问题分为三个方面，并提出了计算小、大屏幕放置质量良好的位置的可行性建议。首先，我们对无通信布局问题进行了建模，并提出了基于向量填充算法的布局模型xpour calculer des solutions de placements initiaux.第二，我们将介绍通信约束的应用和基础设施模型，并提出一种基于图的同态算法的算法，用于计算通信初始位置的解。第三，我们介绍了应用程序的重构概念，并提出了一种能够计算这些哲学家的价值观与精确解算者和元哲学家的艺术方法相比较。我们的montrons en utilisant des simulations que les proposées parviennent à calculer dessolutions de bonne qualité en quelques secondes tandis que des autres approchesprennent des heures voir des jours pour les calculer.Xi内容1介绍11.1应用程序的挑战。. . . . . . . . . . . . . . . . . .11.2动机：云计算。 . . . . . . . . . . . . . . . . . . . . . . .31.3目标。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41.4解决问题的方法 . . . . . . . . . . . . . . . . . . . . . . . . . .41.5捐款. . . . . . . . . . . . . . . . . . . . . . . . .51.6出版物和通讯。 . . . . . . . . . . . . . . . . . . . . .51.6.1同行审查会议。. . . . . . . . . . . . . . . . . . . . .51.6.2研讨会演讲（特邀演讲）。. . . . . . . . . . . . .51.6.3海报展示。. . . . . . . . . . . . . . . . . . . . . . . . .61.7论文结构. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62 上下文72.1分布式系统. . . . . . . . . . . . . . . . . . . . . . . . . . . .72.2云计算。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .82.2.1定义云 . . . . . . . . . . . . . . . . . . . . . . . . .82.2.2部署模型。. . . . . . . . . . . . . . . . . . . . . . . . .92.2.3服务模式。. . . . . . . . . . . . . . . . . . . . . . . . . . .92.2.4IaaS回顾102.2.5容器122.2.6云基础设施132.2.7讨论142.3分布式应用142.3.1基于代理的软件范例152.3.2基于模型162.3.317份2.4在云上的位置172.4.1在应用程序生命周期182.4.2执行自动布局192.5结论213 问题定义和方法论23Xii3.1目标和问题定义233.1.1分布式应用233.1.2基于云的基础设施243.1.3安置25内容3.2办法283.3评价方法303.3.1战略303.3.2实验303.3.3基线算法323.3.4评价报告323.4结论324 初始成本意识安置334.1一.导言. 334.2问题陈述334.2.1优化问题公式化344.3相关工作354.3.1多维装箱问题364.3.2基于精确算法364.3.3基于元启发式的策略374.3.4基于贪婪启发式的374.3.5讨论404.4改进的贪婪启发式414.4.1选择贪婪的启发式来适应414.4.2增加成本意识414.4.3异构仓424.4.4第43集Greedy4.5评价464.5.1A.方法464.5.2MIP求解器和模拟退火分析474.5.3贪婪的启发式494.6结论555初始沟通和成本意识安置575.1一、导言. 575.2在多云环境5.2.1问题陈述595.2.2CAPDAMP作为图同态问题605.2.3优化问题公式化605.3相关工作615.3.1精确算法61Xiii5.3.2元分析学625.3.3启发式625.3.4讨论635.4为云基础架构和分布式应用建模645.4.1云网络拓扑645.4.2分布式应用程序通信拓扑655.5两阶段通信感知启发式655.5.1第1阶段：分解66Xiv内容5.5.2阶段2：组成。. . . . . . . . . . . . . . . . . . . . . . .695.5.3 2PCAP算法。. . . . . . . . . . . . . . . . . . . . . . . . .705.5.4讨论。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .725.5.5 2PCAP复杂性。 . . . . . . . . . . . . . . . . . . . . . . . . .725.6例子. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .735.6.1示例1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .735.6.2例2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .745.7评价. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .745.7.1方法。. . . . . . . . . . . . . . . . . . . . . . . . . . . .775.7.2 2PCAP在小问题上的性能 . . . . . . . . . . . . . .785.7.3 2PCAP在大型问题上的性能 . . . . . . . . . . . . . .805.8结论. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .826 通信和成本感知布局与重新配置856.1一、导言. 856.2问题陈述856.2.1分布式应用和云计算模型866.2.2应用程序执行的预计持续时间866.2.3重建规格866.2.4安置目标876.2.5优化问题公式化876.3相关工作896.3.1迁移组件906.3.2迁移成本建模906.3.3讨论. 916.42 PCAP-REC启发式916.4.1应用程序和云模型926.4.293型重组6.4.32 PCAP-REC6.4.42 PCAP-REC算法956.4.52 PCAP-REC复杂度966.5评价986.5.1A.方法. 986.5.2小问题（A类实验）1006.5.3中型和大型问题（B类和C类实验）1006.5.4讨论1046.6结论1047结论与展望1057.1观点1067.1.1不同的用例视角1067.1.2应用程序和约束模型透视图。1077.1.3多目标优化108Xv图目录1.1Web应用程序放置示例。. . . . . . . . . . . . . . . . . . . .21.2布局的一般视图。 . . . . . . . . . . . . . . . . . . . . . . . . .32.1VM和容器环境的比较。.......................................................................................132.2应用程序生命周期。............................................................................................... 152.3简单的基于组件的应用程序162.4基于组件的应用程序162.5Winery17实现的TOSCA拓扑模型2.6“生产/放置”步骤的表示3.1分布式应用和云基础架构模型。.........................................................................243.2假设7的情景示例263.3资源限制问题的例子。......................................................................................... 273.4通信约束问题的例子。......................................................................................... 294.1分布式应用程序在多个云上的初始放置问题。344.2MIP解算器与S.A. -A类-成本距离。...................................................................494.3MIP求解器与贪婪组.............................................................................................. 504.4S.A.与贪婪组-A类-成本距离。...........................................................................504.5S.A.与贪婪组-B类-成本距离。...........................................................................514.6累积S.A.与贪婪组-B类-成本距离。.................................................................. 524.7S.A.执行时间第5 2 集 Greedy Group...................................................................4.8S.A.之间的执行时间比率 第53集Greedy Group...............................................4.9Greedy Group解决方案排名。..............................................................................534.10 Greedy Group54的解决方案5.1通信感知放置示例。..............................................................................................595.2云拓扑和应用程序图645.3布局示例。.............................................................................................................. 675.4完成放置示例#1（参见第5.6.1节）。......................................................... 755.5完成放置示例#2（参见第5.6.2节）。......................................................... 765.6应用拓扑方案。......................................................................................................785.7MIP求解器与2 PCAP............................................................................................. 79Xvi5.82PCAP和SCIP求解器的执行时间之和（以秒为单位）。.............................. 795.9放松CAPDAMP与2 PCAP.....................................................................................805.10 S.A.1与2 PCAP........................................................................................................815.11 S.A.2与2 PCAP........................................................................................................82Xvii图5.12 2PCAP的执行时间。...........................................................................................................................836.1重建安置方案。......................................................................................................886.2应用和云拓扑。......................................................................................................926.3重新配置位置示例。..............................................................................................946.4S.A.1与2 PCAP-REC............................................................................................ 1016.5S.A.2与2 PCAP-REC............................................................................................ 1026.6S.A.3与2 PCAP-REC............................................................................................ 1036.7迁移成本摊销........................................................................................................ 1036.8B类和C类实验的2 PCAP-REC执行时间...........................................................104XVi表的列表2.1Rackspace IaaS服务目录的一部分..........................................................................102.2Amazon EC2的IaaS服务目录的一部分............................................................... 112.3Google Cloud Platform IaaS服务目录的一部分..................................................112.4Amazon EC2的数据传输成本示例.......................................................................123.1实验类参数示例。..................................................................................................313.2维的数据生成间隔示例......................................................................................... 314.1公式4.1中使用的变量总结。................................................................................364.2首次拟合窗口化多容量40的秩匹配示例4.3体验课。................................................................................................................... 474.4数据生成间隔474.5greedy economistics54的执行时间4.6贪婪集团潜在的成分。......................................................................................... 555.1本节和公式5.2中使用的变量总结。................................................................... 615.2实验班参数............................................................................................................... 775.3尺寸数据生成786.1公式6.2中使用的变量总结。................................................................................896.2问题类及其参数。..................................................................................................986.3尺寸数据生成99XVii算法列表1模拟退火212首次拟合递减383在算法2中调用函数赋值384首次拟合递减优先级435点积446首次拟合窗口化多容量4572PCAP718计算9692 PCAP-REC（突出显示算法7的差异）97
我的内容管理
展开
