1、2023 03 10计算机应用,Journal of Computer Applications2023,43(3):853-859ISSN 10019081CODEN JYIIDUhttp：/面向软件定义车联网的链路故障快速恢复方法顾源1*，张震2，段通2（1.战略支援部队信息工程大学 信息技术研究所，郑州 450002；2.国家数字交换系统工程技术研究中心，郑州 450002）（通信作者电子邮箱 ）摘要：针对软件定义车联网（SDIV）的车-路实时查询类通信场景中单链路故障的问题，提出一种面向SDIV的链路故障快速恢复方法，综合考虑了链路恢复过程时延和恢复后路径的传输时延。首先，对故障恢复时
2、延建模，将最小化时延的优化目标转化为0-1整数线性规划问题。然后，分析该问题，力图最大化复用已有计算结果，并根据不同情况提出两种算法：在流表更新时延相对路径传输延迟不可被忽略的情况下，提出基于拓扑划分的路径恢复算法（PRA-TP）；在流表更新时延相对路径传输延迟较小可被忽略的情况下，提出基于单链路搜索的路径恢复算法（PRA-SLS）。实验结果表明，相较于 Dijkstra 算法，PRA-TP 的计算时延和路径恢复时延分别降低 25%和 40%，PRA-SLS的计算时延降低60%，可实现快速的汽车端的信息传输单链路故障恢复。关键词：软件定义车联网；车路协同；单链路故障；故障恢复时延；路径恢复中图
3、分类号：TP393.01；文献标志码：AFast link failure recovery method for software-defined internet of vehiclesGU Yuan1*，ZHANG Zhen2，DUAN Tong2（1.Information Technology Research Institute，Information Engineering University，Zhengzhou Henan 450002，China；2.National Digital Switching System Engineering and Technologica
4、l Research Center，Zhengzhou Henan 450002，China）Abstract:Aiming at the single link failure problem in the vehicle-road real-time query communication scenario of Software-Defined Internet of Vehicles（SDIV），a fast link failure recovery method for SDIV was proposed，which considered link recovery delay a
5、nd path transmission delay after link recovery.Firstly，the failure recovery delay was modeled，and the optimization goal of minimizing the delay was transformed into a 0-1 integer linear programming problem.Then，this problem was analyzed，two algorithms were proposed according to different situations，
6、which tried to maximize the reuse of the existing calculation results.In specific，Path Recovery Algorithm based on Topology Partition（PRA-TP）was proposed when the flow table update delay was not able to be ignored compared with the path transmission delay，and Path Recovery Algorithm based on Single
7、Link Search（PRA-SLS）was proposed when the flow table update delay was negligible because being farless than the path transmission delay.Experimental results show that compared with Dijkstra algorithm，PRA-TP can reduce the algorithm calculation delay by 25%and the path recovery delay by 40%，and PRA-S
8、LS can reduce the algorithm calculation delay by 60%，realizing fast single link failure recovery at vehicle end.Key words:Software-Defined Internet of Vehicles（SDIV）;vehicle-road cooperation;single link failure;failure recovery delay;path recovery0 引言 车联网（Internet of Vehicles，IoV）是智能交通系统的重要组成部分，通过车联
9、网与路侧基础设施进行信息交换，可为车辆提供辅助驾驶、异常提醒、躲避拥堵等多种服务信息；但紧耦合的网络设备操作方式以及对可扩展性、灵活性、可靠性需求的增长导致传统车联网难以满足未来网络的发展需求1。软件定义网络（Software Defined Network，SDN）作为一种新型网络结构，通过三层架构实现了控制平面与数据平面的分离2，并由控制平面的控制器实现网络控制3，满足了车辆的连通性和通信需求4，同时具有加入蜂窝网络和车联网的潜力5。软件定义车联网（Software-Defined Internet of Vehicles，SDIV）架构6支持车联网开放统一的接口，数据层与控制层的分开和逻
10、辑上的集中控制使SDIV架构具有很高的可扩展性和网络可管理性，如图1所示。图 2中的车路协同通信是车联网中一种典型的实时查询类通信场景，在这种场景下车联网需与路侧基础设施进行V2I（Vehicle to Infrastructure）通信，从路侧的信息服务器（Information Server，IS）中获取实时道路导航、充电设施位置、交通拥堵等信息。路侧单元（RoadSide Unit，RSU）通过无线信道与车联网相连，同时通过路由器与IS相连，从而将车联网所请求的数据信息从IS发送至车联网。在SDIV架构中，RSU 和 IS 之间的路由器均为 SDN 交换机，而从 IS 到 RSU 之间的
11、数据流量传输路径也被SDN控制器所控制，因此具有较高的灵活性。然而，当 RSU 与 IS 之间的通信系统发生链路文章编号：1001-9081（2023）03-0853-07DOI：10.11772/j.issn.1001-9081.2022010058收稿日期：20220117；修回日期：20220427；录用日期：20220428。基金项目：国家自然科学基金资助项目（61872382）。作者简介：顾源（1993），女，黑龙江佳木斯人，硕士研究生，主要研究方向：车联网安全；张震（1985），男，山东济宁人，副研究员，博士，主要研究方向：网络测量、网络管理、车联网安全；段通（1992），男，河南
12、驻马店人，助理研究员，博士，主要研究方向：车联网体系架构。第 43 卷计算机应用故障时，SDN控制器需要根据实时网络状态更新交换机的流表规则，以快速恢复传输。同时，此类场景中车辆的快速移动特性以及所连RSU潜在的切换特性需要快速的故障恢复能力，以保持车联网的服务质量，最终满足用户需求。对于链路故障恢复问题，文献 7-10 中提前安装了备份路径的转发规则。当链路出现故障时，数据平面交换机自动激活备份路径，在提前配置备份路径的转发规则方案中，不涉及SDN控制器，因此能够快速地从链路故障中恢复。但工作路径和备份路径相关，每次改变工作路径时，都需要重新分配备份路径，因此容易导致交换机和链路带宽资源耗尽
13、，并不适用于车联网场景中复杂且动态变化的网络环境。文献 11 中提出了一种基于最短路径优先算法的响应式链路故障恢复方法。该方法将每条路径上的报文分为高优先级和低优先级，保证了高优先级数据包的最小延迟，还通过在可用路径上平均分配流量以避免拥塞。因此，随着网络规模的扩大，该方法的复杂度也随之增加。该方法的另一个缺点是为实现机制提供的信息不足；此外，还没有在标准的互联网拓扑数据集上进行测试。文献 12 中表示忽略流表处理时间的基于最短路径恢复可能无法快速恢复流表时延。根据文献 13-14 的研究，SDN 交换机中插入一条流表的延迟为 0.510 ms。文献 15-16 中关注了恢复过程中的流表处理时
14、间，考虑了异构网络中节点具有不同规格的路径交换延迟问题，并基于处理时间最短的交换机选择备选路径。文献 17 中提出一种考虑恢复过程中的交换机流表处理时间和网络带宽的方法。文献 18 中提出基于社区检测的方法和基于路径解剖的方法。文献 19 中在替代路径选择时，鼓励选择具有更好的链路质量和最小的关键交换机数量的路径。文献 15-19 考虑了流表更新时延，但没有综合考虑路径开销和流表更新权衡问题，其中文献 15-17 从降低每个交换机处理时间的角度，降低恢复时延；文献 18-19从减少路径恢复过程中流表更新数量的角度，降低恢复时延。文献 20 中考虑了路径开销和流表更新权衡问题，并在一定条件下找到
15、最优解和次优解，但没有将路径开销和流表更新次数统一为时间标准后进行权衡，并且只能在系数特定的情况下求解。基于以上研究现状，为解决软件定义车联网实时查询类通信场景中的单链路障恢复问题，本文引入恢复过程时延和恢复之后路径传输时延作为链路参数，并设计相应的路径恢复方案。本文的主要工作有：1）对故障恢复时延建模，综合考虑恢复过程时延和恢复之后路径开销这两个关键性能指标：2）在流表更新时延可以忽略和流表更新时延不可忽略的情况下，分别提出两种路径恢复算法，理论分析和实验结果表明，本文算法具有较小的计算时延和故障恢复时延。1 问题描述与模型构建 1.1问题描述SDIV架构下链路故障恢复机制的优劣主要由以下性
16、能指标评估：1）恢复过程的时延开销trecovery，由故障发现时延tdiscovery、openflow消息通道时延topenflow（包括packet-in消息上传及 packet-out消息的下发等）、路径计算时延tcompute和流表更新时延tupdate构成。其中：tdiscovery和topenflow由通信系统本身的性能决定，无法优化；tupdate则由旧路径切换到新路径所需要的流表规则增删操作次数决定。2）恢复之后的路径传输时延tnewpath，一般由路径的端到端时延所定义，以实现最小的新路径传输时延。因此在求解链路故障恢复问题时，tcompute、tupdate、tnewpath可以优化，且tupdate和tnewpath可以参数化。本文首先将tupdate和tnewpath参数化，并统一到链路故障恢复的优化目标中；其次，在求解优化问题的过程中，在最小化tupdate和tnewpath的同时考虑tcompute，寻找统筹上述关键性能指标的最优解。1.2模型构建网络拓扑结构表示为G=()V，E，其中：V=vi表示拓扑中的节点集合，vs为路径上的源节点，vt为路径上的目的