石鸿伟 黄凤芝

（1.网络通信与安全紫金山试验室未来网络研究中心 江苏省南京市 211111）

（2.南京铁道职业技术学院机车车辆学院 江苏省南京市 210031)

1 引言

随着网络技术的不断演进，新兴的网络业务种类越来越多，不同业务对网络的要求不尽相同，尤其是对传统的互联网提出了新的挑战。

智能化流量调度是下一代互联网络的关键能力，对业务应用质量的保障、网络带宽资源的优化起到非常重要的作用。现有的多协议标签交换（MPLS, Multi-Protocol Label Switching）[1]及基于流量工程扩展的资源预留协议（RSVP-TE, Resource ReSerVation Protocol-Traffic Engineering）[2]等技术可以满足应用对带宽的差异化保障需求，但存在协议种类多、部署复杂、管理困难、可扩展性差等问题，无法满足下一代互联网络业务动态部署、弹性扩展、灵活调度等方面的要求。

因此，国际互联网工程任务组（IETF, The Internet Engineering Task Force）提出了的一种新型的标准化体系架构-分段路由（SR, Segment Routing）[3]。这种新型的SR 协议既能够兼容MPLS 网络[4]也可以兼容IPv6 网络[5-7]，既很好的继承了MPLS 技术的优势，又能够适应未来IPv6、SDN 等技术的发展[8]，为互联网络提供了一种高效灵活的管控手段，具有部署简单、灵活扩展的特点，可以更好的实现流量调度和路径优化，均衡流量分布，提高专线利用率，保障关键业务质量，降低线路成本。

SR 协议是基于源路由的机制。路径描述采用在数据报文头中插入带顺序的段列表（Segment List）以指示收到这些数据包的节点（路由器、主机或设备）如何去转发和处理这些数据包。在基于SR 的互联网络中，不再需要LDP 和RSVP-TE 等信令协议，仅依赖于已经部署的路由协议（如OSPF[9]和ISIS[10]）进行扩展。互联网服务提供商（ISP, Internet Service Provider）可以在无需额外投资的情况下，在当前生产网络中的节点上启用部署SR，极大降低了网络的资本性支出（CAPEX, Capital Expenditures）和运营成本（OPEX, Operating Expense）[11]。

表1：SR 标签分类

图1：邻接标签

图2：SR 引流方案

SR 路径是由一系列有序的段标识符（SID, Segment Identifiers）组成。每个SID 与数据平面转发指令相关联，例如，沿着IGP 最短路径进行转发或者转发到指定的出接口上。在SR MPLS 中，这些SID 被编码为标签堆栈。在流量工程中，由于需要提供差异化的服务能力，多约束条件（最短时延，最大带宽等）被用于路径计算。承载业务流量的转发路径并不一定遵循最短路径。因此，标签堆栈的大小与转发路径的长度成正比关系。

然而，当前在转发平面数通设备上，为了达到数据报文线速转发，厂商都是通过供专门应用的集成电路（ASIC, Application Specific Integrated Circuit）上实现的MPLS 报文转发[12]。由于这些专用集成电路被设计成高效执行某些特定任务，因此，可执行的操作的大小和类型受到了限制，即硬件设备的最大堆栈深度（MSD, Maximum Stack Depth）。这种限制会影响到数据报文头插入标签堆栈的大小。一些典型的商用网络设备当前最多只能支持3 到5 层标签[13]。如何有效的对转发路径进行标签编码，减少标签堆栈的大小，扩大受控网络的规模具有至关重要的意义。

2 相关工作

目前，为了解决或降低最大堆栈深度MSD 对SR 标签栈的限制，研究领域内有两种主流的研究方向：标签压缩[14-15]和粘连标签[16-17]。标签压缩是指在不影响转发路径表达的前提下降低标签堆栈的深度。粘连标签是指在标签堆栈中加入一种可扩展的特殊标签，该标签到达转发设备后，根据映射规则，被重新替换为多个有序SR标签，重新压入数据包的报文头中，继续转发。不过，即便使用粘连标签技术，在粘连之前先通过标签压缩技术降低标签栈的总深度也是很有必要的。因此，本文重点在标签压缩方向进行深入研究。

