英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
云计算中多资源采购的组合拍卖机制
G. Vinu Prasad，Abhinandan S. Prasad，IEEE会员，Shrisha Rao IEEE高级会员
摘要 - 在混合云计算中，云用户有能力从多个云供应商处获得资源，并且还可以选择不同的资源组合。 从许多云供应商之一采购单个资源的问题可以模拟为标准的赢家确定问题，并且在给定不同的QoS（服务质量，指一个网络能够利用各种基础技术，为指定的网络通信提供更好的服务能力, 是网络的一种安全机制， 是用来解决网络延迟和阻塞等问题的一种技术。）和定价参数的情况下存在用于单个项目资源采购的机制。 然而，没有兼容的方法可以让云用户从云供应商购买任意捆绑的资源。 我们设计CA（组合拍卖）算法来解决混合云中的多资源采购问题。 云用户提交他们的要求，然后供应商提交包含价格，QoS及其提供的资源集合的出价。 这种方法是可扩展的，鉴于有大量的云供应商，并且持续出现，这是必要的。 我们使用各种标准分发基准（如随机，统一，衰减和CATS(时间序列协整分析)）对CABOB算法进行采购成本和可扩展性功效实验。 使用我们的方法进行模拟，使用从多个云供应商的数据集中采购的价格显示其在多个资源采购中的有效性。
索引术语 - 云计算，组合拍卖，云代理，动态定价，线性规划，资源分配。
1.介绍
云计算是通过互联网提供服务的流行范例[1]，[2]。 目前，亚马逊，salesforce.com，3Tera等许多公司都提供云服务。 这些云供应商通常遵循固定的定价策略。 考虑例如想要在云上以计算平台（PaaS）的形式使用服务的用户。 有些云供应商以不同的价格提供该应用程序的版本，并且具有不同的服务质量（QoS）参数。云用户根据使用情况收费，但不按照从服务派生的价值收费。 这种方法有其局限性; 例如，考虑到大量可用于提供与特定类型资源相关的服务的云供应商，它不能提供最好的服务[3]。
大多数云供应商使用现收现付或固定定价模式。 许多供应商不会谈判合同，可能是因为缺乏对动态定价的基础和益处的理解。供应商提供的任何默认协议都可能会使供应商而不是用户受益，从而导致与用户需求不匹配[4]。 另外，服务级别协议（SLA）通常没有明确的承诺[4]。 动态定价是解决这些问题的方法[5]。 因此，从用户的角度来获取资源是一个重要和有趣的问题。
目前与固定价格相关的一些问题是：
bull; 通常，资源采购合同有利于云供应商。可能有些地方云供应商和云用户的需求是不匹配的[4]。
bull; SLA（服务等级协议）对于企业客户来说是一个非常重要的方面，但在给定固定价格的情况下实施SLA是非常困难的[4]，[5]。
动态定价[6]，[7]克服了这些问题。 动态定价在云计算中的应用是一个有趣但尚未开发的领域[8]。
资源采购是在互联网上面临的一个重要挑战，特别是在大型分布式系统如网格，云计算等领域。资源分配是网格研究的一个非常活跃的领域[9] - [12]。
资源采购可以使用传统或经济模式完成。 传统模型[13] - [15]假设资源提供者是非战略性的（不是寻求利润最大化），而经济模型则假设资源提供者是理性的和智能的。 在传统方法中，用户支付所消费的服务。 在经济模型中，用户根据服务的价值付款。 因此，经济模型在云计算环境中更为合适。
经济模式的主要优势是向参与者分配奖励。 但有些情况下参与者可能无法如实行事。 因此，我们假设云供应商是自私和理性的。 此外，云代理代表云用户执行反向拍卖[6]\
随着对云资源需求的增加，特别是对于需要多种资源的复杂任务，云服务提供商与云用户之间的分歧范围有所扩大。 这导致了双方之间无效的交易，这反过来导致云资源的次优使用。 我们提出采用组合拍卖和机制设计的资源采购方法来解决这些问题。
我们的工作是对Prasad和Rao的扩展[8]，其中提出了几个云供应商在单一资源拍卖中竞标的云代理进行资源分配的机制。 他们完成的工作是在任何给定的情况下采购单一资源。 Prasad和Rao假设云用户一次请求单个资源，并且赢得拍卖的供应商提供该资源。 然而，在实践中，云用户可能需要单一供应商可能无法提供的资源组合，这个问题在[8]中没有考虑，它没有解决用户如何可能需要几个资源在一起的问题而不是一次一个），以及供应商如何使用资源组合进行投标而不是提供单一资源。
为了解决这些问题，我们考虑了多个云供应商在任何时候都考虑进行拍卖的多种资源。 多资源分配是一个组合拍卖问题，它与混合云计算具有特别的相关性，目前很少有人探索，但被认为是未来重要的[17]。
在真实系统中，云供应商和云用户都不会预测需求。 因此，也存在价格不确定性。 Bichler等人 [18]指出，商品价格的不确定性以及对市场参与者的了解很少，这是动态定价的障碍。 拍卖在这种情况下特别有用[18]，[19]。
我们提出了一种基于组合拍卖的算法来实现混合云中的动态定价。 我们的算法CABOB（投标组合拍卖部门）负责处理这一问题，重点关注时间复杂性而不是激励相容性。 CABOB允许动态定价，并且不提前预留资源，这可以克服其他地方出现的缺点[20]。 获胜者的决定可以缩小到标准的组合拍卖问题之一，并且我们的工作中会部署一个这样的缩放比例。
我们使用三种资源执行组合拍卖，即RAM，存储和CPU功率。 我们的研究结果表明，在连续拍卖中，随着要采购的资源数量的增加，每个资源的成本会相应增加。 在组合拍卖的情况下，随着要拍卖的资源数量的增加，组合拍卖机制为所请求的一组资源提供最佳价格。
由于我们建议使用我们方法的领域是云计算，因此我们方法的可扩展性是一个突出问题。 我们分析了使用随机，统一，衰减和CATS分布来扩展我们的方法以满足大量用户需求的实施时间效率[21]。 我们用Sandholm [22]提出的参数进行了模拟，并记录了结果。 我们在云计算方面的主要优势在于它具有高度的可扩展性和非常快的赢家决心。 赢家决心所用的时间是O（| V | | E |）的顺序。
在联合云或混合云[17]中，用户拥有选择从不同的云供应商那里选择所需的资源，而云供应商则需要彼此协调。 因此，采购模块 -在这种情况下，[8]中介绍的ule不适用。 在我们的案例中，云用户可以选择将资源作为来自不同云供应商的一组项目进行采购。 因此，组合拍卖适合这种情况。
在组合拍卖中，获胜者的决定是一项不平凡的任务[23]。 在真正的云系统中，预计也会有大量的云供应商。 因此，设计用于在云中执行组合拍卖的可扩展解决方案是重要且有趣的。
这组出价被表示为树节点。 树节点被标记为赢或输。 该树使用深度优先搜索进行搜索。 使用启发式，计算未分配项目的贡献。 这种贡献以及从出价中产生的收入用于决定是否在一组最佳解决方案中包含出价。
在将出价提交给CABOB算法之前，我们会执行预处理步骤以规范由云供应商生产的出价。 通过这样做，每个出价都有与每个正在竞标的资源相关的整数值
在最初的步骤中，资源集被划分，使得没有出价会包括来自多个子集的资源。 每个子集中分别确定获胜者以加速搜索。 CABOB使用未分配资源可贡献的收入上限。 如果当前的解决方案并不比最佳解决方案好，CABOB会修剪搜索路径。 我们使用线性规划（LP）公式来估计上限。 估计上限后，我们应用整数放宽，我们可以完全接受出价，或完全拒绝出价。
我们的部署使最终用户能够自动执行多个资源选择过程，并对大量资源请求进行扩展。 我们的工作可帮助云代理商确定可为用户请求提供服务的最佳云供应商。 迄今为止，云中智能资源分配的这一方面没有得到很详细的探讨，而我们的第一个努力就是实现这一目标。 我们考虑来自不同云供应商的云资源产品，并倾向于相信未来可能会出现供应商之间的标准化和互操作性，如Rochwerger等人所建议的那样。 [17]。
CloudSim [24]是一个众所周知的云应用程序仿真工具，但它不支持拍卖协议[25]。 因此，我们使用基于用户请求的标准云供应商数据集[26]实施了所提议的方法，并且发现云计算中组合拍卖的赢家确定可以通过最大化云供应商的利润来实现，同时提供向最终用户提供所需资源的最佳出价。 我们的工作也为终端用户提供了奢侈品，他们只需要把他们的资源请求放在一边，而不用担心获取他们的机制。云代理在混合云环境中执行拍卖，并以最佳的价格和服务质量(QoS)向最终用户提供所请求的资源
本文的其余部分安排如下。 第2节简要介绍了在这方面完成的背景工作。 第3节描述了我们工作中采用的系统模型。 第四部分阐述了采用的云计算组合拍卖机制。 第5节讨论了所提出模型的实现和准确性以及效率，我们在第6节结束。
2. 相关工作
2.1网格和云中的资源分配
资源分配是当今互联网的一个重要挑战，尤其是在像电网，云等大型分布式系统中。资源分配是电网研究中一个非常活跃的领域[9] - [12]。 这些资源由公司所有，主要分布在地理上。 资源分配算法可以是集中式的，也可以是分散式的。 集中式算法[13] - [15]需要全局知识和实时信息，这对于大多数大型分布式系统来说是不切实际的。 集中式算法的成本模型根据资源的使用情况获得成本。
资源分配的经济模型采用分散算法。这些模型基于用户从服务获得的价值而派生出成本[12]。大多数基于经济模型的资源分配算法都依赖于单一市场机制。Vilajosana等[27]开发了一个可配置的拍卖服务器，它提供了动态配置市场的能力。Buyya等[12]利用商品市场、发布价格等经济模式，开发资源管理的网格资源代理。
Lin等[28]使用动态拍卖(基于Vickrey拍卖)来执行资源分配。云用户竞拍资源，出价最高者赢得拍卖。赢家支付第二高的价格。Zaman和Grosu[29]设计了一种基于拍卖的机制，在虚拟机配置过程中基于用户需求执行动态虚拟机配置和分配
2.2 组合拍卖
Parsons等[16]对拍卖理论进行了全面的介绍，包括各种类型的拍卖、其特点及其在计算中的应用。
组合拍卖是一种拍卖，其中拍卖人对物品组合进行投标，而不是像传统拍卖那样对单个物品进行投标。 Vohra和Vries [30]调查了有关组合拍卖设计的艺术状况，并讨论了整数编排组合拍卖所需的编程。 不幸的是，组合拍卖在一般情况下是一个N P完全问题。 藤岛等人提出两种处理一般情况的方法。 在第一种方法中，搜索空间被构造为使得深度优先搜索（DFS）避免了出价冲突。 这种方法减少了运行时间。第二种方法是基于市场的启发式方法，其中虚拟代理为虚拟多轮拍卖中的每个商品投标。 Hoos和Boutilier [31]提出了一个随机局部搜索算法来解决组合拍卖。 Nisan [32]不仅使投标语言形式化，而且比较了他们的优势。 他还证明，如果价格附加到拍卖中的单个项目，线性规划方法会导致最优分配。
Sandholm [33]可能是第一个在组合拍卖中胜出的重要作品。他提出了一种通用算法，允许组合拍卖比之前的方法获得更大数量的项目和投标，比之前的方法更容易获得优胜者的确定[34]，这是因为在实践中，投标的空间很少。这也说明了一个事实，即基本的组合拍卖只允许投标者表达物品的互补品。
Sandholm和Suri [35]提出了一种分配出价以确定组合拍卖优胜者的算法。 该算法也被称为“BOB”算法。 在BOB算法中，出价被表示为树节点，并且在该树上执行DFS以确定胜出者。 不幸的是，BOB算法的基本形式并不容易实现。 所以Sandholm等人 [22]建议BOB的改进版本称为“CABOB”算法。CABOB是组合拍卖中赢家确定最快的最佳算法之一。
3.系统模型
我们的系统模型基于Prasad和Rao [8]。 云用户具有资源需求。 用户希望对采购资源进行逆向拍卖（也称为采购拍卖），这实际上是由云代理来完成的，以减轻用户的负担。 云供应商已准备好提供资源。 云用户的目标是最大限度降低采购资源的总成本，而不会影响所寻求的服务质量。 为了降低采购成本，云用户有必要了解云供应商的真实成本。
云用户向云代理表明他们的需求。 云代理将这些要求的信息传递给所有云供应商。 云供应商根据这些信息决定是否参与拍卖。 并在参与时提交出价。 我们假设云供应商是理性和智能的，因为他们可能会以虚假估价出价以最大化他们的效用。
云供应商由N ={1,2，hellip;，N}表示。在这次采购拍卖中，每个云供应商都以出价的方式来回应，并承诺k QoS属性qi1,qi2，hellip;，qik。我们将QoS属性规范化，让qi成为ith云供应商的规范化QoS值。
拍卖师有一组资源，M ={1,2，hellip;,m },采购。让Bi i云供应商的报价和Bi =溪,pi;,qii Sisube;M是一组云供应商所提供的资源。
其中一个重要的假设是，在组合拍卖中，如果最终用户以较低的费率与期望的服务质量相比获得单独获取资源的投标组合，则他倾向于参与投标，即使他可能没有得到他所要求的全部资源。
同样，从云供应商的角度来看，如果云供应商可以通过以期望的速率和期望的QoS包含更多资源来出售更多的资源，它就会继续使用这些资源进行出价，并保留剩余的资源以使其利润最大化，是投标费用加上剩余所有剩余资源成本的总和。 有了这些假设，云经纪人就可以继续执行竞标，以确定在拍卖中获胜的一组云供应商。 在现实世界中，有非常多的云供应商提供不同的资源。 因此，总的资源组合也很庞大。 同时，近乎实时地确定赢家非常重要（因为云用户不太可能接受延迟采购）。
3.1 QoS缩放
该模型的QoS扩展方面也来自Prasa
全文共14004字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[14781]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
