基于遗传算法和虚拟化技术的网络配置方法*

2020-05-18孙美卫

菏泽学院学报 2020年2期

孙美卫

(泉州经贸职业技术学院信息技术系，福建泉州 362000)

引言

近几年，除了网络数据激增之外，以大数据为基础的数据分析也显著增加.大数据处理有着极大的容量要求，这为通信开销带来了很大负担，因为在利用远程计算机资源时需要进行数据迁移[1].此外，频繁的数据迁移也会产生安全问题.在分析和处理大数据时，经常遇到这样的问题，即：大规模计算机被集中在某个特定的位置(如数据中心)，而数据附近的计算机资源可能不足以分析大容量数据.

光虚拟网络[2]是解决上述问题的重要手段，目前已有一些光虚拟网络构建方法.如利用波分复用(Wavelength Division Multiplexing, WDM)[3,4]技术满足速率和容量需求的光网络构建方法.然而，总体来看，虽然网络链路上实施了高速WDM，但电信号和光信号的转换，以及节点上的跨层处理是数据传输的瓶颈.为了解决此问题，诸多学者提出了相应的措施，如罗广俊等[5]人提出采用光交叉连接(Optical cross connect, OXC)技术，通过数据包传输的光切换来解决[5]，也就是任何节点间数据发送和数据接收的传输路径均使用的光波长进行标记.

Halabi 等人[6]应用IP和光信号特性进行网络虚拟化.由于光信号的不同波长不会对彼此产生干扰.因此，对于不同网络使用不同波长，进行各自波长的操作，可使得在相同的物理链路上可创建多个不同的虚拟链路.其优点是能够通过光切换技术，降低路径中数据包传输时的IP处理数量.

Tode等[7]提出了“阿米巴网络架构”，该架构使用光波长路径将分散于不同地理位置的节点组合在一起，并向该节点集合赋予路由器功能.通过OXC实现光传输层中的高速交换处理，以实现节点集合的互连.其优点是降低IP处理数量，通过在IP层的网络规模简并降低路由处理的复杂性.另一方面，仅通过识别阿米巴节点就可对拓扑的处理能力进行自由调整，不需要对物理设施进行加强.

以往的大数据分析方法围绕着几个庞大的数据中心进行集中式计算.本文提出了基于细粒度的云计算，在分布式并行计算环境中进行大数据分析.假设分布式计算资源，建立一个低延迟的计算环境，其中计算机资源位于用户附近.该方法通过降低延迟拉近计算机资源与大数据的距离，来实现对所分配的计算机资源在距离方面的公平性.最后，测试所提算法的用户和供应商的公平性指数，以及光波长路径总数的变化情况.

1 光虚拟网络配置方法

基于计算机资源以细粒度[8]分布，提出建立一个低延迟的边缘计算环境，其中计算机资源被放置于用户附近.从网络基础设施的角度，旨在提升计算机资源之间的邻近度.在大数据方面，通过引入一个光虚拟网络，降低用户将数据传输到计算机资源的延迟，该虚拟网络应用了光波长路径技术，以实现IP级网络拓扑的自由更改[9].本文计算环境结构如图1所示,计算机资源的所有者为小规模供应方：各个企业和个人被放置于一个公用通信运营商所提供的网络基础设施上.

图1 提出的计算环境的结构

1.1 网络模型和控制流程

研究的网络模型使用两种类型的终端主机，分别称为“用户”和“供应商”，连接到物理光网络的每个节点.用户请求大数据分析计算机资源,供应商向用户提供计算机资源.此外，计算机资源表明计算机的总体计算力，并概括出CPU和内存容量等性能参数.

控制器和所有用户、供应商相互连接，随时收集来自网络中每个节点的流量信息，并接收用户的计算机资源请求和供应商的计算机资源供给.控制器通过使用一个遗传算法[10](Genetic Algorithm, GA)，确定任意两个节点之间光波长路径的最优配置，以及能够满足每个用户需求的计算机资源分配，并将信息传输到网络所有节点和用户.其中，信息节点通过设定与相应节点间的光波长路径，构建出一个光虚拟网络.其后，供应商的计算机资源被分配给用户，以供其对大数据的分析和处理.