为了解决标签压缩方法计算量大、压缩效率不高等问题，本文提出了一种基于关键节点的标签栈压缩算法（LSC-K, Label Stack Compression based on Key-node），根据网络节点间的互连意图，通过分析网络组网拓扑关系，识别关键网络节点，结合分段路由松散路径原理，消减转发路径上无效的节点数量，实现标签堆栈的压缩。

3 Segment Routing技术分析

在广域网场景中，MPLS 技术已经得到了大规模的部署。随着社会的发展，ISP 服务提供商、OTT（Over The Top）业务商、大型企业等迫切需要广域网能够提供租户隔离、差异化的流量调度等网络服务能力。因此，LDP、RSVP-TE 等协议也得到了广泛应用部署。但这种解决方案的问题也逐渐暴露出来。

MPLS 网络的控制面技术主要依赖LDP 和RSVP-TE。首先LDP 没有流量工程机制，无法按需指定转发路径，也无法基于业务（时延、带宽、丢包等）进行流量调度。因此需要通过叠加RSVPTE 实现流量工程。但是RSVP 信令非常复杂，每个节点都需要维护一个庞大的链路信息数据库。由于RSVP-TE 要求节点之间构建Full-mesh 隧道，在大规模部署时，扩展性受到了限制。另外RSVP-TE 隧道不支持等价多路径（Equal-Cost Multipath Routing，ECMP），无法满足现代IP 网络的需求。

因此，被业内称为下一代MPLS技术的Segment Routing出现了。SR 技术源于MPLS，但是又对MPLS 进行了革命式的创新，它是一种全新的网络思维，即业务驱动网络。通过源路由机制，将业务逻辑进行按需编排，封装到数据报文头部，在MPLS 网络中，根据编排后的SR 标签堆栈指导数据报文进行转发。因SR 与SDN 技术天然结合的特性，也逐渐成为SDN 网络架构的一个重要技术应用。

SR 技术从被设计之初就坚持了对网络协议做减法的原则。首先，裁剪掉了RSVP 复杂的信令机制。通过SDN 集中式控制思想和源路由机制，很好的解决了信令交互带来的复杂性。其次，裁剪掉了LDP 标签分发机制，直接通过网络中已部署的IGP 协议进行分发和同步标签信息。例如IS-IS 协议是通过TLV 实现，OSPF 协议通过不透明LSA 实现。如果网络中引入SDN 控制器，分发和同步标签信息的工作也可以由控制器完成。

图3：标签栈深大小

图4：接口调用响应时间

SR 标签主要分三类，具体参见表1。

Prefix SID：前缀标签，是为目的地址前缀分配的标签，标签在整个SR 域内全局唯一，标识的方式为SRGB+Index，其中SRGB（Segment Routing Global Block）为分段路由全局块。例如，如果SRGB 从16000 起始，10.0.0.0/24 网段被分配的Index 为1，那么10.0.0.0/24 的Prefix-SID 为16001。

Node SID：节点标签，可以理解为一种特殊的Prefix-SID。例如，将设备Loopback 接口下配置的IP 地址作为前缀，其对应的 Prefix SID 实际就是Node SID。

Adjacency SID：邻接标签，表示转发设备上某条链路的单跳路径，仅在设备本地有效。如图1 所示，9001、9002、9003 分别表示的是为每条链路分配的邻接标签。

根据以上的标签分类原则，SR-TE 转发路径也可以分两类。

松散路径（Loose Explicit）：利用Prefix/Node SID 的组合，结合使用IGP 算路，可以在网络中形成多条转发路径。

严格路径（Strict Explicit）：当需要对流量进行精细化调度时，使用Adjacency SID，可以唯一指定一条显式路径。

具体的SR 引流方案如图2 所示。

（1）SDN 控制器通过BGPLS 协议收集全网的拓扑信息、链路状态信息，并分配SR 标签利用Netconf 协议下发到设备上。

（2）当存在10.0.1.0/24 和10.0.2.0/24 互访需求时，网络中会有非常多的转发路径，比如ABCF，ADEF，ABCEF 等。如果不需要对流量做调度，按照默认的多路径转发即可。

（3）如果应用对网络提出了SLA 要求，比如需要一条带宽大于10M，延时少于30ms 的转发路径。

