服务功能链中基于单纯形法的路径规划算法

居 翔，李沛武，王 奇，韩 飞，章荣辉

（1.南昌工程学院信息工程学院，江西 南昌 330099；2.江西省水信息协同感知与智能处理重点实验室，江西 南昌330099；3.常州大学机械与轨道交通学院，江苏 常州 213164）

0 引言

随着网络技术的迅速发展，互联网产品也越来越丰富，其逐渐融入人类的衣食住行，成为学习、工作、生活不可或缺的一部分。2020年新冠疫情席卷全球，为避免因人员聚集而引起病毒扩散，各大中小学将课堂从线下搬到了线上、研究生复试也由传统形式改为网络视频复试……这使得网络安全益发重要，一旦网络出现故障，网络通信就会受到影响，轻则网络跌宕，重则网络瘫痪。传统链路下网络故障处理的成本较高，如2011年日本东北地区发生了地震，该地区大部分信号基站停运，网络历时7天才被恢复[1]，流量报文解析速率是正常周期的1.8倍[2]，期间各大运营商、设备商调用大量运维人员、库存设备等资源；此外，用户所在园区网的通畅还需人工排故等。因而，降低网络不可达故障对用户的影响一直以来都是网络工程师的追求。

目前，解决这一系问题潜在的方案有网络功能虚拟化（Network Fuctions Virtualization，NFV）和软件定义网络（Software Defined Network，SDN）。NFV通过一系列软件将网络功能虚拟化，在NFV框架中运行网络功能。NFV减少运维商在设备配置方面的开销、缩短网络服务部署周期、简化了系统管理难度、动态实现网络服务扩展、提升了通信系统的灵活性；但NFV目前需要对网络的延迟、吞吐量、处理开销、安全性、稳定性、平台复杂等方面作出提升[3]。SDN框架的核心思想在于将数据平面与管理平面分离[4]，使网络可拓展性、部署的便捷性突出，其逐渐被厂商接受，成为新一代的网络框架。基于SDN框架的网络功能服务链（Service Function Chain，SFC），采用OpenFlow协议实现数据层与控制层的通信，将底层网络通信设备有机地整合，合理分配资源，提高网络的效率。SDN框架把网络当成一个资源池，对其展开协调调度，提升网络利用率[5]。SFC能够对网络进行灵活编排、部署、割接，从而使网路的管理基于管理员的意志，为用户提供高质量的网络服务。

由于TCP/IP模型中的三层（Internet层）多故障、延时、易丢包等缺点（IP协议不靠谱），使得SFC在路由模式（Routering Model，RM）面临一些挑战。主要体现在：动态部署、路径规划、三层节点跌宕方面。需要解决这些问题需，才能发挥SFC的智能管理功效。鉴于此，本文提出基于单纯形法的路径规划算法来解决SFC在RM模式下的路径规划（Path Planning，PP）问题，增强SFC的流量调度处理能力，提高其最优选路速度，提升SDN网络的智能性。

1 相关工作

线性规划（Liner Programming）是运筹学、决策科学和管理科学最重要的基础，现在已经成为人们合理利用、调配有限资源并作出最佳决策的有力工具[6-7]。随着科学技术的快速发展，一般线性规划已经不能满足工程人员对工程问题的低消耗、高回报的要求，因此对项目最优化也应运而生。由于网络路径问题的变量和约束的数量不是很大，因而有很多算法可以有效得到最优解，例如单纯形法。单纯形法作为线性规划的最优化方法之一，在工程项目中实施的过程中起到了决定性作用。下面我们将对单纯形法以及NP模型作出简单的介绍。

1.1 单纯形法算法

单纯形法算法（Simplex Algorithm）由丹西格于1947年提出，是一种解决线性规划问题的有效方法[8-9]，它的原理：把线性规划问题的解的可实施部分看作一个n维向量空间中的凸集，单纯形法能够找到可形基与可行解，且能够判断其是否为最优解；若不是最优解，则寻找下一个更优的可行基和基本可行解。

