利用多目标优化方法实现的GSON网拓扑构建算法

赵 星

(陕西财经职业技术学院，陕西 咸阳 712000)

利用多目标优化方法实现的GSON网拓扑构建算法

赵 星

(陕西财经职业技术学院，陕西 咸阳 712000)

覆盖网(Overlay)虚拟化能有效分离网络应用服务与底层网络基础设施，提升服务质量和用户体验，设计了一种利用多目标优化(multi-objective optimization, 简称MOO)的通用覆盖网(general service overlay network，简称GSON)网拓扑构建算法(MOO-GSON)。该算法利用多目标优化模型提出了以服务节点和物理链路重用为约束，从而提高了虚拟拓扑与物理网络匹配度，最小化虚拟链路代价。降低了网络总体开销。采用随机网络拓扑进行试验仿真的结果表明，在满足各类约束的条件下，本算法能有效地优化时间和成本。

异构网络；QoS参数；参数映射；映射模型；映射方法；Omnet

Overlay是移动互联网体系中部署为满足各种新业务发展需求的虚拟化网络。移动互联网是互联网与移动通信网的融合[1]，Overlay借助虚拟化技术，在原有网络基础之上虚拟化服务节点以及连接服务节点的虚拟链路组成虚拟网络。虚拟网通过虚拟节点和虚拟链路相连接，为移动互联网的新业务提供增值服务和QoS保障，形成GSON。核心网络运营商利用虚拟化技术， 不仅能够便捷地在现有网络架构基础上推出新兴服务，而且能够统一管理各个虚拟网，一方面加快了新服务的部署速度，另一方面降低了基础设施的投入成本[2]，并为 QoS 的敏感业务提供良好的 QoS 保证[3]。

Overlay可以根据其应用分为多种，包括P2P overlay network，服务覆盖网(service overlay network，简称SON)，内容分发网络(content deliver network，简称CDN)以及虚拟实验床 PlantLab等。大多数Overlay服务提供商根据服务需求、终端用户的规模等设置节点服务器，节点通常由服务内容提供商与ISP(Internet 服务提供商)签署相关服务等级协议(service level agreement，简称SLA)部署，同时向ISP提供带宽保障[4]。由于应用型的Overlay架构、节点部署，ISP 带宽预留租用等都需要大的投资资金，拓扑设计就成为 Overlay 构建的关键问题。选择良好的拓扑构建和优化算法，能够满足运营需求，提供给终端用户具有端到端QoS保证的Internet增值服务，同时考虑最优的拓扑结构，最少的构建费用和带宽预留的租用费用。

Overlay的拓扑构建本质是在 ISP 提供的底层物理网络中抽象出一个子网，该子网能够提供指定节点间的数据传输服务。其拓扑是一种层次化拓扑，层次化拓扑在节点固定的情况下，根据节点关系和互联网的自治域(autonomous system)链接来生成Overlay的拓扑，其逻辑拓扑和物理拓扑有较好的匹配性，易于优化提高网络的资源利用率和数据传输性能。本文设计了一种通用型的服务覆盖网(GSON)拓扑构建算法——基于多目标优化的GSON构建算法(multi objective optimization，MOO-GSON)，该算法结合服务节点和节点间链路性能感知物理拓扑，并利用最小生成树来优化覆盖网逻辑链路，进行算法收敛，具有与物理拓扑匹配度高，整体开销小的优点。

1 国内外研究现状

根据覆盖网的结构，其拓扑构建方式可以分为集中式拓扑(centralized topology)、分布式非结构化拓扑(decentralized unstructured topology)、分布式结构化拓扑[5]和层次化拓扑(hierarchical control)，集中式拓扑中，Overlay架构包括控制节点和一般节点，集中式机构由于控制节点存在单点失效，安全性和通信流量问题，因此只针对特定规模应用[6]。结构化Overlay系统通常利用DHT等来构建虚拟的应用层覆盖网络，相比起无结构化Overlay和P2P 系统，其路由更有目的性，构建并不基于节点物理位置，易造成逻辑拓扑结构和物理拓扑结构不匹配。基于移动互联网的Overlay整合了多项新业务应用，作为一种GSON，具有层次化特征。Overlay节点均为服务器节点，除路由存储转发功能外，还提供其他处理能力，其虚拟链路则由多条物理链路组成，能够结合应用层的业务需求，选择相应的应用层资源。

