云计算环境下的协调模型

B.Sreekanth¹, G.Lokesh²

学生，计算机科学与工程系，维木理工学院，蒂鲁帕蒂，普撒拉帕图，吉图(地区)，A。P、印度
助理教授，计算机科学与工程系，Vemu理工学院，普撒拉帕图，Chittoor(地区)，A。P、印度

摘要

提出了一个利用虚拟化技术根据请求需求动态分配数据中心资源的系统，并通过优化使用中的服务器数量来支持绿色计算。我们引入了“偏度”的概念来衡量服务器多维存储利用率的不均匀性。通过最小化偏度，我们可以很好地组合不同类型的工作负载，并提高服务器资源的整体利用率。我们开发了一套有效防止系统过载的启发式方法，同时节省了所使用的能量。轨迹驱动仿真和实验结果表明，该算法具有良好的性能。本文介绍了一种基于云分区概念的更好的公有云负载均衡模型，并通过切换机制根据不同的情况选择不同的策略。该算法将博弈论应用于负载均衡策略中，提高了公有云环境下的负载均衡效率。

介绍

我们提出了一个自动化资源管理系统的设计和执行，该系统实现了两个目标之间的良好平衡。我们做出了以下贡献:我们开发了一个资源分配系统，可以有效地避免系统中的过量，同时最大限度地减少服务器的使用数量。我们引入了“偏度”的概念来计算服务器的不均匀利用率。通过最小化偏度，我们可以在多维资源约束的情况下提高服务器的整体利用率。我们设计了一种负载预测算法，可以准确地捕捉应用程序未来的资源使用情况，而无需查看虚拟机内部。该算法可以捕捉到资源使用模式的上升趋势，并有助于显著减少布局流失。由于作业到达模式不可预测，并且云中每个节点的容量不同，因此为了负载平衡

问题是，工作负载控制对于改善系统表现和保持稳定性至关重要。负载平衡方案取决于系统动态是否重要，可以是静态的，也可以是动态的。静态方案不使用系统信息，不太复杂，而动态方案会给系统带来额外的成本，但会随着系统状态的变化而变化。由于动态方案的灵活性，本文采用了动态方案。该模型由主控制器和平衡器组成，用于收集和分析信息。因此，动态控制对其他工作节点的影响很小。然后，系统状态为选择正确的负载相反策略提供了依据。本文给出的负载平衡模型是针对公共云的，公共云有许多节点，计算资源分散在许多不同的地理位置。因此，该模型将公共云划分为几个云分区。当环境非常大且复杂时，这些划分简化了负载平衡。 The cloud has a main manager that chooses the suitable partition for arriving jobs while the balancer for each cloud partition chooses the best load balancing strategy.

偏度算法

我们引入了偏度的概念来量化服务器上多个资源使用的不均匀性。设n为我们考虑的资源数量，为第i种资源的利用率。我们定义服务器p的资源偏度为

其中为服务器p所有资源的平均使用量。实际上，并不是所有类型的资源都有性能危险，因此在上述计算中我们只需要考虑瓶颈资源。通过最小化偏度，我们可以很好地组合不同类型的工作负载，并提高服务器资源的整体利用率。下面，我们将详细描述我们的算法。算法的分析可以在附加文件中获得，该文件可以在计算机协会数字图书馆(ComputerSociety Digital library)上找到。

热点和冷点

我们的算法有时会根据对虚拟机未来资源需求的预测来评估资源分配状态。如果服务器的任何资源的操作高于热阈值，则将其定义为热点。这表明该服务器负载过重，因此应该迁移一些运行在该服务器上的虚拟机。我们将热点的温度p定义为超出热阈值的资源利用率的平方和:

其中R是服务器p中重载资源的集合，R是资源R的热阈值(注意，在计算中只考虑重载资源)。热点的温度反映了它的过载程度。如果服务器不是热点，则其温度为零。如果服务器的所有资源利用率低于冷阈值，则将其定义为冷点。这表明服务器大部分时间处于空闲状态，可能需要关闭服务器以节省能源。但是，只有当系统中所有活跃使用的服务器(即apm)的平均资源利用率低于绿色计算阈值时，我们才这样做。如果服务器上至少有一个虚拟机在运行，则该服务器被积极使用。否则，它是不活跃的。最后，我们将温暖阈值定义为一个资源利用率水平，该水平足够高，可以让服务器运行，但又不会高到在面对应用程序资源需求临时波动时冒成为热点的风险。不同类型的资源具有不同的阈值。 For example, we can define the hot thresholds for CPU and memory resources to be 90 and 80 percent, respectively. Thus a server is a hot spot if either its CPU usage is above 90 percent or its memory usage is above 80 percent.

热点缓解

我们对系统中热点的列表按温度下降进行排序(即，我们先处理最热的那个)。我们的目标是尽可能消除所有热点。否则，尽量降低他们的体温。对于每个服务器p，我们首先决定它的哪些vm应该迁移。如果虚拟机被迁移出去，我们将根据服务器的结果温度对其虚拟机列表进行排序。我们的目标是去掉能够最大程度降低服务器温度的VM。在绑定的情况下，我们选择移除最能降低服务器偏度的虚拟机。对于列表中的每个VM，我们看看是否可以找到一个目标服务器来容纳它。服务器在接受该虚拟机后不能成为热点。在所有这样的服务器中，我们选择一个通过接受这个VM可以最大程度地降低倾斜度的服务器。 Note that this reduction can be negative which means we select the server whose skewness increase the least. If a destination server is found, we record the migration of the VM to that server and update the predicted load of related servers. Otherwise, we move onto the next VM in the list and try to find a destination server for it. As long as we can find a destination server for any of its VMs, we consider this run of the algorithm a success and then move onto the next hot spot. Note that each run of the algorithm migrates away at most one VM from the overloaded server. This does not essentially eliminate the hot spot, but at least reduces its temperature. If it remains a hot spot in the next decision run, the algorithm will repeat this process. It is possible to design the algorithm so that it can migrate away multiple VMs during each run. But this can add more load on the related servers during a period when they are already overloaded. We decide to use this more conservative approach and leave the system some time to react before initiating additional migrations.

绿色计算

当活动服务器的资源利用率过低时，可以关闭部分活动服务器以节省能源。这是在我们的绿色计算算法中处理的。这里的测试是在低负载期间减少活动服务器的数量，而不牺牲现在或将来的性能。我们需要避免系统振荡。当活动服务器上所有资源的平均利用率低于绿色计算阈值时，将调用我们的绿色计算算法。我们根据内存大小的升序对系统中的冷点列表进行排序。由于在关闭未充分利用的服务器之前，我们需要迁移其所有虚拟机，因此我们将冷点的内存大小定义为在其上运行的所有虚拟机的内存大小的总和。回想一下，我们的模型假设所有vm连接到共享后端存储。因此，VM热迁移的成本主要取决于它的内存占用。本节在补充文件中解释了为什么内存是一个很好的深度测量。 We try to eliminate the cold spot with the lowest cost first. For a cold spot p, we check if we can migrate all its VMs somewhere else. For each VM on p, we try to find a target server to accommodate it. The resource utilizations of the server after accepting the VM must be below the warm threshold. While we can save energy by consolidating underutilized servers, overdoing it may create hot spots in the future. The warm threshold is designed to prevent that. If multiple servers satisfy the above criterion, we prefer one that is not a present cold spot. This is because increasing load on a cold spot reduces the likelihood that it can be eliminated. However, we will accept a cold spot as the destination server if necessary. All things being equal, we select adestination server whose skewness can be reduced the most by accepting this VM. If we can find destination servers for all VMs on a cold spot, we record the sequence of migrations and update the predict load of related servers. Otherwise, we do not migrate any of its VMs. The list of cold spots is also efficient because some of them may no longer be cold due to the proposed VM migrations in the above process. The above consolidation adds extra load onto the related servers. This is not as serious a problem as in the hot spot improvement case because green computing is initiated only when the load in the system is low. Nevertheless, we want to bound the extra load due to server consolidation. We restrict the number of cold spots that can be eliminated in each run of the algorithm to be no more than a certain percentage of active servers in the system. This is called the consolidation limit. Note that we eliminate cold spots in the system only when the average load of all active servers (APMs) is below the green computing threshold. Otherwise, we leave those cold spots there as potential destination equipment for future offloading. This is consistent with our philosophy that green computing should be conducted conservatively.