线性规划问题可用公式（1）表示，它的目标函数可使用min（也可以使用max），其约束条件表示为Ax=b。单纯形法中，约束矩阵A可表示成m×n的矩阵，A=（p1，p2…pm），b=（b1，b2…bn），C=（c1，c2…cn）。采 用B=（p1，p2，…，ps）（s＜m）来表示可行基，B的数量满足 个，对应的可行解不超过 个，j为可行基的下标。若不满足非负，则Bj为非可行基，操作停止；若满足非负，则Bj为可行基，计算得到约束行列式的列系数，求解得非基变量的检验数[8]，并依据检验数的正负判断公式（2）是否为当前最优解。

1.2 网络模型

为降低网络开销成本，本文以网络程序模型（Network Program，NP）基采用F=（V，E）机制来获取网络实时流量状态，其中，顶点V对应行（约束或网络节点的集合），E对应边缘响应列（变量或网络中的有向边缘设备）。系数矩阵A的行由服务功能链（SFC）中的服务功能（SFs）决定，列由SFs三层模式（RM）下的路由表决定。如果F是n（n＞0）个SFs（节点）的链接有向图，则表明它的列不依赖于线性，所以但是由于将A的所有行相加，最后将NP转化为线性规划问题，具有以下特征：每一列的系数都有一个1其形式也可使用公式（1）所示，其中，和一个-1，剩下的系数都是0；m表示约束的数量，n表示变量的数量；行由节点（SFs）的数量决定。

1.2.1 节点模型

在SFC中，SFs的状态分别为“Up”“Down”（分别对应二进制1、0），我们将其建成一个元组Node（id，Nstate，Nset）。其中，id表示SFs的序列号，Nstate表示SFs的状态，Nset表示相邻的两个节点之间Edge的集合。

OpenFlow控制器通过OpenFlow协议在SFC中收集各个SFs的信息，并将响应的信息分析并存储在列表。节点状态为“Up”，转换为数值1；节点状态为“Down”，转换为数值0。由于SFC中SDN交换机的端口分为：常用端口和特殊端口；常用端口为与交换机、路由器、防火墙等设备相连接的设备，在设备未启动的状态下，SDN对应端口无法通过数据流，则状态为0；特殊端口为特殊服务如镜像、监控等端口，此类端口需要实时监控网络流量状态，因而其状态必须为1。

1.2.2 链路模型

由于SFC的上、下行链路以及SFs的上、下行链路的通信方式都可选为全双工模式，因而本文对网络链路抽象成有向连接图（见图1），每一条逻辑链路对应一条相应的有向 表示，其中，id表示Edge的序号，s表示Edge的源SFs，d表示Edge的目的SFs，cn表示链路的开销，ln表示容量下限，un表示容量上限，bn表示总流量，bw为Edge的带宽，rw表示Edge的剩余带宽。可将图2描述为：每一个变量（Edge）xj是沿着第j个边缘设备发送的Flow；发送1单位Flow的cost是cj；流不能超过容量uj，必须有一个最小流lj（最小流通常为0）；顶点i处的总流量是由bi所决定。因此，网络流量的求解就是沿着图寻找可行流程，使cost最小化。节点设备R1、R2、R3的有向边Edge表示为x1、x2、x3、x4，其对应的总流量bi由花括号中的5、0、-5；中括号中的元素对应cj、lj、uj。

图1 网络链接图

将链路的路径表示为 ，路径周期如式（3）所示，其中，ae是e在顶点边缘射入矩阵A的列，ev是第v个单位向量（除了束引v处的1外，所有为0）。

2 算法描述

本文提出RM模式下SFC的基于单纯形法的路径规划算法采用了单纯形法、NP模型，它能够筹划SFC在RM模式下的网络流量的路径，即通过检测获取网络流量的数据报头部的源和目的地址、服务功能（SFs）的数量进行计算，并采用遍历比较cost从而获取最优路径。对于算法的参数，选取5个自适应的参数。自适应是指根据算法的演化状态动态地更新算法各策略中用到的关键参数以及恰当地进行策略的调用、转换和设置[10-11]。算法启动时需要同时开启2个线程，一个用于检测、规划路径如算法1所示，另一个用于发生故障为处理故障争取时间的流量调度（Traffic Schedule， SHC）如算法2所示。