目前，Overlay拓扑构建作为覆盖网路由，资源搜索定位和信息分发的基础，对上述功能有极大影响。而Overlay拓扑构建中影响Overlay性能的关键问题是拓扑的感知和拓扑的匹配，层次化Overlay构建中，由于节点的部署是固定的，其拓扑发现和构建的关键点在于构建拓扑的虚拟链路。算法可大致分为2类：一类算法基于坐标和位置信息来优化结构化网络使得拓扑具有更好的匹配性，如有关文献提到的基于Chord和基于CAN改进的Overlay构建算法；另一类算法基于节点位置感知底层拓扑构建虚拟链路和Overlay拓扑，其中较为经典的算法分别是最小生成树算法和临近连接算法等。

最小生成树算法在全网状覆盖层拓扑的基础上进行多次最小生成树的构建。KMST链路代价为物理层网络层跳数，其优点是便于实现性能测量开销最小化，缺点是网络跳数感知不能获得物理链路的重用而导致的网络拥塞。基于KMST同时感知物理链路的的Overlay拓扑构建算法是拓扑感知K最小生成树算法，该算法是基于全网状覆盖层拓扑，感知物理节点和链路被纳入拓扑的次数，其构建最小生成树代价是链路跳数，当两跳覆盖网链路通过相同的IP层链路，则根据通过的相同IP链路数目增加这两条覆盖网链路的代价；因此，算法提供了节点对在IP层不同的物理路径匹配，避免了链路和节点的过载。

2 构建目标模型

基于移动互联网的GSON构建准则如下。

1)约束条件。约束条件体现在节点约束和链路约束，节点约束表示物理节点的处理能力存在限制，虚拟链路不应多次经过服务节点，增加转发和处理压力，增大节点度数；链路约束包括构造的逻辑链路最大可用带宽，跳数存在限制，由于链路可用带宽限制，要求物理链路不能重复被多条虚拟链路抽象，当出现物理链路重用，应相应增大虚拟链路代价。

2)最大最小化要求。最大最小化要求体现在感知物理网络基础上进行拓扑优化，在满足业务运营要求基础上，构建GSON能够最大化网络资源利用率，最小化网络构建的时间代价和成本代价，最大化提升用户体验以及可用资源利用率。

(1)

(2)

B(eij)≥B0,w(eij)≤L

(3)

在满足节点约束和链路约束的条件下，最小化网络构建的时间和成本代价，并尽可能最大化用户体验和网络资源利用率，该问题可以被完全建模成一个多目标优化模型，可以使用整数线性规划来求解模型，该模型中c,b,a均为确定的参数：

(4)

根据整数线性约束集合具有的结构特点，整数线性约束集合中的复杂约束通过拉格朗日乘子被引入到目标函数中，导出具有约束系数矩阵是全幺模矩阵特点的整数线性规划问题，从而这类整数线性规划问题能用单纯形法迭代地求解。该问题采用多目标优化建模抽象Overlay拓扑构建问题，利用线性规划和单纯形法获得模型的最优解可以作为算法优劣的评价标准。

3 算法流程

根据建模阶段的理论结果，将算法分成两阶段，第一阶段实现满足约束，满足节点和链路能力的约束需求，构建虚拟链路时，将经过的重用节点虚拟链路删除，并将重用的物理链路代价增大；第二阶段实现优化需求，在原有虚拟链路基础上，根据最小化条件进行拓扑优化。因此，算法分为拓扑构建和拓扑优化两阶段；拓扑构建是在部署节点的Overlay上，根据物理网络链路，构建全相连的虚拟链路，计算每一个虚拟节点与其他节点之间虚拟链路代价，链路代价计算利用节点、跳数以及链路重用作为约束，在每次进行计算时其值会随着经过的节点以及重用的链路跳数动态改变，深度遍历以后最终的输出是一个或多个无环无重边的无向连通分支，分支之间是不连通的；拓扑优化是在多个分支基础上构建满足最小化的子图，遍历拓扑判断连通性，针对每个子图构建最小生成树，得到生成树森林，形成GSON的虚拟链路。

在拓扑构建阶段，排序服务节点，将所有节点设为全相连，感知服务器节点间的物理路径，选取网络层拓扑的跳数作为路径的代价，构建两虚拟节点之间的虚拟链路，回避服务节点，如虚拟链路经过Overlay中的节点，将w(eij)标记为无穷大，并跳出计算；对物理链路的重用进行计数，每次选取同一跳物理链路时，该虚拟链路的代价w(eij)增加一个物理单位；因此，链路代价值将随经过节点和链路重用而改变。构建拓扑得到的拓扑结构较复杂，节点之间存在多个虚拟链路，需要进一步优化，剪去多余链路，缩小路由表项规模，便于实现GSON的路由，资源查找定位以及多播等多项服务网络的通用功能。

