本文來自:克勞斯·蒂喬·佛斯特(Klaus-Tycho Foerster)2020年6月11日,星期四發(fā)布的第一版本的故障轉(zhuǎn)移的論文,并在文末尾附屬了論文地址,給深入學(xué)習(xí)的用戶。
故障轉(zhuǎn)移是自動化運(yùn)維中重要的組成部分,有效的自動化故障轉(zhuǎn)移可以保證服務(wù)的連續(xù)性,無故障運(yùn)行。
2020060804
論文摘要:
為了提供高彈性并快速響應(yīng)鏈接故障,現(xiàn)代計(jì)算機(jī)網(wǎng)絡(luò)支持完全分散的流重新路由,也稱為本地快速故障轉(zhuǎn)移。簡而言之,本地快速故障轉(zhuǎn)移算法的任務(wù)是僅使用本地可用信息為每個(gè)節(jié)點(diǎn)預(yù)定義快速故障轉(zhuǎn)移規(guī)則。這些規(guī)則為數(shù)據(jù)包可能到達(dá)的每個(gè)傳入鏈路以及本地鏈路故障集(即,發(fā)生故障的鏈路入射到節(jié)點(diǎn))確定了數(shù)據(jù)包應(yīng)在哪個(gè)出站鏈路上轉(zhuǎn)發(fā)。理想情況下,這種本地快速故障轉(zhuǎn)移算法可確定性地提供完美的彈性:只要基礎(chǔ)網(wǎng)絡(luò)保持連接,從任何源發(fā)出的數(shù)據(jù)包都可以到達(dá)任何目標(biāo)。Feigenbaum等。展示了并非總是能夠提供完美的彈性,并展示了如何容忍任何網(wǎng)絡(luò)中的單個(gè)故障。有趣的是,關(guān)于完美彈性的可行性目前知之甚少。
本文在一個(gè)模型中可以使用源也可以不使用源快速轉(zhuǎn)發(fā)決策的模型中,重新審視了本地快速故障轉(zhuǎn)移的完美彈性。我們首先得出幾個(gè)相當(dāng)普遍的不可能結(jié)果:通過在圖形次要圖和彈性之間建立聯(lián)系,我們證明不可能在任何非平面圖上實(shí)現(xiàn)完美的彈性;此外,盡管平面度是必需的,但對于完美的彈性來說也是不夠的。
從積極的方面來看,我們顯示了在鏈接細(xì)分下閉合的圖形族可以使用簡單有效的故障轉(zhuǎn)移算法,該算法僅跳過失敗的鏈接。我們通過為外部平面圖和相關(guān)方案以及故障后源和目標(biāo)在拓?fù)渖辖咏姆桨傅贸鐾昝赖膹椥詠硌菔敬思夹g(shù)。
介紹
分布式系統(tǒng)的可靠性通常取決于由一組路由器實(shí)現(xiàn)的底層網(wǎng)絡(luò)。為了提供高可用性,現(xiàn)代路由器支持流量的本地快速重路由:路由器可以預(yù)先配置有條件的故障轉(zhuǎn)移規(guī)則,這些規(guī)則為每個(gè)傳入端口和所需目標(biāo)定義,到達(dá)該傳入端口的數(shù)據(jù)包應(yīng)轉(zhuǎn)發(fā)到哪個(gè)端口,僅取決于事件鏈路的狀態(tài):由于路由器需要快速反應(yīng),因此它們沒有時(shí)間了解遠(yuǎn)程故障。
本文的出發(fā)點(diǎn)是本地快速重路由機(jī)制引入的以下基本問題:是否可以預(yù)先定義確定性的本地故障轉(zhuǎn)移規(guī)則,以保證只要底層網(wǎng)絡(luò)連接,數(shù)據(jù)包就可以到達(dá)其目標(biāo)?這種理想的特性被稱為完美彈性。因此,提供完美彈性的挑戰(zhàn)在于問題的分散性,以及路由器僅具有關(guān)于失敗鏈路的本地信息;利用全局知識實(shí)現(xiàn)完美彈性是簡單的,因?yàn)榭梢院唵蔚赜?jì)算最短路徑。
不幸的是,總的來說,完全的彈性是無法實(shí)現(xiàn)的:Feigenbaum等人。[19,20]給出了一個(gè)有12個(gè)節(jié)點(diǎn)的示例,在某些故障之后,原始網(wǎng)絡(luò)上沒有轉(zhuǎn)發(fā)模式允許目標(biāo)連接組件中的每個(gè)幸存節(jié)點(diǎn)到達(dá)目標(biāo)。從積極的方面來說,作者表明,至少可以容忍一個(gè)鏈路故障,即1-彈性。有趣的是,現(xiàn)在對于什么時(shí)候可以實(shí)現(xiàn)完美的彈性,什么時(shí)候不可以,知之甚少。
本文研究了在節(jié)點(diǎn)只具有局部信息的網(wǎng)絡(luò)中,同時(shí)考慮到節(jié)點(diǎn)能夠和不能匹配包源的模型,提供完美彈性的問題。在消極方面,我們描述了不允許完全彈性解決方案的網(wǎng)絡(luò)實(shí)例。從這一特性可以看出,在簡單和小平面圖上,即使在源在故障后仍然通過Ω(n)不相交路徑與目標(biāo)高度連接的情況下,也不可能實(shí)現(xiàn)完全恢復(fù);但是,它無法路由到目標(biāo)。我們還得到了一個(gè)相當(dāng)一般的否定結(jié)果,即完全彈性在任何非平面圖上都是不可能的,并且完全圖K5和完全二部圖K 3,3都不允許有完全彈性解。為此,我們證明了圖的子圖與完全彈性之間的一種有趣的聯(lián)系,并證明了每一個(gè)圖的子圖都保留了完全彈性的性質(zhì)。
從積極的方面來說,我們描述了所有外平面圖和相關(guān)場景(例如,失敗后源和目標(biāo)位于同一個(gè)面上的場景)以及目標(biāo)位于源的兩個(gè)跳內(nèi)的非外平面場景的完全彈性算法。對于我們的積極結(jié)果,我們建立了一個(gè)普遍的觀點(diǎn),即在細(xì)分鏈接下閉合的圖族,允許簡單的故障轉(zhuǎn)移算法,其中節(jié)點(diǎn)可以跳過本地故障端口,需要非常小的轉(zhuǎn)發(fā)表。
論文地址:https://arxiv.org/abs/2006.06513
- 蜜度索驥:以跨模態(tài)檢索技術(shù)助力“企宣”向上生長
- 比亞迪上半年研發(fā)投入超200億元,比特斯拉多出約40億
- 英偉達(dá)第二財(cái)季營收300.40億美元 凈利潤同比大增168%
- 知名特斯拉投資人“心灰意冷”:持倉已砍半,AI和機(jī)器人都救不了它!
- 騰訊音樂Q2持續(xù)高質(zhì)量增長:總收入71.6億元,付費(fèi)用戶數(shù)1.17億
- 微軟Q4營收647億美元凈利220億 盤后一度大跌7%
- 英偉達(dá)市值接近蘋果 高增長可以持續(xù)嗎?
- 優(yōu)信發(fā)布財(cái)報(bào):零售量環(huán)比同比均增長 預(yù)計(jì)2025財(cái)年業(yè)務(wù)量增長超200%
- 36氪Q4季報(bào)圖解:營收1億同比增7% 凈虧1766萬
- 聯(lián)想控股2023年凈虧損38.74億元同比轉(zhuǎn)虧,營收下降10%
- 騰訊音樂Q4及年報(bào):在線音樂強(qiáng)勁增長,持續(xù)促進(jìn)產(chǎn)業(yè)共贏
免責(zé)聲明:本網(wǎng)站內(nèi)容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿,凡在本網(wǎng)站出現(xiàn)的信息,均僅供參考。本網(wǎng)站將盡力確保所提供信息的準(zhǔn)確性及可靠性,但不保證有關(guān)資料的準(zhǔn)確性及可靠性,讀者在使用前請進(jìn)一步核實(shí),并對任何自主決定的行為負(fù)責(zé)。本網(wǎng)站對有關(guān)資料所引致的錯(cuò)誤、不確或遺漏,概不負(fù)任何法律責(zé)任。任何單位或個(gè)人認(rèn)為本網(wǎng)站中的網(wǎng)頁或鏈接內(nèi)容可能涉嫌侵犯其知識產(chǎn)權(quán)或存在不實(shí)內(nèi)容時(shí),應(yīng)及時(shí)向本網(wǎng)站提出書面權(quán)利通知或不實(shí)情況說明,并提供身份證明、權(quán)屬證明及詳細(xì)侵權(quán)或不實(shí)情況證明。本網(wǎng)站在收到上述法律文件后,將會依法盡快聯(lián)系相關(guān)文章源頭核實(shí),溝通刪除相關(guān)內(nèi)容或斷開相關(guān)鏈接。