基于覆盖网络的灾后恢复策略研究综述

吴之沫，马琳茹

（中国人民解放军军事科学院 系统工程研究院，北京 100039）

0 引言

人们的日常生活离不开网络提供的各种服务，各行各业对网络性能的要求越来越严格，网络规模和复杂度呈爆炸性增长趋势。然而，当前的网络基础设施面临着各种各样的潜在威胁，除了网络部件自然老化而导致的失效问题，还随时可能遭遇地震、洪水、飓风等自然灾害，以及恐怖袭击、军事战争等人为灾难性事件。即使发生故障的是一个或几个网络部件，其周围区域也会由于受到网络信息流量过载的影响而发生拥塞，引发连锁效应，最终导致相当一部分节点甚至整个网络崩溃。因此，及时对网络故障进行修复至关重要。

为解决现有TCP/IP 体系架构服务质量提升缓慢、路由故障恢复效率低下以及可扩展性差等问题，科学家们提出使用覆盖网络对现有网络进行系统性、广泛性、整体性改造。覆盖网络是一种整合式互联网改进方案，相较于打补丁式的改良式方案与从零开始的革命式方案，其是一种介于二者之间的折中方案［1］，既不会明显增加网络复杂性，也无需抛弃现有网络体系，只需在现有网络结构的IP 层之上、应用层之下增加一个中间层，采用覆盖网络改善当前互联网即可。这种对互联网体系架构的系统性修补可以在保留现有互联网架构的前提下提供更可靠的服务，为下一代互联网设计提供了一种可行性方案。

基于虚拟化传输的特性，覆盖网络部署时间短、可拓展性强，在灾后恢复方面的应用研究呈上升趋势，目前已被广泛应用于公路交通网络［2］、光网络［3］、相互依存网络［4］、水下无线传感器网络［5］等各个领域。然而，覆盖网络在灾后恢复中的应用研究尚不成体系，或仅聚焦于单纯的故障定位［6］、故障检测［7］，或侧重于相互依存网络［4］的灾后响应。为此，本文对覆盖网络应用于信息网络灾后恢复方面的相关文献进行整理与总结，从故障建模和受损网络连接恢复两个方面入手，综述覆盖网络灾后恢复方法，为相关研究者提供参考。

1 覆盖网络容灾性研究基础

1.1 覆盖网络发展历程

覆盖网络本质上是一种面向服务的逻辑网络［8］，其节点由连接在互联网上的部分终端节点或应用类服务器组成，每条网络链路对应一条或多条物理链路。如图1 所示，覆盖网络将二层报文封装在IP 报文之上，利用成熟的IP 路由协议进行数据分发，构建了一层逻辑拓扑。其网络拓扑由服务提供商们根据用户需求定义，可以在不改变互联网基础设施的前提下提供更可靠、容错性更好的服务，弥补了传统网络路由的缺陷，提高了互联网的可扩展性和鲁棒性。

Fig.1 Impact of overlay network technology on the Internet hierarchy architecture图1 覆盖网络技术对互联网层次架构的影响

早在1974 年，英国学者Duerdoth［9］就提出了覆盖网络的概念，不过这个概念最初是应用于电信技术上。在那个模拟技术与数字技术并存的时期，使用覆盖网络作为主干网络可以在保留原有电话服务的基础上引入数字技术，同时避免高昂的经济成本。随着信息技术的发展，光纤技术开始走进大众视野。1986 年，德国学者提出宽带通信服务覆盖网络［10］，德国邮政公司将覆盖网络技术视为发展高效集成通用网络的战略［11］。自此，覆盖网络正式被视为承旧启新的框架技术，继电报网、电话网、综合业务数字网之后走进了人们的视线。21 世纪初，覆盖网络被应用于可靠多播技术［12］，充分利用底层网络拓扑，通过覆盖树协议构造了可靠分发树，为用户提供故障容忍的密集带宽。此后，覆盖网络普遍应用于网络组播技术。

近年来，覆盖网络技术得到了深入研究和广泛应用，如以去中心化为特点的对等网络（Peer to Peer，P2P）常用于文件共享［13-14］、即时通信［15］、协同处理［16］和流媒体通信［17］领域；内容分发网（Content Delivery Network，CDN）用于视频分发，采用重定向机制缩短了分发服务器与用户的距离［18］，不仅可以提高访问速度，还能缓解网络拥塞；应用层多播机制通过建立路由器间的多播分发树管理成员和分发数据［19］。此外，覆盖网络还常用于增强服务质量（Quality of Service，QoS）［20］、云计算数据中心网［21］、软件定义网络（Software Defined Network，SDN）［22］等技术领域。