综合运动

在上述每个步骤中生成的动作直到所有步骤都完成才执行。然后对操作列表进行合并，以便每个VM最多移动一次到其最终目的地。例如，热点缓解可能要求VM从PM a移动到PM B，而绿色计算则要求VM从PM B移动到PM C。在实际执行中，VM直接从a移动到C

系统模型

有几个云计算类别集中在公共云上。公有云基于标准的云计算模型，由服务提供商提供服务。一个大型的公共云将包括许多节点以及位于不同地理位置的节点。云分区用于管理这个大型云。云分区是基于地理位置划分的公共云的子区域。结构如图1所示。相反的负载策略基于云分区概念。在创建云分区之后，负载平衡就开始了:当一个作业到达系统时，主控制器将决定哪个云分区应该接收该作业。然后，分区负载均衡器决定如何将作业分配给节点。当云分区的负载状态正常时，可以对该云分区进行本地天赋。 If the cloud partition load status is not normal, this job should be transferred to another partition. The whole process is shown in Fig.2.

主控制器和平衡器

负载均衡的解决方案由主控制器和均衡器共同完成。主控制器首先将作业分配到合适的云分区，然后与每个分区中的平衡器通信以刷新此状态信息。

由于主管理器处理每个分区的信息，较小的数据集将导致较高的处理速率。每个分区中的平衡器按顺序从每个节点收集状态，然后进行选择

将作业分配到云分区

云分区状态分为三种:

(1)“空闲”:当空闲节点超过所占百分比时，将节点切换到空闲状态

(2)正常:当负载状态正常的节点超过负载状态的百分比时，恢复正常负载状态。

(3)过载:当过载节点超过百分比时，切换到过载状态。参数、、和由云分区平衡器设置。主控制器必须频繁地与平衡器通信以刷新状态信息。主控制器执行以下调度策略:当作业i到达系统时，主控制器查询作业所在的云分压器。如果该位置的状态为空闲或正常，作业将在本地处理。如果不是，则找到另一个没有重载的云分区。算法见算法1。

将作业分配给云分区中的节点

云分区平衡器按顺序从每个节点收集负载，以评估云分区状态。对每个节点负载状态的评估是非常重要的。第一个任务是定义每个节点的负载程度。节点负载程度与各种静态参数和动态参数有关。静态参数包括CPU的数量、CPU分配速度、内存大小等。动态参数包括内存利用率、CPU利用率、网络带宽等。荷载程度由这些参数计算如下:

操作步骤步骤1定义加载参数

与每个

参数为静态或动态。M表示参数的总数。

步骤2计算负载度为:

是不同类型的工作可能不同的权重。N表示当前节点。步骤3定义评估基准。根据节点负载度统计数据计算平均云分区度如下:

标杆

，然后根据步骤4的不同情况设置三个节点的负载状态级别，定义为:_ Idle When

该节点没有正在处理的作业，因此该状态被记为Idle。

_正常的

节点状态正常，可以处理其他任务。_过载时

节点不可用，直到高电平恢复正常后才能接收作业。负载程度结果输入到云分区平衡器创建的负载状态表中。每个均衡器都有一个负载状态表，并在每个固定周期T时刷新它。然后，平衡器使用这个表来计算分区状态。每个分区状态都有不同的负载均衡解决方案。当作业到达云分区时，平衡器根据其当前的负载策略将作业分配给节点。随着云分区状态的变化，平衡器将更改此策略。

云分区负载均衡策略

动机