在拓扑优化阶段，选用图的深度遍历算法或者广度遍历算法从根出发对拓扑构建得到无向图进行遍历，得到1个或多个分支，多个分支之间是不连通的。采用Prim等贪心策略执行最小生成树算法，得到生成树或者生成森林(每个生成树则为1个连通分支，生成森林则为该图的连通分支集合)。基于最小化构建成本代价和时间代价作为一个优化后的模型，结构简单，便于应用服务的加载，能有效提高业务的QoS和用户的QoE。

基于MOO的GSON网构建拓扑算法(MOO-GSON)为

输入：物理网络的拓扑G。

输出： 构建代价最小且感知物理拓扑的Overlay

1)初始化所有Overlay 节点，并将各个节点设为全相连，边权值为null。

2)计算全相连虚拟链路的实际值，并赋值；当虚拟链路经过Overlay节点，则设边权值为∞，跳出；当虚拟链路经过重用的物理链路，该虚拟链路权值动态增加，继续(得到虚拟链路的构建拓扑)。

3)深度遍历构建好的拓扑，得到各个连通分支(连通分支数≥1)。

4)深度遍历构建好的拓扑，得到各个连通分支最小生成树。

5)保留各个连通分支最小生成树的边，构成优化的拓扑。

基于多目标优化的GSON拓扑构建算法特点在于：1)在网络层拓扑感知部分，考虑链路复用保证了网络层链路较低的重用，并避免了服务节点的重复计算，使得构建出的覆盖网与网络层拓扑保持较高的匹配度，且具有更好的抗毁性能；2)基于最小生成树算法优化逻辑链路，使整个覆盖网拓扑的代价为最小，有效保证服务节点间的通信，保证了更好的业务QoS和用户QoE。

4 仿真实验与数据分析

4.1 仿真环境

本文采用GT-ITM拓扑产生器创建平面随机图进行试验仿真，GT-ITM是由乔治亚理工学院于2000年研发并投入到大规模Internet的仿真模拟的研究中。许多文献的研究都使用该拓扑生成器进行模拟仿真。随机拓扑结构适用于大规模网络拓扑仿真。使用随机拓扑进行仿真可以客观验证算法的普遍适用性，在和同类算法进行对比仿真实验时其仿真结果更为可信。

GT-ITM可生成各种平面随机图作为模型。基本模型是纯随机模型，随着边概率函数不同，GT-ITM包括Waxman 1，Waxman 2 和Doar-Leslie多种幂律拓扑。本文采用Waxman 1模型。在Waxman 1模型中，从节点u到v的存在边概率为P(u,v)=α×exp(-d/(βL))，其中0<α，β≤1，d是节点u,v的欧式距离，L是平面上任意两节点间的最大距离。当增加α时，模型将有更多短边，更长跳数，β增大则增加图中长边比例。

采用文件形式输入模拟器构建模型，拓扑的节点随机选取，智能服务器在所有节点中占有的比例为Ps。本试验的目的在于验证算法有效性，在有效优化拓扑基础上，尽量减小网络时间代价，从节点度和时间复杂度来验证算法。服务节点的节点度决定了转发的大小以及Overlay中和其他服务节点相连的有效路径的多少。本文设计了GSON拓扑构建算法中，节点度通过虚拟链路数来获得，通常情况下，当其他性能参数一致，则节点度越低越好，因为高节点度会增大网络拓扑的维护开销。GSON拓扑构建算法除了能够构建出与物理层匹配的拓扑外，还需控制其时间性能，使得服务节点能够有效转发数据。

4.2 数据分析

本算法在仿真过程中选取了2种Overlay拓扑构建算法，即最小生成树算法(KMST算法)和最小生成树算法(TKMST算法)，算法选取节点度和算法时间性能进行评估。节点度体现了该节点在逻辑链路路径数，节点度包含出度入度，通常较低较平均的节点度能体现网络资源的均衡利用。算法的时间复杂度是算法的直接开销，体现了实际组网应用的价值。3种算法节点度和时间复杂度的性能分析对比如图1和图2所示。图1中，横坐标为GT-ITM随机拓扑中的参数α，α值的大小与网络中节点个数成正比；图2中，横坐标为另一个参数β，β增加节点不变情况下边长增加。仿真时，本文将参数设定为：s=0.3。