在真实的操作环境中，控制器接收到请求计算机资源的用户组，并为其执行该GA算法.此时，除了正在使用的计算机资源之外，其余可用计算机资源，被视为供应商的可分配资源容量的初始数值.出于效率考虑，本文对该问题应用了GA算法.这主要是因为大数据分析要求快速响应，而GA算法能够通过在范围宽广的求解区域进行多点搜索，推导出网络配置的最优解.

1.2 利用遗传算法推导出最优解

通过遗传算法推导光波长路径的最佳配置，以及分配给每个用户的计算机资源量.

1)染色体表达：即一个染色体与两条信息相关联.第1条信息是任意两个节点间的光波长路径的配置信息，其被直接表示为一个染色体表征；第2条信息是用户与供应商间资源分配的复合信息.基于这两条信息，确定每个染色体的相对优点.

算法的染色体表征代表从任意两个节点之间通过K-最短路径算法推导出K个路径，沿此路线设置任意两个节点间的光波长路径.每个基因被表示为整数[-K，K].即配置阿米巴节点的内部链路，而负整数则代表将节点连接在一起的外部链路，基因的绝对值对应于路由ID.当该数值为零时，表示不存在连接两个节点的光波长路径.

网络拓扑示例如图2所示，其网络拓扑中染色体表征的样例如图3所示.图3的染色体中最左边的数值指的是节点I和节点II间的路径，数值为-2.这说明节点I和节点II之间的外部链路(IP级逻辑链路)，沿着图2中三个不同路由间的NO.2路径所设定的光波长路径而实现.

图2 网络拓扑的示例

图3 染色体表征的示例

2)变异：在提出的算法中，染色体中任何一个基因(随机选择)均会变异为其他数值.此处，如果完全随机地将变异后的数值确定在[-K，K]中，则收敛效率会变得较差，因为在染色体中需要出现许多个“0”数值，以应对在染色体表征中需要展示真实解情况.但是，如果按上文所述方法确定变异后的数值，则会生成许多个包含极少“0”的染色体.由此，会形成很多使用过度的光波长资源的染色体，这样会造成无用解空间的搜索.

为避免这一问题，本文通过以下方法设定了变异算法.首先，以二分之一的相同概率，选择“0(无光波长路径)”或“一个非零数值(存在光波长路径)”.如果选择的是后者，则以相同的概率从[-K，1]或[1，K]中选择，并变异为该数值.由此，可以通过对算法进行调整使得“0”经常出现在染色体中，以搜索有效的解空间.

3)适应度：本文使用一个适应性度量，通过采用以下的目标函数F，确定基因的相对优点，当解的质量较高时，F的数值较小：

(1)

式中，User和Supplier分别表示用户和供应商的集合.此外，Demu(s)表示分配给用户u的供应商s的计算机资源，Hopu(s)表示从用户u至供应商s的IP跳数.由于所使用的计算机资源量的增加，会造成通信量的增加，因此有必要最大限度减少Demu(s)和Hopu(s)的乘积和.

4)操作程序：下文将展示基于前文的设置环境，基因算法的特定操作程序.

a)染色体组的初始化

使用随机数，建立起Nc个数量的染色体.

b)交叉

从染色体组中随机选择两个染色体，并通过这些染色体的均匀交叉，生成两个子染色体.重复这一操作，直到建立起Nc个数量的子染色体.

c)变异

通过1.2节的2)中介绍的变异方法，取一定概率Pm应用到两个染色体上，这两个染色体包括一个父染色体和一个子染色体.

d)选择

通过1.2节的3)中介绍的适应度方法，计算所有染色体的适应度，并执行Nc次的竞赛选择，以使得竞赛的规模为Nt.由此，确定具有子染色体的染色体的数量Nc.

e)重复从b)至d)的操作，重复次数为Ng代.

1.3 向每个用户分配的资源

