网络虚拟化环境下的资源监控策略

江逸茗兰巨龙周慧琴

①(国家数字交换系统工程技术研究中心 郑州 450002)②(解放军信息工程大学信息系统工程学院 郑州 450002)

1 引言

随着互联网规模的不断增长和新型网络服务的不断涌现，现有网络结构僵化、可扩展性差的缺点日益突出，但是研发和部署新型网络体系架构不但面临着更新成本较高的问题，也受限于各个运营者相互之间的利益冲突。在这种背景下，网络虚拟化成为了当前互联网向未来网络体系架构过渡的一种有效解决方案，同时网络虚拟化也是未来网络体系架构应具备的关键特性之一[1]。

网络虚拟化技术可以支持在共享的底层物理网络上创建多个虚拟网络(Virtual Network, VN)，从而为用户提供多样化和可定制的端到端服务，例如为网络视频会议或 IPTV[2]等服务建立专门的虚拟网。在网络虚拟化环境中，基础设施提供商(Infrastructure Provider, InP)负责管理和运营底层网络，服务提供商(Service Provider, SP)以虚拟网请求(virtual network request)的方式向InP申请网络资源，InP将会根据对底层网络的资源监测结果和 SP的实际需求，为各个虚拟网请求制定出合理的资源划分方案[3]。

每一个虚拟网可以看作是底层网络的一个资源片，它由虚拟节点和虚拟链路组成。构建虚拟网的过程中最重要的步骤是如何将虚拟节点和虚拟链路映射到底层网络的实际节点和链路上。目前的映射算法大多依赖于集中式的管理模式，即由一个中心管理节点来负责映射决策的制定[47]-。由于虚拟网对资源的实际需求会随着用户需求的更改而不断改变，底层网络的设备运行状态和资源占用情况也是动态变化的，因此为了给映射决策提供必要的资源状态信息，中心管理节点需要对底层网络设备的运行状态和资源状态进行实时的监控。不同的监控策略对网络的响应速度、通信开销等性能指标会产生不同影响，所以选择合理的监控策略是提升虚拟网性能的重要基础。

文献[8]提出了一种虚拟网管理架构IMO，该架构提出了一整套集中式的资源状态信息监控、聚合与过滤策略，IMO通过计算每个节点的压力值(pressure score)来制定信息汇聚节点(information aggregation points)的部署策略。文献[9]提出的HotSpot则是通过计算每个节点的邻居节点数量来制定信息收集节点的部署策略。IMO和HotSpot都无法自动获取信息收集节点的最优数量值，只能依靠管理员进行预先设定，且这两种方法都是将节点间的距离简单地定义为节点间的跳数，没有考虑时延等参数对状态监控和信息收集带来的影响。文献[10-13]对虚拟网运行管理框架、资源管理策略等方面进行了研究。

智能优化算法通过模拟某些自然现象和过程来解决复杂的优化问题，在网络虚拟化领域，目前仅有一些研究通过利用粒子群[14]或蚁群[15]等智能优化算法来解决虚拟网映射问题。遗传算法是一种应用比较广泛的智能优化算法，它通过模拟生物的遗传与进化过程，能够较好地解决离散型优化问题。Narayanan[16]首次将量子计算理论与遗传算法进行结合，提出了量子遗传算法，Han等人[17]进一步将量子旋转门引入了量子遗传算法，此外还出现了一些对于量子旋转门的改进[18]。

本文主要研究了在网络虚拟化环境下如何生成最优的资源监控方案。为了减少资源监控产生的通信开销，提高监控系统的响应速度，设计了基于代理的资源监控策略，并将量子遗传算法引入到监控方案的制定过程中。仿真结果显示与同类监控策略相比，本文提出的资源监控策略能够以较低的通信代价完成资源状态信息的上报和收集。

2 网络资源监控模型

在网络虚拟化环境下，底层网络模型包括以下几个部分：

(1)底层节点：底层节点不但具有路由功能，同时还可以承载虚拟节点，为网络服务提供其所需的计算存储资源，包括可用CPU、内存等等。每个底层节点都要对本节点的资源状态进行感知并上报。