2.1 路径规划算法

路径规划算法，顾名思义通过检测、分析、计算得到LAN的最优路径以及备用路径（多条），将有效路径设置优先级存并储进OpenFlow控制器，方便SFC在遇到网络故障的情况下（自然灾害等）查找、调用网络路径，从而使故障网络能够快速恢复正常。

2.1.1 算法简介

普遍而言，使用蛮力法解决网络问题是最简单的方法，但蛮力法的成本较高，后期可扩展性较差；而贪心算法核心是用最小的代价，获取最大利润[12]。此外，贪心算法处理事件速率是非常迅速的，可以用在线性规划问题中[13]。因而，为了减少跳跃赘余的节点，我们开发了一种多路径、快速替换的路径规划算法。该算法对流量集进行最优化分析与计算，从而得到损耗最小的三层模式（RM）路径，具体步骤如算法1：①SFC采集并提取SDN网络中流量的SFs和连接在SFs上Edge的数量，将其放入SFC的数据库中，遍历输入量使其初始化，使其通过NP模型映射于单纯形法的约束变量，寻找输入量的可行基B，计算B-1、B-1b、CTBB-1b，其中Nnode、nedge分别表示SFs（或节点）数量、边缘设备的数量；②计算路径的成本（即单纯形法的最优解），计算则返回最优值，否则令dq＜0的情况下计算；③接下来，计算测试比例，判断是否绑定；④存储单纯形法的最优、次优值；⑤更新数据库中的路径；⑥输出最优路径。

2.1.2 参数设定

在SDN环境下的SFC中，三层模式下SFs的正常化通信，关系着SFC的推广以及市场化。本文采用服务功能数量、源目地址作为算法参数，cost作为评估参数，以确保在基于单纯形法的路径算法下SFC能够提供更高质、安全、便捷、可靠的服务。

（1）Node数量、Edge数量，可通过SFC向链路发送LLDP数据报进行网络检测，获取网络的网元设备状况信息而得知；具体过程如图2所示：①OpenFlow控制器向SDN交换机发送Packet_Out消息（含有LLDP数据包），来检测服务功能链（SFC）的服务功能（SF）以及设备。SDN交换机将LLDP帧添加到Packet_In消息中，然后发送给OpenFlow控制器[14]。OpenFlow控制器依据接收到的Packet_In消息（LLDP帧），构建用于网络拓扑检测的数据库。②服务功能（SFs）由控制器实时管理，以确保为网络提供持续、稳定、可靠的服务。

图2 SFC中LLDP数据报传输

（2）源、目的地址，服务功能链（SFC）触发后，通过接收其上、下行链路上的ARP报文来学习地址等相关信息；

（3）cost，由于其是OSPF协议选路的重要参考度量，因而将其用于用于检测单纯形法的路径是否最优；

对于传输过程以及存储过程中因参数的缺失或遗失，本算法采用拉格朗日插值法[15]取参数的近似值，以降低算法的错误，见式（4）。

2.2 故障路径流量调度算法

在SDN网络中，在SFC上动态部署、下线服务功能（SFs）或服务功能组（SFG），调度网络流量成为了非常重要的问题。流量调度是一个NP-hard问题，即使使用一些启发式算法，获得接近最佳的调度方案也非常耗时[13]。当下主流的协调调用方法共同优化NFV中的资源分配（Jointly Optimize the Resource Allocation in NFV，JoraNFV），其主要方向在运营成本和链路消耗的混合型整数线性规划调用，其一般运用于大型运营商网络，对于园区网的本地局域网（LAN）而言其代价太高。将SFs的下一跳可以视为线性规划问题，尽管它不能保证全局流量调度是最佳解决方案，但其能够将下一跳调度性能作为衡量SFC的性能指标[16]，可以使用单纯形法来解决该问题。本文的故障路径流量调度算法基于故障SFs流量的数据报文进行流量处理，其消耗成本较低。

