本文來自：克勞斯· 蒂喬·佛斯特（Klaus-Tycho Foerster） 2020年6月11日，星期四發(fā)布的第一版本的故障轉(zhuǎn)移的論文，并在文末尾附屬了論文地址，給深入學(xué)習(xí)的用戶。

故障轉(zhuǎn)移是自動化運(yùn)維中重要的組成部分，有效的自動化故障轉(zhuǎn)移可以保證服務(wù)的連續(xù)性，無故障運(yùn)行。

論文摘要：

為了提供高彈性并快速響應(yīng)鏈接故障，現(xiàn)代計算機(jī)網(wǎng)絡(luò)支持完全分散的流重新路由，也稱為本地快速故障轉(zhuǎn)移。簡而言之，本地快速故障轉(zhuǎn)移算法的任務(wù)是僅使用本地可用信息為每個節(jié)點預(yù)定義快速故障轉(zhuǎn)移規(guī)則。這些規(guī)則為數(shù)據(jù)包可能到達(dá)的每個傳入鏈路以及本地鏈路故障集（即，發(fā)生故障的鏈路入射到節(jié)點）確定了數(shù)據(jù)包應(yīng)在哪個出站鏈路上轉(zhuǎn)發(fā)。理想情況下，這種本地快速故障轉(zhuǎn)移算法可確定性地提供完美的彈性：只要基礎(chǔ)網(wǎng)絡(luò)保持連接，從任何源發(fā)出的數(shù)據(jù)包都可以到達(dá)任何目標(biāo)。Feigenbaum等。展示了并非總是能夠提供完美的彈性，并展示了如何容忍任何網(wǎng)絡(luò)中的單個故障。有趣的是，關(guān)于完美彈性的可行性目前知之甚少。

本文在一個模型中可以使用源也可以不使用源快速轉(zhuǎn)發(fā)決策的模型中，重新審視了本地快速故障轉(zhuǎn)移的完美彈性。我們首先得出幾個相當(dāng)普遍的不可能結(jié)果：通過在圖形次要圖和彈性之間建立聯(lián)系，我們證明不可能在任何非平面圖上實現(xiàn)完美的彈性；此外，盡管平面度是必需的，但對于完美的彈性來說也是不夠的。

從積極的方面來看，我們顯示了在鏈接細(xì)分下閉合的圖形族可以使用簡單有效的故障轉(zhuǎn)移算法，該算法僅跳過失敗的鏈接。我們通過為外部平面圖和相關(guān)方案以及故障后源和目標(biāo)在拓?fù)渖辖咏姆桨傅贸鐾昝赖膹椥詠硌菔敬思夹g(shù)。

介紹

分布式系統(tǒng)的可靠性通常取決于由一組路由器實現(xiàn)的底層網(wǎng)絡(luò)。為了提供高可用性，現(xiàn)代路由器支持流量的本地快速重路由：路由器可以預(yù)先配置有條件的故障轉(zhuǎn)移規(guī)則，這些規(guī)則為每個傳入端口和所需目標(biāo)定義，到達(dá)該傳入端口的數(shù)據(jù)包應(yīng)轉(zhuǎn)發(fā)到哪個端口，僅取決于事件鏈路的狀態(tài)：由于路由器需要快速反應(yīng)，因此它們沒有時間了解遠(yuǎn)程故障。

本文的出發(fā)點是本地快速重路由機(jī)制引入的以下基本問題：是否可以預(yù)先定義確定性的本地故障轉(zhuǎn)移規(guī)則，以保證只要底層網(wǎng)絡(luò)連接，數(shù)據(jù)包就可以到達(dá)其目標(biāo)？這種理想的特性被稱為完美彈性。因此，提供完美彈性的挑戰(zhàn)在于問題的分散性，以及路由器僅具有關(guān)于失敗鏈路的本地信息；利用全局知識實現(xiàn)完美彈性是簡單的，因為可以簡單地計算最短路徑。

不幸的是，總的來說，完全的彈性是無法實現(xiàn)的：Feigenbaum等人。[19,20]給出了一個有12個節(jié)點的示例，在某些故障之后，原始網(wǎng)絡(luò)上沒有轉(zhuǎn)發(fā)模式允許目標(biāo)連接組件中的每個幸存節(jié)點到達(dá)目標(biāo)。從積極的方面來說，作者表明，至少可以容忍一個鏈路故障，即1-彈性。有趣的是，現(xiàn)在對于什么時候可以實現(xiàn)完美的彈性，什么時候不可以，知之甚少。

本文研究了在節(jié)點只具有局部信息的網(wǎng)絡(luò)中，同時考慮到節(jié)點能夠和不能匹配包源的模型，提供完美彈性的問題。在消極方面，我們描述了不允許完全彈性解決方案的網(wǎng)絡(luò)實例。從這一特性可以看出，在簡單和小平面圖上，即使在源在故障后仍然通過Ω（n）不相交路徑與目標(biāo)高度連接的情況下，也不可能實現(xiàn)完全恢復(fù)；但是，它無法路由到目標(biāo)。我們還得到了一個相當(dāng)一般的否定結(jié)果，即完全彈性在任何非平面圖上都是不可能的，并且完全圖K5和完全二部圖K 3,3都不允許有完全彈性解。為此，我們證明了圖的子圖與完全彈性之間的一種有趣的聯(lián)系，并證明了每一個圖的子圖都保留了完全彈性的性質(zhì)。

從積極的方面來說，我們描述了所有外平面圖和相關(guān)場景（例如，失敗后源和目標(biāo)位于同一個面上的場景）以及目標(biāo)位于源的兩個跳內(nèi)的非外平面場景的完全彈性算法。對于我們的積極結(jié)果，我們建立了一個普遍的觀點，即在細(xì)分鏈接下閉合的圖族，允許簡單的故障轉(zhuǎn)移算法，其中節(jié)點可以跳過本地故障端口，需要非常小的轉(zhuǎn)發(fā)表。

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