一种基于段路由的带内遥测路径规划算法

1.本发明属于网络安全与网络测量交叉领域，尤其涉及一种对段路由环境下的带内遥测进行路径规划的算法。


背景技术：

2.段路由(segment routing，sr)是一种源路由协议，其核心思想是将网络报文转发路径切割为不同的分段，并在路径起始点往报文中插入分段信息指导报文转发。段路由基于sdn理念，构成面向路径连接的网络架构，支撑未来网络多层次的可编程需求，可以满足5g超大连接和切片的应用场景下的连接需求，其目的是简化网络和提高可控性，支持多种转发平面，如mpls和ipv6，具有流量工程、网络编程、应用驱动等优势。
3.带内网络遥测是一种混合测量技术，通过在数据包中嵌入遥测指令和元数据，实现了网络状态的收集、携带、整理和上报。在带内网络遥测架构中，交换设备转发处理携带遥测指令(telemetry instructions)的数据包。当遥测数据包经过该设备时，这些遥测指令告诉具备网络遥测功能的网络设备应该收集并写入何种网络状态信息。其优点是不需要额外的控制平面干预，可以实时地监测网络拓扑、性能和流量，对网络故障定位、拥塞控制、路径决策等场景有很大的帮助。学术界目前已有各种遥测方案，但作为一个底层基元，int仅仅定义了如何提取设备的内部状态，如入口速率、出口流量等，本身不能主动决定监测哪条路径。例如，将int头被嵌入到ip数据包中，遥测路径将由其目的ip地址和每个交换机的路由表被动决定，完全不受int服务器的控制。规划路径时也没有考虑遥测的覆盖率等因素，导致如果随流进行带内测量，测量的路径区域较集中，并且存在很大程度上的冗余问题。
4.综上所述，本发明使用了段路由的带内遥测技术，并通过优化欧拉路径规划算法和重叠路径消除算法进行路径规划。


技术实现要素：