覆盖网络受到大众青睐的主要原因是其可以在不改变底层网络的前提下提供组播、QoS 增强等服务，对下层网络故障透明，结构多样化且具有较低的部署成本和部署难度。这些优点有效缓解了传统IP 网络的僵化问题，精简和优化了网络整体结构。同时，超节点的存在使复杂的网络链路变得简单灵活，具有很好的鲁棒性［23］。

1.2 网络容灾性的含义

伴随科学技术日新月异的发展，通信网络面临的潜在威胁也越来越极端，一个完备的通信网络体系必须具备一定的容灾能力。从数学层面来说，网络容灾性可被描述为一个网络被彻底破坏所需要除掉的节点数占总节点数的比例，在现实世界中则表现为当局部网络遭到破坏或网络服务大规模损毁时，网络仍然可以保持关键服务正常运行的能力。具有较高容灾性的网络能够更好地预防和抵御攻击，并在受到攻击后快速恢复。

如图2 所示，围绕提高容灾性这一目标，覆盖网络研究工作可以分为两个方面：一是灾难损毁模型建立。合适的损毁模型可以精确描述网络受损情况，分为确定性损毁模型和概率故障模型两种；二是受损网络的连接恢复。可采用主动式保护、被动式恢复以及主被动结合恢复3 种策略，其中主动式保护策略通过提供备份节点或链路，使覆盖网络可以迅速切换受损节点或链路，防止由于部分节点或链路失效而造成的大面积瘫痪；被动式恢复策略是指在灾难发生后，即使网络遭受到外力破坏导致拓扑结构发生变化或重组，仍然可以通过重路由等方式使系统恢复正常运作，完成预期主要目标，强调的是网络的恢复能力。

Fig.2 Classification of overlay network research work图2 覆盖网络研究工作分类

2 灾难损毁故障建模

网络灾后恢复的前提是定位网络发生损毁的位置，及时精确地监控网络故障，这就需要对灾难损毁故障进行建模。灾难损毁模型可以直观展示灾害对网络的影响，包括受损位置、损毁范围、瘫痪程度等。然而，由于灾难类型多样，研究人员很难为每一种自然灾害和人为损坏建立合适的模型，现有研究多为利用几何知识建立理论模型，主要分为确定性损毁模型和概率故障模型两种。

2.1 确定性损毁模型

确定性损毁模型的关键在于找到受灾区域，关注的是故障的地理位置，一旦计算出受灾区域，便假设这个区域中所有的网络设备全部被损毁，即故障概率为1。2010年，Neumayer 等［24］首次将计算几何的理论工具应用于网络容灾性研究中，提出一个简化的二部图模型。该模型使用线段表示飓风等造成的线性灾害，圆形表示地震等造成的区域性灾害，利用多项式时间算法在平面图模型中识别最坏线切割和最坏圆切割，这是网络最脆弱的部分，任何在地理位置上与该灾害区域相交的网络组件均无法正常工作；Stojan 等［25］降低了Neumayer 等研究的复杂性，在其基础上开发了一种多项式时间算法，采用椭圆形和多边形表示网络失效的脆弱区域；Tapolcai 等［26］受到二部图模型的启发，提出固定半径的圆盘破坏模型，以故障点为圆心，认为一定半径内的所有网络部件均受到了灾难影响。考虑到大多数灾难可能并不是均匀分布的，Gour 等［27］在固定半径的圆盘失效模型中引入边和路径脆弱区的概念，使其适用于失效事件非均匀分布的灾难区域。该模型使用圆盘表示灾难损毁区域，简单直观，极大降低了处理区域性损毁的复杂度，在灾后恢复工作中得到广泛使用。然而，圆盘形灾难模型仅适用于区域性灾害，如地震、大规模杀伤性武器导致的灾难，而对于飓风、海啸、山体滑坡、自然火灾等，圆盘模型并不能精确描述。

