法律状态公告日
法律状态信息
法律状态
2016-08-10
授权
授权
2013-10-16
实质审查的生效 IPC(主分类):G06F9/455 申请日:20130530
实质审查的生效
2013-09-11
公开
公开
技术领域
本发明涉及计算机应用技术领域，特别涉及一种降低数据中心通信负载及能耗的方法。
背景技术
在云计算席卷全球、云计算产业发展浪潮风起云涌的背景下，近年来云计算数据中心能 耗成为了学术界和产业界关注的话题之一。日本经济产业省(METI)预测，全球IT能耗将于 2025年翻5倍，而到2050年将增长12倍。大量的能耗使得像Google，Microsoft和Facebook 这样的IT公司每年的电费就高达几百万美元，其中数据中心网络设备的能耗也相当巨大。据 统计数据中心中的网络设备能耗占据数据中心全部能耗的10%-20%。例如，在2006年美国 数据中心的网络设备能耗高达30亿度电。
与传统数据中心相比，云计算数据中心的特性主要体现在：（1）模块化的标准基础设施。 针对数据中心的云服务需求，云数据中心对服务器、存储设备、网络等设施按工业标准进行 模块化配置设计，使其具有适应性与可扩展性；（2）虚拟化资源与环境。云数据中心广泛采 用虚拟化技术将物理资源聚集形成一个共享虚拟资源池，从而更加灵活高效、低成本地使用 资源；（3）高可靠自动化管理．云计算数据中心应是24X7无人值守的、可远程管理的，实 现设备到应用端到端的统一管理。（4）快速的可扩展能力。随着大数据爆炸式增长以及用户 需求的可变多样性，云数据中心必须根据业务应用需求和服务质量来动态配置、定购、供应 虚拟资源，具有资源利用的快速扩展能力；（5）节能与节省空间。云计算数据中心将大量使 用节能服务器、存储和网络设备，并通过先进的供电系统和散热技术，实现供电、散热和计 算资源的无缝集成和管理，解决传统数据中心的过量制冷和空间不足的问题。
现有技术中，为降低网络设备能耗，许多科学家提出了多种解决方案：
1）Heller等人提出将网络流量聚集在一个弹性树中，关闭未被使用的网络设备[1]。然 而此方法未发挥如今云计算数据中心的优势（也就是虚拟机迁移技术），没有充分利用云计 算数据中心的资源，控制方式单一。
2）Meng等人针对网络设备节能问题提出了一个新的问题——基于流量的虚拟机分配问 题（TVMPP）[2]，但是其解决方法没有考虑链路容量约束，可能导致将含有拥塞链路的虚拟 机分配方式引入数据中心。
3）Shirayanagi等人提出了一个Honeguid解决方案[3]，但是此方法需要在物理机和交 换机之间增加跨接链路，增大了数据中心出现故障几率。
发明内容
本发明提供了一种降低数据中心通信负载及能耗的方法，通过本方法，实现合理分配数 据中心网络流量，降低通信负载，减少交换机使用量，达到数据中心节能的目标，见下文描 述：
一种降低数据中心通信负载及能耗的方法，所述方法包括：
（1）调度中心通过花费矩阵和业务需求矩阵计算虚拟机初步放置序列；
（2）根据带宽的约束条件，将业务通信数据配置到相应的交换机和链路中，获取初始业 务路由信息表；
（3）判断当前虚拟机执行所承载业务的通信时间是否超过通信时间门限值，如果是，将 当前虚拟机迁移到与目的虚拟机逻辑上最近的目标物理机中，然后执行步骤（4）；如果否， 执行步骤（4）；
（4）调度中心判断所有承载超过通信时间门限值业务的虚拟机是否迁移完成，如果是， 执行步骤（5）；如果否，重新执行步骤（4）；
（5）调度中心更新所述虚拟机初步放置序列和所述初始业务路由信息表，关闭数据中心 中未被使用的交换机。
所述调度中心通过花费矩阵和业务需求矩阵计算虚拟机初步放置序列的步骤之前，所述 方法还包括为：
调度中心初始化数据中心，获取计算域内信息；调度中心通过数据中心拓扑结构确定各 物理机间的所述花费矩阵，根据用户需求自动生成所述业务需求矩阵。
所述带宽的约束条件具体为：
其中是业务流从虚拟机i到虚拟机j在链路l上的通信速率，α是根据资源预留协议 设置的常数，Cl是链路l的带宽。
所述判断当前虚拟机执行所承载业务的通信时间是否超过通信时间门限值的步骤之前， 所述方法还包括：调度中心确定所述通信时间门限值。
所述调度中心确定所述通信时间门限值的过程具体为：
调度中心通过对数据中心记录的网络运行历史数据进行统计，确定所述通信时间门限值。
另，所述调度中心确定所述通信时间门限值的过程还可以为：
交换机检测各业务的通信速率并传输至调度中心，调度中心确定各业务之间的通信时间， 并通过业务需求矩阵获取业务数据流的通信数据量，调度中心根据各业务之间的通信时间和 业务数据流的通信数据量确定通信时间门限值。
另，所述调度中心确定通信时间门限值的过程还可以为：
网络信息感知交换机检测各业务的通信速率并确定各业务之间的通信时间，将各业务之 间的通信时间传输至调度中心，调度中心通过业务需求矩阵获取业务数据流的通信数据量， 调度中心根据各业务之间的通信时间和业务数据流的通信数据量确定通信时间门限值。
所述网络信息感知交换机包括：光模块或网线接口、电源模块、处理器、交换芯片、控 制面板、可读可写闪存、启动区只读内存和动态随机存取存储器，还包括：信息统计、分析 模块。
“信息统计、分析模块”用于检测各业务的通信速率并确定各业务数据流的运行时间， 将各业务数据流的运行时间传输至处理器，处理器通过交换芯片和光模块或网线接口将各业 务数据流的运行时间传输至调度中心。
本发明提供的技术方案的有益效果是：
1)应用本发明后数据中心能够监测到网络更多的运行参数，包括业务数据流之间的通信 速率，通信时间等。利用交换机多余的计算能力，可将一部分调度中心计算任务分配给交换 机执行，实现更广泛的分布式计算。
2)应用本发明后数据中心能耗明显降低。由于实时采集数据中心内网络运行信息，可动 态准确调整虚拟机初步放置序列及初始业务路由信息表，从而关闭未被使用的交换机，达到 数据中心节能目的。按照美国2006年数据中心用电量数据，结合仿真结果推算，使用本方法 可使美国数据中心每年节约电能约1.8亿度电。
3)应用本发明后数据中心网络通信数据包延时可降低1%左右。由于本方法将通信时长 超过时间门限值的业务进行合理迁移，从而可使这部分业务数据流占用更少的交换机和通信 链路，从而降低了链路拥堵，使得数据中心的网络服务质量可以得到提升。
4)应用本发明后数据中心网络可以节约出更多的可用带宽。本方法具有动态感知网络信 息及反馈调节功能，避免了其他方法静态布局导致的资源浪费情况。本方法将通信时长超过 时间门限值的业务进行合理分配，可充分利用数据中心底层带宽，占用更少的数据中心中间 层和顶层通信链路带宽，使得其他业务的通信路径拥有更多的选择，从而节约出更多的中间 层和顶层可用带宽，进一步提升数据中心的网络服务质量。
附图说明
图1为本发明建议的数据中心调度系统参考体系结构示意图；
图2为一种降低数据中心通信负载及能耗的方法具体流程图；
图3为步骤106中所述虚拟机迁移过程示意图；
图4为网络信息感知交换机框图；
图5为信息统计分析模块的框图；
图6为以太网帧结构；
图7a为各通信速率下平均能耗示意图；
图7b为各通信速率下算法节能效果比较示意图；
图8为数据包平均延时示意图；
图9a为CBR通信速率服从(5,10,0,8)截尾正态分布时GRAPS算法及GRASP-JAVPRS算法 的各层链路剩余带宽示意图；
图9b为CBR通信速率服从(5,10,0,8)截尾正态分布时SA算法及SA-JAVPRS算法的各层 链路剩余带宽示意图；
图10a为CBR通信速率服从(5,70,0,8)截尾正态分布时GRAPS算法及GRASP-JAVPRS算法 的各层链路剩余带宽示意图；
图10b为CBR通信速率服从(5,70,0,8)截尾正态分布时SA算法及SA-JAVPRS算法的各层 链路剩余带宽示意图。
具体实施方式
为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明实施方式作进 一步地详细描述。
为了合理分配数据中心网络流量，降低通信负载，减少交换机使用量，达到数据中心节 能的目标，本发明实施例提供了一种降低数据中心通信负载及能耗的方法，本发明主要通过 对数据中心网络数据流监测，利用虚拟机（VM）迁移技术，将承载云计算业务的虚拟机在物 理机中重新分配，从而关闭未使用的交换机，达到数据中心节能的目的，其中，实施例1和 实施例2中的交换机为本领域技术人员所公知的交换机，实施例3中的交换机为本发明所设 计的网络信息感知交换机，具体实现时实施例1和实施例2的操作步骤也可采用本发明所设 计的网络信息感知交换机，详见下文描述：
实施例1
101：调度中心初始化数据中心，获取计算域内信息；
其中，计算域中的各类信息通常包括：数据中心拓扑结构、物理机个数、交换机个数和 各链路带宽，物理机用来承载计算及通信任务的虚拟机（每个物理机都对应一个虚拟机集， 虚拟机集中虚拟机的个数由物理机的承载能力确定）；交换机和链路带宽信息用来保证通信 通畅，以及为路由的规划确定通路，该些信息的具体值由调度中心确定。
本发明中所述的调度中心为能完成调度任务的大型服务器等，上述的物理机和交换机的 型号本发明实施例对此不做限制，只要能完成上述功能的器件均可。
102：调度中心通过数据中心拓扑结构确定各物理机间的花费矩阵D，根据用户需求自动 生成业务需求矩阵F；
其中，花费矩阵D中的每一个元素用Dqp表示，Dqp为从物理机q到物理机p之间通信 所需要的交换机个数。花费矩阵D在不同的网络结构中具有不同的值。本方法定义了胖树 （Fat-tree）结构花费矩阵D的数学表达式，在胖树结构中，花费矩阵的每个元素Dqp是每 个交换机端口个数k值的函数，见公式1。
其中，p，q和k的取值为大于等于1的正整数，花费矩阵D的维数由物理机的个数确定， 物理机个数是每个交换机端口个数的函数，即例如：当每个交换机端口个数为4时，物 理机个数为16，q和p的取值为1和2时，因为所以D12=1；q和p的 取值为1和4时，因为所以D14=3。当每个交换机端口个数为4时， 物理机个数为16，胖树拓扑的花费矩阵D为下式：
其中，业务需求矩阵F中的每一个元素用Fij表示，Fij表示从虚拟机i到虚拟机j之间的 业务通信量。在本发明中不考虑物理机的节能控制策略，从而在步骤101得到可用物理机编 号后，将各类通信业务整合入虚拟机集中，一个虚拟机集S代表多个虚拟机的集合，即 S={s1,s2,...,sn}。
由于一个虚拟机集分配在一个物理机中，减少网络节点数量问题可以归纳为二次分配问题 （QAP），数学公式见公式2。
服从:
(2)
xiq∈{0,1} 1≤i,q≤n
xjp∈{0,1} 1≤j,p≤n
在公式2中n表示可用物理机数量，fij表示虚拟机i与虚拟机j之间的业务通信量，是业务 需求矩阵F的一个元素；dqp是物理机q与物理机p之间的花费，是花费矩阵D的一个元素； xiq∈{0,1}表示xij取值为0或者1。xiq取1表示虚拟机i放置在物理机q中，取0表示虚 拟机i没有放置在物理机q中。同样，xjp取1表示虚拟机j放置在物理机p中，取0表示虚 拟机j没有放置在物理机p中；1≤q≤n中，表示为一个物理机智能承载 一个虚拟机集，例如：当q=1时当q=2时当q=3时 1≤i≤n中，表示为一个虚拟机集只能放置在一个物理机中， 例如：当i=1时
103：调度中心通过花费矩阵D和业务需求矩阵F计算虚拟机初步放置序列；
为了减少网络设备使用量，在一个物理机承载一个虚拟机集的虚拟机分配方法中本发明 采用贪婪随机适应性搜索方法（GRASP）[4]和模拟退火（SA）[5]算法来求解虚拟机初步放置序 列。该步骤的具体操作，为本领域技术人员所公知，本发明实施例对此不做赘述。
104：根据带宽的约束条件，将业务通信数据配置到相应的交换机和链路中，获取初始业 务路由信息表；
当虚拟机在物理机中初步放置完成后，各虚拟机中业务的初始路由信息为：从源虚拟机 （业务数据流的发出端）经由数据中心网络的最左侧的链路和交换机至目的虚拟机，将已有 业务所对应的链路和交换机的信息存储至初始业务路由信息表。有新的业务通信数据加入时 将其放置到已经启用的链路和交换机中，当已启用的链路带宽达到资源预留协议所定义的带 宽时，新的业务通信数据随机选择未被使用的链路和交换机，并将新的业务通信数据所使用 的链路和交换机加入至初始业务路由信息表中。
本发明优先将业务通信数据放置到已经启用的链路和交换机中，关闭未被使用链路、交 换机及交换机端口。在路由选择时必须满足资源预留协议所定义的带宽，即公式3，从而保 证了链路的通畅和网络的服务质量，避免了将包含拥塞链路的虚拟机配置及路由方法引入数 据中心。
其中是业务流从虚拟机i到虚拟机j在链路l上的通信速率，α是根据资源预留协议 设置的常数，Cl是链路l的带宽。其中，资源预留协议为本领域技术人员所公知，本发明实 施例对此不做赘述。
105：调度中心通过对数据中心记录的网络运行历史数据进行统计，确定通信时间门限值 （TH）；
业务数据流通信时间门限值TH是本发明的核心参数，调度中心通过对数据中心记录的网 络运行历史数据进行统计得出具有普遍性并且稳定的业务数据流运行时间规律，对数据统计 分析公式为公式4。
Flowv≤Flowv+1 v∈(1,N)
max{T(Flowu)} u∈(1,M)
数据中心记录的网络运行历史数据中，业务数据流运行时间和业务流具有对应关系。公 式4中Flowv表示第v号业务数据流的通信数据量，总共具有N条数据流。 Flowv≤Flowv+1v∈(1,N)表示对所有数据流的通信量进行从小到大排序。 M≤N表示从1号到M号的业务数据流的通信量求和小于 或者等于全部业务数据流通信量的一半。M值对于不同的统计数据具有不同的值，可以从 公式4求解得到。公示max{T(Flowu)}u∈(1,M)表示求取满足公式4前两个约束条 件的业务流运行时间的最大值，这个值就是通信时间门限值TH，公式4中T(Flowu)表示第 u号业务数据流的运行时间。
106：当前虚拟机与目的虚拟机之间进行通信，判断当前虚拟机执行所承载业务的通信 时间是否超过通信时间门限值，如果是，将当前虚拟机迁移到与目的虚拟机逻辑上最近的目 标物理机中，然后执行步骤107；如果否，执行步骤107；
其中，逻辑最近指的是目标物理机与目的虚拟机的宿主物理机之间通过较少的交换机即 可连通，并且当所承载的业务迁移后能够在满足链路拥塞条件下保持顺畅通信。确定通信时 间门限值及将承载超过通信时间门限值业务的虚拟机进行迁移的方法称为JAVPRS算法。 GRASP-JAVPRS算法为：首先利用GRASP算法求解虚拟机初步放置序列，然后再根据通信时间 门限值及链路带宽约束条件对虚拟机进行迁移，并计算虚拟机迁移后的业务路由信息。GRASP 算法不进行通信时间门限值确定及虚拟机迁移，其他步骤与GRASP-JAVPRS算法相同。SA算 法及SA-JAVPRS算法不再赘述。
例如：参见图3，S1、S2、S3等分别代表序号不同的交换机（Switch），L11、L12、L22 等分别代表序号不同的链路（Link），虚拟机A配置在物理机1中，虚拟机B配置在物理机 14中，虚拟机C配置在物理机2中，虚拟机D配置在物理机4中。虚拟机A与虚拟机B通信， 通信时间为30秒；虚拟机C与虚拟机D通信，通信时间为10秒；通信时间门限值为25秒。 根据本方法，虚拟机C与虚拟机D之间的通信时间未超过通信时间门限值，所以不需要进行 迁移，其中，虚拟机C与虚拟机D之间的路由信息为：{物理机2,L12,S1,L13,S3,L23,S2,物理 机4)}。虚拟机A与虚拟机B之间通信时间超过通信时间门限值，需要将虚拟机A迁移。若 将虚拟机A迁移至物理机13，判断物理机13与物理机14之间的业务通信带宽能否满足公式 3，若满足公式3，则物理机13为目的虚拟机B逻辑上最近的物理机；若不满足公式3，则 若将虚拟机A迁移至物理机15，判断物理机15与物理机14之间的业务通信带宽能否满足公 式3，若满足公式3，则物理机15为目的虚拟机B逻辑上最近的物理机；若不满足公式3， 则用相同的方法判断将虚拟机A迁移至物理机16能否满足公式3；若物理机16不能满足条 件，则不将虚拟机进行迁移。
虚拟机A与虚拟机B之间原始路由信息为：
{物理机1,L11,S1,L13,S3,L35,S5,L59,S9,L91,S11,L41,物理机14}；假设通过上面判断，物 理机13为目的虚拟机B逻辑上最近的物理机，则虚拟机A与虚拟机B之间的路由信息为：{物 理机13,L31，S11,L41,物理机14}。
107：调度中心判断所有承载超过通信时间门限值业务的虚拟机是否迁移完成，如果是， 执行步骤108；如果否，重新执行步骤106；
实际应用中，完成每一个承载业务都对应一个完成时间，调度中心对完成时间和通信时 间门限值进行比较，当存在完成时间超过通信时间门限值时，对完成时间所对应的虚拟机执 行步骤106，对虚拟机进行迁移。通过该步骤实现了调度中心的监测，减少了交换机的使用 数量。
108：调度中心更新虚拟机初步放置序列和初始业务路由信息表，关闭数据中心中未被使 用的交换机。
实施例2
201：调度中心初始化数据中心，获取计算域内信息；
其中，计算域中的各类信息通常包括：数据中心拓扑结构、物理机个数、交换机个数和 各链路带宽，物理机用来承载计算及通信任务的虚拟机（每个物理机都对应一个虚拟机集， 虚拟机集中虚拟机的个数由物理机的承载能力确定）；交换机和链路带宽信息用来保证通信 通畅，以及为路由的规划确定通路，该些信息的具体值由调度中心确定。
本发明实施例中所述的调度中心为能完成调度任务的大型服务器等，上述的物理机和交 换机的型号本发明实施例对此不做限制，只要能完成上述功能的器件均可。
202：调度中心通过数据中心拓扑结构确定各物理机间的花费矩阵D，根据用户需求自 动生成业务需求矩阵F；
其中，该步骤的详细操作详见实施例1，本实施例对此不做赘述。
203：调度中心通过花费矩阵D和业务需求矩阵F计算虚拟机初步放置序列；
为了减少网络设备使用量，在一个物理机承载一个虚拟机集的虚拟机分配方法中本发明 采用贪婪随机适应性搜索方法（GRASP）[4]和模拟退火（SA）[5]算法来求解虚拟机初步放置 序列。该步骤的具体操作，为本领域技术人员所公知，本发明实施例对此不做赘述。
204：根据带宽的约束条件，将业务通信数据配置到相应的交换机和链路中，获取初始业 务路由信息表；
本发明优先将业务通信数据放置到已经启用的链路和交换机中，关闭未被使用链路、交 换机及交换机端口。在路由选择时必须满足资源预留协议所定义的带宽，即实施例1中的公 式3，从而保证了链路的通畅和网络的服务质量，避免了将包含拥塞链路的虚拟机配置及路 由方法引入数据中心。该步骤的详细操作参见实施例1，本实施例对此不做赘述。
205：交换机检测各业务的通信速率并传输至调度中心，调度中心确定各业务之间的通信 时间Ter，并通过业务需求矩阵F获取业务数据流的通信数据量Flowv，调度中心根据各业 务之间的通信时间和业务数据流的通信数据量确定通信时间门限值（TH）；
通过交换机所检测到的各业务流通信速率矩阵R（矩阵R中的每个元素Rer表示各业务 的通信速率），再结合业务需求矩阵F，计算得出各业务流在非拥塞情况下的通信时间，见 计算公式(5)。
Ter=Fer/Rer (5)
公式5中Ter表示业务e与业务r之间的通信时间，Fer为业务需求矩阵F的元素。将 各业务之间的通信时间Ter作为业务数据流的运行时间T(Flowv)，再根据公式(4)即可得到 业务数据流通信时间门限值TH。
206：当前虚拟机与目的虚拟机之间进行通信，判断当前虚拟机执行所承载业务的通信时 间是否超过通信时间门限值，如果是，将当前虚拟机迁移到与目的虚拟机逻辑上最近的目标 物理机中，然后执行步骤207；如果否，执行步骤207；
其中，逻辑最近指的是目标物理机与目的虚拟机的宿主物理机之间通过较少的交换机即 可连通，并且当所承载的业务迁移后能够在链路拥塞条件下保持顺畅通信。
207：调度中心判断所有承载超过通信时间门限值业务的虚拟机是否迁移完成，如果是， 执行步骤208；如果否，重新执行步骤206；
实际应用中，完成每一个承载业务都对应一个完成时间，调度中心对完成时间和通信时 间门限值进行比较，当存在完成时间超过通信时间门限值时，对完成时间所对应的虚拟机执 行步骤206，对虚拟机进行迁移。通过该步骤实现了调度中心的监测，减少了交换机的使用 数量。
208：调度中心更新虚拟机初步放置序列和初始业务路由信息表，关闭数据中心中未被使 用的交换机。
其中，实施例2中的执行步骤除特殊说明外，详细的操作步骤均和实施例1相同，请参 考实施例1的操作步骤，本实施例对此不做赘述。
实施例3
本发明实施例还包括对交换机进行改进，参见图4，交换机通常包括：光模块或网线接 口（通常采用RJ45插座）、电源模块、处理器、交换芯片、控制面板、可读可写闪存、启动 区只读内存和动态随机存取存储器，本实施例中的网络信息感知交换机还包括：信息统计、 分析模块，该模块用于检测各业务的通信速率并确定各业务数据流的运行时间，将各业务数 据流的运行时间传输至处理器，处理器通过交换芯片和光模块或网线接口将各业务数据流的 运行时间传输至调度中心，上述交换机中的各个模块之间通过电气连接。
具体实现时，信息统计、分析模块可以为FPGA，本发明实施例以采用Altera公司生产 的EP1C12F256C6N型号FPGA为例进行说明，还可以为其他型号的FPGA，本发明实施例对此 不做限制。
301：调度中心初始化数据中心，获取计算域内信息；
其中，计算域中的各类信息通常包括：数据中心拓扑结构、物理机个数、网络信息感知 交换机个数和各链路带宽，物理机用来承载计算及通信任务的虚拟机（每个物理机都对应一 个虚拟机集，虚拟机集中虚拟机的个数由物理机的承载能力确定）；网络信息感知交换机和 链路带宽信息用来保证通信通畅，以及为路由的规划确定通路，该些信息的具体值由调度中 心确定。
302：调度中心通过数据中心拓扑结构确定各物理机间的花费矩阵D，根据用户需求自 动生成业务需求矩阵F；
303：调度中心通过花费矩阵D和业务需求矩阵F计算虚拟机初步放置序列；
304：根据带宽的约束条件，将业务通信数据配置到相应的网络信息感知交换机和链路中， 获取初始业务路由信息表；
305：网络信息感知交换机检测各业务的通信速率并确定各业务之间的通信时间Ter，将 各业务之间的通信时间Ter传输至调度中心，调度中心通过业务需求矩阵F获取业务数据流的 通信数据量Flowv，调度中心根据各业务之间的通信时间Ter和业务数据流的通信数据量确 定通信时间门限值（TH）；
以太网帧结构见图6，
PRE:先导字节,7个10101010
SFD:帧开始标志,10101011
DA:目的MAC地址SS:源MAC地址
L/T:帧长度（值<=1500）/类型（值>1500）
DATA:数据字段
PAD:填充字段
CRC:校验字段
“信息统计、分析模块”分析从SS到DA在单位时间内收集到的数据包，也就是从SS到 DA的数据流通信速率，存放至一个二维数组
Message={SS1,DA1,Rer(1);SS2,DA2,Rer(2);......;SSw,DAw,Rer(w)}
其中SS1表示第一条业务数据流的源MAC地址，其物理机编号也就是通信速率Rer中的e； DA1表示第一条业务数据流的目的MAC地址，其物理机编号也就是通信速率Rer中的r， Rer(1)表示从SS1到DA1的通信速率（其他字符的含义类似，本实施例对此不做赘述），w 表示经过本交换机共w条业务数据流，统计公式为公式6。
(6)
公式6中TD表示“信息统计、分析模块”从前一次统计结束到本次统计结束之间的时间 段，Bytee()为计算以太网帧中各部分字节数的函数，例如Bytee(PREt(w))表示在t 时刻业务w的以太网帧中先导字节数，为7字节，是个固定值。公式6的分子之和表示TD时 间段内统计交换机接收/发送的字节总数。该步骤的详细操作参见实施例2，本实施例对此不 做赘述。
306：当前虚拟机与目的虚拟机之间进行通信，判断当前虚拟机执行所承载业务的通信时 间是否超过通信时间门限值，如果是，将当前虚拟机迁移到与目的虚拟机逻辑上最近的目标 物理机中，然后执行步骤307；如果否，执行步骤307；
307：调度中心判断所有承载超过通信时间门限值业务的虚拟机是否迁移完成，如果是， 执行步骤308；如果否，重新执行步骤306；
308：调度中心更新虚拟机初步放置序列和初始业务路由信息表，关闭数据中心中未被使 用的网络信息感知交换机。
其中，实施例3中的执行步骤除特殊说明外，详细的操作步骤均和实施例1相同，请参 考实施例1的操作步骤，本实施例对此不做赘述。
下面以具体的实验来验证本发明提供的一种降低数据中心通信负载及能耗的方法的可行 性，详见下文描述：
在仿真实验中采用6端口Fat-Tree拓扑作为数据中心的网络结构，物理机个数为每个交 换机端口数k值的函数，即k3/4，从而物理机个数为54；采用Montage科学计算工作流来 初始化各业务通信量，Montage[3]是由NASA/IPAC的一个开源工具创建，可以由输入FITS 格式的图片产生星空的马赛克图片，一个Montage实例见表1；使用从源到目的的交换机个 数来定义花费矩阵D（公式（1））；使用四种算法：GRASP、GRASP-JAVPRS、SA和SA-JAVPRS， 四种算法具有相同的路由策略，其中GRASP和SA仅求解QAP问题，不再重新调整虚拟机 分配序列；而GRASP-JAVPRS和SA-JAVPRS先求解QAP问题，然后根据本方法对虚拟机 分配序列做调整；业务流发生器采用CBR，CBR速率使用三种截尾正态分布数据（5,01,0,8）、 （5,10,0,8）、（5,70,0,8）来模拟三种不同特性的数据流，其中(5,01,0,8)表示CBR速率服从 均值为5，方差为1，最小值大于0，最大值不超过8的正态分布（其他两个正态分布数据中 字符的含义以此类推），各层交换机能耗见表2。
表1
表2各层交换机各部分能耗
本方法从能耗、延时和剩余带宽3个方面进行评价，其中，图7(a)是三组相同通信速率 分布下数据中心能耗试验结果的平均值，从图中可以看出在相同QAP算法情况下，运用 JAVPRS算法后网络设备能耗明显降低，并且随着数据流通信速率方差的增大，能量节约的 越来越多，例如：在CBR通信速率服从(5,10,0,8)截尾正态分布时，GRASP算法能耗为140.39 瓦*时，GRASP-JAVPRS算法能耗为130.13瓦*时，GRASP-JAVPRS算法比GRASP算法节 约140.39-130.13=10.26瓦*时；在CBR通信速率服从(5,70,0,8)截尾正态分布时，GRASP算法 能耗为213.20瓦*时，GRASP-JAVPRS算法能耗为124.73瓦*时，GRASP-JAVPRS算法比 GRASP算法节约213.20-124.73=88.47瓦*时；在CBR通信速率方差为70时比CBR通信速率 方差为10时多节约88.47-10.26=78.21瓦*时。
图7（b）为CBR各通信速率下应用JAVPRS算法比原始算法（GRASP或者SA）多节 约电能的百分比图。从图7(b)可以看出，当在CBR通信速率方差为10时GRASP-JAVPRS 算法比GRASP算法节约(140.39-130.13)/140.39*100%=7.3%；从图7(a)可以看出，在CBR通 信速率方差为10时SA算法能耗为：190.74瓦*时，SA-JAVPRS算法能耗为184.88瓦*时， SA-JAVPRS算法比SA算法节约(190.74-184.88)/190.74*100%=3.1%；从图7(a)可以看出，在 CBR通信速率方差为70时，GRASP算法能耗为213.20瓦*时，GRASP-JAVPRS算法能耗为 124.73瓦*时，GRASP-JAVPRS比GRASP算法节约(213.20-124.73)/213.20*100%=41.5%，同 时SA算法能耗为196.00瓦*时，SA-JAVPRS算法能耗为164.53瓦*时，SA-JAVPRS算法比 SA算法节约(196.00-164.53)/196.00*100%=16.1%。这就说明业务通信速率方差越大，也就是 某个业务通信时间偏离均值较大时，JAVPRS算法节能效果越明显。这是因为JAVPRS算法 将通信时间超过时间门限值的业务调整到合适的虚拟机中，大部分目标虚拟机与目的虚拟机 连接在同一个接入交换机上，从而使这部分业务不再占用过多的交换机，而且接入交换机服 务时间更长，从而这部分业务只增加少量的能耗。
延时定义为从数据包的产生到它到达目的地的时间间隔。它不仅仅包括传输时间，也包 括在交换机缓存中的队列延时。缓存延时主要受数据包拥塞影响。从图8可以看出，随着通 信速率方差的增大，应用本算法后数据包延时降低的更多，例如：在CBR通信速率方差为 10时，GRASP算法数据包延时为0.059秒，GRASP-JAVPRS算法数据包延时为0.056秒，应 用本方法后数据包延时降低(0.059-0.056)/0.059*100%=5.1%；在CBR通信速率方差为70时， GRASP算法数据包延时为0.059秒，GRASP-JAVPRS算法数据包延时为0.055秒，应用本方 法后数据包延时降低(0.059-0.055)/0.059*100%=6.8%，GRASP-JAVPRS算法在CBR通信速 率方差为70时比方差为10时数据包延时多降低：
[(0.059-0.055)-(0.059-0.056)]/(0.059-0.056)*100%=33.3%。说明JAVPRS算法有效降低了 网络拥塞。
剩余带宽指被占用的通信链路中可用带宽。定义底层链路为服务器和接入交换机之间的 通信链路，中间层链路为接入交换机和汇聚交换机之间的通信链路，顶层链路为汇聚交换机 和核心之间的通信链路。图9、图10分别为数据流通信速率服从(5,10,0,8)和(5,70,0,8)截尾正 态分布时仿真得到的各层链路剩余带宽。横轴为仿真运行时间，以秒为单位。纵轴为剩余带 宽百分比。
图9和图10中的数据为时间为3秒时各层链路剩余带宽百分比，数据从上到下分别对应 应用JAVPRS算法后的底层链路，原始算法（GRASP或者SA）的底层链路，应用JAVPRS 算法后的中间层链路，原始算法的中间层链路，应用JAVPRS算法后的顶层链路，原始算法 的顶层链路。从图9（a）可以看出，GRASP-JAVPRS算法顶层链路剩余带宽比GRASP算法 顶层链路剩余带宽多出50.81%-43.20%=7.61%的剩余带宽；GRASP-JAVPRS算法中间层链路 剩余带宽比GRASP算法中间层链路剩余带宽多出66.86%-63.68%=3.18%的剩余带宽； GRASP-JAVPRS算法底层链路剩余带宽比GRASP算法底层链路剩余带宽多出 70.65%-70.48%=0.17%的剩余带宽；从图10（b）可以看出，在时间为3秒时，SA-JAVPRS 算法顶层链路剩余带宽比SA算法顶层链路剩余带宽多出50.86%-39.12%=11.74%的剩余带 宽；SA-JAVPRS算法中间层链路剩余带宽比SA算法中间层链路剩余带宽多出 65.41%-62.36%=3.05%的剩余带宽；SA-JAVPRS算法底层链路剩余带宽比SA算法底层链路 剩余带宽多出70.57%-70.13%=0.44%的剩余带宽。相同的规律可以从图9（b）及图10（a） 可以得出。
从图9、图10可以看出无论是GRASP-JAVPRS算法还是SA-JAVPRS算法，无论是底层 还是中间层或者顶层，在绝大多数时间应用JAVPRS算法都比未使用JAVPRS算法时得到更 多的剩余带宽，这是由于JAVPRS算法将通信时间长但是通信速率小的业务插入在运行的链 路中，一方面提高了链路带宽利用率，另一方面为通信速率大的业务节约出了可用链路。从 中间层和顶层可以看出JAVPRS算法在提高链路带宽利用率方面具有明显优势。
参考文献
[1]Heller,B.,Seetharaman,S.,Mahadevan,P.,Yiakoumis,Y.,Sharma,P.,Banerjee,S.,McKeown, N.:ElasticTree:Saving Energy inDataCenter Networks.In USENIX NSDI,April2010
[2]X.Meng,V.Pappas,and L.Zhang.:Improving the scalability of data center networks with traffic-aware virtual machine placement.In Proceedings of the29th IEEE Conference on Information Communications(INFOCOM’10),pp.1154-1162,2010
[3]Shirayanagi,H.,Yamada,H.,Kono,K.:Honeyguide:A VM migration-aware network topology for saving energy consumption in data center networks.In IEEE Symposium on Computers and Communications,pp.460-467,2012
[4]Oliveira,C.,Pardalos,P.,Resende,M.:GRASP with path-relinking for the quadratic assignment problem.In3rd International Workshop on Experimental and Efficient Algorithms,pp.356-368, 2004
[5]Misevicius,A.:A modified simulated annealing algorithm for the quadratic assignment problem. In INFORMATICA,vol.14,pp497-514,2003
本领域技术人员可以理解附图只是一个优选实施例的示意图，上述本发明实施例序号仅 仅为了描述，不代表实施例的优劣。
以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之 内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
机译： 云数据中心降低能耗
机译： 云数据中心降低能耗
机译： 能耗降低的云数据中心