5.针对以上问题，本发明提出了一种基于段路由的带内遥测路径规划算法，该算法能够自适应规划路径，以减少对路径的重复测量。在确定流的起点和终点后，结合历史int数据，如其余流经过的路径、网络拥塞程度等信息，指导流在网络中以更均匀的方式分布。在随流遥测时，可减少对链路的冗余测量，并且提高遥测的覆盖率。
6.为实现本发明的目的，本发明的技术方案如下：一种基于段路由的带内遥测路径规划算法，判断网络中的活跃流，并根据其原路径生成子图g
′
，使用优化欧拉路径算法生成路径规划结果集e
′
，最后使用重叠路径消除算法去除冗余路径。该算法包括以下步骤：
7.(1)对网络拓扑和网络流进行建模。将网络拓扑建模成无向连通图g，将流建模成六元组；
8.(2)根据网络中流的已有信息及历史信息，判断该流是否活跃。将所有被判断为活跃流的原路径转化为连通子图g
′
；
9.(3)确定连通图g
′
中每条流的起点和终点对应关系的条件下，使用优化欧拉路径算法，在连通图g
′
中生成路径结果集e
′
，规划出重叠数较少的网络遥测路径方案；
10.(4)使用重叠路径消除算法，通过添加辅助点的手段，将重叠的路径进行迁移，引入新节点和新链路，降低冗余度并生成最终路径规划结果。
11.作为本发明的一种改进，步骤(1)的具体方法如下：
12.(1.1)将网络拓扑建模为无向连通图g＝(v，e)，网络中各个设备抽象成图中的顶点，各条链路抽象为图中的边；
13.(1.2)将网络中的流抽象为六元组f＝(tuple,r,flag,ts,te,path)，其中tuple为数据包五元组，即指源ip地址、目的ip地址、源端口、目的端口和传输层协议，具有相同五元组的数据包构成了流；
14.(1.3)flag为该流是否活跃的标识，1表示该流为活跃状态，可以纳入测量范围，0表示该流为不活跃状态，不纳入测量的考虑范围；ts为该流的开始时间，te为该流的结束时间，则t
e-ts即可计算出流的持续时间；path表示该流所经过的路径，段路由环境下，path可表示为path(f)＝(sid[n],
…
,sid[2],sid[i])＝(v1,v2,
…
,vn)，其中v1∈v,(v1,v1)∈e；
[0015]
(1.4)时间t
e-ts内，所有活跃的流构成了集合f＝{f1,f2,
…
,fn}，对于其中任意一条流，都有原有的转发路径，即
[0016]
通过该步骤，网络拓扑被抽象建模成图，路径规划问题被抽象为图论问题，便于使用算法实现。
[0017]
作为本发明的一种改进，步骤(2)中活跃流判断与连通子图生成的设计方法如下：
[0018]
(2.1)设定活跃流阈值；
[0019]
(2.2)根据历史int数据，判断流的活跃程度。若为活跃流，则将其flag置1，若为非活跃流，则将其flag置0；
[0020]
(2.3)以生成有重复的路径为代价，将所有活跃流的原路径转化为图g的连通子图g
′
；
[0021]
(2.4)确定连通子图g
′
中每一条流的起点与终点间对应关系。
[0022]
通过该步骤，根据流活跃程度判断，将已有流的路径转化为连通图g转化为图g的连通子图g
′
，并固定每条流的起点和终点。
[0023]
作为本发明的一种改进，步骤(3)中路径规划算法的具体方法如下：
[0024]
(3.1)在图g
′
中奇数点间寻找覆盖率最大的路径；
[0025]
(3.2)去除路径集中已经规划好的路径；
[0026]
(3.3)从起点寻找尽可能不重复的路径；
[0027]
(3.4)生成路径规划结果集e
′
。
[0028]
通过该步骤，初步生成存在重复路径的规划结果集，以待后续使用重叠路径消除算法去除冗余路径。
[0029]
作为本发明的一种改进，步骤(4)重叠路径消除算法的具体方法如下：
[0030]
(4.1)在路径规划集e
′
中统计重叠路径；
[0031]
(4.2)在{g-g
′
}中选取相邻的节点，引入g
′
以外的路径，尽可能的消除重叠的路径。在选取节点时，由于受实际问题限制只能选取链路相邻的节点，不能凭空捏造节点；
[0032]
(4.3)利用辅助节点构造新的路径，降低路径规划冗余度；
[0033]
(4.4)生成去除冗余后的路径结果集r。
[0034]
通过该步骤，生成了基于段路由的路径规划结果集，与传统方法相比，由于段路由的可控性，能够获得冗余度更低的流路径规划，提高了遥测数据的有效性，以便后续分析。
[0035]
相对于现有技术，本发明的优点如下：该方案通过一种基于段路由的带内遥测路径规划算法，将传统的带内网络遥测int加入到段路由技术中，其路径在数据包转发前以sid格式写入sr扩展头，在转发时不会受到路由的影响。因此，本工作充分利用该特性，确定流的起点和终点后，再结合历史int数据，如其余流经过的路径、网络拥塞程度等信息，指导流在网络中以更均匀的方式分布，这样在随流遥测时，可减少对链路的冗余测量，并且提高遥测的覆盖率。此外，由于段路由的特殊性，能够提高网络可靠性和灵活性，支持多种方式生成候选路径，并可以通过优先级和权重实现路径选择和负载分担。同时，基于原生ipv6或mpls进行转发，具有良好的兼容性和扩展性，不改变原有报文的封装结构，可以与普通ipv6或mpls设备共存，并能够进入数据中心网络甚至用户终端，促进云网融合。
附图说明
[0036]
图1为基于段路由的带内遥测路径规划流程图；
[0037]
图2为欧拉路径算法示意图；
[0038]
图3为单流路径重叠示意图；
[0039]
图4为多流路径重叠示意图；
[0040]
图5为辅助节点示意图；
[0041]
图6为nsfnet拓扑结构图；
[0042]
图7为gbn拓扑结构图；
[0043]
图8为geant拓扑结构图；
[0044]
图9为germany50拓扑结构图。
具体实施方式：
[0045]
为了加深对本发明的认识和理解，下面结合附图对本发明做详细的说明。
[0046]
实施例：参见图1-图9，为实现本发明的目的，本发明的技术方案如下：一种基于段路由的带内遥测路径规划算法，判断网络中的活跃流，并根据其原路径生成子图g
′
，使用优化欧拉路径算法生成路径规划结果集e
′
，最后使用重叠路径消除算法去除冗余路径。该算法包括以下步骤：
[0047]
(1)对网络拓扑和网络流进行建模。将网络拓扑建模成无向连通图g，将流建模成六元组；
[0048]
(2)根据网络中流的已有信息及历史信息，判断该流是否活跃。将所有被判断为活跃流的原路径转化为连通子图g
′
；
[0049]
(3)确定连通图g
′
中每条流的起点和终点对应关系的条件下，使用优化欧拉路径算法，在连通图g
′
中生成路径结果集e
′
，规划出重叠数较少的网络遥测路径方案；
[0050]
(4)使用重叠路径消除算法，通过添加辅助点的手段，将重叠的路径进行迁移，引入新节点和新链路，降低冗余度并生成最终路径规划结果集。
[0051]
步骤(1)的具体方法如下：
[0052]
(1.1)将网络拓扑建模为无向连通图g＝(v，e)，网络中各个设备抽象成图中的顶点，各条链路抽象为图中的边；
[0053]
(1.2)将网络中的流抽象为六元组f＝(tuple,r,flag,ts,te,path)，其中tuple为数据包五元组，即指源ip地址、目的ip地址、源端口、目的端口和传输层协议，具有相同五元组的数据包构成了流；
[0054]
(1.3)flag为该流是否活跃的标识，1表示该流为活跃状态，可以纳入测量范围，0表示该流为不活跃状态，不纳入测量的考虑范围；ts为该流的开始时间，te为该流的结束时间，则t
e-ts即可计算出流的持续时间；path表示该流所经过的路径，段路由环境下，path可表示为path(f)＝(sid[n],
…
,sid[2],sid[i])＝(v1,v2,
…
,vn)，其中v1∈v,(v1,v1)∈e；
[0055]
(1.4)时间t
e-ts内，所有活跃的流构成了集合f＝{f1,f2,
…
,fn}，对于其中任意一条流，都有原有的转发路径，即
[0056]
步骤(2)中活跃流判断与连通子图生成的设计方法如下：
[0057]
(2.1)设定活跃流阈值；
[0058]
(2.2)根据历史int数据，判断流的活跃程度。若为活跃流，则将其flag置1，若为非活跃流，则将其flag置0；
[0059]
(2.3)以生成有重复的路径为代价，将所有活跃流的原路径转化为图g的连通子图g
′
；
[0060]
(2.4)确定连通子图g
′
中每一条流的起点与终点间对应关系。
[0061]
步骤(3)中路径规划算法的具体方法如下：
[0062]
(3.1)初始化路径规划集e
′
，在图g
′
中奇数度节点中寻找最长的欧拉路径并加入路径规划集e
′
；
[0063]
(3.2)在流起点与终点映射关系f
′
中去除路径集e
′
中已经规划好的路径；
[0064]
(3.3)在流起点与终点映射关系f
′
中，对于每个startpoint，将其作为起点，重复(3.1)至(3.2)的操作，寻找不重复路径；
[0065]
(3.4)生成路径规划结果集e
′
。
[0066][0067]
步骤(4)重叠路径消除算法的具体方法如下：
[0068]
(4.1)初始化路径集r。在路径规划集e
′
中，统计重叠路径，若存在重复path，则将其加入重叠路径集t中；
[0069]
(4.2)在{g-g
′
}中选取相邻的节点构造辅助节点point。在选取节点时，由于受实际问题限制不能凭空捏造节点，所以只能选取链路相邻的节点；
[0070]
(4.3)利用辅助节点和当前重叠路径构造新的路径，在重叠路径集t中去除重叠路径path，更新路径集r；
[0071]
(4.4)重复(4.3)中操作，生成去除冗余后的路径结果集r。
[0072]
[0073][0074][0075]
如图1所示，为基于段路由的带内遥测路径规划流程图。
[0076]
其中，首先将若干网络流输入。对于某条流的活跃程度，本发明以如下公式进行判断：
[0077]
在t
e-ts时间段内，通过计算可得，该流共发送的数据量为(t
e-ts)
×
r，若：
[0078][0079]
则判断该流为活跃流，将其flag置1。公式中通过flagi的值来筛选出已有的活跃流，flow
th
为判断当前流是否活跃的阈值，其计算方法如公式所示：
[0080][0081]
从上述公式可以看出，阈值的设定与流速方差有较大的关系。当方差小于某一范围(用户自定参数值)时，flow
th
的值会趋于0，即当所有流在某一时间片内发送的数据量较统一时，则可以放宽对活跃流的判断；当方差较大时，阈值的设定与速率偏差与大流占所有活跃流的比例有关，即若当前流在某一时间片内发送的数据量远远小于目前活跃流的均值，则该流被判定为不活跃流的可能性较大。
[0082]
为详细说明基于段路由的带内遥测路径规划算法，将介绍欧拉路径规划算法。如图2生成路径示意图，生成的路径严格满足路径之间不重叠的要求，但是生成的路径的起点和终点不一定满足本研究的要求，并且对路径起点的奇数度要求过于严格。如果在真实环境下，如果节点b只能作为流的终点则生成的路径中便存在无法使用的情况。
[0083]
接着，如图3与图4所示，网络拓扑中链路被反复测量主要有两种情况：一种是由于路径规划问题，导致该链路被两条或多条的遥测路径经过，即多条遥测路径存在公共边；第
二种是由于流的某些需求，导致这条链路被该流两次或者多次经过，即使得，(vh,v
h+1
)＝＝(vk,v
k+1
)。但不管是由于哪些原因，只要该链路每被多测量了一次，便在图中为其添加一个节点，通过节点引出新的路径。添加辅助节点的思想一方面可以将重叠路径进行消除并且由于添加了新的路径从而提高了遥测范围，另一方面可以将原来度为偶数的节点变为奇点，便于路径规划算法的执行。
[0084]
为详细说明基于段路由的带内遥测路径规划算法，接着介绍重叠路径消除算法。在生成的路径结果集e
′
中，若有重复路径，则在{g-g
′
}中选取相邻的节点，引入g
′
以外的路径，尽可能的消除重叠的路径。在选取节点时，由于受实际问题限制只能选取链路相邻的节点，并且不能凭空捏造节点。图5给出了添加节点的示意图，可从图中看出原重叠的链路，在引入了新的节点和新的路径后，可降低冗余度并且添加了新的测量路径。
[0085]
下面结合具体用例和发明书附图对本发明作说明。该发明有以下步骤：
[0086]
(1)对网络拓扑和网络流进行建模。将网络拓扑建模成无向连通图g，将流建模成六元组；
[0087]
(2)根据网络中流的已有信息及历史信息，判断该流是否活跃。将所有被判断为活跃流的原路径转化为连通子图g
′
；
[0088]
(3)确定连通图g
′
中每条流的起点和终点对应关系的条件下，使用优化欧拉路径算法，在连通图g
′
中生成路径结果集e
′
，规划出重叠数较少的网络遥测路径方案；
[0089]
(4)使用重叠路径消除算法，通过添加辅助点的手段，将重叠的路径进行迁移，引入新节点和新链路，降低冗余度并生成最终路径规划结果。
[0090]
为了详细说明一种基于段路由的带内遥测路径规划算法的工作步骤，接下来以5个用例，具体阐述该算法在不同拓扑结构图下的工作模式。
[0091]
具体实施例1：
[0092]
若此次算法使用拓扑为随机生成的特殊网络拓扑结构，此时一种基于段路由的带内遥测路径规划算法工作流程如下。
[0093]
使用python随机生成有2k+1个奇数度节点的特殊网络拓扑结构。欧拉路径算法中，对于有2k个奇数度节点的无向连通图g＝(v，e)，至少存在k条不同路径{p1,p2…
,pk}，并且有e(g)＝e(p1)∪e(p2)
…
∪e(pk)，即这些非重叠路径会覆盖图中的所有边。在具有2k+1个奇数度节点的网络拓扑结构中，能够覆盖图中所有边的路径规划集必然存在路径重叠。
[0094]
当使用基于段路由的带内遥测路径规划算法对该拓扑结构图进行路径规划时，具体步骤如下：
[0095]
(1.1)将随机生成的具有2k+1个奇数度节点的特殊网络拓扑建模成无向连通图g，将网络中的流建模成六元组；
[0096]
(1.2)根据网络中流的已有信息及历史信息，判断该流是否活跃。将所有被判断为活跃流的原路径转化为连通子图g
′
；
[0097]
(1.3)确定连通图g
′
中每条流的起点和终点对应关系的条件下，使用优化欧拉路径算法，在连通图g
′
中生成路径结果集e
′
，规划出重叠数较少的网络遥测路径方案；
[0098]
(1.4)使用重叠路径消除算法，通过添加辅助点的手段，将重叠的路径进行迁移，引入新节点和新链路，降低冗余度并生成最终路径规划结果集。
[0099]
具体实施例2：
[0100]
若此次算法使用拓扑为nsfnet网络拓扑结构图，此时一种基于段路由的带内遥测路径规划算法工作流程如下。
[0101]
如图6所示，nsfnet网络拓扑结构具有14个节点和18条边构成，其中14个节点中有8个是奇数度节点，因此至少存在4条非重叠路径能够覆盖该拓扑图中的所有边。
[0102]
当使用基于段路由的带内遥测路径规划算法对该拓扑结构图进行路径规划时，具体步骤如下：
[0103]
(1.1)将nsfnet网络拓扑结构建模成无向连通图g，将网络中的流建模成六元组；
[0104]
(1.2)根据网络中流的已有信息及历史信息，判断该流是否活跃。将所有被判断为活跃流的原路径转化为连通子图g
′
；
[0105]
(1.3)确定连通图g
′
中每条流的起点和终点对应关系的条件下，使用优化欧拉路径算法，在连通图g
′
中生成路径结果集e
′
，规划出重叠数较少的网络遥测路径方案；
[0106]
(1.4)使用重叠路径消除算法，通过添加辅助点的手段，将重叠的路径进行迁移，引入新节点和新链路，降低冗余度并生成最终路径规划结果集。
[0107]
具体实施例3：
[0108]
若此次算法使用拓扑为随机生成的特殊网络拓扑结构，此时一种基于段路由的带内遥测路径规划算法工作流程如下。
[0109]
如图7所示，gbn网络拓扑结构具有17个节点和26条边构成，其中17个节点中有6个是奇数度节点，因此至少存在3条非重叠路径能够覆盖该拓扑图中的所有边。
[0110]
当使用基于段路由的带内遥测路径规划算法对该拓扑结构图进行路径规划时，具体步骤如下：
[0111]
(1.1)将gbn网络拓扑结构建模成无向连通图g，将该网络中的流建模成六元组；
[0112]
(1.2)根据网络中流的已有信息及历史信息，判断该流是否活跃。将所有被判断为活跃流的原路径转化为连通子图g
′
；
[0113]
(1.3)确定连通图g
′
中每条流的起点和终点对应关系的条件下，使用优化欧拉路径算法，在连通图g
′
中生成路径结果集e
′
，规划出重叠数较少的网络遥测路径方案；
[0114]
(1.4)使用重叠路径消除算法，通过添加辅助点的手段，将重叠的路径进行迁移，引入新节点和新链路，降低冗余度并生成最终路径规划结果集。
[0115]
具体实施例4：
[0116]
若此次算法使用拓扑为随机生成的特殊网络拓扑结构，此时一种基于段路由的带内遥测路径规划算法工作流程如下。
[0117]
如图8所示，geant网络拓扑结构具有个24节点和37条边构成，其中24个节点中有8个是奇数度节点，因此至少存在4条非重叠路径能够覆盖该拓扑图中的所有边。
[0118]
当使用基于段路由的带内遥测路径规划算法对该拓扑结构图进行路径规划时，具体步骤如下：
[0119]
(1.1)将geant网络拓扑结构建模成无向连通图g，将网络中的流建模成六元组；
[0120]
(1.2)根据网络中流的已有信息及历史信息，判断该流是否活跃。将所有被判断为活跃流的原路径转化为连通子图g
′
；
[0121]
(1.3)确定连通图g
′
中每条流的起点和终点对应关系的条件下，使用优化欧拉路径算法，在连通图g
′
中生成路径结果集e
′
，规划出重叠数较少的网络遥测路径方案；
[0122]
(1.4)使用重叠路径消除算法，通过添加辅助点的手段，将重叠的路径进行迁移，引入新节点和新链路，降低冗余度并生成最终路径规划结果集。
[0123]
具体实施例5：
[0124]
若此次算法使用拓扑为随机生成的特殊网络拓扑结构，此时一种基于段路由的带内遥测路径规划算法工作流程如下。
[0125]
如图9所示，germany50网络拓扑结构具有50个节点和87条边构成，其中50个节点中有26个是奇数度节点，因此至少存在13条非重叠路径能够覆盖该拓扑图中的所有边。
[0126]
当使用基于段路由的带内遥测路径规划算法对该拓扑结构图进行路径规划时，具体步骤如下：
[0127]
(1.1)将随机生成的具有2k个奇数节点的特殊网络拓扑建模成无向连通图g，将网络中的流建模成六元组；
[0128]
(1.2)根据网络中流的已有信息及历史信息，判断该流是否活跃。将所有被判断为活跃流的原路径转化为连通子图g
′
；
[0129]
(1.3)确定连通图g
′
中每条流的起点和终点对应关系的条件下，使用优化欧拉路径算法，在连通图g
′
中生成路径结果集e
′
，规划出重叠数较少的网络遥测路径方案；
[0130]
(1.4)使用重叠路径消除算法，通过添加辅助点的手段，将重叠的路径进行迁移，引入新节点和新链路，降低冗余度并生成最终路径规划结果集。
[0131]
实验1：仿真环境模拟测试
[0132]
实验目的：
[0133]
测试基于段路由的带内遥测路径规划算法在随机生成的拓扑结构图和真实数据中心拓扑图中所探测的链路总数
[0134]
实验步骤：
[0135]
1.在mininet中布置int仿真环境，使用python随机生成顶点数不同的拓扑结构图和真实数据中心网络拓扑图中，确定每条流的起点和终点的对应关系；
[0136]
2.按照专利步骤进行活跃流判断，路径集生成，重叠路径消除；
[0137]
3.收集并处理生成路径中的链路总数。
[0138]
实验2：路径规划算法对比
[0139]
实验目的：
[0140]
测试基于段路由的带内遥测路径规划算法与传统欧拉路径算法生成路径的重复链路对比
[0141]
实验步骤：
[0142]
1.在mininet中布置int仿真环境，使用python随机生成顶点数不同的拓扑结构图，确定每条流的起点和终点的对应关系；
[0143]
2.按照专利步骤进行活跃流判断，路径集生成，重叠路径消除；
[0144]
3.在mininet中布置同样的网络拓扑；
[0145]
4.使用传统欧拉路径算法生成规划路径集；
[0146]
5.对比两种算法生成路径集中的重复链路数量。
[0147]
需要说明的是上述实施例仅仅是本发明的较佳实施例，并没有用来限定本发明的保护范围，在上述技术方案的基础上做出的等同替换或者替代，均属于本发明的保护范围。

