本文来自Klaus-Tycho Foerster于2020年6月11日(星期四)发表的关于故障转移的论文的第一个版本,论文末尾附有论文的地址,供深入研究的用户参考。
故障转移是自动化操作和维护的重要组成部分。有效的自动故障转移可以确保服务的连续性和无故障运行。
摘要:
为了提供高灵活性和对链路故障的快速响应,现代计算机网络支持完全分散的流重新路由,也称为本地快速故障转移。简而言之,本地快速故障转移算法的任务是仅使用本地可用信息为每个节点预定义快速故障转移规则。对于数据包可能到达的每个传入链路和本地链路故障集(即故障链路发生在节点上),这些规则确定数据包应在哪个出站链路上转发。理想情况下,这种本地快速故障转移算法可以提供完美的弹性:只要底层网络保持连接,从任何源发送的数据包都可以到达任何目的地。Feigenbaum等人表明,在任何网络中,不可能总是提供完美的弹性以及如何容忍单一故障。有趣的是,人们对完全弹性的可行性知之甚少。
本文在有或没有源的快速转发决策模型中重新检验了本地快速故障转移的完美弹性。我们首先得出几个相当常见的不可能结果:通过建立图形二次图与弹性的关系,证明在任何非平面图形上不可能达到完美弹性;另外,虽然平坦度是必要的,但对于完美的弹性来说,这还不够。
从积极的方面来看,我们证明了链路细分下的封闭图族可以使用简单有效的故障转移算法,该算法只跳过失败的链路。我们通过获得外部计划和相关方案的完美弹性,以及失败后源和目标在拓扑上接近的方案来展示这种技术。
介绍
分布式系统的可靠性通常取决于由一组路由器实现的底层网络。为了提供高可用性,现代路由器支持流量的本地快速重新路由:路由器可以预先配置条件故障转移规则,这些规则定义了每个传入端口和所需的目标,到达传入端口的数据包应该转发到哪个端口仅取决于事件链路的状态:因为路由器需要快速反应,所以它们没有时间了解远程故障。
本文的出发点是本地快速重路由机制引入的以下基本问题:能否预先定义确定性本地故障转移规则,以确保只要底层网络连接,数据包就能到达其目标?这种理想特性称为完全弹性。因此,提供完美弹性的挑战在于问题的分散性,路由器只有失效链路的本地信息;利用全局知识实现完美弹性很简单,因为最短路径可以简单计算。
不幸的是,一般来说,完全的弹性是无法实现的:Feigenbaum等人[19,20]给出了一个12节点的例子。在一些故障之后,原始网络上没有转发模式来允许目标连接组件中的每个幸存节点到达目标。从积极的方面来看,作者表明至少可以容忍一个链路故障,即1-弹性。有趣的是,对于什么时候可以实现完美的灵活性,什么时候不能,我们知之甚少。
本文研究了在节点只有本地信息的网络中提供完全弹性的问题,考虑了节点可以和不可以匹配分组源的模型。另一方面,我们描述了不支持完全灵活的解决方案的网络实例。从这个特性可以看出,在简单小计划上,即使源在失效后仍然通过 (n)不相交路径连接到目标高度,也不可能达到完全恢复;但是,它无法路由到目标。我们还得到了一个相当一般的否定结果,即在任何非平面图上完全弹性是不可能的,完全图K5和完全二部图K 3,3不允许有完全弹性解。因此,我们证明了图的子图和完全弹性之间的一个有趣的关系,并且证明了每个图的子图都保持完全弹性的性质。
从积极的方面来说,我们描述了一种完全弹性的算法,适用于所有平面外图和相关场景(例如,失败后源和目标在同一平面上的场景)以及目标在源两跳以内的非平面外场景。对于我们的正结果,我们建立了一个总的观点,即细分链接下的闭图族允许一个简单的故障转移算法,其中节点可以跳过本地故障端口,需要一个非常小的转发表。
地址:https://arxiv.org/abs/2006.06513.
()
!
报酬
二维码
分享
分享给
报酬
更多关于云服务器,域名注册,虚拟主机的问题,请访问西部数码代理官网:www.chenqinet.cn。