(2)底层链路：底层链路用于承载虚拟链路，一条虚拟链路可以映射在多条底层链路上。底层链路的属性包括带宽、时延等等。底层链路的状态可以由与其相连的底层节点来进行感知。

(3)中心管理节点：中心管理节点一方面对底层网络域内所有节点和链路的资源状态进行收集和维护，另一方面还负责接收服务提供商提交的虚拟网请求，并根据底层网络的资源状态为虚拟网请求制定合适的映射策略。中心管理节点可以部署在一个专门的服务器上，也可以部署在域内的一个或多个底层节点之上。本文假设每个域只设置一个中心管理节点，并在底层网络中任选一个底层节点作为中心管理节点。

在虚拟网的运行过程中，对底层网络的监控将产生一定的通信开销。若所有的底层节点都将自己的状态信息直接上报给中心管理节点，将会造成状态信息的传输路径过长，从而增加了监控系统的响应时间和带宽消耗，而且也会引起中心管理节点的负载压力过大。为了解决上述问题，在监控系统中引入了监控代理 (monitoring agent)的概念：

(4)监控代理：在底层网络中，除了中心管理节点以外，还可以选择部分底层节点作为监控代理，监控代理将收集自身及其附近节点上报的状态信息，并将这些状态信息进行整理后再统一上报给中心管理节点。监控代理将会记录并维护其所监控的底层节点的实时状态，若底层节点上报的状态与其之前上报的状态相比没有发生变化，则监控代理则会过滤掉该状态信息，进一步减少资源监控所消耗的通信代价。每个底层节点只向一个监控代理进行状态上报。

虚拟网资源监控体系如图1所示。在把部分底层节点设置为监控代理之后，其余的底层节点将会把自身的资源状态及其周边链路的状态上报给监控代理，再由监控代理进行汇总和过滤后统一上报给中心管理节点。由此可见，设置监控代理的目的是为了减少底层节点上报状态信息所需的时间和带宽开销，而监控代理的部署方案将会对整个监控系统的效率产生很大的影响。

资源状态信息上报的通信开销主要包括两个方面：(1)信息传递消耗的带宽资源，假设每个节点上报的信息量相等，则带宽消耗主要取决于信息传递路径的跳数；(2)信息传递消耗的时间，这主要与信息传递路径上每条链路的时延相关。因此，节点 s向目的节点t上报状态信息的通信开销可以定义为s和t的最短路径上所有链路的时延之和。

其中p(s,t)为节点s到节点t的某一条路径，d(l)为底层链路l的时延。

图1 虚拟网资源监控体系

资源状态监控的整体通信开销主要包含两个部分：(1)所有底层节点向指定的监控代理进行状态上报的通信开销；(2)所有监控代理向中心管理节点进行状态上报的通信开销。最优的监控代理部署策略应该使得所有底层节点能以最小的整体通信开销来完成状态信息的上报，因此可以把监控代理的部署转化为一个0-1规划问题，问题模型如下：

变量：

xi为二进制变量，如果编号为i的节点是监控代理，则xi为1，否则xi为0；

输入：

N为底层节点的集合；C为最短路矩阵，C(s,t)为源端点s到目的端点t的通信开销；m为中心管理节点的编号。

目标函数：

约束：

其中式(2)定义了资源监控的通信开销，ai是负责收集第i个底层节点状态的监控代理。式(3)表示将节点i的ai指定为与其具有最小通信开销的监控代理。

3 基于改进型量子遗传算法的监控代理部署

为了使资源监控的整体通信开销最低，监控代理部署方案需要确定在底层网络中设定多少个监控代理，以及将哪些底层节点设置为通信代理。由于量子遗传算法在处理离散型优化问题方面有着良好的性能，本文提出了一种基于改进型量子遗传算法的监控代理部署策略(Monitoring Agents Deployment policy based on Advanced Quantum Genetic Algorithm, AQGA-MAD)，该策略在基本量子遗传算法的基础上，加入了动态旋转角机制、量子变异、群体灾变等改进措施，并用其求解第 2节中描述的0-1规划问题，从而得出最优的监控代理部署方案。