在实际场景中，受灾区域往往不是呈现出圆盘形、四边形、线形等规则形状。为精确描述灾难造成的不规则伤害，Agrawal 等［28］针对地震造成的损毁，结合震中位置、震中密度、地震震级和网络拓扑等要素提出地震风险骨干网络模型，将地理区域细分为多个任意形状的地震带，表示不同级别的地震风险；同时还提出地震风险最小化节点迁移方案，使得模型在网络动态变化时也能准确描述受损区域与受损程度。然而，这些关于灾难建模的研究均默认网络在一个平面上，而地球是类球形的，这种计算方式难免有些失真。对于一些小规模的损毁，这种失真是微不足道的，而对于一个幅员辽阔的国家、大陆甚至大洲，这种映射的误差将会超过5%。为此，Vass 等［29］通过改进多项式共享风险链路组（Shared Risk Link Groups，SRLG）生成技术，使模型适应球面几何，生成更精确的SRLG 列表，同时还引入图密度参数，使模型同样适用于不规则受灾区域。

2.2 概率故障模型

确定性损毁模型虽然直观，但过于简化，难以表达真实损毁场景的一些重要特征。事实上，某区域即使发生了灾害，其网络组件也未必全部损毁，只是大大增加了发生故障的概率。网络损毁的概率与链路长度、节点密度、灾害强弱和灾害区域大小均有关系，可采用概率损毁模型进行预测。例如，Vass等［30］假设在灾害发生后区域网络平面中会产生一个明显的故障概率分布，并依据该假设构造了链路失效的联合概率分布，提出通用概率区域损毁模型，其中链路的累积失效概率取决于链路长度以及链路与灾害的地理邻近性。针对虚拟网络的生存性，Oliveira 等［31］提出高度时空相关的多链路故障灾难模型。由于网络功能虚拟化（Virtual Network Feature，VNF）基础设施具有极高的复用度，VNF 网络中的节点和链路故障具有高度相关性，如果在前一组故障修复前发生了更多灾害，可能会导致多组相关链路发生故障。该文献还创造性地采用基于网格分区的方案估计随机区域故障下的各种网络统计指标，网格划分不仅有助于识别网络的脆弱区域，还可以依据网格对故障发起适当保护。

表1 对以上灾难损毁故障建模方案的基本信息进行了总结，其中适用网络为静态网络的方案只能在灾难发生后进行一次建模，而动态网络则可以根据受灾区域的变化进行适应性建模。

Table 1 Disaster damage modeling schemes表1 灾难损毁建模方案

3 受损网络连接恢复

3.1 主动式连接保护策略

建立灾难损毁故障模型的目的是为了更加及时有效地恢复受损链接。当前应用最为广泛的网络连接恢复策略为主动式连接保护策略，主要应用于发生单链路故障或多条独立链路故障的场景，即当网络遭受不严重的破坏，只有个别节点或链路发生故障之时。研究指出，网络中70%的故障都是单链路故障［32］。在大多数情况下，任意网络节点对之间传输数据都只选择路径最优的那一条，如果这条最优路径上的任何一条链路发生了故障，那么该节点对之间的通信便会中断。主动式连接保护策略即在灾难发生前为这对节点设置一条或多条备用路径，当使用最优路径无法进行通信时，源节点快速将流量转入次优路径，使得通信业务得到恢复并实现正常传输。

根据备份原理，主动式连接保护策略又可分为节点备份方案和链路备份方案。在节点备份方案方面，Zhi 等［33］以节点度作为评价指标，采用对等覆盖网络拓扑自动恢复算法为关键节点的每一条边选取一个度较小的点作为备用节点，同时在节点接收数据包时执行路径压缩算法，以确保网络拓扑的正确性和连通性，提高网络传输效率；朱国晖等［34］将建立覆盖网络的成本与收益纳入考量，综合考虑节点资源度、接受中心度、网络收益开销比、链路重要程度等因素建立覆盖网络，只有新生成的链路所需资源之和小于物理网络剩余资源时才将链路端点纳入备用节点候选集；郝党科等［35］将大数据技术引入节点筛选算法，将研究场景设定在高速公路网络上，利用工程参数表和大数据用户识别技术筛选出核心节点，并由此建立关系库；然后应用黄金分割搜索算法得出最优备份节点，最终实现了站点故障后网络的自修复，确保了故障区域的网络覆盖与业务质量。