（4）SDN 控制器根据已经掌握的全网拓扑信息、状态信息、标签信息，计算出符合条件的显式路径，通过Netconf 下发到源节点A 上，转发路径为ABCF。

（5）当链路CF 出现流量拥塞，SDN 控制器感知到后，重新计算满足业务需求的路径，将转发路径下发到源节点A 上，转发路径为ABCEF。

根据以上的分析和举例，可以看到，在网络节点不多，链路不复杂的情况下，SR 标签堆栈已经被用掉5 个了。如果在广域大规模组网的情况下，由于MSD 的限制，是很难做到大网级满足业务要求的精细化流量调度。

4 LSC-K算法设计

4.1 设计思路

详细分析图2 中的网络拓扑，从源节点A 到目的节点F 的转发路径中，对于B 节点，无论如何计算路径，经过B 节点的转发路径是唯一确定的，因此该节点是可以被压缩的，本文把这种节点叫做互连节点。对于C 节点，由于业务意图的不同，网络拓扑的变化，经过C 节点的Adjacency SID 存在不同选择，本文把这种节点叫做关键节点。

因此，在大规模网络组网中，合理选择关键节点，在关键节点之间确定唯一的转发路径，可极大压缩互连节点上的Node SID，最终实现减少转发路径节点数量，达到标签堆栈压缩的目标。

本文的求解MSD 问题可以归纳为，如何根据网络组网情况，结合源目的节点互联需求，合理确定网络拓扑中的关键节点，有效压缩转发路径上互连节点的问题。

4.2 算法描述

首先，给出算法中的相关定义。

转发路径：aij表示从节点i 到节点j 的路径描述。路径描述内容包括转发路径的跳数nij，以及转发路径节点列表PathListij，由于两点之间可能存在多条转发路径，因此，它是一个二维列表。

互连节点：两个网络节点直接互连，路径跳数nij为1，这两个网络节点互为互联节点。

关键节点：节点i 的互连节点个数大于2 时，该节点为关键节点。

分支节点：当两点之间存在多条等价多路径的时候，选择其中一条路径上的首个节点作为分支节点。

路径矩阵：由 m × m 个转发路径aij排成的m 行m 列的数表。其中，m 表示网络拓扑节点个数。由于转发路径的无向性，因此，路径矩阵也是对称矩阵。

Dijkstra 算法：Dijkstra 算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。

4.2.1 步骤一：确定关键节点

根据网络拓扑初始化路径矩阵，其中到自己的路径跳数nii设置为0，节点i 到互连节点j 的路径跳数nij设置为1，节点i 到非互连节点j 的路径跳数nij设置为*。

分别计算节点i 的互连节点个数Mi。

当Mi大于2 时，确定为节点i 为关键节点，并插入到关键节点列表KeynodeList 中。如果Mi都不大于2，则跳转到步骤四，处理没有关键节点的情况。

4.2.2 步骤二：更新关键节点之间的转发路径

（1）遍历KeynodeList，根据Dijkstra 算法，分别计算关键节点之间的转发路径aij{nij，PathListij}。

（2）如果PathListij只有一条路径链表，继续后续处理流程。

（3）如果PathListij有多条路径链表，选取路径跳数nij最小那条转发路径，如果跳数相同，随机选一条路径。并设置该路径上首节点为分支节点。

（4）确定好转发路径后，进行剪枝操作，遍历该路径上的所有节点（除了源、目的节点），如果该节点为关键节点或分支节点，则保留，否则剪枝。

（5）根据剪枝结果，更新转发路径aij{nij, PathListij}。

4.2.3 步骤三：更新其他节点之间的转发路径

（1）查找源节点i 直连的关键节点KeynodeListi

1.如果源节点是关键节点，继续后续处理流程。

2.如果源节点非关键节点，通过路径矩阵中，遍历查找所有节点i 的互连节点是否为关键节点，如果是，插入KeynodeListi中，如果没有找到，遍历所有互连节点，迭代查找关键节点，直到找到所有距离节点i 最近的关键节点。

（2）查找目的节点j 直连的关键节点KeynodeListj

1.如果目的节点是关键节点，继续后续处理流程。