3.1 获取最短路矩阵

为了求解 0-1规划问题，首先需要计算出输入参数C，也就是求解每个底层节点到所有其它节点的最小通信开销，因此可将该问题转化为求解网络中的最短路径。求解步骤是：先将底层网络拓扑转化为一个带权无向图，图中每条边的权值为底层链路的时延。然后通过多次调用Bellman-Ford算法[19]依次计算出每个底层节点到其它节点的单源最短路径，并记录在矩阵C中，C中第s行第t列上的值表示状态信息从节点s上报到节点t所需的最小通信开销。

3.2 量子遗传算法的初始化

量子遗传算法是基于量子比特和量子叠加态的概念提出的，量子比特是量子计算中的最小信息单元，量子比特可以处于|0〉态，|1〉态，以及|0〉和|1〉之间的任意叠加态，其状态可以描述为

其中, α β是复数，分别表示量子比特为|0〉和|1〉的概率幅，表示量子比特被观测为|0〉态的概率，表示量子态被观测为|1〉态的概率，且满足归一化条件：

量子遗传算法的运算对象是由多个可行解组成的种群，可行解可以看作是个体的染色体，每个染色体由多个量子比特组成，一个量子比特的概率幅可以定义为[αβ]T，而一个由m位量子比特组成的染色体的编码形式为

染色体中的每个基因可以为|0〉态和|1〉态，以及|0〉和|1〉的叠加态，一个染色体可以同时描述 2m个状态，在观测时染色体将坍缩为一个确定的状态。这种编码方法使得量子遗传算法比传统的进化算法拥有更好的种群多样性。

在AQGA-MAD策略中，染色体中的第i个量子位 qi表示是否将第 i个节点设置为监控代理，qi为|0〉态表示该节点不设为监控代理，qi为|1〉态表示将该节点设置为监控代理。由于在底层网络中，监控代理的数量一般会小于其它底层节点的数量，所以为了加快量子遗传算法的收敛速度，在染色体初始化时，可以使量子位被观测为|1〉态的概率小于被观测为|0〉态的概率，AQGA-MAD策略将第0代染色体随机设为一个满足上述约束的固定值。

3.3 适应度计算

在确定了染色体的编码以后，就可以对染色体进行测量，并计算种群中个体的适应度。测量就是使染色体中的每个量子比特都坍缩为一个确定的状态。测量的方法是为每一个量子比特都生成一个随机数，若该随机数小于2| |α，则该量子比特位的测量值为0，否则为1。

适应度是衡量个体好坏的标准，也是决定量子旋转角度的主要依据。适应度越高代表个体离最优解越近，资源监控消耗的通信开销也就越小，因此对于个体来说，可将式(2)进行变换得出适应度函数为

在计算一个监控代理的部署策略X的适应度之前，都要先为每个底层节点指定一个固定的监控代理ai, AQGA-MAD策略是将ai设为与节点i具有最小通信开销的监控代理。

3.4 量子旋转门

在量子遗传算法中，可以通过量子旋转门来进行种群的更新。量子旋转门是一种具有酉性的矩阵，用于改变量子叠加态的概率幅，其定义为

其中k为[0,1]中的常数，n为当前的进化代数，N为最大进化代数。

3.5 量子变异和群体灾变

为了防止量子遗传算法在运行时陷入局部最优解，可以通过采用量子变异和群体灾变的方法对量子遗传算法的性能进行改进。量子变异可以使种群产生新的个体，其方法是在每一代的进化过程中，以很小的概率随机在染色体中指定一个变异位，并将变异位上α和β的值进行对调。若最优个体在经历了多代进化后仍然没有发生变化，则表明算法可能已经陷入了局部最优解，这时可以通过群体灾变来使算法能够搜索新的解空间，从而脱离局部最优解。群体灾变的具体操作是只保留群体中最优个体，而对其它全部个体重新进行初始化，初始化的策略是为染色体的每个量子位生成一个范围在(0,0.3)内的随机数r，并将该量子位的α设为设为。

