最优化建模求解云计算中的负载问题

最优化建模求解云计算中的负载问题前言云计算是一种新的商业计算模型和服务模式，它将计算任务分布在大量计算机构成的资源池上，使用户能够按需获取计算能力、存储空间和信息服务。目前，云计算已经在网络搜索、科学计算、虚拟环境、能源和生物信息等领域开始了相关的应用和探索。随着云计算的发展，云计算基础设施的规模正在急剧地变大。云计算数据中心通常拥有成千上万台物理结点，在其上运行着各种各样的服务和应用程序。在这些系统中，具有不同资源请求和动态工作负载的各种应用程序共享着数据中心的资源。虚拟化技术则通过允许计算系统按需分配资源和动态迁移工作负载的方式来支持数据中心的资源共享。然而，由系统规模的增加带来系统管理的复杂性和系统内在的动态性，对云计算数据中心中的虚拟机资源管理来说具有很大的挑战性。1云计算概述1.1云计算介绍云计算是一种共享的网络交付信息服务的模式，云服务的使用者看到的只是服务本身，而不关心相关基础设施的具体实现。IBM认为，云计算是一种革新的IT运用模式。这种模式的主体是所有连接着互联网的实体，可以是人、设备和程序。这种运用方式的客体是IT本身，包括我们现在所接触到的，以及会在不远的将来出现的各种信息服务。而这种运用方式的核心原则是：硬件和软件都是资源并被封装为服务，用户可以通过互联网按需的访问和使用。在云计算中，IT业务通常运行在远程的分布式系统上，而不是在本地的计算机或者单个服务器上。这个分布式系统由互联网相互连接，通过开放的技术和标准把硬件和软件抽象为动态可扩展、可配置的资源，并对外以服务的形式提供给用户。该系统允许用户通过互联网访问这些服务，并获取资源。服务接口将资源在逻辑上以整合实体的形式呈现，隐藏其中的实现细节。该系统中业务的创建、发布、执行和管理都可以在网络上进行，而用户只需要按资源的使用量或者业务规模付费。1.2当前云计算研究中所存在的问题当前，云计算数据中心面临着许多关键性问题，而虚拟机资源管理的问题则首当其冲，并且随着数据中心的快速发展和不断普及，虚拟机资源管理的重要性呈现逐步上升趋势。对于云计算数据中心中结点间的虚拟机资源管理还需要进一步研究，如下问题仍然尚待解决：（1）虚拟机的初始化放置在虚拟机的初始化放置问题上，大多数研究采用启发式方法或遗传算法来进行全局优化搜索，解决虚拟机的初始化放置问题。然而启发式方法只能给出问题的局部最优解，缺乏全局寻优能力；遗传算法虽然具有大范围快速全局搜索能力，但其没有充分利用系统反馈信息，使搜索具有盲目性。另一方面，遗传算法求解到一定范围时往往做大量冗余迭代，向最优解收敛的速度大大降低，从而导致求最优解的效率较低。（2）虚拟机的动态管理目前已经有大量的工作通过对虚拟机的动态整合或管理来减少数据中心的资源竞争或降低数据中心的电源消耗等。其中，一部分工作的管理目标只是关注结点的资源利用或应用的性能，但没有考虑电源消耗问题；另外有一些工作只是为了降低系统的电源消耗，而忽略了应用的性能。然而，不同管理目标之间是相互冲突的。例如，以电源管理为目标的方法考虑将虚拟机更紧凑地放置到物理结点上，但是这会增加违反SLA的风险；而以资源竞争为目标的方法将虚拟机更松散地放置到物理节点上，同样会增加较多的电源消耗。虽然最近的一些研究提出通过整合多个目标的方法来管理虚拟机。但是这些方法只是将不同的管理目标简单地进行整合，并没有很好地均衡这些目标之间的冲突。（3）虚拟机的实时迁移预拷贝方法存在一个主要问题就是在迭代过程中重复传输同一脏页内存，从而导致迁移过程占据较长的迁移时间。而较长的迁移时间对于云计算数据中心是不利的。一方面，在实时迁移过程中传输的数据越多，消耗的网络带宽和CPU资源就越多。进一步说，总迁移时间就会相应地变长，从而使迁移中的虚拟机遭受长时间的服务性能下降。另一方面，实施迁移的目的是为了系统的维护和管理。较长时间的迁移将失去其他迁移的机会，从而使系统的维护失效。2数据中心概述数据中心为信息服务提供运行平台，对新一代数据中心的需求从根本上源于对新一代信息服务的需求。随着信息服务在数量上和种类上的快速增长，企业纷纷把核心业务和数据放到IT系统中运营。与此同时，用户数量也在不断攀升，用户对信息服务的依赖越来越强，企业和个人都需要更安全可靠、易于管理、成本低廉的信息服务。对信息服务的更高要求指明了新一代数据中心的发展方向。一个完整的数据中心由支撑系统、计算设备和业务信息系统这三个逻辑部分组成。支撑系统主要包括建筑、电力设备、环境调节设备、照明设备和监控设备，这些系统是保证上层计算机设备正常、安全运转的必要条件。计算设备主要包括服务器、存储设备、网络设备、通信设备等，这些设备支撑着上层的业务信息系统。业务信息系统是为企业或公众提供特定信息服务的软件系统，信息服务的质量依赖于底层支撑系统和计算机设备的服务能力。只有整体统筹兼顾，才能保证数据中心的良好运行，为用户提供高质量、可信赖的服务。可见，数据中心的概念既包括物理的范畴，也包括数据和应用的范畴。数据中心容纳了支撑业务系统运行的基础设施，为其中的所有业务系统提供运营环境，并具有一套完整的运行、维护体系以保证业务系统高效、稳定、不间断地运行。3云计算中的节能问题在云计算中考虑节能问题，而由于硬盘，内存等耗能是个固定值，因此我们只有通过减少CPU的耗能来节省能耗。在节能中，我们可以通过减少物理机的使用量，节省数据中心的能源消耗，由此我们提出了虚拟机的整合，考虑虚拟机的整合涉及到三个问题：1虚拟机的初始化放置，2何时迁移虚拟机3如何迁移虚拟机。本文主要考虑虚拟机的动态迁移，随着负载的变化，如何整合虚拟机，减少物理机的使用量。云计算中的节能致力于解决两个问题：虚拟机镜像文件的放置和虚拟机上的工作负载的特性。出于性能的考虑，在虚拟机迁移之前，云系统拷贝镜像文件到本地物理机的磁盘中，如果物理机所存储的虚拟机的镜像文件是离线的，我们将不能运行这个虚拟机。虚拟机工作负载的类型可以分为数据密集型虚拟机和CPU密集型物理机，我们考虑的系统是分布式文件系统，因此一个物理机可以运行任何虚拟机，即使这个虚拟机不含镜像文件。然后，数据密集型虚拟机运行在不含其镜像文件的物理机上会导致60%的能源损失比起运行在同样的含有其镜像文件的物理机上。另一方面，CPU密集型虚拟机对于物理机是否含有其镜像文件性能影响不大。4考虑不同类型的负载建立模型考虑虚拟机工作负载的特性来建立模型，这是一个变种的装箱问题.传统的装箱问题仅仅是考虑将同性质的物品装到最少数量的箱子中。而我们现在讲物品分为两种类型：用红色物品来表示数据密集型虚拟机，用绿色物品来表示CPU密集型虚拟机。因为我们通常将数据密集型运行在拥有其镜像文件的物理机上，所以本模型限制任何一个红色物品在一个箱子中的总重量都不能超过K，即一台物理机上总共容纳的数据密集型虚拟机的总容量不能大于K，假设每个箱子的容量为1.虚拟机的重量代表它的资源需求。我们假定有P个红色物品，分别是r1,……,rp,对于1ip，w（ri）k,w表示物品的总重量，同样的，每个代表CPU密集型虚拟机的重量不超过1-k，用q来代表绿色物品的个数，分别为g1,……,gq对于所有的1iq，w(gi)1-k求将p个红色物品和q个绿色物品个、放在容量为1的箱子中，总共需要的最小的箱子数目。N(i,x)表示绿色物品的最大数量，在第i个箱子中首次能容纳x个红色物品的数量。N(i.x)=maxj(N(i-1,x-j)+(1-j*X)/Y),j*Xk求箱子最小数量的最优解i*N(i*,p)q,p,q分别代表红色物品和绿色物品的数目。假设我们有c种红色物品的类型，它们的重量分别为R1，……,Rc。其相应的红色物品的数目是xi，同样的绿色物品有d种，其重量分别为G1，……,Gd，其相应的绿色物品的数目是yiB(x1,...,xc,y1,...,yd)表示所需箱子的最小数目。s=(x1,...,xc,y1,...,yd)，表示可以装在一个箱子中的物品的集合，s∗表示任何箱子中物品的组合可以放在一个箱子中xiRi+yiGi1I=1,ci=1,dxiRikI=1,cB(s)=1,whens∈S,B(s)=1+mins∗∈SB(s−s∗),otherwise5装箱问题装箱问题[15]（BinPacking）是一个组合优化问题，其要将n个物品装入到许多个箱子中（箱子的个数最多为n），每个物品都有各自的体积（0jw），且每个箱子的容量是一定的（容量为0jc），目标是把所有的物品装入到箱子里，使得每个箱子的物品体积之和不会超过箱子的容量，并且使用的箱子数最少。通常，所有的箱子具有相同的体积限制（0c）。显然，将每个物品放入一个箱子是一个可行解，但不是最优解。装箱问题的数学表示如下：1min()niizyy1..,{1,2,,}njijijstwxcyiNn11,nijixjN01,iyiN或=01,,ijxijN或其中，1iy表示箱子i被装入物品，反之则表示箱子i空着。1ijx表示物品j放入箱子i，反之则表示物品j未放入箱子i。装箱问题属于NP-hard问题，从而几乎不可能在多项式时间内找到最优解（除非NPP），所以大部分的研究都集中在近似算法的分析和讨论上。目前解决装箱问题的方法主要采用启发式算法和遗传算法。启发式算法主要有首次适应算法（FirstFit，FF），最佳适应算法（BestFit，BF），降序首次适应算法（FirstFitDescending，FFD）和降序最佳适应算法（BestFitDescending，BFD）等近似算法。6多目标优化问题多目标优化问题又称为多标准优化问题。一般地，多目标优化问题由n个决策变量参数、k个目标函数和m个约束条件组成，目标函数、约束条件与决策变量之间是函数关系。多目标优化问题的公式如下：12max=(x)=(f(x),f(x),,f(x))kimizeyf12(x)=(e(x),e(x),,e(x))0msubjecttoe其中，12(,,,)nxxxxX为决策向量，X为决策向量x形成的决策空间，12(,,,)nyyyyY为目标向量，Y为目标向量y形成的目标空间，约束条件()0ex确定决策向量的可行取值范围。下面再给出多目标优化问题的几个重要的定义：定义1（可行解集）可行解集fX定义为满足式（2.7）中的约束条件)(xe的决策向量x的集合，即{|()0}fXxXex定义2（Pareto占优）假如a和b为可行解集fX中的两个可行解，那么与b相比，a为Praeto占优的，当且仅当1,2,,,()()1,2,,,()()iiiiikfafbjkfafb记为ba，也称为a支配b。定义3（Pareto最优解）如果某个解*fxX被称为Pareto最优解（或非支配解），当且仅当其满足以下条件：*:fxXxx定义4（Pareto最优解集）所有Pareto最优解的集合构成Pareto最优解集，其定义为：***{|:}fPxxXxx定义5（Pareto前沿面）Pareto最优解集*P中所有Pareto最优解对应的目标向量组成的曲面被称为Pareto前沿面*PF，其定义为：*******12{()((),(),,())|}kPFFxfxfxfxxP根据上述公式和定义，可以进一步总结如下：（1）在大多数情况下，类似于单目标优化的最优解在多目标问题中是不存在的，只存在Pareto最优解。多目标问题的一个Pareto最优解只是可以接受的“不坏”的解，并且多目标优化问题大多数都具有很多个Pareto最优解。（2）若一个多目标优化问题存在所谓的最优解，则该最优解必定是Pareto最优解，并且Pareto最优解也只由这些最优解组成，不包含其他解。因此说Pareto最优解是多目标优化问题合理的解集合。（3）通常多目标优化问题的Pareto最优解是一个集合。对于实际应用问题的最后方案决策，必须根据对问题的了解程度和决策人员的偏好，从多目标优化问题的Pare