原鹏翼(1996-), 男, 硕士生, 主要研究领域为软件定义网络
王淼(1975-), 女, 博士, 副研究员, CCF专业会员, 主要研究领域为未来网络体系结构, 网络智能调度
王凌豪(1996-), 男, 博士生, 主要研究领域为未来网络体系结构, 流量工程
张玉军(1976-), 男, 博士, 研究员, CCF高级会员, 主要研究领域为计算机网络
周继华(1979-), 男, 博士, 研究员, 主要研究领域为通信网络, 5G/6G
软件定义网络(SDN)是一种将控制与转发平面分离的新型网络架构, 可以基于全局信息进行网络资源的调度和优化, 而精确的调度需要对全网信息(包括网络中所有交换设备状态及拓扑中所有链路信息)进行准确的测量. 带内网络遥测可以在转发数据包的同时实现相关信息的采集, 其中配置全网覆盖的探测路径是带内网络遥测需要解决的关键问题之一. 但现有SDN网络中全网覆盖的带内网络遥测路径配置方案存在以下问题: (1)需要提前部署大量探测节点导致维护开销增大; (2)探测路径过长导致探测分组长度超过网络中的MTU值; (3)冗余的探测路径导致测量引入的流量负荷在网络整体流量中占比过大; (4)动态变化拓扑下探测路径调整恢复时间长等. 为解决上述问题, 提出了SDN中基于图分割的自适应带内网络遥测探测路径配置(ACGS)方法, 其基本思想是: 利用图分割对网络拓扑图进行划分, 通过控制拓扑规模来限制探测路径长度; 在分割后的子图中求解欧拉回路得到只遍历子图中有向边一次的探测路径, 以避免探测节点数量过多、探测路径冗余度高的问题; 并利用局部调整与整体调整相结合的方式解决拓扑动态变化时探测路径恢复时间长的问题. 实验结果证明ACGS方法能够在SDN网络环境下, 实现探测路径长度适中、探测节点数量较少、探测路径冗余程度更低的全网覆盖带内网络遥测探测路径配置, 并实现其在拓扑动态变化后更快速的调整.
Software-defined network (SDN) is a new network architecture that separates the control and forwarding planes. It can schedule and optimize network resources based on global information. Nevertheless, precise scheduling requires accurate measurement of information on the entire network (including the status of all switching devices in the network and all link information in the topology). In-band network telemetry (INT) can realize the collection of relevant information while forwarding data packets, and configuration of detection paths which cover the entire network is one of the key issues to be solved for INT. However, existing detection path configuration methods for INT have the following problems. (1) The deployment of a large number of detection nodes is required in advance, which leads to increased maintenance overhead. (2) The detection path is too long, which results in the length of detection packet exceeding the MTU value in the network. (3) The redundant detection paths cause the traffic load introduced by the measurement to account for too much of the overall network traffic. (4) The recovery time of the detection path adjustment under the dynamically changing topology is too long. In order to solve the above problems, an adaptive detection path configuration method for in-band network telemetry in SDN based on graph segmentation (ACGS) is proposed. The basic idea is to divide the network topology with the graph segmentation to restrict the length of detection path by controlling the topology scale, solve the Euler circuit in the divided subgraph to obtain a detection path that only traverses the directed edges in the subgraph once, to avoid the problems of too many detection nodes and high detection path redundancy; and use the combination of local adjustment and global adjustment to solve the problem of long recovery time of the detection path when the topology changes dynamically. The experimental results prove that the ACGS method can realize the INT detection path configuration in SDN with moderate detection path length, fewer detection nodes, lower detection path redundancy, and faster adjustment under the dynamically changing topology.
软件定义网络(software defined network, SDN)[
带内网络遥测是指探测路径上的节点在转发数据包的同时, 将设备状态和网络链路信息插入数据包, 以完成相关信息的采集. 如
带内网络遥测测量过程示例
目前, 研究者提出了一些带内网络遥测探测路径配置方法[
为了解决上述问题, 提出了一种基于图分割的自适应带内网络遥测路径配置方法(adaptive detection path configuration method for in-band network telemetry in SDN based on graph segmentation, ACGS): 首先, 通过图分割的方式把网络拓扑划分为多个子图, 通过限制拓扑的规模从而解决单条探测路径长度过长的问题; 然后, 基于欧拉回路的思想在子图中规划得到覆盖拓扑中有向边仅一次的探测路径, 以解决探测节点数量和探测路径冗余问题; 并给出在动态拓扑下, 自适应使用局部调整与整体调整相结合的方式, 解决了网络拓扑动态变化时重新部署探测路径时间长的问题. 实验结果表明, ACGS方法能够在控制探测节点数量的同时, 降低探测路径平均长度, 降低探测路径冗余程度, 并在动态拓扑下保证调整速度更快.
软件定义网络中带内网络遥测能够持续监测网络状态, 动态高效地测量网络参数, 使控制器能够获得全网网络状态, 统筹管理全网流量[
文献[
文献[
文献[
文献[
综上所述, 现有全网覆盖的带内网络遥测探测路径配置方法存在的问题包括: 额外配置的探测节点会带来更大的维护开销; 因为探测路径上的转发节点需要插入遥测数据, 所以长度过长的探测路径会引起探测包大小超过网络MTU, 从而导致探测包丢包率增加; 而存在大量冗余的探测路径会导致测量引入的流量负荷在网络整体流量中占比过大.
同时, 现有方法当网络拓扑动态变化时就重新部署探测路径, 探测路径恢复速度慢的问题, 所以在动态变化的网络拓扑中, 如何减少探测路径配置的维护难度, 提高拓扑变化后部署测量路径的效率, 也是软件定义网络环境下带内网络遥测待解决的问题.
为解决上述问题, 提出了ACGS方法, 包括基于图分割的探测路径部署机制和探测路径自适应调整机制, 方法思路如下.
基于图分割的探测路径部署机制负责规划出覆盖全网的带内网络遥测探测路径. 首先, 通过图分割算法将拓扑图分割为多个拓扑子图, 以解决探测路径过长导致的数据包长度超过MTU, 引起丢包的问题; 然后, 通过在拓扑子图中求解欧拉回路获得遍历子图中所有边的探测路径, 解决探测节点数量过多以及探测路径冗余的问题; 最后, 控制器将探测路径下发至交换设备, 以完成全网覆盖的带内网络遥测探测路径配置.
探测路径自适应调整机制是为了解决当网络拓扑发生变化时, 重新部署探测路径面临的探测路径恢复速度慢的问题, 使用探测路径局部调整与整体调整相结合的方式调整带内网络遥测的探测路径. 由于探测路径的规划过程中将网络拓扑分割为多个子图, 对拓扑变化的子图中的探测路径进行局部调整, 有效降低了探测路径的调整范围, 减少了修复探测路径的时间; 由于多次局部调整会引起探测路径冗余程度增高, 所以当变化的拓扑子图超过一定比例后, 需要整体调整探测路径, 重新调用基于图分割的探测路径部署机制以完成探测路径的规划.
基于图分割的探测路径部署机制负责根据网络拓扑规划出覆盖全网的带内网络遥测探测路径, 其主要流程如
基于图分割的探测路径部署机制流程
图分割作为基于图分割的探测路径部署机制的预处理部分, 作用是将较大的拓扑子图分为多个符合拓扑分割阈值大小的拓扑子图, 并保证子图之间的割边尽量少.
图分割涉及到如下两个概念[
依据S-T割概念, 一个无向图求割的过程中, 两点
通过在Stoer-Wagner算法[
算法主要流程如下.
● Step 1. 根据Stoer-Wagner算法, 在图
● Step 2. 记录分割结果, 合并
● Step 3. 选择记录结果中符合子图阈值大小且割的权值最小的第1个结果作为一个子图.
● Step 4. 删除分割好的子图, 更新整体拓扑的节点集合和边集合.
● Step 5. 对新的子图重新执行Step 1, 直到所有子图符合阈值大小.
伪代码如算法1.
算法
输入:
输出:
1.
2.
3.
4.
5.
6.
7.
8. 计算使
9.
10.
11.
12.
13.
14.
15.
16. 找到与
17.
18.
19. 选择数组
20. 删除
21.
22.
23.
24.
图分割示例流程
关于子图阈值大小的选择, 子图的欧拉回路路径长度
在传统网络中, 以太网数据包大小在64–1500 B之间; 带内网络遥测的头部长度为12 B, Metadata长度为16 B; 网络中MTU通常为1500 B. 将上述理论值带入公式(1), 得到子图的欧拉回路路径长度
路径规划作为基于图分割的探测路径部署机制的主要部分, 负责在划分好的拓扑子图中求解一条覆盖子图所有有向边仅一次的带内网络遥测探测路径.
欧拉路径是指图
欧拉回路的求解是利用欧拉定理判断出一个图存在欧拉回路或欧拉通路后, 随机选择一个正确的起始顶点, 用DFS算法遍历所有的边(每一条边只遍历一次), 遇到走不通就回退. 在搜索前进方向上将遍历过的边按顺序记录下来. 这组边的排列就组成了一条欧拉通路或回路. 由于拓扑图是由无向图扩展得来的, 而求解欧拉路径的目的是覆盖无向图的所有边, 由一条无向边扩展来的两条边只需要覆盖一条即可, 所以上述计算过程是可以提前结束的, 通过维护两个数组undirctedVisited和dirctedVisited, 分别表示无向图边的访问情况和有向图边的访问情况, 当undirctedVisited全覆盖时, 即无向图边全覆盖, 就可以结束算法, 回到起始点. 通过遍历选取子图各个节点作为源节点, 选择欧拉回路最短的起点作为最终的源节点.
路径的下发作为基于图分割的探测路径部署机制的最后一步, 负责将规划好的探测路径下发至交换设备, 其功能主要通过P4 Runtime实现.
P4 Runtime是一套基于Protobuf以及gRPC框架上的协议, 通过P4 Runtime, SDN控制器可以控制P4的设备, 并获得设备基本信息. 与传统SDN南向协议OpenFlow不同, 除了具备高度弹性的信息格式以外, 控制器与设备之间连接的顺序也不同, 以往OpenFlow是需要控制器开启特定的接口, 然后设备才能连上控制器, P4 Runtime则是在设备上开启RPC server, 由控制器联系设备, 因此设备上会有一个Agent负责处理由控制器发来的请求, 完成与控制器互连. 上述路径规划求解后的路径通过P4 Runtime[
探测路径自适应调整机制主要负责在拓扑发生变化时, 及时根据拓扑变化情况, 在局部或整体上调整探测路径, 以降低因拓扑改变导致的探测路径调整时间. 主要包括网络状态动态监测、探测路径局部调整、探测路径整体调整3部分.
网络动态检测实时监控网络拓扑, 并在拓扑发生变化时, 及时上报控制器, 主要由两部分功能组成: 实时链路状态收集和链路状态上传汇报. 其中, 链路状态收集主要通过LLDP协议实现, 链路状态上传汇报主要通过P4 Runtime来完成.
LLDP[
网络设备通过LLDP获取网络中其他设备的MIB信息, 并将相关信息通过P4 Runtime上传至控制器, 从而收集到网络拓扑, 以及网络设备之间的实时链路状态.
探测路径局部调整是在网络设备或网络链路发生故障, 且已发生故障的子图数量占子图总数的比例低于一定阈值(此阈值将在后续实验中探究)时, 从局部调整恢复带内网络遥测探测路径.
由于带内网络遥测探测路径固定, 一旦一条路径中的一台交换机出现故障(如
带内网络遥测故障示例
具体来说, 对于发生变化的拓扑, 考虑其影响会集中于少数几个拓扑子图中, 局部利用生成树算法调整探测路径, 即在拓扑变化的子图中, 若源节点未发生故障, 则以已有源节点为生成树的根, 采用最小生成树算法, 重新计算探测路径; 若源节点发生故障, 则随机选择一个交换设备作为生成树的根, 利用最小生成树算法, 重新计算探测路径. 探测路径局部调整会减轻由于交换机节点在测量中角色发生变化带来的开销.
探测路径整体调整是在网络设备或网络链路发生故障, 且已发生故障的子图数量占子图总数的比例超过一定阈值(此阈值将在后续实验中探究)时, 从整体调整恢复带内网络遥测探测路径.
由于探测路径局部调整并不能保证子图内的探测路径是冗余度低且路径长度短的最优解, 当拓扑改变过大时, 将导致存在很多非最优的探测路径, 网络状态测量效率下降. 所以在超过一定比例的子图发生改变后, 需要重新对探测路径进行整体调整, 即重新执行基于图分割的探测路径部署机制. 至于何时触发探测路径的整体调整, 需要在实验中进行尝试来寻找合适的值.
实验所用环境如
全网覆盖的带内网络遥测实验环境
实验参数包括: INT探测节点数量、INT探测路径平均长度、INT报文丢包率、INT元数据流量占比[
● INT探测节点数量包括带内网络遥测的源节点和汇聚节点的总数.
● INT探测路径平均长度为探测路径总长度除以探测路径数量.
● INT报文丢包率是网络中丢失的INT探测包个数总和与INT探测数据包个数总和的比值.
● INT元数据流量占比的计算方式如公式(2)所示, 分子为一段时间内网络中所有流量中的Metadata部分的长度总和, 分母为这段时间内所有流量的长度总和, 计算出来的百分比可以代表带内网络遥测为网络流量带来的负荷, 此百分比越大, 代表带内网络遥测为整体网络流量带来的负荷越大.
● INT探测路径冗余度的计算方式如公式(3)所示, 分子为探测路径总长度, 即所有子图中的探测路径长度总和, 分母为实验所用网络拓扑中的链路个数, 此参数代表了探测路径的冗余程度. 同一拓扑下链路总数一定, 即公式中的分母一定, 而拓扑图中的链路被重复测量的次数越多, 分子越大, INT探测路径冗余度越高. INT探测路径冗余度的最优值为1, 表示探测路径不存在冗余.
● 探测路径调整时间为链路改变的时间与经过调整后带内网络遥测重新开始工作时间的差值.
上述参数中INT探测节点数量主要反映了带内网络遥测中数量过多的探测节点带来的维护开销问题; INT探测路径平均长度和INT报文丢包率反映了带内网络遥测中长度过长的探测路径会引起探测包大小超过网络MTU, 导致探测包丢包的问题; INT元数据流量占比和INT路径冗余度反映了带内网络遥测中大量冗余的探测路径会导致测量引入的流量负荷在网络整体流量中占比过大的问题; 探测路径调整时间反映了链路发生改变后探测路径的恢复速度.
FatTree拓扑示例
子图分割阈值的选择会影响部署时INT探测流量在网络整体流量中的占比和所需探测节点的数量.
Metadata流量占比与探测点个数对比图
探测节点数量对比图
探测路径平均长度对比图
INT报文丢包率对比图
路径覆盖冗余度对比图
Metadata 流量占比对比图
路径覆盖冗余度对比图
探测路径调整时间对比图1
探测路径调整时间对比图2
本文提出的ACGS方法基于图分割的划分方式将拓扑图划分为多个子图; 并基于欧拉回路得到能够覆盖拓扑子图的带内网络遥测探测路径; 结合局部调整与整体调整, 在动态拓扑下进行自适应探测路径调整, 以降低因拓扑改变导致的探测路径调整时间. 实验结果验证了SDN网络带内网络遥测探测路径配置方法的有效性, 后续研究主要在实际环境中部署应用ACGS方法, 并对其进行改进和优化.
Karakus M, Durresi A. Quality of service (QoS) in software defined networking (SDN): A survey. Journal of Network and Computer Applications, 2017, 80: 200–218. [doi: 10.1016/j.jnca.2016.12.019]
张恒, 蔡志平, 李阳. SDN网络测量技术综述, 中国科学: 信息科学, 2018, 48(3): 293–314.
Zhang H, Cai ZP, Li Y. An overview of software-defined network measurement technologies. SCIENTIA SINICA Informationis, 2018, 48(3): 293–314 (in Chinese with English abstract). [doi: 10.1360/N112017-00203]
Kim C, Sivaraman A, Katta N, Bas A, Dixit A, Wobker LJ. In-band network telemetry via programmable dataplanes. ACM SIGCOMM, 2015, 15(1): 1–2.
刘争争, 毕军, 周禹, 王旸旸, 林耘森箫. 基于P4的主动网络遥测机制, 通信学报, 2018, 39(S1): 2018181
Liu ZZ, Bi J, Zhou Y, Wang YY, Lin YSX. Paradigm for proactive telemetry based on P4. Journal on Communications, 2018, 39(S1): 2018181 (in Chinese with English abstract). [doi: 10.11959/j.issn.1000-436x.2018181]
Ford Jr LR, Fulkerson DR. A simple algorithm for finding maximal network flows and an application to the Hitchcock problem. Canadian Journal of Mathematics, 1957, 9: 210–218. [doi: 10.4153/CJM-1957-024-0]
Boykov Y, Funka-Lea G. Graph cuts and efficient N-D image segmentation. International Journal of Computer Vision, 2006, 70(2): 109–131. [doi: 10.1007/s11263-006-7934-5]
Queyranne M. Minimizing symmetric submodular functions. Mathematical Programming, 1998, 82(1): 3–12. [doi: 10.1007/BF01585863]
Bosshart P, Daly D, Gibb G, Izzard M, McKeown N, Rexford J, Schlesinger C, Talayco D, Vahdat A, Varghese G, Walker D. P4: Programming protocol-independent packet processors. ACM SIGCOMM Computer Communication Review, 2014, 44(3): 87–95. [doi: 10.1145/2656877.2656890]
Dandavate V, Jinjala J, Keharia H, Madamwar D. Production, partial purification and characterization of organic solvent tolerant lipase from
Leiserson CE. Fat-trees: Universal networks for hardware-efficient supercomputing. IEEE Transactions on Computers, 1985, C-34(10): 892–901. [doi: 10.1109/TC.1985.6312192]
Marques JA, Luizelli MC, Da Costa Filho RIT, Gaspary LP. An optimization-based approach for efficient network monitoring using in-band network telemetry. Journal of Internet Services and Applications, 2019, 10(1): 12. [doi: 10.1186/s13174-019-0112-0]