表1 量子旋转门的调整策略

3.6 部署方案生成流程

在本策略中，将采用改进型量子遗传算法来计算监控代理的部署方案。首先随机生成m个部署方案并对其进行编码，形成初始种群，然后调用改进型量子遗传算法进行计算，在进行N轮进化后算法终止，输出进化过程中的最优解作为最终的部署方案，并按照该方案进行监控代理的部署。策略执行流程如表2所示。

4 仿真结果分析

本实验在Pentium 4 CPU 3.2 GHz, 1 G内存的PC机上运行。底层网络拓扑由GT-ITM工具[20]生成，底层链路时延的取值在[1,100]内均匀分布(单位为 ms)。仿真程序在 Matlab下实现并运行。AQGA-MAD的仿真结果将与IMO[8], HotSpot[9]生成的监控代理部署结果进行对比，此外还将仿真结果与基于遗传算法(GA-MAD)与基于基本量子遗传算法(QGA-MAD)的资源监控策略进行了对比。各个策略的评价标准为式(2)所定义的全网监控通信开销。AQGA-MAD的种群大小设为20，变异概率设为0.01。

首先对各个监控策略计算出的监控代理数量进行分析。IMO和HotSpot都不支持自动确定最优的监控代理数量，只能依靠管理人员事先指定，而监控代理数量的设置会对通信开销产生较大的影响。基于智能算法的部署策略能够自动计算出最优的监控代理数量，使其计算出的部署方案不受人为设置的影响。由图2可知，当底层网络的规模为100个节点时，若将监控代理节点占全部节点的比例分别设为8%和16%，则IMO和HotSpot计算出的方案评价最好；当底层网络的规模为500个节点时，将监控代理节点的比例都设为10%时上述两种策略才能计算出最优的方案。而AQGA-MAD计算出的部署方案的监控代理比例则不是固定的，不同的底层网络会有不同的监控代理比例(如图 3所示)，取值的范围一般在[0.05, 0.15]之间。

表2 筞略抽行流程

进化代数n是遗传算法的迭代次数，n的取值越大，算法求得的解就越好。HotSpot和IMO没有进化代数的概念，其最优解只受监控代理比例的影响，因此HotSpot和IMO的部署方案设为这两种策略在最优比例(16%和8%)下生成的方案。图4给出底层网络规模为100个节点时，各类策略生成的最优部署方案的进化过程。可以看出，AQGA-MAD的收敛速度最快，其计算出的部署方案所消耗的通信开销也最少，其次是QGA-MAD和GA-MAD，而这3种策略计算出的部署方案都好于HotSpot和IMO。

如图5所示，随着网络规模的扩大，各个策略生成的最优部署方案的通信开销也会增大。在每个不同的网络环境下，AQGA-MAD生成的部署方案都要优于其它策略生成的部署方案。

图2 监控代理数量对IMO和HotSpot的影响

图3 AQGA-MAD在不同网络规模下的监控代理比例

图4 最优解的进化过程

图5 不同网络规模下各个 策略的通信开销

5 结束语

本文针对虚拟网构建与管理的实际需求，设计了一种网络虚拟化环境下的资源监控策略，该策略通过设置监控代理来减少资源监控所需的通信开销。为了把整个监控系统的通信开销降到最低，首先将监控代理的部署问题转化为 0-1规划问题，并利用改进的量子遗传算法求解该问题，从而得到最优部署方案。仿真实验表明，本文提出的策略不但无需管理员手动设置监控代理的数量，而且生成的部署方案比其它策略所消耗的通信开销更少。

[1] Chowdhury M and Boutaba R. A survey of network virtualization[J]. Computer Networks, 2010, 54(5): 862-876.

[2] Biao S, Mohammad H, and Eui-Nam H. Delivering IPTV service over a virtual network: a study on virtual network topology[J]. Journal of Communications and Networks, 2012,14(3): 319-335.

[3] Jorge C and Javier J. Network virtualization: a view from the bottom[C]. Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures,Barcelona, Spain, 2009: 73-80.