SFC在SDN网络的三层模式下，检测到SFs下线（由断电、人为下线等引起故障），此时流经下线SFs的流量需要被调度，以保持网络的稳定性，同时为备用路径的启用预留反应时间。故障SFs流量调度算法具体步骤如下：

Step1：将途径流量的IP数据报头部字段、故障SFs的物理地址映射到算法中，其中msrc、Mdst、isrc、Idst分别表示源Mac地址、目的Mac地址、源IP地址、目的IP地址，将点分十进制的IP地址初始化转换成十六进制，并使用列表存储。

Step2：将转换成十六进制的目的IP地址分别存入新生成的伪地址（）的0-3号，将SFC的ID号转换成十六进制作为4号元素，最后将本算法的代号H7（次数作为参考数据）作为5号元素。

Step3：当SFC检测到其SFs发生故障并停止工作时，途径SFs去往边缘设备的流量报文急需处理，此时故障路径流量调度将伪MAC地址封装进报文的目的MAC地址，得到ARP响应报文，使得SFs（处于故障状态）的上、下行链路通畅。

Step4：待路径规划算法的备用路径启动后，若备用路径正常则调度算法将伪Mac地址更改成真实的备用SFs的端口Mac，通过Packet_In消息发送给OpenFlow控制器；若备用路径故障，返回执行Step2。

Step5：OpenFlow控制器向SDN交换机下发启用备用路径的流表。

3 实验验证与分析

在本节中，我们着重介绍实验环境和最终的性能评估。为了测试基于单纯形法的路径规划算法，将其与JoraNFV算法、传统网络做对比实验。首先，我们在SDN网络中搭建SFC环境以及搭建传统网络链路。之后，为了检验动态部署、三层节点跌宕引发的路径故障，我们通过在网络中的添加、删除网元设备（节点）。SFC实验拓扑如图3所示，定义了SFs在SFC环境中的流量上、下行链路，将SFs部署为三层模式，以便于网络流量在SFC上流通。传统网络环境实验拓扑如图4所示。

图3 SFC实验拓扑

3.1 动态部署测试

传统网络由于数据层平面与链路层平面的深度耦合，其网络拓扑一经搭建，不易动态调整[17]，无法捕获网络演化趋势[18]，也无法智能编排。服务功能链由于其高效、可编排等优点，可实现快速自动部署[14]；寻找网络节点间联系，适应网络实时变化，生成更精确的网络表示[18]。下面通过对SFC进行动态部署服务功能（SFs），将本文算法与JoraNFV算法、传统网络算法面对此类情况下引起故障做对比。如图5所示，PC机在访问百度的服务器时，通过追踪PC机所在的服务功能上动态添加网元设备，对比3种算法的每分钟内千条请求通过节点所耗时间可知：随着动态添加节点设备数量的增加，三层模式下的传统算法无法在短时间内处理转发数据包；JoraNFV随着添加节点数量的增加，其对添加节点的新路径转发数据报的能力下降；基于单纯形法的路径规划算法相比JoraNFV而言，其对动态部署节点设备更加友好，能大量添加网元设备，耗时0.5s内。

图5 动态部署测试

3.2 路径故障处理测试

为了展示基于单纯形法的路径规划算法处理路径故障的能力，我们对服务功能进行下线或断电。使用ping、tracert等请求命令来探索网络流量途径下线的服务功能设备（导致链路故障）时数据报文是否可达以及显示处理网络不可达节点时使用时间，本算法与JoraNFV、传统网络算法进行比较，其结果如图6所示：随着故障路径数量的增加，三种处理故障方法所消耗的间也随之增加。传统网络链路，一旦遇到链路上的网元设备下线，途径网络的数据流将陷入不可达状态；无法智能处理，需要手工重启网元设备并配置命令，时间成本较高，与此同时，随着路径故障数量增多，其消耗时间大幅上升；JoraNFV方法在处理路径故障时其消耗时间上升率较稳定；单纯形法的路径规划算法面对大量路径故障时由于其流量调度子算法为其节约时间，在面对大量路径故障时其消耗时间降（40秒内），较JoraNFV有优势。