图1 3种算法节点度、时间复杂度与节点数目关系对比

图2 3种算法节点度、时间复杂度与边长关系对比

图1为本算法与KMST算法、TKMST算法仿真时的节点度、时间复杂度与节点数目之间关系的对比情况。TKMS-T算法的平均节点度最低，本算法的平均节点度处于中间位置，而KMST算法的平均节点度远高于前2个算法。其主要原因是本算法在拓扑构建时充分考虑节点的重用，因此算法在节点度上高于KMST，低于TKMST。对于时间复杂度，本算法在节点度数增加时，其时间复杂度增幅在二者之间，但在节点数目增多时，收敛较快。

图 2为本算法与KMST算法、TKMST算法仿真时的节点度、时间复杂度与边长度之间关系的对比情况。长边比例增加，物理跳数不变，将降低本算法的链路复用，而长边比例对三种算法的时间复杂度关系暂无明显影响，本算法时间复杂度仍处于二者之间。考虑到算法的构建成功率，仿真中将有30%左右概率KMST算法和TKMST算法无法完成覆盖网构建，主要原因是KMST算法和TKMST算法在构建最小生成树的拓扑上遇到了非连通分支，导致算法的非正常收敛。而本算法考虑非连通分支能够在此基础上判断并进行拓扑优化，因此本算法更具实用性。

5 结语

网络虚拟化将应用服务与物理网络设施分离，从而在不改变网络设施的基础上，有效提升业务QoS和用户QoE。本文关注Overlay的拓扑构建问题，采用多目标优化的方法对该问题进行建模，分析了求解的线性规划方法，给出了为解决链路和节点重用的构建基本方案，该算法基于最小生成树方法，将原始Overlay拓扑进行优化，得到一个简约高效的Overlay的拓扑结构，减小了Overlay构建的时间和代价成本，简化了服务器节点路由器表空间。为验证本方案的有效和实用性，从理论分析和仿真角度做出了对比，仿真采用随机网络生成器提供试验数据，和传统算法KMST和TKMST相比，优化过程增加了对节点的感知和算法收敛条件，拓扑构建结果对物理网络有更好匹配度。试验结果表明，该算法在满足各约束的基础上，有效优化了生成的时间和成本代价。

[1]李伟, 徐正全,杨铸.应用于移动互联网的 Peer-to-Peer 关键技术[J]. 软件学报, 2009, 20(8): 2199-2213.

[2]齐宁, 均衡虚拟网构建算法研究[J]. 电子与信息学报, 2011(6): 1301-1306.

[3]Zhi L, Mohapatra P. QRON: QoS-aware routing in overlay networks. Selected Areas in Communications, IEEE Journal on, 2004, 22(1):29-40.

[4]Duan Z, Zhang Z, Hou Y T. Service overlay networks: SLAs, QoS, and bandwidth provisioning. IEEE/ACM Transactions on Networking (TON), 2003，11(6):870-883.

[5]张栋,吴春明,姜明,等. 大规模服务覆盖网拓扑设计[J]. 电子与信息学报, 2010(4): 841-845.

[6]Lua E K. A survey and comparison of peer-to-peer overlay network schemes[J]. IEEE Communications Surveys and Tutorials, 2005，7(1-4): 72-93.

责任编辑李思文

OverlayConstructionandOptimizationMethodwithMOO

ZHAO Xing

(Shaanxi Vocational College of Finance and Economics, Xianyang 712000, China)

Considering that the Overlay (network) virtualization can effectively separate network application service and the underlying network infrastructure, improve service quality and user experience. A way was designed by using a multi-objective optimization (multi - objective optimization, MOO), a general network (GSON) network topology construction algorithm (MOO-GSON), the algorithm using the multi-objective Optimization model is put forward to the service nodes and the physical link reuse as constraint, thus improve the virtual topology and the physical network compatibility, minimized the virtual link cost, reduces the network overhead as a whole. Using random network topology experiment simulation, the results showed that under the condition of satisfying various constraints, the algorithm can effectively optimize the time and costs.

heterogeneous network, QoS parameters, parameter mapping, mapping model, mapping method, Omnet

TP 393.2

：A

赵星(1982-)，男，讲师，主要从事计算机技术及教学等方面的研究。

2015-01-05