2.如果目的节点非关键节点，通过路径矩阵中，遍历查找所有节点j 的互连节点是否为关键节点，如果是，插入KeynodeListj中，如果没有找到，遍历所有互连节点，迭代查找关键节点，直到找到所有距离节点j 最近的关键节点。

（3）确定KeynodeListi与KeynodeListj之间转发路径

1.判断KeynodeListi和KeynodeListj中，是否有相同的关键节点。

2.如果存在，节点之间的路径链表PathListij为{节点i，Keynode，节点j}。

3.如果不存在，从源节点列表KeynodeListi中，选择一个节点o，在目的节点列表KeynodeListj中，选择一个节点p，根据步骤二关键节点之间的转发路径结果，找到节点o 和节点p 之间的路径链表PathListop，得到PathListij为{节点i，PathListop，节点j}。以此类推，迭代遍历KeynodeListi和KeynodeListj中所有的节点。选取路径跳数nij最小那条路径链表。

4.2.4 步骤四：处理没有关键节点的场景

当拓扑中没有关键节点，该拓扑只有两种情况：线状拓扑或者环状拓扑。

如果是线状拓扑，任意两点之间路径链表PathListij为{节点i，节点j}。

如果是环状拓扑，采用Dijkstra 算法计算出任意两点之间路径链表PathListij为{节点i，节点k，……，节点m，节点j}，设置节点k 为分支节点，最终节点i 和节点j 之间的路径链表PathListij为{节点i，节点k，节点j}。

5 实验验证及分析

一个高效的路径压缩算法可以从有效性和服务质量两个方面进行评价。有效性指的是衡量该算法对标签转发路径进行压缩的效果。服务质量指的是业务调用该算法进行路径计算请求的时间。

本文使用JAVA 语言编写网络仿真软件进行测试验证，分别从不同源目节点的路径栈深以及算路查询效率两个方面，将Dijkstra算法和LSC-K 算法进行对比，得出结论。

实验平台的硬件环境为Intel® Core TM，且有四个3.6GHz 的内核CPU，支持八线程并行，内存为16GB 的X86 服务器，运行Windows 10 专业版（x64）的操作系统。

5.1 不同源目节点的路径栈深

实验拓扑采用未来网络试验设施CENI 项目进行建模，该项目覆盖全国40 个核心节点，133 个边缘节点，随机选择不同源目节点进行30 次采样，对比不同算法的路径栈深情况，判断路径压缩算法的有效性，如图3 所示。

从图中可以看出，当随机选择源目节点进行路径计算时，由于Dijkstra 算法是基于最短路径算路，受所选择源目节点的物理位置影响，路径栈深在4 ～7 跳不规则波动，而采用LSC-K 算法，通过拓扑分析，智能选择关键节点，进行转发节点压缩，路径栈深被有效的压缩到3 ～4 跳，而且受节点物理位置影响小，可以达到很好的压缩效果。

5.2 算路查询效率

随着万物互联的时代到来，越来越多的业务用户对网络服务质量提出更高的要求。路径计算是最基本的需求。除了算路结果的有效性外，快速响应算路查询请求，能够极大提升用户的使用体验。因此，根据30 次算路的API 接口响应时间进行对比，判断算路算法的查询效率，如图4 所示。

通过对比，发现使用Dijkstra 算法时，每次算法查询请求都需要重新计算，由于受到服务器性能、转发路径差异等因素影响，接口调用响应时间上下波动较大。而采用LSC-K 算法时，由于该算法会提前构建路径矩阵，因此在响应算路请求时，只需从内存中，将算好的路径结果直接进行查找反馈，不受外部环境影响，非常平稳，且基本都在1ms 左右。

6 结束语

本文针对分段路由（Segment Routing）网络中，在进行路径计算时，针对所存在最大栈深（MSD）的问题进行了分析和改进，提出了基于关键节点的标签栈压缩算法（LSC-K 算法）。该算法通过分析网络拓扑关系，识别关键网络节点，结合分段路由松散路径原理，消减转发路径上无效的转发节点数量，实现标签堆栈的压缩。同时，利用快速构建路径矩阵的方式，极大缩小算路查询请求的时间。实验结果表明，LSC-K 算法可以有效的压缩标签堆栈大小，提高网络服务的质量，扩大受控网络的规模，提高网络资源的利用率，满足未来网络业务的需求。