图6 路径故障处理时间

传统网络链路路径故障处理与JoraNFV、单纯形法算法的路径故障处理的最优率对比如图7所示。

图7 故障处理的最优率对比图

3.3 链路cost测试

接下来，我们将重点讨论SFC的SFs上链路（上、下行）的cost实验。如图8所示，我们绘制了部署SFs的数量以及标注了链路Edge的cost。SF1、SF2上部署了实例Router3、Router4、Router5，SF1有50单元流量，SF2有40单元流量，这些流量需要被调度到3个实例中，由于每条链路的传输延迟和转发时间都不同，从而产生了链路cost（公式5）。传统链路算法、JoraNFV和单纯形法算法对不同请求的转发执行机制是一致的；链路的cost在遇到请求量较大的通信数据流，在链路上部署更多网元设备时会话质量会下降。

图8 SFs和链路cost

基于图8实验环境，图9中请求的流量数据量设置为5、10、15、20个单位，分别表示为T5、T10、T15、T20。图9（a）描述在不同请求流量部署实例（WAF、FireWall、IPS、Qos等）的数量，图9（b）表示不同请求流量的链接成本。考虑到链接成本和部署实例，不同的请求流量在3种算法在上执行方法上是相同的。它表明，随着Traffic请求量增大、部署的实例增多时，传统网络链路方法的性价比会变得更差，这会导致网络资源的分散；单纯形法的路径算法与JoraNFV算法也存在差异，当请求流量达到T5时，基于JoraNFV的算法性能高于单纯形法算法；但请求量超过T5时，单纯形法算法其在相同请求流量时的实例部署随着请求流的增加而成本趋于最低且能够部署的实例最多，综合性能高于JoraNFV。

图9 (a) 在不同请求流量上部署实例

图9 (b) 在不同请求流量上的链路cost

3.4 算法评估

为了评估3种算法面对故障的处理准确率，其具体计算公式为：

式中，Nnode表示节点的数量；Na表示节点的可达数量；p表示算法的精确度；cost表示网络链路的开销。对比的结果如表1所示，由表1实验结果可知，在同类型的流量请求等数量节点中在面对网络不可达时，传统网络链路算法的可达节点数量伴随着请求类型过节点数量的增加而其节点的可达性大幅降低，算法的准确率中等；JoraNFV算法在服务功能数量增幅时，其节点的可达性、算法的准确率较稳定；基于单纯形法的路径规划算法在面对不同类型请求跳跃节点时，通过故障路径的流量调度保持了节点可达性和算法高精确率。

表1 算法精准度对比

4 结束语

本文提出的基于单纯形法的路径规划算法，解决了SDN服务功能链SFC在三层模式下，服务功能的动态部署、割接、下线引发网络不通畅问题。在本文算法中，在SFC启动时，SDN交换机转发服务功能的ARP请求报文，OpenFlow控制器学习SF的真实MAC并生成伪MAC，下发给SF[19]；本文算法通过将流量牵引到伪MAC，为SFC的路径替换争取时间，并保障更改时间段内网络通畅。最后，与JoraNFV、传统网络链路算法进行对比实验。结果表明，单纯形法算法能够有效地解决SFC由动态添加节点、三层网元跌宕、节点下线及断电产生的路径故障，进一步提高了SFC的安全性、集成性、灵活性。从性价比方面讲，单纯形法算法相比Bypass等硬件设备，能够节约网络建设、改造的成本；相比JoraNFV、传统网络算法，其可扩展性强、处理速度快、稳定性强。因而，接下来的研究是进一步深入探索出SDN的转发图嵌入（SDN Forwarding Graph Embedding），并进一步提高算法的准确性和智能性。