技术特征：
1.一种基于段路由的带内遥测路径规划算法，其特征在于，该算法包括以下步骤：(1)对网络拓扑和网络流进行建模，将网络拓扑建模成无向连通图g，将流建模成六元组；(2)根据网络中流的已有信息及历史信息，判断该流是否活跃，将所有被判断为活跃流的原路径转化为连通子图g
′
；(3)确定连通图g
′
中每条流的起点和终点对应关系的条件下，使用优化欧拉路径算法，在连通图g
′
中生成路径结果集e
′
，规划出重叠数较少的网络遥测路径方案；(4)使用重叠路径消除算法，通过添加辅助点的手段，将重叠的路径进行迁移，引入新节点和新链路，从而降低冗余度并生成最终路径规划结果。2.根据权利要求1所述的一种基于段路由的带内遥测路径规划算法，其特征在于，步骤(1)的具体方法如下：(1.1)将网络拓扑建模为无向连通图g＝(v，e)；(1.2)将网络中的流抽象为六元组f＝(tuple,r,flag,t
s
,t
e
,path)；(1.3)段路由环境下，path可表示为path(f)＝(sid[n],
…
,sid[2],sid[i])＝(v1,v2,
…
,v
n
)，其中v1∈v,(v1,v1)∈e；(1.4)时间t
e-t
s
内，所有活跃的流构成了集合f＝{f1,f2,
…
,f
n
}。3.根据权利要求1所述的一种基于段路由的带内遥测路径规划算法，其特征在于，步骤(2)中活跃流判断与连通子图生成的设计方法如下：(3.1)设定流活跃阈值；(3.2)根据历史int数据，判断流的活跃程度是否超过阈值；(3.3)以生成有重复的路径为代价，将所有活跃流的原路径转化为图g的连通子图g
′
；(3.4)确定连通子图g
′
中每一条流的起点与终点间对应关系。4.根据权利要求1所述的一种基于段路由的带内遥测路径规划算法，其特征在于，步骤(3)中路径规划算法的具体方法如下：(4.1)在图g
′
中奇数点间寻找覆盖率最大的路径；(4.2)去除已经规划好的路径；(4.3)从起点寻找尽可能不重复的路径；(4.4)生成路径规划结果集e
′
。5.根据权利要求1所述的一种基于段路由的带内遥测路径规划算法，其特征在于，步骤(4)重叠路径消除算法的具体方法如下：(5.1)统计所有重叠路径；(5.2)为重叠路径选取辅助节点；(5.3)利用辅助节点构造新的路径；(5.4)生成去除冗余后的路径结果集r。

技术总结
本发明公开了一种基于段路由的带内遥测路径规划算法，在确定流的起点和终点后，结合历史遥测数据，如其余流经过的路径、网络拥塞程度等信息，指导流在网络中以更均匀的方式分布。本发明将网络拓扑建模成无向连通图，根据每条流的活跃度对图进行重新划分，再添加辅助节点消除重复链路，从而完成对网络拓扑结构的自适应路径规划。此外，通过随机生成的特殊拓扑结构和真实数据中心拓扑等案例对该发明的可行性进行了验证。可行性进行了验证。可行性进行了验证。


技术研发人员：程光 赵玉宇 陈暄 顾周超 吴桦
受保护的技术使用者：东南大学
技术研发日：2023.05.10
技术公布日：2023/8/1