故障转移是自动化运维中重要的组成部分，有效的自动化故障转移可以保证服务的连续性，无故障运行。

论文摘要：

为了提供高弹性并快速响应链接故障，现代计算机网络支持完全分散的流重新路由，也称为本地快速故障转移。简而言之，本地快速故障转移算法的任务是仅使用本地可用信息为每个节点预定义快速故障转移规则。这些规则为数据包可能到达的每个传入链路以及本地链路故障集（即，发生故障的链路入射到节点）确定了数据包应在哪个出站链路上转发。理想情况下，这种本地快速故障转移算法可确定性地提供完美的弹性：只要基础网络保持连接，从任何源发出的数据包都可以到达任何目标。Feigenbaum等。展示了并非总是能够提供完美的弹性，并展示了如何容忍任何网络中的单个故障。有趣的是，关于完美弹性的可行性目前知之甚少。

本文在一个模型中可以使用源也可以不使用源快速转发决策的模型中，重新审视了本地快速故障转移的完美弹性。我们首先得出几个相当普遍的不可能结果：通过在图形次要图和弹性之间建立联系，我们证明不可能在任何非平面图上实现完美的弹性；此外，尽管平面度是必需的，但对于完美的弹性来说也是不够的。

从积极的方面来看，我们显示了在链接细分下闭合的图形族可以使用简单有效的故障转移算法，该算法仅跳过失败的链接。我们通过为外部平面图和相关方案以及故障后源和目标在拓扑上接近的方案得出完美的弹性来演示此技术。

介绍

分布式系统的可靠性通常取决于由一组路由器实现的底层网络。为了提供高可用性，现代路由器支持流量的本地快速重路由：路由器可以预先配置有条件的故障转移规则，这些规则为每个传入端口和所需目标定义，到达该传入端口的数据包应转发到哪个端口，仅取决于事件链路的状态：由于路由器需要快速反应，因此它们没有时间了解远程故障。

本文的出发点是本地快速重路由机制引入的以下基本问题：是否可以预先定义确定性的本地故障转移规则，以保证只要底层网络连接，数据包就可以到达其目标？这种理想的特性被称为完美弹性。因此，提供完美弹性的挑战在于问题的分散性，以及路由器仅具有关于失败链路的本地信息；利用全局知识实现完美弹性是简单的，因为可以简单地计算最短路径。

不幸的是，总的来说，完全的弹性是无法实现的：Feigenbaum等人。[19,20]给出了一个有12个节点的示例，在某些故障之后，原始网络上没有转发模式允许目标连接组件中的每个幸存节点到达目标。从积极的方面来说，作者表明，至少可以容忍一个链路故障，即1-弹性。有趣的是，现在对于什么时候可以实现完美的弹性，什么时候不可以，知之甚少。

本文研究了在节点只具有局部信息的网络中，同时考虑到节点能够和不能匹配包源的模型，提供完美弹性的问题。在消极方面，我们描述了不允许完全弹性解决方案的网络实例。从这一特性可以看出，在简单和小平面图上，即使在源在故障后仍然通过Ω（n）不相交路径与目标高度连接的情况下，也不可能实现完全恢复；但是，它无法路由到目标。我们还得到了一个相当一般的否定结果，即完全弹性在任何非平面图上都是不可能的，并且完全图K5和完全二部图K 3,3都不允许有完全弹性解。为此，我们证明了图的子图与完全弹性之间的一种有趣的联系，并证明了每一个图的子图都保留了完全弹性的性质。

从积极的方面来说，我们描述了所有外平面图和相关场景（例如，失败后源和目标位于同一个面上的场景）以及目标位于源的两个跳内的非外平面场景的完全弹性算法。对于我们的积极结果，我们建立了一个普遍的观点，即在细分链接下闭合的图族，允许简单的故障转移算法，其中节点可以跳过本地故障端口，需要非常小的转发表。

论文地址：https://arxiv.org/abs/2006.06513