[4] 蔡志平, 刘强, 吕品, 等. 虚拟网络映射模型及其优化算法[J].软件学报, 2012, 23(4): 864-877.Cai Z P, Liu Q, and Lü P, et al.. Virtual network mapping model and optimization algorithms[J]. Journal of Software,2012, 23(4): 864-877.

[5] Chowdhury M, Rahman M R, and Boutaba R. ViNEYard:virtual network embedding algorithms with coordinated node and link mapping[J]. IEEE Transactions on Networking, 2012,20(1): 206-219.

[6] Yu M, Yi Y, and Rexford J. Rethinking virtual network embedding: substrate support for path splitting and migration[C]. Proceedings of ACM SIGCOMM on Computer Communication, Seattle, WA, USA, 2008: 17-29.

[7] 齐宁, 王保进, 汪斌强. 均衡虚拟网构建算法研究[J]. 电子与信息学报, 2011, 33(6): 1301-1306.Qi N, Wang B J, and Wang B Q. Research on balanced construction algorithm of virtual network[J]. Journal of Electronics ＆amp; Information Technology, 2011, 33(6):1301-1306.

[8] Clayman S, Clegg R, Mamatas L, et al.. Monitoring,aggregation and filtering for efficient management of virtual networks[C]. Proceedings of the 7th International Conference on Network and Services Management, Paris, France, 2011:234-240.

[9] Mamatas L, Clayman S, Charalambides M, et al.. Towards an information management overlay for emerging networks[C]. Proceedings of Network Operations and Management Symposium 2010, Osaka, Japan, 2010: 527-534.

[10] Houidi I, Louati W, and Zeghlache D. Virtual resource description and clustering for virtual network discovery[C].Proceedings of the ICC Workshop on Communications,Dresden, Germany, 2009: 1-6.

[11] Soares M A and Madeira E R M. A multi-agent architecture for autonomic management of virtual networks[C].Proceedings of Network Operations and Management Symposium 2012, Maui HI, USA, 2012: 1183-1186.

[12] Miyamura T, Ohsita Y, Kamamura S, et al.. Management of managed self-organizing network in network virtualization environment[C]. World Telecommunications Congress(WTC), Miyazaki, 2012: 1-6.

[13] Ghazar T and Samaan N. Pricing utility-based virtual networks[J]. IEEE Transactions on Network and Service Management, 2013, 10(2): 119-132.

[14] Zhang Zhong-bao, Cheng Xiang, Su Sen, et al.. A uni fi ed enhanced particle swarm optimization-based virtual network embedding algorithm[J]. International Journal of Communication Systems, 2012, DOI: 10.1002/dac.1399.

[15] Fajjari I, Aitsaadi N, Pujolle G, et al.. VNE-AC: virtual network embedding algorithm based on ant colony metaheuristic[C]. 2011 IEEE International Conference on Communications ICC, Kyoto, Japan, 2011: 1-6.

[16] Narayanan A. An introductory tutorial to quantum computing[C]. Proceedings of IEEE Colloquium on Quantum Computing Theory, Applications and Implications, London,1997: 1-3.

[17] Han K H, Park K H, Lee C H, et al.. Parallel quantum inspired genetic algorithm for combinatorial optimization problem[C]. Proceedings of the 2001 Congress on Evolutionary Computation, USA, 2001: 1422-1429.

[18] 邢焕来, 潘炜, 邹喜华. 一种解决组合优化问题的改进型量子遗传算法[J]. 电子学报, 2007, 35(10): 1999-2002.Xing H L, Pan W, and Zou X H. A novel improved quantum genetic algorithm for combinatorial optimization problems[J].Acta Electronica Sinica, 2007, 35(10): 1999-2002.

[19] Bellman R. Dynamic Programming[M]. Princeton: Princeton University Press, 1957: 124-126.

[20] Zegura E, Calvert K, and Bhattacharjee S. How to model an internetwork[C]. Proceedings IEEE Fifteenh Annual Joint Conference of the IEEE Computer Societies, Networking the Next Generation, INFCCOM’96, San Francisco, USA, 1996, 2:594-602.