在面向业务的覆盖网络中可优先选择最佳链路恢复故障。例如，Li等［36］将保护能力感知技术与面向故障避免技术相结合以提高虚拟网络的可靠性。其假设每条链路都对应一个失效概率，由此选出需要重点保护的主链路，并使用基于马尔可夫的线性规划为每条主链路计算备份路径。为减少预备份所需资源，耿海军等［37］提出可在每个路由节点转发表中保存和维护最优下一跳和次优下一跳，当目标节点的最优路径发生故障时便自动切换至次优下一跳，如此以来大大减小了算法的存储空间；Hirano 等［38］和Khouangvichit 等［39］认为传统稳健优化方案高估了备份链路的容量，分别将备份链路设计问题描述为具有鲁棒优化和稳健优化的混合整数线性规划（Mixed Integer Linear Programming，MILP）问题，以最小化备份资源为目标寻找最优备份链路；Wang 等［40］以提高备份资源利用率为思路，提出一种基于环的单链路故障恢复方法，根据节点重要性与链路性能选择核心节点并将其连接成共享环，使所有备份路径共享该路径，即每个备份路径都包含共享环的一部分。共享环生成后，根据故障链路的位置处理故障，若故障链路不属于共享环，就先将受故障影响的数据包重定向至环节点，然后沿环传输；若故障链路属于共享环，受故障影响的数据包将沿环以相反方向传输。该方法提高了备份的可重用性，降低了备份路由数；同时为了保证备份路由性能，该方法还会根据预测负载定期更新环路。

主动式连接保护策略可以非常高效地恢复网络连接，这是由于所有路径的计算工作是预先完成的，故障发生后只需要进行简单的路径切换。然而，为不同故障场景建立不同备份路径需要较高的部署成本，而且当发生地震、洪水等大规模区域损毁时，主动式连接保护策略提供的多条备份路径极有可能同时失效。表2 列出了上述主动连接保护策略的优点、局限性等基本信息。

3.2 被动式重新寻路策略

被动式重新寻路策略无需提前预留资源，只需要在故障发生后根据当前网络的实时路由状态及资源剩余情况计算重路由方案，基于设定的反应机制应对灾难损毁。目前关于该策略的研究主要集中在最短路径计算、故障信息传播等方面，且多数研究是依靠覆盖网络的虚拟性灵活绕开发生故障的网络部件，以保持信息的正常传输。例如，张艳梅［41］通过限制网络拓扑单位时间内需要维护的消息数量，在给定维护代价的基础上使用自适应搜索的免疫克隆算法求解路由性能最好、物理链路重用度最小的备选链路，将网络灾后恢复工作转化为多目标约束优化问题。从单个角度来看，该方法找到的备选链路可能并不是最优的，但当同时考虑维护代价、路由性能和物理链路负载等多个子目标时，其是最优方案。然而与大多数主动式连接保护策略相同，这种选择节点或链路的方法难以应对大规模灾难损毁。Zad 等［42］提出一种针对大规模区域损毁场景的网络恢复方法，称为迭代随机恢复算法（Iterative Stochastic Recovery，ISR）。该算法将修复成本建模为网络中每个要素的失效概率函数，该成本与节点所在位置有关，旨在恢复连接的同时最小化期望恢复成本。该算法无需使用故障概率先验知识，解决了在不了解受损节点确切位置时的网络恢复问题，但没有考虑到灾难损毁后恢复资源受限的情况。

考虑到发生故障时覆盖网络路由与底层网络均会发出报警信号，且会采取各自独立的重路由机制恢复故障，如果不对二者路由策略的冲突问题加以协调控制，将会产生恢复冲突和网络资源浪费现象。为此，Srinivasan 等［43］提出3 种双重路由协调恢复机制：①为覆盖网络的故障恢复设置概率门限；②为网络故障恢复设置计时器，等待IP层先进行重路由；③为覆盖网络与IP 层检测到的故障时间间隔设置门限。然而以上3 种方式均会增加故障恢复时间，且需要确定是哪一层发生了故障。为降低选路代价，武照东［44］提出基于不同自治域的双重路由协调机制，按照自治域对故障进行分类，自治域之内的覆盖网络节点可以采用内部网关协议（如OSPF 路由协议、RIP 协议）选择路由，而自治域之间需要采用外部网关协议（如BGP 协议）使得自治域互联。在OSPF 协议中的Hello 包中加入自治系统（Autonomous System，AS）号，若接收节点的AS 号与源节点相同，则为自治域内故障，可使用IP 网络的重路由机制恢复；若AS 号不同，则采用覆盖网络的重路由机制恢复，如此以来可以降低网络抖动次数，减少恢复时的竞争冲突，实现路由的最优恢复。

3.3 主被动结合的灾后恢复策略