最基本的资源分配方案包括“集体分配方案”，即贪婪算法.首先，该方案逐个选择用户，并识别出从该用户处通过最少IP跳数可以达到的供应商，并将这些供应商的全部空闲计算机资源分配给该用户.一旦该用户的资源请求得到了满足，则为下一个用户进行计算机资源分配.这一方案使得接收到首次资源分配的用户，可以使用邻近度最高的供应商所提供的计算机资源.然而，对后续用户所分配的计算机资源量中，将不包括已经被分配给其他用户的计算机资源.因此，在一个用户发起资源请求，而网络中可用的计算机资源量并不充足的情况下，该方案中网络用户与供应商的距离可能存在不公平现象.此外，该方案还可能使得过量的负载被集中在特定的供应商.

为解决这一问题，提出了一个“分割分配方案”，以确保用户和供应商之间在网络距离方面的公平性，并确保每个供应商的负载均衡.提出的方案确保了计算机资源的所有需求不会一次性分配给单个用户；而是通过将总资源请求量除以复数的轮，得到资源分配的单位量.

按照资源请求的接受顺序，为网络中每个用户分配一个ID.计算机资源的分配过程由“轮”组成(本文定义轮的数量为Ns).该程序在每轮过程中，逐个选择所有用户，并对供应商所支持的计算机资源量X(请求计算机资源量的1/Ns)进行分配.同时，该程序按照用户ID的升序和降序，在每轮交替切换用户的选择顺序，由此，本文通过更改用户选择的次序，解决上述的不公平性问题.

计算机资源的分配以“分配候选供应商列表”为基础，编制该列表的目的是根据特定用户对最高优先级的供应商进行调整，如图4所示.控制器为每个用户生成列表，并在每轮过程对该表进行更新.首先，在主要组中，按照总资源量内已经被分配给用户的计算机资源量的比例(定义为“资源利用率”)进行排序.若资源利用率相同，则按照与供应商距离最近的用户的数量进行排序(定义为“竞争力”).此外，若竞争力也相同，则按照与用户建立连接所需的IP跳数来进行排序.另一方面，在次要组中，将连接到用户所需的IP跳数作为首要排序指标，而资源利用率则作为次级排序指标，竞争力被用作最后排序指标.需要指出的是，在这两个组中，对所有排序指标中排名均相同的供应商进行随机选择.主要组中的成员与用户的邻近度均在可接受范围内，因此，该程序将供应商之间的负载均衡作为首要考虑目标.另一方面，次要组中的成员在与用户的距离方面处于可接受范围之外，因此，该程序将邻近度作为首要考虑目标，并在可能的情况下将负载均衡纳入考虑.

图4 分配候选供应商列表的示例

提出的方法不但考虑到邻近度，还考虑到了资源利用率和竞争力，可以避免将负载集中到某个特定的供应商.如果可接受邻近跳数被指定为一个较大的数值，则负载均衡的优先度最高；如果可接受邻近跳数被指定为一个较小的数值时，邻近度则成为优先考虑的指标.因此，可以通过配置来调整负载平衡和邻近度的具体比重.在对计算机资源进行分配时，提出的方案选择分配候选供应商列表中排名最前的供应商，并向用户分配特定的计算机资源量X.在对可用的计算机资源量进行分配后，提出的方法按照供应商列表中成员排序，依次进行资源分配.当对所有用户执行上述程序后，即完成一轮的处理.一轮处理的工作流程如图5所示.将该轮重复Ns次，直到所有用户请求均得到满足.

图5 每轮中每个用户的资源分配程序

2 仿真与评价

2.1 仿真环境

本文在连接到光网络的每个辖区中依次放置节点，总共包括48个节点和82条链路，通过计算机资源量设定每对节点之间的传输流量.随着用户所使用的供应商计算机资源的增大，流量也会增加.使用公式(2)计算用户i(位于节点i中的用户)与供应商j(位于节点j中的供应商)之间的流量traij如下：

traijfficij=A×Demij

(2)

其中，用户i所使用的供应商的资源量为Demij，A为比例常数.设置A为1，将单个链路中传输的流量上界和单个波长中的下界分别限制在5 000和100.