良好的负载平衡将改善整个云的呈现。然而，没有一种通用的方法可以适应所有可能的不同情况。为了改进现有的解决方案来解决新问题，已经开发了各种方法。每种严格的方法在特定的领域都有优势，但并非在所有情况下都有优势。因此，目前的模型集成了多种方法，并根据系统状态在负载均衡方法之间进行切换。对于分压器空闲状态可以使用相对简单的方法，对于正常状态可以使用较复杂的方法。负载均衡器然后根据状态变化切换方法。这里，空闲状态使用改进的轮询算法，而正常状态使用基于博弈论的负载平衡策略。

空闲状态的负载均衡策略

当云分区空闲时，许多计算资源是可用的，并且相对较少的作业到达。在这种情况下，这个云分区能够尽可能快地处理作业，因此可以使用简单的反向加载方法。负载均衡算法有许多简单的方法，如随机权重轮询和动态轮询。这里使用Round Robin算法是因为它简单。轮询算法是最简单的负载平衡算法之一，它将每个新请求传递给队列中的下一个服务器。该算法不记录每个连接的状态，因此它没有状态信息。在常规的轮询算法中，每个节点都有均等的机会被选择。但是，在公有云中，每个节点的配置和性能都不相同;因此，该方法可能会使一些节点过载。为此，采用了一种改进的轮询算法，即“基于负载度评估的轮询算法”。

算法仍然相当简单。在Round Robin步骤之前，负载均衡表中的节点按照负载程度从低到高进行排序。系统构建一个循环队列，并一次又一次地遍历队列。作业将被分配到负载度较低的节点。当均衡器刷新负载状态表时，节点顺序将被改变。但在刷新周期T时，可能会出现读写不一致的情况。刷新平衡表时，此时如果有作业到达云分区，就会带来不一致的问题。系统状态已经改变，但信息仍然是旧的。这可能导致错误的加载策略选择和错误的节点顺序。为了解决这个问题，需要创建两个Load Status Table: Load Status Table 1和Load Status Table 2。 A flag is also assigned to each table to indicate Read or Write. When the flag = “Read”, then the Round Robin based on the load degree evaluation algorithm is using this table. When the flag = “Write”, the table is being refreshed, new information is written into this table. Thus, at each moment, one table gives the correct node locations in the queue for the improved Round Robin algorithm, while the other is being prepared with the updated information. Once the data is refreshed, the table flag is changed to “Read” and the other table’s flag is changed to “Write”. The two tables then alternate to solve the inconsistency. The process is shown in Fig.4.

正常状态下的负载均衡策略

当云分区正常时，作业到达的速度要比空闲状态快得多，而且情况要复杂得多，因此使用不同的策略来实现负载平衡。每个用户都希望在最短的时间内完成自己的工作，因此公共云需要一种方法，可以在合理的响应时间内完成所有用户的工作。Penmatsa和Chronopoulos提出了一种基于博弈论的分布式系统静态负载平衡策略。本文的工作为我们对云环境中的负载平衡问题提供了一个新的认识。云计算环境中的负载均衡作为分布式系统的一种实现，可以看作是一场游戏。博弈论有非合作对策和合作对策。在合作博弈中，决策者最终会达成一项协议，即约束性协议。每个决策者通过相互比较意见来决定。在非合作博弈中，每个决策者都只为自己的利益做出决策。然后系统达到纳什均衡，每个决策者做出最优决策。 The Nash equilibrium is when each player in the game has chosen a strategy and no player can benefit by changing his or her strategy while the other players strategies remain unchanged.

利用博弈论进行负载平衡的研究已经有很多。Grosu等人提出了一种基于博弈论的负载平衡策略，将分布式系统作为一种非合作博弈，采用分布式结构。他们将该算法与其他传统算法进行了比较，结果表明该算法具有较低的复杂度和较好的性能。Aote和Kharat给出了一个基于博弈论的能量负载平衡模型。该模型与非合作博弈中用户作为决策者时系统的动态负荷状态有关。由于网格计算和云计算环境也是分布式系统，因此这些算法也可以应用于网格计算和云计算环境。以前的研究表明，云分区在正常负载状态下的负载平衡策略可以被视为一种非支持性博弈，如下所述。游戏中的玩家是节点和任务。假设当前云分区中有n个节点，有n个作业到达，然后定义以下参数:

在这个模型中，最重要的步骤是找到合适的值。目前的模型使用Grosu等人的“最佳回复”方法对每个节点进行计算，然后使用贪婪算法对所有节点进行计算。该程序给出了纳什均衡，以最小化每个工作的响应时间。然后，该策略会随着节点状态的变化而变化。

结论

由于这项工作只是一个概念性框架，因此还需要做更多的工作来实现框架并解决新问题。一些要点是:

(1)云划分规则:云划分不是一个简单的问题。因此，该框架将需要一个完整的云划分方法。例如，集群中的节点可能离其他节点很远，或者同一地理区域中的一些集群仍然相距很远。划分规则应该简单地基于地理位置(省或州)。

(2)如何设置刷新周期:在数据统计分析中，主控制器和云分区均衡器需要在固定的周期内刷新信息。如果周期过短，高发生率会影响系统性能。如果时间太长，信息就会太旧，无法做出好的决定。因此，需要测试和统计工具来设置合理的刷新周期。

(3)更好的负荷状态评估:需要一个好的算法来设置和，评估机制需要更加全面。

(4)寻找其他负载均衡策略:其他负载均衡策略可能会提供更好的结果，因此需要进行测试来比较不同的策略。为了保证系统的可用性和效率，需要进行许多测试。

数字一览


图1	图2	图3


图4	图5	图6

参考文献

R. Hunter，《云的原因》，http://www.gartner.com/DisplayDocument?doc cd=226469&ref= g noreg, 2012。

M. D. Dikaiakos, D. Katsaros, P. Mehra, G. Pallis和A. Vakali，云计算:用于IT和科学研究的分布式互联网计算，互联网计算，vol.13, no. 1。5，第10-13页，9月- 10月2009.

P. Mell和T. Grance, NIST对云计算的定义，http://csrc.nist.gov/publications/nistpubs/800145/SP800-145.pdf, 2012。

微软学术研究，云计算，http://libra.msra.cn/Keyword/6051/cloudcomputing?querycloud%20computing, 2012。

云计算趋势，http://www.google.com/trends/explore#q=cloud%20computing, 2012。

N. G. Shivaratri, P. Krueger, M. Singhal，局部分布式系统的负载分配，计算机，第25卷，no. 1。12，第33-44页，1992年12月。

B. Adler，《云负载平衡:工具、技巧和技术》，http://www.rightscale。com/infocenter/whitepapers/Load-Balancing-in-theCloud.pdf 2012

Z. Chaczko, V. Mahadevan, S. Aslanzadeh和C. Mcdermid，云计算中的可用性和负载平衡，在2011年计算机和软件建模国际会议上发表，新加坡，2011。

K. Nishant, P. Sharma, V. Krishna, C. Gupta, K. P. Singh, N. Nitin和R. Rastogi，使用蚁群优化的云节点负载平衡，inProc。第14届计算机建模与仿真国际会议，剑桥郡，英国，2012年3月，pp. 28-30。

M. Randles, D. Lamb，和A. Taleb-Bendiab，云计算分布式负载平衡算法的比较研究，IEEE第24届高级信息网络与应用国际会议，澳大利亚，2010年，第551-556页。

A. Rouse，公有云，http://searchcloudcomputing.techtarget.com/definition/public-cloud, 2012。

D. MacVittie，《为开发人员介绍负载平衡算法》，https://devcentral.f5.com/blogs/us/introtoload-balancing-for-developers-ndashthe-algorithms,2012。

S. Penmatsa和A. T. Chronopoulos，分布式系统的博弈论静态负载平衡，并行与分布式计算杂志，vol.71, no. 1。4，第537-555页，2011年4月。

D. Grosu, A. T. Chronopoulos, m.y. Leung，分布式系统中的负载平衡:一种使用合作游戏的方法，第16届IEEE国际会议。并行和分布式处理符号。4月，美国佛罗里达州2002, pp。52 - 61。

S. Aote和M. U. Kharat，分布式系统中动态负载平衡的博弈理论模型，《计算、通信和控制国际会议》，2009年，第235-238页。

国际计算机与通信工程创新研究杂志