基于直方图和离散时间MDP的异构数据中心电源管理策略

可在www.sciencedirect.com在线获取理论计算机科学电子笔记337（2018）5-22www.elsevier.com/locate/entcs基于直方图和离散时间MDP的异构数据中心电源管理策略Marziyeh Bayati2LACLUniversit'eParis-EstCr'eteil（UPEC）France摘要本文提出了一种基于异构服务器数据中心中一是要确保合理的能量消耗和可接受的服务质量（QoS）。在本文中，到达作业和服务速率用直方图来指定，直方图是从实际轨迹、经验数据或传入的流量测量获得的离散分布。数据中心由队列建模，然后我们通过离散时间马尔可夫决策过程（MDP）来制定优化问题，以找到最优策略。我们证明了最优策略不是滞后的。 我们的方法被应用和测试的几个系统参数超过当我们在同构和异构数据中心之间进行比较时，我们可以看到真实的Google流量跟踪。关键词：马尔可夫决策过程，随机建模，节能优化，异构数据中心，数字污染，分布式系统。1介绍[23，10，17，5]中的几项研究表明，最近云和数据中心的扩张导致能源消耗和数字污染显著增加。大于1. 全球能源消耗的3%是由于使用的电力数据中心。此外，一台数据中心服务器每天可以产生超过10公斤的二氧化碳，[23，40]中进行的调查显示，该比率正在增加，这说明了数据中心不断发展的趋势。因此，节能的需求正在出现，以考虑面对能源问题和数字污染问题的电源管理策略。数据中心旨在支持预期的峰值传输负载，但全球负载约为1特别感谢N。Pekergin。2电子邮件：mbayati@hotmail.frhttps://doi.org/10.1016/j.entcs.2018.03.0311571-0661/© 2018作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。6M. Bayati/理论计算机科学电子笔记337（2018）5峰值负荷[10]。事实上，大量的服务器没有负载，仍然消耗最大能耗的65%-70%[17，5]。1.1相关作品类似[26，3]的研究表明，数据中心消耗的大部分能源主要是用于运行服务器和冷却它们的电力（占数据中心总成本的70%）。因此，这种能源消耗的主要因素与运行服务器的数量有关。一个重要的任务是关注服务器及其冷却。人们已经开始努力构建低能耗处理器和更好的组件[18]，更高效的冷却系统[37]，优化的内核[20]和更高效的能源网络[10]。在此背景下，补充节能方法是考虑管理数据中心中的服务器的接通/断开的功率策略，以确保由这些数据中心提供的更好的服务质量和合理的能量消耗。有两项要求相互冲突：(i) 保持高的服务质量（QoS）。(ii) 消耗更少的能量。对于第一个要求，我们需要打开大量的服务器，这会消耗更多的能源，减少等待时间，降低失业率，但需要高能耗。对于第二个要求，我们需要打开少量的服务器，这会导致更少的能源消耗，但会导致更多的等待时间并增加失业率。 因此，我们的目标是设计更好的电源管理算法，考虑到这两个约束，以尽量减少等待时间，损失率和能源消耗。根据戴尔和Principled Technologies发布的研究，一台服务器的功耗大约在384到455瓦之间。其他工作评估每个服务器的功耗范围在238和376瓦之间[34]。Rajesh等人。[40]估计一千瓦时的能源成本为0。0897美元。这些值可能会有所不同，具体取决于数据中心所在的位置以及如何生成流量。使用该基准，一台服务器每年的运行成本约为300美元。否则，每一份工作都可能产生利润，每一份工作的平均利润可以计算为总利润与服务工作数量的比率。例如，106个请求（页面浏览量）可能带来1000美元的收入。因此，可以说，一份工作平均带来1 0-3美元。[12]中的工作表明，加工作业3产生的利润约为6。2× 10−6 $。在这种情况下，一个失去的工作成本6。2×10−6 $。数据中心服务器的异构性来自于机器在数据中心的生命周期内逐渐升级、配置和更换的事实[4，24]。几项研究[32，36]表明，平均而言，数据中心可以托管三到五代机器，每代机器在速度和大小方面具有不同的配置：内存，处理器，存储和网络。的确，3每个作业都是一个网页浏览请求M. Bayati/理论计算机科学电子笔记337（2018）57在数据中心内具有若干硬件机器配置是自然的。因此，忽略这种异构性可能会显著降低数据中心的效率我们对Google跟踪服务器的分析[47，41]显示了不可忽略的服务器异质性水平主要是，我们观察到基于两个标准的三个层次的异构性：每台机器的CPU速度和内存大小。这些标准是QoS和能耗的良好指标。图1显示了相当数量的服务器以中等CPU速度和中等内存量运行图1.一、服务器异构性：Google跟踪服务器根据CPU速度和内存大小重新分区为了节省能量，[14，15，16，44，48，42，1，35，33]中的作品考虑了特定管理机制下的模型，这导致了阈值策略等次优策略。他们将同构数据中心服务器建模为理论排队模型，以评估等待时间和能耗之间的权衡，其中作业根据独立同分布（i.i.d）泊松过程到达，然后根据指数分布的服务时间提供服务。基于解析方程和实验模拟的分析表明，能耗显著降低（从20%降至40%），同时仍保持合理的等待时间。与其他作者一起，我们做了类似的工作[7]，其中到达作业被建模为直方图。另一方面，还有其他工作集中在计算最优策略[28，49，31，27，9，15]。为了实现这一目标，作者形式化的节能模型的马尔可夫决策过程（MDP）。MDP是一种允许对决策系统建模的形式主义。基本上，它是一个由一组决策行为增强的马尔可夫链。应用一个动作将系统从一个状态移动到另一个状态，并产生一些货币成本。因此，系统进入新状态的概率受所选动作的影响。在节能的背景下，消耗的能量的货币成本取决于操作服务器的数量，并且QoS货币成本取决于等待和/或拒绝的作业的数量。此外，从系统的每个状态，我们必须考虑打开/打开每个服务器的所有不同方式，以找到最佳策略，即最佳操作序列，5.89%百分之九十二点七1.35%13.80%28.62%57.58%低CPU速度中等CPU速度高CPU速度低内存大小中等内存大小高内存容量8M. Bayati/理论计算机科学电子笔记337（2018）5最小化在有限时间内累计的预期总货币成本。MDP模型可以在连续或离散时间背景下考虑。在离散时间MDP的情况下，值迭代算法，实现贝尔曼然而，当通过拟合经验数据或通过断言通常导致泊松分布的一些假设获得连续时间分布来建模到达作业时，考虑连续时间MDP[49，9，31]。通过使用一致化转换过程[2]，将连续时间MDP转换为离散时间框架，然后可以使用值迭代算法来计算最优策略。众所周知，MDP的大小是重要的，并且对于大模型，最优策略的计算可能很难甚至不可能。事实上，分析最优策略的结构特性以加速计算是至关重要的。文献[46，29，43，19，38]研究了最优策略的结构，给出了双门限结构的检验条件。异构系统的MDP模型被认为是在几个作品[28，36]。特别是[30，13，22]使用连续时间MDP用于异构数据中心，其中作业以泊松方式到达并加入由几个不相同的服务器服务的单个队列。研究了最优策略的阈值结构性质。在我们的工作中，真正的传入traffic跟踪采样，然后直接用于建立经验离散分布（直方图）模型的工作到达和服务率。事实上，我们可以容纳比Poisson过程更少的正则过程，如[35，42]中的几个作品。因此，我们的方法分析及其优化过程不需要泊松到达、指数服务和无限缓冲器容量等假设。我们已经在[6，7]中使用了直方图，类似的作品[45]将它们用于网络传输。该数据中心由一个离散时间队列来建模，该队列包括一组具有不同能耗水平和不同服务能力的异构服务器请注意，到达作业和服务器分布的容量处理都是从真实的跟踪、经验数据或传入的流量测量中获得的。最大的尺寸是有限的。我们将时隙的长度设置为用于对传输轨迹进行采样以获得直方图的采样时间的长度。将能量性能优化问题转化为离散时间MDP问题，不经过均匀化过程。然后，我们分析了能源消耗及其演变。1.2文件概要论文的其余部分组织如下。 第2节显示了如何在AR-竞争对手的工作可以通过从真实的谷歌交易轨迹中获得的离散分布来建模[47，41]。本文还提出了一种构造离散同独立分布的方法。第三节用简单排队模型对系统进行建模。然后，第4节将优化问题表述为离散时间MDP。然后，在第5节中，我们证明了与最优策略相关的一些结构性质最后，第6M. Bayati/理论计算机科学电子笔记337（2018）59分析了一个真实的案例研究。2抵达说明在本节中，我们将展示如何通过直方图对到达作业进行建模。设A是取值于N中的离散随机变量。偶对HA=（SA，PA）表示A的直方图，其中PA：N→[0， 1]是A的概率质量函数，SA={i∈N：PA（i）>0}是PA的支集.因此，在时隙期间到达数据中心的作业的数量由直方图HA建模，其中PA（i）给出每个时隙具有i个例2.1假设每个时隙的概率为0。14个接收3个到达工作，0。19人获得7个抵港工作，以及0. 67人接受11个抵港工作。在这种情况下，到达由直方图HA=（SA，PA）建模，其中SA={3，7，11}，PA（3）= 0。17，PA（7）= 0。19，且PA（11）= 0。67.为了对工作到达进行建模，我们使用基于开放集群数据2011-2跟踪的真实交易跟踪[47，41]。与[7]一样，我们关注的是包含与2011年5月整个月指向特定Google数据中心的请求相作业事件被组织为一个包含八个属性的表。列时间戳是指以微秒表示的到达作业时刻50×10345×10340×10335×10330×10325×10320×10315×10310×1035×1030×1030 70 140210280350420490560630700以小时计的图二. 左图：Google跟踪的一个月内到达作业数量的变化（蓝色曲线是实数，红色曲线是实数的周期插值。右上角的地图：龙卷风2011年5月21日至26日的爆发序列右下角的地图：谷歌数据中心的位置入境工作2011年5月18日，26 May 201110M. Bayati/理论计算机科学电子笔记337（2018）5−1 .一、3·10 −21 .一、17· 10−21 .一、04·10−2第九章1· 10−3第七章8·10−3第六章5·10−3五、19·10−33 .第三章。89·10−3二、6·10−31 .一、3· 10−30。800。720。640。560。480。400。320。240。168·10−20.050。0004080120160200240280320360400就业数量0。000 30 60 90 120150180210240270300采样周期（秒）图三.左：谷歌跟踪到达作业分布。右：i.i.d-ness测试。 对采样周期在115 ~ 155秒的采样数据进行转折点检验，值大于>0。05因此在置信水平95%时，我们接受零假设，即到达作业是i.i.d.。图2显示了我们对Google跟踪到达作业的时间序列分析的总结左图显示一个月内抵港工作数目的演变。蓝色曲线是实数，红色曲线是实数的周期插值。我们观察到两个异常点：第一个是2011年5月18日谷歌服务器的负载很重（可能是为了DSK案件的判决）。第二个是2011年5月26日的负荷大幅下降，这可能与美国东南部地区的气象条件有关。右边的两张地图显示了龙卷风的影响和谷歌计算中心的位置该运输跟踪必须以一个采样周期进行采样，在该采样周期内，到达作业可以被视为独立同分布。事实上，我们在一到三百秒之间的几个采样周期内对数据进行采样，然后我们对每个采样周期应用转折点测试[21]，以测试采样数据的i.i. d性我们发现，采样周期在115到155秒之间的p-值更大比0。05，置信度为0。95我们接受零假设，即采样数据是独立同分布的。因此，我们考虑136秒的帧来对轨迹进行采样并构造一个经验分布。 所获得的直方图的支撑由大约200个箱形成，并且到达作业的平均值大约为每个箱50个作业。槽：E（HA）= 50。3模型描述在这项工作中，我们考虑离散时间排队模型。我们的排队模型是一个容量有限的批到达排队模型。我们的模型到达工作和服务率离散分布（直方图）。数据中心由异构服务器组成，这些服务器基本上分为几个能耗级别为了简化，我们考虑以下水平的集合G={高，中，低}（中表示中等）。类型g的可操作服务器的数量由mg表示，并且maxg是级别g的服务器的最大数量。概率p值M. Bayati/理论计算机科学电子笔记337（2018）511ΣΣ⎪⎩Σ⎧⎪⎨n←min{b,max{0, n+i−Σmg×dg}}在一个时间单位内，g由直方图HDg建模，其中PDg（d）给出处理d个作业的概率。因此，运行服务器的总数为mg，max=maxg是可运行服务器的最大数量。g∈Gg∈G高服务器高服务器i：工作到达n：等待作业b：Buyer尺寸医疗服务器医疗服务器服务工作低伺服器低伺服器图四、排队模型的图解在缓冲器中等待的作业数用n表示。被拒绝（丢失）的作业数用l表示。我们假设初始时可运行服务器的数量、等待作业的数量和拒绝作业的数量为0。等待作业的数量n可以通过归纳法计算，其中必须描述时隙期间事件的确切顺序首先，作业被添加到缓冲器，然后由服务器执行。根据Tail Drop策略，对每个作业执行接纳：如果作业中有位置，则接受作业，否则它被拒绝。首先，将作业分配给高自由运行服务器，如果没有高自由运行服务器可用，则将作业归因于中等自由运行服务器，否则将其分配给低自由运行服务器。下面的等式给出了车间中等待的工作和丢失的工作的数量。如果ijobs到达，我们有：g∈Gl←max{0， n+i−mg×dg−b}g∈G（一）假设输入到达是独立同分布的。在这些假设条件下，排队模型是一个时间齐次的离散时间马尔可夫链。由于我们处理的是实数迹，为了确保i. i. d-ness假设，我们必须找到可以假设采样迹为i.i.d.的采样周期事实上，我们使用称为转折点检验的统计假设检验[21]来检验采样轨迹的i.i. d性，然后我们只考虑数据是i.i.d的采样周期（见第2节）。我们必须考虑的问题是在性能和性能之间找到一个平衡点。LS12M. Bayati/理论计算机科学电子笔记337（2018）5Σ(i.e.等待和丢失工作）和能量消耗（即操作服务器的数量）。然而，随着服务器数量的不断变化，系统的分析变得更加复杂。服务器的数量可能会根据流量和性能指标而有所不同。更确切地说，根据n、l和特定的成本函数，做出一些决定来改变m高、m中和m低。3.1能源和性能指标能源消耗考虑了运行服务器的数量。服务器在关闭时可能消耗非常低的能量。但是当它运行时，每个槽消耗一些单位的能量，并且它花费一些单位（e，$，£）。即使我们认为服务器立即打开，服务器也可能消耗额外的能量。在特定期间内消耗的总能量是所有消耗的能量的总和。QoS考虑了等待和丢失作业的数量。每个等待/拒绝的作业都要花费一些货币单位。成本含义c兆g ∈IR+运行一个g型操作服务器的能源成本c ∈IR+开启类型g的服务器所需的能量成本cN∈IR+每单位时间cL∈IR+一个丢失作业3.2目标函数对于给定的时间段，用于能量感知的动态控制策略包括对每个时隙执行动作（开启或关闭特定数量的服务器），以便使操作服务器的数量适应传入的作业变化。最优策略包括找到最佳的行动顺序，以最大限度地减少整体货币成本（能量成本加上性能成本）。每个插槽产生的成本可以表示为：n×cN+l×cL+（mJg×cMg+max{ 0，mJg−mg）}×cOng）（2）g∈G其中，n是等待作业的数量，l是丢失作业的数量，mg是在进行动作之前g级的操作服务器的数量，并且mJg是在进行动作之后的操作服务器4马尔可夫决策过程为了找到最优策略，然后分析在此最优策略下数据中心的性能和能耗，我们将使用马尔可夫决策过程的概念来制定我们的优化问题。 注意（n，l）和{m g：g∈G}是相互依赖的。如果我们减小mg，我们节省了更多的能量，但是n和l都增加了，所以我们将具有不期望的QoS减少，反之亦然。M. Bayati/理论计算机科学电子笔记337（2018）513斯P=⎧⎪⎨SC ××S设（S，A，P，C）是MDP，其中S是状态空间，A是动作集合，P是转移概率，C是每个动作的即时成本。令HA=（SA，PA）是用于对到达作业建模的直方图。系统的状态 由对（（m高，m中，m低），（n，l））定义，实际上状态空间S被定义为：S={（（m g：g ∈ G），（n，l））|m g∈ [0.. max g]，n ∈ [0.. b]和l ∈ [0.. max（S A）]}（3）动作空间定义为：A={α（x，y，z）|x∈[0.. maxhi gh]，y∈[0.. maxme d]，z∈[0..最大值low]}（4）其中，动作α（x，y，z）包括在当前时隙期间精确地保持：x高、y中和z低操作服务器。实际上，我们有概率P（α（x，y，z））在作用α（x，y，z）下从状态s =（m high，mmed，m low，（n，l））移动到状态SJ=（x，y，z，（nJ，lJ））。该概率定义为：α（x，y，z）ss′对于每个i∈SA和每个dg∈SDg，满足：n′=min{b，max{0， n+i−x×dhigh−y×dmed−z×dlow}}阿德尔=max{0， n+a−x×dhi gh−y×dmed−z×dlow−b}PA（i）× PDgg∈G（dg）（五）其中，nJ是新的等待工作数量，lJ是新的丢失工作数量，x，y，z是在应用动作之后Gα（x，y，z）. 在这种情况下，应用动作α（x，y，z）立即导致成本Cα（x，y，z）定义为：α（x，y，z）s=n cN+l cL+x×cM高+ max{ 0，x−m高} ×c高+y×cMmed+ max{ 0，y−mmed}×cOnmed+z×cM低电平+ max{ 0，z−m低电平} ×c低电平导通（六）直接成本Cα（x，y，z）包括两部分。 QoS部分包括由于等待和拒绝作业而产生的成本。电源部分包括运行运行服务器所消耗的能量和用于启动其他服务器的能量。表1恢复了我们的模型和我们的MDP配方中使用的参数。MDP的每个状态都包括三个要素：(i) 在0和maxg之间的每个级别的操作服务器的数量，⎪14M. Bayati/理论计算机科学电子笔记337（2018）5(ii) 在以b为界的缓冲器中等待的工作的数量，以及(iii) 拒绝工件数最多等于max（SA）给出的最大到达工件所以，|S|由（b + 1）×（max（S A）+ 1）×（最大g+ 1）。 事实上，g∈GM. Bayati/理论计算机科学电子笔记337（2018）515g∈GG到一个nu mberoftransition等于|是一个|（每个CH仓的一个转换。支持端口MDP的状态为O。b×max（SA）×maxg Aditionally，fromeach在MDP的状态下，我们至多有g∈G（maxg+ 1）个作用，并且每个作用导致到达分布）。 那么，我们的MDP转换数为O最大值（SA）×最大2英寸b×|是一个|×g∈G表1模型和MDP参数。参数项目说明h分析持续时间b缓冲器尺寸maxg类型的服务器总数HDg直方图建模gH就业人数直方图mg级别的运行服务器数量g n等待作业l拒绝的作业所有可能状态的集合一组所有可能的动作s s=（（mg：g∈G），（n，l））系统状态s0s0=（（0， 0， 0），（0， 0））起始状态α（x，y，z）的作用，以保持精确：x高性能服务器y中型运营服务器z低操作服务器α（x，y，z）ss′α（x，y，z）作用α下从s到SJ（x，y，z）在行动α（x，y，z）下s的直接成本直接成本α（x，y，z）概率SJ（x，y，z）（nJS（m高，m中，m低）（n，l）示例4.1为了说明我们的形式化，让因此，max= 4，b= 4。4这个MDP的州数大约是700个。P16M. Bayati/理论计算机科学电子笔记337（2018）5此外，为了保持示例简单，我们将每个机器类型的服务率设置为仅具有一个箱的直方图：PD高（3）= PD中（2）= PD低（1）= 1。工作到达是由例2.1的直方图建模的。例如，状态s82=（（1，0，1），（3，1））意味着系统仅由一个高服务器和一个低服务器运行，此时三个作业在缓冲器中等待，一个作业被拒绝。动作α（0， 2， 1）切换-关闭高级服务器并切换-打开两个低级服务器。这一行动导致的直接成本为1。45并且以概率0将系统移动到状态S380。14，以概率0到达状态S502。67，并且以概率0到达状态S121。19.图五. MDP示例。5最优策略每个时间单位，每个动作都包括打开特定数量的服务器，并打开其余的服务器。最优策略是在有限的时间内，为了使总成本最小化而采取S133S401（0，1， 1）（四、六）130的（0，1， 1）（2，0）S512（0，1， 0）（4，2）S343S530（0，2， 0）（2，0）（0，1， 1）（4，2）（0，1， 0）（四、六）S216（0，1， 0）（2，0）S400（0，2， 0）（四、六）S125（0，0， 1）（4，2）S348 S64（0， 2， 0）（0， 0， 1）（4， 2）（4， 6）s380s 27（0， 2， 1）（0， 0， 1）（2， 0）（2， 0）s502（0，2， 1）（四、六）1 .一、171 .一、101 .一、38S8（0，0， 0）（4，2）α（0，1， 1）0。89s121（0，2， 1）（4，2）α（0，2， 0）α（0，1， 0）1 .一、45α（0，2，1）α（0，0， 1）S1（0，0， 0）（四、六）0。82s441（1，0， 0）（2，0）α（1，0， 0）s82（1，0，1）（3，1）α（0，0， 0）s0（0，0， 0）（2，0）1 .一、13S270（1，0， 0）（四、六）α（1，0， 1）α（1，2， 1）1 .一、76α（1，1， 0）α（1，2， 0）S346（1，2， 1）（4，2）1 .一、20α（1，1， 1）第213条（1，0， 0）（4，2）1 .一、691 .一、411 .一、48S369（1，2， 1）（四、六）s276（1，0， 1）（2，0）s596（1，2， 1）（2，0）s465s 422（1， 0， 1）（1， 2， 0）（4， 6）（4， 2）S187 S440（1， 0， 1）（1， 2， 0）（4， 2）（4， 6）S47（1，1，0）（2，0）S51（1，1，0）（四、六）S205（1，1， 0）（4，2）S515S429（1，1， 1）（4，2）的45（1，2，0）（2，0）（1，1， 1）（2，0）S388（1，1， 1）（四、六）M. Bayati/理论计算机科学电子笔记337（2018）517ΣΣ斯+Sss′Sss′称为地平线，记为H。更一般地，值函数V：S× [0. H] →IR +目标是使预期的总成本随时间的推移最小化：V（s，t）= minπ不Ek=0π（sk，k）sk（七）价值函数可以看作是贝尔曼方程[8，39，11]：V（s，t）=min.Cα（x，y，z）+<$Pα（x，y，z）V（sJ， t−1）<$（8）s′∈S其中α（x，y，z）是系统采取的行动，Pα（x，y，z）是过渡从状态s到状态S的概率j。在这种情况下，每个状态的最优策略是：ππ（s，t）=argmin.Cα（x，y，z）+<$Pα（x，y，z）V（sJ， t−1）<$（9）s′∈S由于值迭代算法是一种高效的动态规划算法，本文利用Bellman方程的一种新的求解方法，计算了MDP的最优控制策略。如前所述，MDP的大小很重要，最佳策略的计算可能很难，甚至对于大数据中心来说是不可能的。实际上，分析最优策略的结构性质是提高计算效率的关键。特别地，在[49]中的几个模型中，在同构数据中心的情况下证明了双阈值结构。在下文中，我们将对围绕最优策略的一些属性感兴趣，并且我们特别展示了双阈值结构的属性不适用于我们的异构数据中心模型。定义5.1[[46，19]]策略π对于时隙t被称为滞后的，如果[0.. max]，<$α（x，y，z）∈A，如：π（m高，m中，m低），（n，l）），t）= α（x，y，z）= π π（x，y，z），（n，l）），t）= α（x，y，z）.此外，如果π可以用公式表示为双阈值结构，则我们 说π是单调的。此外，如果双阈值结构的阈值是有序的，那么π被称为是保序的[46，19]。定理5.2最优策略（9）不是滞后的。证据 令m =（m高，m中，m低）且j=（x，y，z）。让f（m，j）：.g∈G2[0..最大g]→IR作为切换高操作次数的成本Cα（x，y，z）α（x，y，z）∈AΣΣ18M. Bayati/理论计算机科学电子笔记337（2018）5从M高到X的国家服务器，从M中到Y的中等操作服务器，以及从M低到Z的低操作服务器。并且函数w（（m，（n，l）），t）：S× [0. h] → IR+表示从n个等待作业开始的预期和可能的未来成本，M. Bayati/理论计算机科学电子笔记337（2018）519--V（s，t−1）⎩n×w（（j，（n，l）），t）=x×cMhighgh+y×cMmed+z×cMlow+n×cN+l×cLΣ在一个时隙期间，丢失L个作业的调度器服务于（M高、M中、M低）操作服务器，然后遵循最优策略。因此，我们的最优策略（9）可以公式化为：其中：ππ（s，t）= argminf（m，j）+w（（j，（n，l）），t）（10）α（x，y，z）∈Aα（x，y，z）ss′S′∈Sf（m，j）= max{ 0，x-mhigh}×cOn（十一）高+ max{ 0，y−mmed}×cOnmed+max{ 0，z−mlow}×c低电平时根据[19]的定理1，以下条件对于策略是滞后的是必要的：n（m，j）：mg=x+y+z=f（m，j）= 0（12）g∈G这意味着在具有相同总数的操作服务器的两个状态之间移动不会增加或减少切换能量成本。条件12不适用于我们的MDP模型。 我们只需要选择一个反例m=（x，y，z），j=（x+ 1，y− 1，z），并且g上的每个c都严格为正值。Q推论5.3最优策略（9）既不是保序的，也不是单调的。证据根据[43]中给出的单调性和等规性的定义，滞后是等规性和单调性的必要条件然而，从定理5.2，我们推出的最优策略（9）既不是保序也不是单调。Q6为例本案例研究使用基于开放式cluster-data-2011-2跟踪[47，41]的真实交易跟踪。与[7]一样，我们通过离散分布来建模到达作业以及额外的服务率，这些离散分布是从与2011年5月整个月指定到特定Google数据中心的请求相对应的作业/机器事件构建的。该传输迹线以确保i.i.d-ness假设的采样周期进行采样。因此，我们考虑136秒的帧来对轨迹进行采样并构造经验分布。为了指定，解决，然后分析我们的数据中心的能源消耗，我们使用了一个高效的模型检查器，称为PRISM [25]，这是一个概率软件，可用于指定MDP模型。在PRISM中，⎪20M. Bayati/理论计算机科学电子笔记337（2018）5为我们的MDP模型写一个规范，如果系统参数很小，它可以很容易地写出来例如，与具有10个异构服务器的数据中心相关联的PRISM规范是一个数千行的文件，所有行都彼此不同。尝试在没有自动生成的情况下编写规范是耗时的，容易出错，忘记某些情况，浪费时间进行更新或维护。事实上，由于我们的异构模型的规范是巨大的，并且不容易编写（见第4节），我们已经编写了一个工具，可以帮助我们自动生成PRISM规范文件。表2恢复了我们系统的参数值请注意，成本的大小比每项成本的有效价值更重要。例如，高机器的成本比其他机器的成本更重要。图6示出了当改变缓冲器大小b和单位等待/丢失作业成本并保持表2中的其余参数时，在一天（h = 1天）期间的最小预期总成本。表2参数的数值分析。b最大E（高D）E（HD中）E（高D低）cM高cMmedcM低C高c医疗费用c低电平CNCL50 10 10 5 2 6 4 2 3 2 1 1 2见图6。在左边：在保持其他单位成本不变的情况下，改变单位等待作业成本cN。我们观察到，cN越大，总成本越重要。在右边：在保持其他单位成本不变的情况下，改变单位损失工作成本cL。当b值较大时，系统的总成本并不等于单位成本cL表3总结了以下配置的所得结果：(i) 一个拥有十台异构服务器的数据中心，(ii) 一个数据中心有十个相同的高级服务器，(iii) 一个数据中心有十个相同的中型服务器，(iv) 一个有十个相同的低层服务器的表3数值分析的结果国家1.6×104 1.6×103 1.6×103转换88×106 0.81×106 0.87×106 0.89×106内存2 GB 18.8 MB 20.4 MB 20.7 MB时间1.6小时1分钟2分钟2分钟预计最低费用㈠异构服务器（二）同质的高级服务器（三）同质介质服务器（四）同质低服务器Maxhigh21000最大医疗50100Maxlow30010棱镜线7×1047.5×1027.5×1027.5×102M. Bayati/理论计算机科学电子笔记337（2018）521结果表明，异构模型比异构模型节能12%.然而，三个同质模型的规模相对较小，相比之下，异构模型的规模是巨大的。异质模型的规模是由于大量的不同的动作组合。图7显示了实验的结果，在实验中，我们分析了当改变异构/同构数据中心的缓冲器大小b时我们观察到，当b小于某个值（b040）时，总成本增加。然而，当b大于b0时，对于任何配置，总成本似乎都是收敛的。我们可以解释这种行为如下：对于一个小规模的车间，等待的工作数量是低的。这导致服务的工作数量很少实际上，系统只打开了较少数量的服务器。因此，精力充沛的工作和等待的工作都很低。当车间规模较大时，等待作业的数量越重要。 这导致了更多的服务工作。 事实上，系统会打开更多的服务器。因此，精力充沛的工作和等待的工作增加了。由于到达作业是有界的，当缓冲器的大小大于某个值时，等待作业数和服务作业数趋于稳定，使得运行服务器的数目趋于稳定，从而使得总费用趋于稳定700630560490420350280异构服务器同质高服务器同质中服务器同质低服务器10 20 30 40 50 60 70 80 90 100布氏尺寸图第七章异构数据中心和同构数据中心的不同缓冲器大小b时的总成本我们还可以观察到：• 全局异构模型导致更好的成本最小化：这可以可以解释的事实是，异构模型提出了大量的方式来组合动作，这导致了更好的控制策略，可以节省更多的能量。• 低服务器的同质模型会导致重要的成本：这可以通过低服务器具有低服务能力的事实来解释（E（HD低）=2)这导致了大量的等待工作。最低预期成本22M. Bayati/理论计算机科学电子笔记337（2018）57结论本文提出了一个离散时间马尔可夫决策过程模型，用于优化管理的数据中心与异构服务器，目标是最小化能源消耗和服务质量（QoS）成本。此外，一些理论结果，以及数值研究的最优策略的性能。在这项工作中，工作到达率和服务率建模的一般离散概率分布，可以估计从实际数据的直方图。最优控制策略通过值迭代算法计算，并用于定义动态功率管理，以确保性能和能耗之间的权衡。我们证明了最优异质策略的滞回性和单调性都不成立。因此，最优策略不能被设计为简单的双阈值结构。理论和实验结果表明，非均匀模型的尺寸大于均匀模型的尺寸然而，从实验结果来看，增加服务器异构性似乎会带来更多潜在的节能效果。作为未来的工作，我们考虑用一个异构模型来近似异构模型，并应用一些元启发式方法来更好地近似异构模型在避免状态空间爆炸的前提下，尽可能地选择最优策略。引用[1] K. Aidarov，Paul D.Ezhilchelvan和Isi Mitrani。 客户流的节能管理电子笔记理论 Comput. Sci. ，296：199[2] Oguzhan Alagoz和Mehmet US Ayvaci。马尔可夫决策过程的一致化。运筹学与管理科学百科全书。[3] Jayant Baliga，Robert WA Ayre，Kerry Hinton和Rodney S Tucker。 绿色云计算：在处理、存储和运输中平衡能源Proceedings of the IEEE，99（1）：149[4] 路易斯·A和雷·巴罗佐，吉姆·米·克里达拉斯，还有乌尔斯·霍泽尔。 作为计算机的数据交换机：仓库规模机器设计简介。综合讲座计算机架构，8（3）：1-154，2013年。[5] 路易斯·A和雷·巴罗佐和乌尔斯·霍泽尔。能量比例计算的案例。 Computer，40（12），2007.[6] Marziyeh Bayati。 管理数据中心的能源消耗和服务质量。 第五届智能城市和绿色ICT系统国际会议论文集，第293-301页，2016年[7] Marziyeh Bayati，Mohamed Dahmoune，Jean-Michel Fourneau，Nihal Pekergin，and Dimitrios Vekris.一种基于流量跟踪和随机单调性的工具，用于分析数据中心及其能耗。EAI Endorsed Trans. EnergyWeb，3（10）：e3，2016.[8] 理查德·贝尔曼动态规划Princeton University Press，Princeton，NJ，USA，1 edition，1957.[9] Luca Benini，Alessandro Bogliolo，Giuseppe A Paleologo，and Giovanni De Micheli.动态电源管理的策略优化。IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，18（6）：813[10] Theophilus Benson，Aditya Akella，and David A Maltz. 数据中心的网络传输特性在野外第10届ACMSIGCOMM互联网测量会议论文集，第267-280页。ACM，2010年。[11] 迪米特里·P·伯塞卡斯。动态规划与最优控制，第1卷。Athena Scienti fic Belmont，MA，1995年。M. Bayati/理论计算机科学电子笔记337（2018）523[12] Dmytro Dyachuk和Michele Mazzucco 关于权力和绩效的分配政策。 2010年第11届IEEE/ACM网格计算国际会议，第313-320页。IEEE，2010年。[13] 德米特里·埃弗罗西宁具有异构服务器的受控集群系统。 特里尔大学博士论文，FB 4，Informatik，2004年。[14] 安舒尔·甘地、舍温·多鲁迪、莫尔·哈肖尔-巴尔特和艾伦·谢勒-沃尔夫。用递归更新报酬精确分析m/m/k/setup类马氏链。ACM SIGMETRICS Performance Evaluation Review，第41卷，第153-166页。ACM，2013年。[15] Anshul Gandhi，Varun Gupta，Mor Harchol-Balter，and Michael A Kozuch.服务器群管理的能量-性能权衡优化分析。性能评价，67（11）：1155-1171，2010年。[16] 安舒尔·甘地，莫尔·哈乔-巴尔特，伊沃·阿丹。服务器农场与安装成本。性能评价，67（11）：1123[17] 阿尔伯特·G作者：James R.作者：David A.马尔茨和帕文·帕特尔云计算的成本：数据中心网络中的研究问