主动式保护策略降低了受损网络恢复时间，但需要大量备份资源；被动式恢复策略更加灵活，但所需恢复时间较长。从网络全生命周期的视角考虑，将主动式连接保护策略与被动式重新寻路策略紧密结合起来可对网络拓扑进行更全面的保护，极大提高其对灾难的抵御能力。

覆盖网络中最常见的主被动结合灾后恢复策略均在弹性覆盖网络（Resilience Overlay Network，RON）的基础上进行［45］。作为一种应用层路由技术，RON 节点采用主动与被动相结合的方式监测内部路由的服务质量，并依据这些信息选择下一跳覆盖节点。在生成弹性路由层时需要首先隔离部分链路，然后检查链路的连通性并由此生成路由层。理论上来说，当生成的弹性层足够多、隔离的链路组合足够丰富时便可以恢复所有类型的多链路故障。例如，Andersen 等［46］证实了RON 的故障诊断和恢复能力明显优于普通路由，能有效降低数据传输丢失率和延迟；Iloglu 等［47］对受损后的道路基础设施网络进行数学建模，分别使用基于拉格朗日的求解过程和基于线性松弛的整数规划过程两种启发式算法证明了多重覆盖的可行性。然而，由于要想获得好的恢复效果就必须生成足够多的路由层，导致开销巨大，传统的RON 网络难以大规模部署，可拓展性较差。此外，RON 的路由表只能覆盖RON 节点，对于RON 以外的目的地则无能为力。为此，赵珩等［48］提出基于网络分块的主被动相结合的网络恢复策略，利用Kmeans 算法将网络分块，选取集合中心的节点作为集合中间节点，度最大的节点作为系统覆盖节点，如此以来网络流量在传输中便可以借助源路由及时跳过故障区域，通信网络的可靠性明显提升。此外，考虑到灾后故障区域极容易发生网络信息拥堵现象，该策略还加入拥塞感知恢复系统，以便实现跳级处理，同时客户端模块与覆盖节点模块可保障系统中节点不会发生环路传输情况；Zhang 等［49］提出一种用较少备份资源实现故障恢复的方法，根据链路复用度和带宽利用率两个指标确定链路对故障的影响程度，将其分为3 个具有不同优先级的集合，对于具有更低延迟和更高传输质量要求的链路，使用双路径恢复策略进行恢复，即为其记录两条备份路径；对于复用度低或对延迟与数据包丢失没有较高需求的链路采用反应式恢复策略，该策略的备份路径是动态分配的，但不会在故障发生之前分配恢复路径所需资源，故障发生后需要额外的信令建立备份路径；对于优先级居中的链路采用单路径恢复策略，只需预先配置一条备份路径用于恢复链路故障，从而满足故障切换所需延迟，如果该策略失败再触发反应式恢复策略。以上方法可以在满足链路故障所需恢复延迟的同时降低对预备份资源的需求。

3.4 小结

主动式连接保护策略通过预先规划为重要链路预留出冗余资源，在遭遇故障时及时建立保护连接，保证网络的正常运行。这种方法可以在较短时间内恢复故障，预留资源不能被其他业务共享，会造成网络资源利用率降低，且灵活性相对较差，若发生大规模灾害导致冗余链路同时损毁，该策略便会失效。被动式重新寻路策略可在故障场景中动态地为业务计算路由分配资源，从而恢复通信并提高网络的生存性。这种方法的关键在于根据故障发生时刻的网络现状以及闲置资源重新规划路由，从而实现对故障路由的替代，无需预留冗余资源，大大提高了资源利用率。然而，重新进行路由规划需要花费较多时间，因此对故障的恢复速度不及主动式连接保护策略。为提高网络生存性，目前常在使用主动式连接保护策略的同时通过被动式重新寻路策略对网络业务进行保护。

4 结语

与通用的故障处理思路相同，覆盖网络的灾后恢复策略同样是先定位、再恢复，相关研究主要聚焦于灾难损毁模型建立和受损网络连接恢复两方面。当前对于覆盖网络在灾后恢复方面的应用研究仍处于探索阶段，虽然恢复个别节点或链路故障的方案较为成熟，但面对地震、飓风等自然灾害导致的大规模网络瘫痪，恢复方案仍存在局限性。在未来研究中应充分考虑灾难发生的随机性和不确定性，以降低冗余资源需求、缩短故障恢复时间和提高恢复率为目标进一步优化覆盖网络的灾后恢复策略。