一种多约束条件下基于XGBoost的业务动态路径规划方法

赵瑜 邹雨 陈志坤

摘要：针对多业务的动态路径规划问题，提出综合考虑用户级别、业务种类、任务属性、QoS要求、网络资源状况等多条件，抽象表示为多要素，建立规划约束模型，同时在约束图中标识上述要素，获取实时网络资源情况，根据实时网络资源和拓扑视图信息，基于XGBoost进行最优节点的训练和选择，在更新后的拓扑上计算最优规划路径，在多个约束条件下达到最优规划，在资源最大化利用的前提下满足用户和业务的QoS要求，最后以实例进行仿真验证。提出了一种满足多约束条件的按需业务动态规划方法，设计了一种求解该问题的启发式算法。

关键词：启发式算法；多约束条件；最优路径；规划约束模型

中图分类号：TP18文献标志码：A文章编号：1008-1739（2022）24-64-5

0引言

随着网络规模的扩大和复杂性的日益增加，网络上所承载的业务也越来越多样化且业务服务质量（QoS）存在差异化。如何在已有网络上尽可能多地满足多样化、差异化业务需求是需要追寻和亟待解决的问题。业务规划是一个复杂且多约束几近无解的问题，与业务规划相关的问题有很多，包括业务类型、接入控制策略、资源调控策略、多径路由、QoS和QoE等，体现在如下方面：首先，业务规划需要在多应用需求和网络能力之间建立映射关系，即业务资源的最佳路径规划。其次，业务规划的本质是特征描述问题，即业务建模问题。对于接入控制策略，需要研究业务等级如何设定，对于暂时未能接入的业务，采取拒绝，还是排队等待等问题。接入控制问题是一个多约束条件下的排队问题。最后，对于资源调控策略，需要研究是否对不同业务类型采用不同的资源分配策略，针对数据速率动态变化的业务类型，应该静态分配还是动态分配资源等问题。资源分配策略是一个多维度的背包问题。

本文聚焦动态业务最优资源路径规划问题，综合考虑用户级别、任务紧急程度、QoS要求、网络资源、业务属性要素等多个约束条件，尤其针对网络运行过程中的动态业务对网络资源的需求问题，提出了一种满足多约束条件的按需业务动态路径规划方法，在业务资源调控过程中，将人工智能算法XGBoost应用于最优节点的选择和匹配。

1基于多約束条件的业务规划

业务规划算法的输入包括业务属性要素[1-2]（用户级别、业务种类、任务属性和QoS要求）和网络资源状况（源节点、目的节点、已用资源、可用资源、链路带宽、链路状态和链路利用率），输出按需业务所包括的每一个业务的源、目的地之间的最优规划路径。

1.1多约束条件下的路径规划算法

算法步骤如下：

①获取待规划的业务，属性要素包括业务源和目的，在什么时间（业务运行时间）、什么地方（业务运行的节点和链路），运行何种业务（数据、话音、视频），通常称为4W，将待规划的业务加入业务集合。

②根据策略对业务集合中的业务进行优先级排序，即按业务属性中的用户属性、任务属性和所需业务资源生成QoS优先级要求。QoS优先级确定原则：首先比较用户级别，用户级别高则对应业务的优先级高；当用户级别一定时，比较任务重要性，任务重要性高则业务优先级高；当用户级别和任务重要性一定时，比较业务类型，融合通信业务的优先级高于多媒体会议业务，多媒体会议业务的优先级高于多媒体电话业务。

③从业务集合中取优先级最高的业务进行规划，设业务的源和目的分别为和，业务所需要的带宽为。

④建立一个与业务关联的约束模型[3-5]=（ ， ），其中，为约束模型的顶点集合，为约束模型的边集合，为与业务关联的约束图。

目标函数越小，树的结构越优。XGBoost的学习过程就是建立最佳决策树结构的过程，从深度为0的树开始，采用贪婪策略遍历所有特征，利用式（6）计算节点分裂获得的增益，找到最优的特征进行分裂生成左右子节点，重复上述过程直到条件满足时迭代停止。

2仿真实验验证

以3个不同应用需求同时请求资源为例，验证本文所提的规划算法，应用需求描述如下：应用业务包括从1到3的电话业务，从2到4的交互式视频业务，从视频服务器到1的视频流业务（提供高动态态势）。获取业务属性要素，电话业务所需的带宽为64 kb/s，交互式业务需要的带宽为1 Mb/s（高清），视流需要的带宽为2 Mb/s。

将上述3个业务加入规划集合，基于策略进行优先级排序，假设3个业务的用户级别一样，根据任务紧急程度进行优先级排序：电话业务的优先级最高，视频流业务的优先级次之，交互式视频的优先级最低。

待规划的网络拓扑如图1所示。