一种基于受限最宽路径的段路由流量工程方法及装置

1.一种基于受限最宽路径的段路由流量工程方法，其特征在于，包括：步骤1：搜索获取SRv6网络中的任意流对应的源节点与目标节点之间所有路径中的最宽路径，所述最宽路径为所述所有路径中利用率最小的路径，所述所有路径的每一个路径的利用率为所述每一个路径的所有链路中的最大链路的利用率，所述最大链路为所述每一路径的所有链路中利用率最大的链路，步骤2：用所述SRv6网络中的各个段来对所述最宽路径进行第一编码，以获得用所述各个段构成的段组合表示的编码路径，步骤3：判断用于表示所述编码路径的段组合中所用的段数是否大于所述SRv6网络的段数,若判断为是，则记录所述编码路径中各个段与上游段之间的跳数，并比较各个段对应的跳数，且从所述段组合中删除跳数最小的段，返回所述步骤3，直到所述段组合中的段数不超过所述SRv6网络的段数。 2.根据权利要求1所述的段路由流量工程方法，其特征在于，在所述步骤1之前，还包括：将SRv6网络建模为无向图 ，其中， 表示为网络路由器集合， 表示路由器之间的物理链路，从网络节点 到网络节点 的链路 都具有给定的容量 和权重 ，用以表征在链路 中传输一个单位流的成本，以及将所述SRv6网络的 个流中的第 i 个流 用 表示， 为流 的源节点， 为流 的目的节点， 为流 的大小，其中，在n段SRv6网络中流 可以沿着一条路径 路由，其中 最多有 个节点， 中的每条子路径都是 n 段SRv6网络中上游节点和下游节点之间的最短路径。 3.根据权利要求2所述的段路由流量工程方法，其特征在于，在所述步骤1包括：令 表示流 的源节点 和目标节点 之间的所有路径的集合，所述集合中的每个路径 路径中所有链路的最大链路利用率作为所述路径 的路径利用率 ，用 表示链路 的链路利用率，通过比较所述 ，来确定所述最宽路径为所述集合中路径 ，其中1≤ j ≤ n ， 。 4.根据权利要求3所述的段路由流量工程方法，其特征在于，在所述步骤 1通过迭代法在所述集合中寻找到所述最宽路径，所述迭代法包括：设置已访问列表 和未访问列表 ，并用 表示在第 次迭代中所述路径 q j 的利用率，所述路径 q j 为从源节点 到所述网络路由器集合 V 中的第 j 个节点 的路径，初始化 、 、 ，在每次迭代，更新所述 ，其中 ， ，然后将 值最小对应的节点从 移动到 ，当 为空时，从所述 找出从 到在 中任何节点对应的所述最宽路径。 5.根据权利要求4所述的段路由流量工程方法，其特征在于，在所述步骤2中：使所述段组合 表示所述 f i 的最宽路径编码路径，其中 、 ，且令 是在路径 中 与 之间的子路径，让 表示 到 之间的最短路径，比较 与 的大小，当 时，则用 和 的地址表示 ，通过各个用段表示的各个所述子路径 表示所述编码路径 p i w 。 6.根据权利要求2所述的段路由流量工程方法，其特征在于，所述 n 大于等于2。 7.根据权利要求4所述的段路由流量工程方法，其特征在于，在所述步骤1中，所述迭代法进行了 次迭代，每个迭代都需要执行 次比较，所述迭代法的时间复杂度为 ，在所述步骤2中，所述最宽路径的长度不大于 ，所以迭代法需要比较最宽路径和最短路径 次，在所述步骤3中，对时间复杂度不超过 的所有的所述跳数进行排序。 8.根据权利要求4所述的段路由流量工程方法，其特征在于，那么 n 段SRv6网络建模为:其中，所述SRv6网络建模中的约束公式(3)确保所有的流量都在所述SRv6网络中路由，并且每个流量只通过一个单一的 n 段路由路径，在所述SRv6网络建模中的约束公式(4)中，如果流 是通过路径 路由的，那么 表示 中属于 的流量，且所述约束(4)表示每个链路的链路利用率小于最大链路利用率， 表示流 在所述源节点 和所述目标节点 之间可能的路径数， 表示从 中找到h个不同对象的排列数， 表示源节点 和 之间的所有最短路径， 表示 在 出现在 中出现的总频率， 表示流 是否由 路径路由。 9.一种终端，其特征在于，包括存储器和处理器，所述存储器存储有计算机程序，所述计算机程序被所述处理器执行时执行如权利要求1-8中的任意一所述段路由流量工程方法。 10.一种计算机可读存储介质，其特征在于，存储有计算机程序，所述计算机程序被处理器执行时执行如权利要求1-8中的任意一所述段路由流量工程方法。