在PaaS云平台数据中心,用户向云平台提交的应用程序需要由虚拟机(VM)来运行,以满足租户应用(Guest Application)之间的隔离需求。虚拟机、或称为客户机(Guest),由物理机(Physical Machine,PM)、或称为宿主机(Host),创建、运行和管理,并提供一定的计算资源,例如CPU、内存、磁盘IO、磁盘空间、网络连接等等。然而作为宿主机的物理机计算资源总是有限的,显然宿主机性能不足一定会影响其中客户机的性能,进而影响用户应用的性能。云平台如何通过合理的资源调度,在不影响虚拟机性能的情况下,为更多用户提供服务,尽量减少成本,获取更多利益,是云计算中的重要问题,也是云计算面临的最大难题之一。特别地,考虑到虚拟机之间可能存在的通信,虚拟机放置在不同物理机上,会直接影响用户业务性能。因此,和其他计算资源一样,“网络带宽”也是云平台中重要的计算资源,如何有效地分配网络资源也是云平台中资源调度的重要内容。本文主要解决的是PaaS云中虚拟机在具有混合网络拓扑结构的云数据中心中的物理机上如何进行放置的决策问题,是PaaS云资源调度问题的一个分支。本文首先分析了图背包问题适用网络拓扑结构单一的问题,并分析了现代云数据中心常见的网络拓扑结构。然后提出了针对数据中心复杂网络拓扑结构的分块方法,使得具有限制通信流量作用的图背包问题能够应用于具有混合拓扑结构的云数据中心的虚拟机放置策略建模。本文使用了该问题的一个变形,给出了对应的整数线性规划模型,并使用谷歌优化工具包进行精确求解。四个不同场景的模拟实验结果表明该模型能够在满足宿主机性能限制的情况下,通过将有通信需求的多个虚拟机放置在同一个宿主机上减少物理链路上的通信量,来满足物理链路上的带宽限制,使得放置在云平台上的所有应用价值最大化。然而由于模型中网络对虚拟机通信的限制条件过多,使得当网络成为限制虚拟机放置的主要因素时,模型的求解时间过长,随着问题规模进一步扩大,模型的求解时间将不可接受。