SDN 中基于图分割的自适应带内网络遥测探测路径配置*原鹏翼1,2, 王 淼2, 王凌豪1,2, 张玉军1,2, 周继华31(中国科学院大学, 北京 100049)2(中国科学院 计算技术研究所, 北京 100190)3(金美通信, 重庆 400030)通信作者: 张玉军, zhmj@ict.ac.cn摘　要: 软件定义网络(SDN) 是一种将控制与转发平面分离的新型网络架构, 可以基于全局信息进行网络资源的调度和优化, 而精确的调度需要对全网信息(包括网络中所有交换设备状态及拓扑中所有链路信息) 进行准确的测量. 带内网络遥测可以在转发数据包的同时实现相关信息的采集, 其中配置全网覆盖的探测路径是带内网络遥测需要解决的关键问题之一. 但现有SDN 网络中全网覆盖的带内网络遥测路径配置方案存在以下问题: (1) 需要提前部署大量探测节点导致维护开销增大; (2) 探测路径过长导致探测分组长度超过网络中的MTU 值; (3) 冗余的探测路径导致测量引入的流量负荷在网络整体流量中占比过大; (4) 动态变化拓扑下探测路径调整恢复时间长等. 为解决上述问题, 提出了SDN 中基于图分割的自适应带内网络遥测探测路径配置(ACGS) 方法, 其基本思想是: 利用图分割对网络拓扑图进行划分, 通过控制拓扑规模来限制探测路径长度; 在分割后的子图中求解欧拉回路得到只遍历子图中有向边一次的探测路径, 以避免探测节点数量过多、探测路径冗余度高的问题; 并利用局部调整与整体调整相结合的方式解决拓扑动态变化时探测路径恢复时间长的问题. 实验结果证明ACGS 方法能够在SDN网络环境下, 实现探测路径长度适中、探测节点数量较少、探测路径冗余程度更低的全网覆盖带内网络遥测探测路径配置, 并实现其在拓扑动态变化后更快速的调整.关键词: 软件定义网络; 带内网络遥测; 图分割; 欧拉回路; 动态拓扑中图法分类号: TP393中文引用格式: 原鹏翼, 王淼, 王凌豪, 张玉军, 周继华. SDN中基于图分割的自适应带内网络遥测探测路径配置. 软件学报. http://www.jos.org.cn/1000-9825/6494.htm英文引用格式: Yuan PY, Wang M, Wang LH, Zhang YJ, Zhou JH. Adaptive Detection Path Configuration for In-band NetworkTelemetry in SDN Based on Graph Segmentation. Ruan Jian Xue Bao/Journal of Software (in Chinese). http://www.jos.org.cn/1000-9825/6494.htmAdaptive Detection Path Configuration for In-band Network Telemetry in SDN Basedon Graph SegmentationYUAN Peng-Yi1,2, WANG Miao2, WANG Ling-Hao1,2, ZHANG Yu-Jun1,2, ZHOU Ji-Hua31(University of Chinese Academy of Sciences, Beijing 100049, China)2(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China)3(Jin Mei Communication, Chongqing 400030, China)Abstract: Software-defined network (SDN) is a new network architecture that separates the control and forwarding planes. It can scheduleand optimize network resources based on global information. Nevertheless, precise scheduling requires accurate measurement of* 基金项目: 国家重点研发计划(2018YFB1800403); 网络计算创新研究院课题(E061010003); 国家自然科学基金(61902382, 61972381);中国科学院战略性先导科技专项(XDC02030500).收稿时间: 2021-05-17; 修改时间: 2021-07-07, 2021-09-02; 采用时间: 2021-09-18软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cnJournal of Software [doi: 10.13328/j.cnki.jos.006494] http://www.jos.org.cn©中国科学院软件研究所版权所有. Tel: +86-10-62562563网络首发时间：2022-11-16 11:14:47网络首发地址：https://kns.cnki.net/kcms/detail/11.2560.TP.20221115.1406.005.htmlinformation on the entire network (including the status of all switching devices in the network and all link information in the topology). Inbandnetwork telemetry (INT) can realize the collection of relevant information while forwarding data packets, and configuration ofdetection paths which cover the entire network is one of the key issues to be solved for INT. However, existing detection pathconfiguration methods for INT have the following problems. (1) The deployment of a large number of detection nodes is required inadvance, which leads to increased maintenance overhead. (2) The detection path is too long, which results in the length of detection packetexceeding the MTU value in the network. (3) The redundant detection paths cause the traffic load introduced by the measurement toaccount for too much of the overall network traffic. (4) The recovery time of the detection path adjustment under the dynamicallychanging topology is too long. In order to solve the above problems, an adaptive detection path configuration method for in-band networktelemetry in SDN based on graph segmentation (ACGS) is proposed. The basic idea is to divide the network topology with the graphsegmentation to restrict the length of detection path by controlling the topology scale, solve the Euler circuit in the divided subgraph toobtain a detection path that only traverses the directed edges in the subgraph once, to avoid the problems of too many detection nodes andhigh detection path redundancy; and use the combination of local adjustment and global adjustment to solve the problem of long recoverytime of the detection path when the topology changes dynamically. The experimental results prove that the ACGS method can realize theINT detection path configuration in SDN with moderate detection path length, fewer detection nodes, lower detection path redundancy, andfaster adjustment under the dynamically changing topology.Key words: software-defined network (SDN); in-band network telemetry; graph segmentation; Euler circuit; dynamic network软件定义网络(software defined network, SDN)[1]作为一种新型网络架构, 将传统网络的控制平面与数据转发平面分离, 控制平面负责集中的逻辑控制, 转发平面负责数据转发. 这种架构拥有全局可控的控制平面和高效的转发平面, 可以基于全局信息进行网络资源的调度和优化[2]. 而精确的调度需要对全网信息(包括网络中的所有交换设备状态以及拓扑中的所有链路信息) 进行准确的测量. 带内网络遥测[3]就是近年来在网络测量领域中备受关注的一种全网信息测量方法.带内网络遥测是指探测路径上的节点在转发数据包的同时, 将设备状态和网络链路信息插入数据包, 以完成相关信息的采集. 如图1 所示, 带内网络遥测的探测路径上的节点按功能分为一个源节点(source)、若干个转发节点(transit) 以及一个汇聚节点(sink), 其中, 源节点负责向原始数据包头部插入遥测指令, 指定需要采集的网络状态和设备信息, 并根据遥测指令的要求将设备状态、网络链路信息以及时间戳以元数据(INT metadata) 的形式插入到数据包头部, 然后转发数据包; 中间的转发节点收到带有遥测指令的数据包后, 根据遥测指令的要求将设备状态、网络链路信息以及时间戳以元数据的形式插入到数据包头部, 然后转发数据包; 汇聚节点收到带有遥测指令的数据包后, 同样根据遥测指令要求将设备状态、网络链路信息以及时间戳以元数据的形式插入到数据包头部,然后将数据包中的所有遥测元数据提取出来, 发送至控制器, 并将剔除了遥测元数据后的数据包转发至目的主机.相较于传统网络测量方法, 带内网络遥测方法能够对网络设备状态和网络链路信息进行更细粒度的测量, 其中设计覆盖全部网络链路的探测路径是关键, 包括确定各个节点的功能(源节点、转发节点、汇聚节点) 以及规划从源节点到汇聚节点的探测路径.目前, 研究者提出了一些带内网络遥测探测路径配置方法[4−8], 但存在着以下问题: (1) 探测节点(包括源节点和汇聚节点) 数量过多, 由于控制器需要向源节点下发遥测指令、收集来自汇聚节点的遥测结果, 所以过多的探测节点会导致控制器维护开销增大; (2) 单条探测路径长度过长, 导致探测包大小超过网络MTU, 从而引起探测包的丢包; (3) 探测路径冗余, 即一条链路多次被探测路径覆盖, 这会导致测量引入的流量负荷在网络整体流量中占比过大; (4) 网络拓扑动态变化时, 重新部署探测路径的时间长.为了解决上述问题, 提出了一种基于图分割的自适应带内网络遥测路径配置方法(adaptive detection pathconfiguration method for in-band network telemetry in SDN based on graph segmentation, ACGS): 首先, 通过图分割的方式把网络拓扑划分为多个子图, 通过限制拓扑的规模从而解决单条探测路径长度过长的问题; 然后, 基于欧拉回路的思想在子图中规划得到覆盖拓扑中有向边仅一次的探测路径, 以解决探测节点数量和探测路径冗余问题; 并给出在动态拓扑下, 自适应使用局部调整与整体调整相结合的方式, 解决了网络拓扑动态变化时重新部署探测路径时间长的问题. 实验结果表明, ACGS 方法能够在控制探测节点数量的同时, 降低探测路径平均长度, 降低探测路径冗余程度, 并在动态拓扑下保证调整速度更快.2 软件学报Header PayloadHeader Switch A INT metadata PayloadHeaderHeaderSwitch A+B INT metadata PayloadPayloadINT 源节点(source)INT 转发节点(transit)INT 汇聚节点(sink)INT report header Switch A+B+C INT metadata主机 1Host 2交换机 A交换机 B交换机 C控制器图 1　带内网络遥测测量过程示例1 相关研究软件定义网络中带内网络遥测能够持续监测网络状态, 动态高效地测量网络参数, 使控制器能够获得全网网络状态, 统筹管理全网流量[9], 这个过程中配置覆盖全网的探测路径是关键.文献[4] 提出了一种基于最短路径的生成树算法的路径覆盖机制, 首先, 配置多个探测节点; 然后, 以各个探测节点为生成树的根, 根据最短路径策略规划出多个生成树以覆盖整个网络. 该方法中同一条链路存在极大可能被多个生成树覆盖, 存在探测路径冗余的问题, 使网络测量效率下降, 另外, 额外配置探测节点会导致维护开销增大.文献[5,6] 提出了一种基于欧拉回路的路径覆盖策略, 先将无向图扩展为有向图; 根据欧拉定理[10,11], 一定存在这样一条路径, 即源节点和汇聚节点为同一个节点, 路径覆盖拓扑图中的所有有向边和所有节点, 且这条路径保证每条有向边只遍历一次. 这种方法解决了基于最短路径的生成树算法中测量路径冗余的问题, 但是对于较大规模的网络, 会出现探测链路过长导致探测分组长度超过网络中的MTU 值, 从而引起丢包.文献[7] 中提出了一种基于Hierholzer 算法的路径覆盖机制, 通过Hierholzer 算法求解多条欧拉回路, 以完成全网的路径覆盖. 由于Hierholzer 算法生成的多个欧拉路径的长度是无法限制的, 所以因探测路径过长而导致探测分组长度超过网络中的MTU 值的问题并未解决, 并且每条探测路径长度也可能存在较大差距, 可能引起网络资源分配不均匀的问题.文献[8,12] 中提出了一种基于启发式贪心算法的图覆盖算法, 先将网络拓扑分为多个子集; 然后, 随机选取一条链路, 尽可能向这条路径中添加更多的链路, 合并子集以获得探测路径最少的贪心策略. 这种路径覆盖算法同样存在着探测分组长度超过网络中的MTU 值的问题.综上所述, 现有全网覆盖的带内网络遥测探测路径配置方法存在的问题包括: 额外配置的探测节点会带来更大的维护开销; 因为探测路径上的转发节点需要插入遥测数据, 所以长度过长的探测路径会引起探测包大小超过网络MTU, 从而导致探测包丢包率增加; 而存在大量冗余的探测路径会导致测量引入的流量负荷在网络整体流量中占比过大.同时, 现有方法当网络拓扑动态变化时就重新部署探测路径, 探测路径恢复速度慢的问题, 所以在动态变化的网络拓扑中, 如何减少探测路径配置的维护难度, 提高拓扑变化后部署测量路径的效率, 也是软件定义网络环境下带内网络遥测待解决的问题.原鹏翼 等: SDN 中基于图分割的自适应带内网络遥测探测路径配置32 ACGS 方法为解决上述问题, 提出了ACGS 方法, 包括基于图分割的探测路径部署机制和探测路径自适应调整机制, 方法思路如下.基于图分割的探测路径部署机制负责规划出覆盖全网的带内网络遥测探测路径. 首先, 通过图分割算法将拓扑图分割为多个拓扑子图, 以解决探测路径过长导致的数据包长度超过MTU, 引起丢包的问题; 然后, 通过在拓扑子图中求解欧拉回路获得遍历子图中所有边的探测路径, 解决探测节点数量过多以及探测路径冗余的问题; 最后,控制器将探测路径下发至交换设备, 以完成全网覆盖的带内网络遥测探测路径配置.探测路径自适应调整机制是为了解决当网络拓扑发生变化时, 重新部署探测路径面临的探测路径恢复速度慢的问题, 使用探测路径局部调整与整体调整相结合的方式调整带内网络遥测的探测路径. 由于探测路径的规划过程中将网络拓扑分割为多个子图, 对拓扑变化的子图中的探测路径进行局部调整, 有效降低了探测路径的调整范围, 减少了修复探测路径的时间; 由于多次局部调整会引起探测路径冗余程度增高, 所以当变化的拓扑子图超过一定比例后, 需要整体调整探测路径, 重新调用基于图分割的探测路径部署机制以完成探测路径的规划.2.1 基于图分割的探测路径部署机制基于图分割的探测路径部署机制负责根据网络拓扑规划出覆盖全网的带内网络遥测探测路径, 其主要流程如图2 所示, 首先, 利用图分割算法将输入的拓扑图分为多个符合阈值大小限制的子图; 然后, 在子图中基于欧拉回路的思想规划探测路径; 最后控制器向可编程交换机下发探测路径, 输出遥测指令.图分割路径规划路径下发拓扑子图欧拉路径网络拓扑遥测指令图 2　基于图分割的探测路径部署机制流程2.1.1 图分割图分割作为基于图分割的探测路径部署机制的预处理部分, 作用是将较大的拓扑子图分为多个符合拓扑分割阈值大小的拓扑子图, 并保证子图之间的割边尽量少.图分割涉及到如下两个概念[13]: 1) 无向图的割指的是, 作为无向图G=(V, E), 设C 为图G 中一些弧的集合, 若从G 中删去C 中的所有弧能使图G 不是连通图, 称C 为图G 中的一个割, C 中的边成为割边; 2) S-T 割是使顶点S 与顶点T 不再连通的割.依据S-T 割概念, 一个无向图求割的过程中, 两点A 和B 只可能存在两种情况: 1) A、B 不在同一子图中, 即ST割; 2) A、B 在同一子图中, 即非S-T 割. 那么当求一个无向图割的过程中, 对于其中两点, 只需要先求其S-T 割,再将两点整合为一个点, 同时将与这两点相连的边权值重新计算, 对更新后的拓扑图继续寻找新的S-T 割, 那么就可以覆盖A 和B 两点的所有分割情况.通过在Stoer-Wagner 算法[14]的流程中, 保存每次计算出的割的中间结果, 同时限制子图阈值大小, 选择一个符合阈值大小且割的权值最小的子图作为一个的分割结果. 再对除去这个子图之后的拓扑图重新运行算法, 获得下一个子图, 直到将整个拓扑图分割成多个符合阈值的子图.算法主要流程:● Step 1. 根据Stoer-Wagner 算法, 在图G 中找出任意S-T 最小割.● Step 2. 记录分割结果, 合并S、T, 重复执行Step 1 直到图G 只剩下一个顶点.● Step 3. 选择记录结果中符合子图阈值大小且割的权值最小的第一个结果作为一个子图.● Step 4. 删除分割好的子图, 更新整体拓扑的节点集合和边集合.● Step 5. 对新的子图重新执行Step 1, 直到所有子图符合阈值大小.伪代码如算法1.4 软件学报算法1. 图分割.输入: matrix 拓扑矩阵, devices 交换机数组;输出: res 割.1. function NumRestrictMinCut(matrix, devices)2. while len(devices) > threshold do3. 　weights devs 数组用于记录中间结果4. 　while len(devices) > 1 do5. 　　minCut ← INT_MAX6. 　　dev ← 07. 　　 for device in devices do8. 　　　 计算使device 与图不再连通的割的权值tempCut9. 　　　 if tempCut < minCut then10. 　　　　minCut ← tempCut11. 　　　　dev ← device12. 　　　end if13. 　　end for14. 　　weights.append(minCut)15. 　　devs.append(dev)16. 　　找到与dev 邻接的边里权值最大的边edge, 及edge 的另一个端点dev017. 　　dev 与dev0 组成节点集合{dev, dev0}, 以该集合作为一个新的节点更新matrix、devices18. 　end while19. 　选择数组weights、devs 中, weight 最小且dev 小于threshold 的作为一个子图subGraph20. 　删除matrix 和devices 中, 子图subGraph 包含的节点和边21. 　res.append(subGraph)22. end while23. return res24. end function图3 所示为分割一次子图的示例, 每个步骤对应的Cut 表示当前拓扑对应最小割的权值, 如图3 第4) 步中,节点478 与其他节点的割是当前最小割, 所以Cut 值为3. 当分割子图大小符合子图阈值时, 即为一次成功的子图分割. 例如, 当子图阈值大小为3 时, 图3 第4 步和图2 第7 步都是符合子图阈值且割的权值最小的条件的, 可以随机选择其中一个作为一次子图分割, 删除子图后重新执行算法Step1, 获得下一个符合要求的子图.关于子图阈值大小的选择, 子图的欧拉回路路径长度L 应该符合公式(1) 的条件, 公式(1) 中MTU Length 代表网络MTU 大小; Packet Length 代表探测数据包长度; INT Header Length 代表带内网络遥测头部长度; INTMetadata Length 代表带内网络遥测元数据长度.L <MTU Length���Packet Length���INT Header LengthINT Metadata Length(1)在传统网络中, 以太网数据包大小在64 B 到1 500 B 之间; 带内网络遥测的头部长度为12 字节, Metadata 长度为16 字节; 网络中MTU 通常为1 500 B. 将上述理论值带入公式(1), 得到子图的欧拉回路路径长度L 的理论范围在0 到89 之间, 但是文献[15] 中指出, 网络中超过60% 的流量数据包大小不超过1 KB, 所以为了满足超过60%的流量在插入带内网络遥测数据后, 仍然能够符合MTU 大小, 那么子图的欧拉回路路径长度应小于30, 同时为了原鹏翼 等: SDN 中基于图分割的自适应带内网络遥测探测路径配置5保证由无向图扩展为有向图后, 路径里边的个数仍小于30, 拓扑子图中的无向边个数应小于15, 所以子图阈值节点数量应该控制在15 以下. 实际场景中, 在选择子图阈值时, 除了需要考虑MTU 大小的约束外, 还需要考虑子图的规模过小会导致子图数量增加, 进而导致探测节点数量增加, 系统维护开销增大. 经第3.2.1 节的实验测试, 子图阈值范围应该控制在10 到15 之间.152 3 46 7 81 52 3 46 7 81 52 36 74 81 52 36 4 781 5263 47 81 523467 83 4 67 81 25(1) Cut=2(2) Cut=2(3) Cut=3(4) Cut=3(5) Cut=2(6) Cut=3(7) Cut=3图 3　图分割示例流程2.1.2 路径规划路径规划作为基于图分割的探测路径部署机制的主要部分, 负责在划分好的拓扑子图中求解一条覆盖子图所有有向边仅一次的带内网络遥测探测路径.欧拉路径是指图G 中的一个路径包括每个边恰好一次的有向路径. 如果一个回路是欧拉路径, 则称为欧拉回路(Euler circuit). 一个图G 存在欧拉回路的充要条件是G 为有向图, G 的基图连通, 并且所有顶点的出度与入度都相等; 或者除两个顶点外, 其余顶点的出度与入度都相等, 而这两个顶点中一个顶点的出度与入度之差为1, 另一个顶点的出度与入度之差为−1. 根据上述图G 存在欧拉回路充要条件中的第1 条, 将无向图扩展为有向图, 所有顶点的出度与入度都相等, 则一定存在一条可以覆盖整个拓扑子图的欧拉路径.欧拉回路的求解是利用欧拉定理判断出一个图存在欧拉回路或欧拉通路后, 随机选择一个正确的起始顶点,用DFS 算法遍历所有的边(每一条边只遍历一次), 遇到走不通就回退. 在搜索前进方向上将遍历过的边按顺序记录下来. 这组边的排列就组成了一条欧拉通路或回路. 由于拓扑图是由无向图扩展得来的, 而求解欧拉路径的目的是覆盖无向图的所有边, 由一条无向边扩展来的两条边只需要覆盖一条即可, 所以上述计算过程是可以提前结束的, 通过维护两个数组undirctedVisited 和dirctedVisited, 分别表示无向图边的访问情况和有向图边的访问情况,当undirctedVisited 全覆盖时, 即无向图边全覆盖, 就可以结束算法, 回到起始点. 通过遍历选取子图各个节点作为源节点, 选择欧拉回路最短的起点作为最终的源节点.2.1.3 路径下发路径的下发作为基于图分割的探测路径部署机制的最后一步, 负责将规划好的探测路径下发至交换设备, 其功能主要通过P4 Runtime 实现.P4 Runtime 是一套基于Protobuf 以及gRPC 框架上的协议, 通过P4 Runtime, SDN 控制器可以控制P4 的设备,6 软件学报并获得设备基本信息. 与传统SDN 南向协议openflow 不同, 除了具备高度弹性的信息格式以外, 控制器与设备之间连接的顺序也不同, 以往openflow 是需要控制器开启特定的接口, 然后设备才能连上控制器, P4 Runtime 则是在设备上开启RPC server, 由控制器联系设备, 因此设备上会有一个Agent 负责处理由控制器发来的请求, 完成与控制器互连. 上述路径规划求解后的路径通过P4 Runtime[16]下发至BMv2[17]交换机, 交换机按照规则修改并转发探测包.2.2 探测路径的自适应调整机制探测路径自适应调整机制主要负责在拓扑发生变化时, 及时根据拓扑变化情况, 在局部或整体上调整探测路径, 以降低因拓扑改变导致的探测路径调整时间. 主要包括网络状态动态监测、探测路径局部调整、探测路径整体调整3 部分.2.2.1 网络状态动态检测网络动态检测实时监控网络拓扑, 并在拓扑发生变化时, 及时上报控制器, 主要由两部分功能组成: 实时链路状态收集和链路状态上传汇报. 其中, 链路状态收集主要通过LLDP 协议实现, 链路状态上传汇报主要通过P4Runtime 来完成.LLDP[18]定义在802.1ab 中, 提供了一种标准的链路层发现方式. LLDP 协议使得接入网络的一台设备可以将其管理地址、设备标识、接口标识等信息发送给接入同一个局域网络的其他设备. 当一个设备从网络中接收到其他设备的这些信息时, 它就将这些信息以MIB 的形式存储起来. 这些MIB 信息可用于发现设备的物理拓扑结构以及管理配置信息.网络设备通过LLDP 获取网络中其他设备的MIB 信息, 并将相关信息通过P4 Runtime 上传至控制器, 从而收集到网络拓扑, 以及网络设备之间的实时链路状态.2.2.2 探测路径局部调整探测路径局部调整是在网络设备或网络链路发生故障, 且已发生故障的子图数量占子图总数的比例