从48个节点中随机选出8个节点并逐个与用户连接，然后从剩余的40个节点中随机选出15个节点并逐个与供应商相连接.每个用户请求的计算机资源量为40，每个供应商提供的计算机资源量为30.K为两个节点之间导出的路由候选数量，Ns为提出的分割分配方案中的轮数，α为可接受的邻近跳数，分别设K=8，Ns=10，α=1,还为网络虚拟化设置了四个限制：

1)光波长路径的数量的上限，可在一个链路上进行多路复用，该上限被设为50；

2)通过光波长路径可以直接连接的物理跳数的上限，该上限被设为6；

3)组成一个阿米巴节点的节点数量上限，该上限设为7；

4)阿米巴节点内仅执行波长转换处理而不进行IP处理的连续跳数上限，设为2.最后，遗传算法相关的参数的数值设定如表1所示.

表1 遗传算法相关的参数

2.2 评价指标

将HU-S定义为邻近度的评价指标(如图7所示)，表示在资源分配关系中从用户至供应商的IP跳数.此外，假定对供应商之间的相互通信采用并行分析处理，定义HS-S表示向同一个用户提供计算机资源的供应商间的IP跳数.

通过度量每个用户的平均HU-S和平均HS-S，并推导出其Jain公平性指数[11，12].若该指数接近1，则意味着用户间的差异较小，公平性较高.此外，还度量了每个供应商的资源利用情况，并推导出其公平性指数，以进行负载均衡的评价.

2.3 评价分析

实验中，整个网络的光波长路径设为100个，每个用户的HU-S和HS-S的均值和公平性指数，以及每个供应商之间资源利用率的公平性指数如表2所示.本文对比了四种不同仿真案例：

1)“普通方法”，该案例将集体分配方案应用到一个不带虚拟化的普通IP网络；

2)“阿米巴网络[7]”，该案例用光波长路径将分散于不同地理位置的节点组合在一起，并向该节点集合赋予路由器功能；

3)“虚拟IP+光信号特性[6]”，该案例将一个虚拟IP网络，通过引入光波长路径对网络进行配置；

4)将分割分配方案应用到一个虚拟的IP网络，通过引入捷径路径和阿米巴节点对该网络进行配置.

表2中给出了在整个网络的光波长路径设为100个情况下，每个用户的HU-S和HS-S的均值和公平性指数，以及每个供应商之间资源利用率的公平性指数.由表2可知，在普通方法和阿米巴网络[7]的比较中，即使没有使用虚拟化技术，在采用了提出的分割分配方法后，HU-S和HS-S的平均IP跳数略有增加，但其公平性指数得到了改善，在每个用户之间实现了邻近度上的公平性.而集体分配方案由于后续的用户仅有非常少的供应商可供选择，因此各用户之间的公平性会变得很低.此外，集体分配方案因为资源请求集中在用户附近的供应商，所以会产生负载偏差.

表2 仿真结果均值

目标函数F(公式(1))随网络中光波长路径总数的变化情况如图6所示，HU-S随网络中光波长路径总数的变化情况如图7所示，HS-S随网络中光波长路径总数的变化情况如图8所示，从三项指标的示意图，可以看出，普通方案由于不带虚拟化的IP网络，其目标函数F值更大，HU-S和HS-S的平均跳数也更高.在阿米巴网络[7]和本文方法中，每项指标均降低(即性能提高)，这主要因为光波长所确定的路径总数增加了.文献[6]仅通过节点间的外部链路来改善网络距离，所提方法较优，主要是因为其使用光波长实现了更灵活的网络配置，能够更自由地对节点配置内的IP拓扑进行简并.

在本文提出的分割分配方案中，虽然负载均衡和公平性相关问题得到了解决，但为了维持公平性，并非一定要为每个用户分配距离最近的供应商，因此造成平均跳数的增加.为解决这一问题，本文通过光波长路径引入了网络虚拟化，如图7和图8，其平均跳数得到了较大改善.