算力網(wǎng)絡(luò)中一種新穎的看門狗故障檢測協(xié)議

梁 轟，馮 麗，徐方鑫，李光程，周郭許

（1. 澳門科技大學(xué) 資訊科技學(xué)院，澳門 999078；2. 廣東工業(yè)大學(xué) 自動化學(xué)院，廣東 廣州 510006；3. 粵港澳離散制造智能化聯(lián)合實(shí)驗(yàn)室，廣東 廣州 510006）

1 問題的提出

邊緣計算是云計算的擴(kuò)展，是一種流行的計算范式，能使計算設(shè)備更接近終端用戶，旨在為用戶提供便捷且快速的計算服務(wù)。它通過云中心來進(jìn)行計算資源分配。如圖1(a)所示，每當(dāng)任務(wù)到達(dá)一個邊緣節(jié)點(diǎn)時，該邊緣節(jié)點(diǎn)就會向云中心發(fā)送資源請求。然后，云中心確定應(yīng)為該任務(wù)分配哪種類型的資源(云中心的或邊緣的)，并將資源分配的結(jié)果反饋給相關(guān)的邊緣節(jié)點(diǎn)。收到分配結(jié)果后，請求節(jié)點(diǎn)將任務(wù)卸載(offload)到目標(biāo)邊緣節(jié)點(diǎn)。但是，因?yàn)檫吘壓驮浦g的網(wǎng)絡(luò)延遲，這種集中式分配機(jī)制可能導(dǎo)致從發(fā)起請求到任務(wù)開始處理所需的時間較長，這實(shí)際上違反了邊緣計算的設(shè)計目標(biāo)(例如，快速響應(yīng))。

圖1 傳統(tǒng)邊緣計算及CFN中的資源分配框架Fig.1 Resource allocation framework in tranditional edge computing and CFN

近年來，學(xué)者提出算力網(wǎng)絡(luò)(Compute First Networking, CFN)[1]，以解決邊緣計算中的上述問題，如圖1(b)所示。CFN是一種用于計算資源分配的新穎分布式框架，它可以根據(jù)計算負(fù)載和網(wǎng)絡(luò)狀態(tài)將任務(wù)動態(tài)路由到最佳計算節(jié)點(diǎn)。CFN平等對待邊緣節(jié)點(diǎn)和云節(jié)點(diǎn)，并將它們集成到分布式計算資源池中，然后引入一個新的控制平面來管理資源池，以便智能地分配資源，從而滿足用戶的需求。如果用戶的請求是實(shí)時任務(wù)，則控制平面會綜合考慮網(wǎng)絡(luò)條件和可用的計算資源，智能地向用戶分配鄰近資源。否則，它將任務(wù)卸載到云中心進(jìn)行處理。

CFN采用分布式框架為任務(wù)分配計算資源。它利用眾多具有異構(gòu)計算能力且在地理上分散的邊緣/云節(jié)點(diǎn)構(gòu)造一個公共計算資源池。在CFN中，一個任務(wù)可能被多個節(jié)點(diǎn)本地或遠(yuǎn)程地處理。這些節(jié)點(diǎn)之間網(wǎng)絡(luò)連接的多樣性和由此帶來的網(wǎng)絡(luò)延遲，以及節(jié)點(diǎn)計算能力的巨大差異，使得監(jiān)控任務(wù)的處理狀態(tài)非常困難。即使可以監(jiān)控狀態(tài)，在分布式框架中檢測任務(wù)或虛擬機(jī)(Virtual Machine, VM)故障通常需要花費(fèi)很長時間[2-3]。此處，故障是指當(dāng)任務(wù)或VM的程序拋出運(yùn)行時發(fā)生異常。另一方面，CFN要求本地或遠(yuǎn)程計算資源的可用狀態(tài)應(yīng)實(shí)時可見，以便有效地從計算池分配資源。因此，需要一種能夠及時、遠(yuǎn)程地檢測任務(wù)或虛擬機(jī)故障的機(jī)制，以快速回收這些故障所占用的資源。

1.1 動機(jī)

CFN現(xiàn)在處于起步階段，并不提供獲取本地或遠(yuǎn)程計算資源實(shí)時可用性的機(jī)制。IP網(wǎng)絡(luò)或云計算中流行的故障檢測方法也不適用于CFN。例如，IP網(wǎng)絡(luò)中的雙向轉(zhuǎn)發(fā)檢測協(xié)議[4]主要用于檢測網(wǎng)絡(luò)設(shè)備的故障，而不是任務(wù)或VM的故障。云計算中Hadoop的JobTracker[5]主要用于檢測本地任務(wù)故障，而不是遠(yuǎn)程檢測。因此，在CFN的分布式框架下，任務(wù)是在多個節(jié)點(diǎn)中本地或遠(yuǎn)程處理的，它需要一種新穎的遠(yuǎn)程故障檢測設(shè)計以及時監(jiān)控任務(wù)和VM的狀態(tài)。

1.2 貢獻(xiàn)

借鑒傳統(tǒng)的Watchdog timer[6]思想，本文設(shè)計并分析了一種新穎的故障檢測協(xié)議CFN-Watchdog(簡稱Watchdog)，以解決上述CFN中本地或遠(yuǎn)程計算資源的可見性問題。本文的貢獻(xiàn)總結(jié)如下。

(1) 提出Watchdog，這是第一個在CFN中的集中式任務(wù)和VM故障檢測協(xié)議，可遠(yuǎn)程監(jiān)視邊緣計算中分布式計算資源的可用狀態(tài)。在本文的協(xié)議中，許多Watchdog客戶端定期向連接到CFN的一個Watchdog服務(wù)器報告其監(jiān)視VM的狀態(tài)。受益于集中協(xié)議的快速響應(yīng)特點(diǎn)，CFN的控制平面可以實(shí)時顯示其托管資源狀態(tài)，并及時回收故障所占用的資源。

(2) 建立理論模型分析所提的Watchdog協(xié)議的性能。本文的模型考慮重要參數(shù)，包括檢測閾值、任務(wù)處理時間和網(wǎng)絡(luò)延遲，并闡述對系統(tǒng)吞吐量造成影響的誤報(false alarm)，以及錯誤事件的漏檢(miss detection)。本文的模型能夠?yàn)閃atchdog協(xié)議選擇最佳的參數(shù)設(shè)置。

(3) 運(yùn)行大量的仿真，以驗(yàn)證該設(shè)計的有效性和理論模型的準(zhǔn)確性。

本文的其余部分安排如下。第2節(jié)總結(jié)了相關(guān)工作。第3節(jié)概述了CFN。第4節(jié)設(shè)計了CFN-Watchdog協(xié)議。第5節(jié)從理論上分析了CFN的吞吐量。第6節(jié)評估系統(tǒng)性能。第7節(jié)總結(jié)了本文工作。

2 相關(guān)工作

在本節(jié)中，列出了有關(guān)傳統(tǒng)網(wǎng)絡(luò)、云計算和邊緣計算中故障檢測的相關(guān)工作。高可用性是計算框架的關(guān)鍵要求，其基本思想是檢測故障或錯誤，然后執(zhí)行恢復(fù)策略。

2.1 傳統(tǒng)網(wǎng)絡(luò)中的故障檢測

在傳統(tǒng)的網(wǎng)絡(luò)體系結(jié)構(gòu)中，可以使用某些方法來實(shí)現(xiàn)故障檢測。典型的代表是Internet控制報文協(xié)議(Internet Control Message Protocol, ICMP)[7]，雙向轉(zhuǎn)發(fā)檢測協(xié)議(Bidirectional Forwarding Detection,BFD)[4]，單向主動測量協(xié)議(One-way Active Measurement Protocol, OWAMP)[8]和連接故障管理(Connectivity Fault Management, CFM)[9]。

ICMP[7]協(xié)議通過判斷接收方是否可以通過一次ping操作成功反饋其狀態(tài)來檢測故障。雖然ICMP可以用于檢測任何設(shè)備，但其缺點(diǎn)是只能進(jìn)行單向故障檢測，并且檢測頻率很低。BFD[4]是一種雙向檢測機(jī)制，參與檢測的雙方都可以通過hello數(shù)據(jù)包確認(rèn)對方是否仍在正常運(yùn)作。BFD側(cè)重于發(fā)現(xiàn)相距一跳鄰居設(shè)備的故障，而無法處理相距多跳設(shè)備的場景。OWAMP[8]是基于TCP連接的網(wǎng)絡(luò)性能測試協(xié)議。它不僅可以檢測故障，而且可以高精度地測量網(wǎng)絡(luò)性能。但是，OWAMP需要基于NTP的時間同步，因此需要更多的控制開銷。CFM[9]是基于數(shù)據(jù)中心方案的連接故障檢測協(xié)議，它采用定期檢測的方式在更大的范圍內(nèi)維持所有網(wǎng)絡(luò)的穩(wěn)定運(yùn)行。但是CFM過于復(fù)雜，不適合CFN場景。

所有這些故障檢測方法都僅用于檢測網(wǎng)絡(luò)連接的問題，而不是檢測任務(wù)執(zhí)行的狀態(tài)。因此，它們不能應(yīng)用于CFN[1,10]。

2.2 云計算中的故障檢測

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，云計算中心[11]取代了傳統(tǒng)的數(shù)據(jù)中心，相關(guān)技術(shù)也在不斷發(fā)展，其中包括故障檢測。在云計算場景中，典型的故障檢測技術(shù)是Hadoop下的JobTracker[5]或storm下的nimbus[12]。對于這種情況，典型的參考文獻(xiàn)包括[5, 13-15]。

文獻(xiàn)[5]提出了一種通過自適應(yīng)檢測心跳數(shù)據(jù)包來檢測任務(wù)是否可以成功完成的解決方案。它通過匹配軟件的統(tǒng)計狀態(tài)和心跳條件的反饋來判斷任務(wù)的執(zhí)行是否失敗，然后決定采用哪種失敗處理策略。但是文獻(xiàn)[5]并未考慮網(wǎng)絡(luò)延遲的影響，這將導(dǎo)致誤檢率的提高。文獻(xiàn)[13]提出了一種基于機(jī)器學(xué)習(xí)的故障檢測方法，該方法通過檢測節(jié)點(diǎn)的心跳反饋來判斷運(yùn)行狀態(tài)。此外，通過調(diào)度方法，故障恢復(fù)將有序地執(zhí)行。文獻(xiàn)[14]提出了一種故障感知調(diào)度方法，可以避免故障造成的損失。該方法是預(yù)先預(yù)測任務(wù)是否有風(fēng)險，并在任務(wù)失敗時立即安排備份以進(jìn)行替換，從而將故障損失降至最低。文獻(xiàn)[14]則專注于優(yōu)化故障恢復(fù)策略，而不是故障檢測。它們的方法在云計算場景中具有一定的影響。但是，CFN場景不同于云計算場景，其擁有異構(gòu)計算資源。因此，如果節(jié)點(diǎn)沒有足夠的計算能力來提供備份，則不建議使用此方法。文獻(xiàn)[15]基于驗(yàn)收測試的思想，設(shè)計了大規(guī)模云場景中的故障檢測機(jī)制?；谄ヅ錂z測的基本思想，它可以匹配包括軟件故障、黑客攻擊等不同故障場景，并建立了更直接的檢測模型。但是它們沒有考慮網(wǎng)絡(luò)鏈接的影響。

上述方法專注于檢測軟件故障，而不是網(wǎng)絡(luò)連接故障，不能應(yīng)用于網(wǎng)絡(luò)鏈路不穩(wěn)定、時延波動范圍大的CFN場景。

2.3 算力網(wǎng)絡(luò)和邊緣計算中的故障檢測

霧計算[16]和邊緣計算[17-18]擴(kuò)展了云計算的功能并滿足應(yīng)用程序?qū)崟r性和低延遲的要求。在霧計算中，通常在物聯(lián)網(wǎng)網(wǎng)關(guān)或局域網(wǎng)的節(jié)點(diǎn)中處理任務(wù)。在邊緣計算中，任務(wù)直接在邊緣設(shè)備(例如傳感器、智能手機(jī)、iPad)上處理。但是它們的兩種集中式分配機(jī)制都可能導(dǎo)致從發(fā)起請求到任務(wù)開始處理的持續(xù)時間很長。為了解決該問題，CFN[1]被提出。作為用于邊緣計算的新型分布式計算框架，它采用分布式方式為任務(wù)分配計算資源，其可以在本地或遠(yuǎn)程處理任務(wù)。但是，在分布式框架中檢測任務(wù)或VM故障通常需要很長時間。一方面，CFN現(xiàn)在處于早期研究階段，還沒有這樣的機(jī)制來獲取本地或遠(yuǎn)程計算資源的實(shí)時狀態(tài)。另一方面，常規(guī)網(wǎng)絡(luò)中的傳統(tǒng)故障檢測協(xié)議(例如，BFD[4])主要用于檢測網(wǎng)絡(luò)設(shè)備的故障，而不是VM故障。Hadoop在云計算中的JobTracker[5]主要用于檢測本地任務(wù)故障，而不是遠(yuǎn)程檢測。因此，它們不能直接應(yīng)用于CFN。本文首次提出名為CFN-Watchdog的故障檢測協(xié)議，以檢測本地和遠(yuǎn)程故障，從而可以及時回收故障所占用的資源。

3 算力網(wǎng)絡(luò)

本節(jié)闡述了CFN中邊緣節(jié)點(diǎn)之間的交互邏輯。首先，給出邊緣節(jié)點(diǎn)中組件的概述；然后，詳細(xì)說明它們之間的交互，以分別說明邊緣節(jié)點(diǎn)中的資源分配和任務(wù)處理。

CFN是用于邊緣計算[10]的分布式計算框架，它由控制平面和統(tǒng)一的計算資源池組成(如圖1 (b)所示)?？刂破矫尕?fù)責(zé)將資源分配給任務(wù)，而資源池負(fù)責(zé)管理邊緣/云節(jié)點(diǎn)的資源。控制平面由任務(wù)代理和VM管理器(VM manager)組件組成(如圖2中所示)。任務(wù)代理(Task agent)組件緩沖任務(wù)并為任務(wù)分配資源。VM管理器組件創(chuàng)建用于任務(wù)處理的VM，并在任務(wù)完成或檢測到故障后釋放VM。此外，資源池由VM和IP底層(IP underlay)組件組成(如圖2中所示)，并負(fù)責(zé)資源管理。VM組件包含用于執(zhí)行任務(wù)的多個VM。IP底層組件為邊緣/云節(jié)點(diǎn)之間的通信(例如，卸載任務(wù))提供網(wǎng)絡(luò)資源。

圖2 CFN中看門狗協(xié)議的概覽Fig.2 An overview of watchdog protocol for CFN

當(dāng)任務(wù)到達(dá)CFN中時，任務(wù)代理首先會緩沖任務(wù)，然后，代理提取此任務(wù)的資源要求，再將可用資源查詢請求發(fā)送到VM管理器。最后，代理判斷可用資源量是否足以執(zhí)行任務(wù)。如果有足夠的可用資源，任務(wù)代理將處理當(dāng)前節(jié)點(diǎn)中的任務(wù)處理請求。否則，代理會智能地考慮網(wǎng)絡(luò)條件和可用資源的數(shù)量，找到可以執(zhí)行任務(wù)的另一個節(jié)點(diǎn)，然后通過IP底層組件將其卸載到目標(biāo)節(jié)點(diǎn)。

對于任務(wù)的處理，任務(wù)代理首先將具有任務(wù)資源需求的VM創(chuàng)建請求發(fā)送到VM管理器。然后，VM管理器將啟動VM，并部署任務(wù)。任務(wù)完成后，任務(wù)代理將收集任務(wù)執(zhí)行的結(jié)果。最后，代理將向VM管理器發(fā)送請求，以停止并釋放VM。

3.1 Watchdog協(xié)議

為了在CFN中支持所提的Watchdog協(xié)議，VM需要添加新功能，通過kick數(shù)據(jù)包報告其狀態(tài)。在VM的生命周期中，VM會定期將kick數(shù)據(jù)包發(fā)送到Watchdog客戶端。本文基于用戶數(shù)據(jù)報協(xié)議(User Datagram Protocol，UDP)設(shè)計kick數(shù)據(jù)包，從而無需接收相應(yīng)的確認(rèn)數(shù)據(jù)包，降低了通信成本，因此適用于邊緣節(jié)點(diǎn)。其payload部分包括以下字段：

(1) kickID：標(biāo)識kick數(shù)據(jù)包的唯一ID；(2) vmID：發(fā)送kick數(shù)據(jù)包的VM的唯一標(biāo)識ID；(3) nodeID：發(fā)送kick包的VM所在宿主節(jié)點(diǎn)的唯一標(biāo)識ID；(4) sendTime：VM發(fā)送kick數(shù)據(jù)包的時間。

Watchdog客戶端是一個將kick數(shù)據(jù)包從VM中繼到Watchdog服務(wù)器的進(jìn)程。虛擬機(jī)啟動后，它將在邊緣/云節(jié)點(diǎn)的虛擬化管理平臺(hypervisor)中運(yùn)行。

一旦一個VM和相應(yīng)的Watchdog客戶端被創(chuàng)建，系統(tǒng)就通知Watchdog服務(wù)器開始監(jiān)控VM，并連續(xù)向CFN控制平面報告其狀態(tài)，直到該VM被釋放。首先，服務(wù)器估算從其到托管VM的節(jié)點(diǎn)的平均網(wǎng)絡(luò)延遲(例如，通過ping數(shù)據(jù)包)。其次，服務(wù)器根據(jù)延遲設(shè)置閾值r，以避免false alarm。然后，服務(wù)器執(zhí)行位圖機(jī)制，即持續(xù)地比較實(shí)際接收到的kick數(shù)據(jù)包和預(yù)期kick數(shù)據(jù)包的數(shù)量，以檢測VM上是否發(fā)生故障事件。一旦檢測到故障事件，服務(wù)器就會將bite數(shù)據(jù)包發(fā)送到VM管理器，以釋放該VM。bite是一種通過調(diào)用管理程序API(應(yīng)用程序編程接口)以達(dá)到釋放/關(guān)閉VM目的的數(shù)據(jù)包。一旦收到來自Watchdog服務(wù)器的bite數(shù)據(jù)包，VM管理器就會執(zhí)行釋放/關(guān)閉VM的命令。

3.2 bitmap機(jī)制

位圖(bitmap)機(jī)制用于根據(jù)接收到的kick數(shù)據(jù)包連續(xù)檢測故障事件，能夠減少由于網(wǎng)絡(luò)延遲或傳輸錯誤[19]而導(dǎo)致的false alarm。當(dāng)需要監(jiān)控一個執(zhí)行任務(wù)的VM時，Watchdog服務(wù)器首先根據(jù)一個閾值r啟動一個計時器(該閾值將在閾值設(shè)置部分詳細(xì)介紹)，并與該VM保持時間同步，這里，成功執(zhí)行完一個任務(wù)的時長為T。然后，該服務(wù)器創(chuàng)建一個位圖數(shù)組(bitmap array)以記錄VM的狀態(tài)。此后，對于VM的執(zhí)行時間[0，T)中的每個時間單位，Watchdog服務(wù)器執(zhí)行以下2個階段。

(1) 構(gòu)造bitmap數(shù)組。Watchdog服務(wù)器可能會收到在sendTime=i時刻發(fā)出的kick數(shù)據(jù)包。如果該數(shù)據(jù)包的接收時間在時間[i，i+r]以內(nèi)，則服務(wù)器會將位圖數(shù)組中的第i個元素設(shè)置為1，這表示VM在時刻i的狀態(tài)是正常的。相反，如果服務(wù)器直到時刻i+r都沒有收到kick數(shù)據(jù)包，它將把位圖數(shù)組中的第i個元素設(shè)置為0，這表明在時刻i時，VM上發(fā)生了故障事件。以圖3為例，假設(shè)閾值r設(shè)置為2，Watchdog服務(wù)器在時刻2之后收到在時刻0發(fā)出的kick數(shù)據(jù)包，以及在時間[1,3]內(nèi)接收到了在時刻1發(fā)出的kick數(shù)據(jù)包。因此，位圖的第0個元素為0，位圖的第1個元素為1。

(2) 使用滑動窗口w檢測故障事件[1,20]。位圖數(shù)組中設(shè)置了0和1值并從第i個元素開始，Watchdog服務(wù)器檢查w個元素(即從i到i+w?1的元素)，其中i=0,1,···,T?1。如果在w個元素中存在一個0，則Watchdog服務(wù)器檢測到VM上發(fā)生了故障事件；否則，如果w個元素的值都為1，則Watchdog服務(wù)器認(rèn)為VM上沒有故障事件發(fā)生。為簡單起見，本文設(shè)計滑動窗口大小等于閾值，即w=r。以圖3為例。假設(shè)邊緣節(jié)點(diǎn)中的VM在持續(xù)T時間內(nèi)執(zhí)行任務(wù)，并且位圖的第0個元素和第1個元素的值分別為0和1，并且滑動窗口w的值設(shè)置為2。由于在前2個元素中存在0，Watchdog判斷VM遇到了故障。但是，如果將第0個元素設(shè)置為1，則Watchdog會認(rèn)為VM正在正常運(yùn)行。

圖3 看門狗監(jiān)控的bitmapFig.3 Bitmap for watchdog monitoring

3.3 閾值設(shè)置

閾值用于避免false alarm問題。引入閾值設(shè)置的原因解釋如下。邊緣/云環(huán)境中的網(wǎng)絡(luò)延遲在很大范圍內(nèi)變化，這會影響kick數(shù)據(jù)包的到達(dá)時間(例如，kick數(shù)據(jù)包可能無法及時到達(dá))。在這種情況下，Watchdog服務(wù)器將錯誤地判斷有故障事件發(fā)生(即false alarm)。因此，需要為Watchdog服務(wù)器設(shè)置一個閾值，以防止網(wǎng)絡(luò)延遲對kick數(shù)據(jù)包的影響。

閾值的設(shè)置基于Watchdog服務(wù)器與受監(jiān)控VM所在的邊緣/云節(jié)點(diǎn)之間的網(wǎng)絡(luò)延遲。首先，當(dāng)創(chuàng)建并啟動一個VM時，Watchdog服務(wù)器將通過ping數(shù)據(jù)包估計與該VM之間的網(wǎng)絡(luò)延遲。其次，服務(wù)器將檢查延遲閾值映射表以找到合適的閾值(該表可以手動維護(hù)，也可以使用機(jī)器學(xué)習(xí)方法維護(hù))。最后，設(shè)置閾值并用于監(jiān)控VM。

4 理論分析

本節(jié)將從理論上分析所提出的CFN-Watchdog協(xié)議的吞吐量。首先給出模型假設(shè)，然后定義VM和Watchdog之間的交互情況(interaction cases)，最后給出吞吐量。

4.1 模型假設(shè)

首先進(jìn)行模型假設(shè)：

(1) 每當(dāng)任務(wù)到達(dá)時，系統(tǒng)都會為該任務(wù)創(chuàng)建一個VM，然后以T個時間單位正常處理它，并在完成后最終釋放VM。此外，任務(wù)的數(shù)量是無限的，而且系統(tǒng)按順序處理任務(wù)。為簡單起見，本文忽略VM創(chuàng)建和發(fā)布的時間。

(2) Watchdog與VM保持完美的時間同步，以監(jiān)控VM的狀態(tài)。

① 對于VM，如果它可以正常運(yùn)行以處理任務(wù)，它將在時刻0,1,···,T?1向監(jiān)控程序發(fā)送一個kick數(shù)據(jù)包，其中包括一個時間戳和一個序列號。一旦VM出現(xiàn)錯誤，它將不會發(fā)送kick數(shù)據(jù)包。假設(shè)每次發(fā)生VM故障或錯誤的概率為perr。

② 對于Watchdog，它將在每次i=0,1,···,T?1時啟動閾值為r(0

(3) kick或bite數(shù)據(jù)包的網(wǎng)絡(luò)延遲遵循指數(shù)分布。

4.2 交互情況

考慮一個VM。本文定義以下變量。

(1) ξ：虛擬機(jī)的狀態(tài)，其中ξ=0表示虛擬機(jī)正常運(yùn)行，ξ=1表示虛擬機(jī)出故障。

(2)Xi：第i個(0 ≤i≤T?1) kick數(shù)據(jù)包的網(wǎng)絡(luò)延遲，即從VM在時間i發(fā)送kick數(shù)據(jù)包的時刻至該kick數(shù)據(jù)包到達(dá)Watchdog的時間段。圖4給出了X0的示例。假設(shè)Xi遵循帶參數(shù)λ的指數(shù)分布，即其概率函數(shù)由式(1)給出。

(3)Yi：第i個(0 ≤i ≤T?r) bite數(shù)據(jù)包的網(wǎng)絡(luò)延遲，即從Watchdog在時刻i+r發(fā)出bite數(shù)據(jù)包的那一刻起到該bite數(shù)據(jù)包到達(dá)VM管理器時刻的時間。在這里，Watchdog發(fā)送bite數(shù)據(jù)包的原因是：由于虛擬機(jī)錯誤或網(wǎng)絡(luò)延遲，Watchdog沒有收到預(yù)期的應(yīng)該在時刻i發(fā)出的kick數(shù)據(jù)包，因此在r時間單位后觸發(fā)了一個bite數(shù)據(jù)包。圖4給出了Y1的示例。本文假設(shè)Yi也遵循帶參數(shù)λ的指數(shù)分布，即其概率函數(shù)由g(x)=λe?λx,x≥0給出。

圖4 X0和Y1的示例，其中r=2以及T=5Fig.4 Examples of X0 and Y1, where r=2 and T=5

(4)f(y;b)：截斷的指數(shù)分布的概率密度函數(shù)(Probability Density Function, PDF)，即取值在0到b之間的指數(shù)隨機(jī)變量的PDF，即式(2)。

然后根據(jù)VM是否出錯(ξ=0)，kick數(shù)據(jù)包超時是否發(fā)生(Xi>r)以及bite數(shù)據(jù)包超時是否發(fā)生，將所有VM和Watchdog交互分為8種情況，如圖5所示。

圖5 8種情況的樹Fig.5 Tree of 8 cases

在分析每種情況下發(fā)生的概率以及VM在每種情況下消耗的時間之前，定義以下事件。

通常，VM在時刻0開始執(zhí)行任務(wù)，并在時刻T完成任務(wù)，此后將釋放VM的資源。但是，該期間可能會發(fā)生任務(wù)或VM故障，因此Watchdog服務(wù)器可能會與Watchdog客戶端進(jìn)行通信，以監(jiān)控任務(wù)處理或VM的狀態(tài)。Perri表示時刻i(i=0,1,···,T?1)發(fā)生任務(wù)或VM故障或錯誤的概率，Psuc表示在VM執(zhí)行期間沒有故障的概率。每個時刻VM故障或錯誤發(fā)生的概率為perr。Perri和Psuc分別如式(3)和式(4)所示，其中式(4)的T為完成一個任務(wù)所需的時間。

下文詳細(xì)介紹情況1、2、3，其他情況的分析方法與之類似。

4.2.1 情況1和情況3

在這2種情況下(如圖5所示)，VM正常運(yùn)行，并且正常事件(normal event)的發(fā)生使得VM由于未收到任何bite數(shù)據(jù)包而成功完成任務(wù)。未收到任何bite數(shù)據(jù)包的情況有2種：(1) 無bite數(shù)據(jù)包發(fā)送，對應(yīng)情況1；(2) bite數(shù)據(jù)包超時，對應(yīng)于情況3。下面，描述每種情況。

(1) 在情況1中，有兩種因素導(dǎo)致無bite數(shù)據(jù)包發(fā)送：一種是任何kick數(shù)據(jù)包都沒有超時；另一種是第i個踢包有超時，但i等于或大于T?r，即i≥T?r。圖6給出了該兩種因素導(dǎo)致正常事件發(fā)生的示例。在圖6 (a)中，假設(shè)VM每次從0到T?1發(fā)送kick數(shù)據(jù)包，并且它們均未超時。因此，它們中的任何一個kick數(shù)據(jù)包都不會觸發(fā)Watchdog發(fā)送bite數(shù)據(jù)包，并且VM將成功完成任務(wù)。在圖6 (b)中，假設(shè)VM發(fā)送第i個kick數(shù)據(jù)包，其中i=T?r并且該kick數(shù)據(jù)包超時，這應(yīng)該觸發(fā)了Watchdog在閾值r單位時間后(即時刻T)，發(fā)送bite數(shù)據(jù)包。但是，在時刻T及之后，VM結(jié)束并且Watchdog停止發(fā)送任何bite數(shù)據(jù)包。因此，無任何bite數(shù)據(jù)包發(fā)出以終止VM，這將導(dǎo)致任務(wù)成功執(zhí)行。

圖6 情況1的例子Fig.6 Examples of case 1

(2) 在情況3中，normal event是因?yàn)閎ite數(shù)據(jù)包超時而發(fā)生的。圖7給出了情況3的正常事件的示例，該例子中由于第i個bite數(shù)據(jù)包的超時，Watchdog無法終止正常運(yùn)行的VM，從而使得任務(wù)能夠成功執(zhí)行。假設(shè)VM在時刻i發(fā)送第i個kick數(shù)據(jù)包，并且該數(shù)據(jù)包超時。然后，在閾值r之后，Watchdog在[i,i+r]期間未收到預(yù)期的第i個kick數(shù)據(jù)包，因此發(fā)送第i個bite數(shù)據(jù)包嘗試終止正常運(yùn)行的VM。但是，該bite數(shù)據(jù)包超時，因此Watchdog無法終止VM，從而導(dǎo)致任務(wù)成功執(zhí)行。

圖7 情況3的例子Fig.7 An example of case 3

令Pnor表示normal event (即情況1和情況3)發(fā)生的概率，可以通過式(5)計算。

其中Pfa可在4.2.2章節(jié)的末尾計算得到。并且能夠通過此公式計算Pnor的原因是當(dāng)沒有錯誤發(fā)生時，只有normal event或false alarm事件會發(fā)生。

令Tnor表示normal event(即情況1和情況3)發(fā)生時VM的平均占用時間，即從VM開始執(zhí)行任務(wù)到VM成功完成任務(wù)的時間間隔。因此，很明顯Tnor可通過式(6)計算。

4.2.2 情況2

在這種情況下(如圖5所示)，VM正常運(yùn)行，但是false alarm事件的發(fā)生錯誤地終止了正常運(yùn)行的VM的執(zhí)行。假設(shè)VM發(fā)送第i個kick數(shù)據(jù)包(即在時刻i發(fā)出的kick數(shù)據(jù)包)，而且由于網(wǎng)絡(luò)延遲該數(shù)據(jù)包發(fā)生超時(即kick數(shù)據(jù)包未能在[i,i+r]時間內(nèi)到達(dá))。此超時將導(dǎo)致Watchdog發(fā)送bite數(shù)據(jù)包，并且該bite數(shù)據(jù)包會及時到達(dá)VM管理器，從而錯誤地終止了正常運(yùn)行的VM。圖8給出了情況2的示例，當(dāng)Watchdog由于第i個kick數(shù)據(jù)包超時而錯誤地終止了正常運(yùn)行的VM時，誤報事件發(fā)生。

圖8 情況2的例子Fig.8 An example of case 2

令Pfai表示第i個kick數(shù)據(jù)包超時而導(dǎo)致false alarm的概率。請注意，Pfai是在VM正常運(yùn)行的情況下的概率。

4.3 吞吐量

5 性能評估

在本節(jié)中，將進(jìn)行廣泛的仿真，以評估CFNWatchdog設(shè)計的有效性和理論模型的準(zhǔn)確性。

令T表示成功執(zhí)行任務(wù)的時間，1 /λ表示平均網(wǎng)絡(luò)延遲，perr表示每次發(fā)生VM錯誤的概率。令Prob-Normal表示VM正常完成任務(wù)的概率，Prob-FA表示沒有錯誤時(即情況2)false alarm的概率，Prob-Det表示情況4的成功檢測(detection)的概率。Prob-Miss表示情況5、6和8漏檢(miss detection)的概率，而Prob-FAErr表示發(fā)生錯誤時false alarm的概率(即情況7)。下面，展示了系統(tǒng)參數(shù)(即T，1 /λ和perr)如何影響Thg，Prob-Normal，Prob-FA，Prob-Det，Prob-Miss和Prob-FAErr。表1顯示了4組仿真實(shí)驗(yàn)的參數(shù)設(shè)置(包括設(shè)置(a)、(b)、(c)、(d))。在這里，利用“a:b:c”模式表示參數(shù)值從a到c隨著步長b的增加而增加。例如，“1:1:10”表示將參數(shù)值從1增加到10，步長為1。

圖9和圖10使用表1的設(shè)置(a)繪制了Thg和Normal，F(xiàn)A，Det，Miss，F(xiàn)AErr的概率趨勢圖。在此仿真中，將平均網(wǎng)絡(luò)延遲1 /λ的值設(shè)置為2，錯誤概率perr的值設(shè)置為0.1，而Watchdog的閾值r設(shè)置為2，但是任務(wù)的執(zhí)行時間T從3增長到12。

表1 參數(shù)設(shè)置Table 1 Parameter settings

圖9繪制了T在3到12之間變化時系統(tǒng)仿真和理論分析的吞吐量(分別由藍(lán)線和紅線表示)。從圖9可以看出，吞吐量隨著T增加而減少。原因如下：一方面，當(dāng)將perr設(shè)置為0.1時，隨著T的增加，VM上發(fā)生錯誤的可能性也會增加。另一方面，如果T較長，則等于Watchdog閾值的固定平均網(wǎng)絡(luò)延遲將導(dǎo)致FA和FAErr的概率更高，從而終止正常運(yùn)行的VM，降低吞吐量。

圖9 Thg隨著成功執(zhí)行一個任務(wù)時間的變化趨勢Fig.9 System throughput varies as time of successfully executing a task varies

圖10繪制了當(dāng)T在3到12之間變化時，F(xiàn)A，Det，Miss和FAErr的概率變化圖。從圖10中，有以下觀察結(jié)果。

圖10 各種情況下事件發(fā)生的概率隨著成功執(zhí)行一個任務(wù)時間的變化趨勢Fig.10 Probabilities of event of each case happening vary as time of successfully executing a task varies

(1) 隨著T增加，Normal概率降低。這是由于隨著T增加，F(xiàn)A和FAErr發(fā)生概率增加且概率值增加到非常大，這意味著FA和FAErr事件都占用了整個系統(tǒng)運(yùn)行的時間。

(2) FA的概率先緩慢增加然后降低，而FAErr的概率隨著T的增加而急劇增加。原因可以解釋如下：當(dāng)錯誤概率設(shè)置為0.1時，隨著T的增加，在任務(wù)執(zhí)行過程中任何時間都不會發(fā)生錯誤的概率將迅速下降。結(jié)果，F(xiàn)A的概率首先緩慢增加到最大值，然后降低，因?yàn)闆]有遇到錯誤的VM數(shù)量迅速變小。但是，將錯誤概率設(shè)置為0.1時，發(fā)生錯誤的概率幾乎不會降低，并且遇到錯誤的VM數(shù)量也不會改變太多。因此，F(xiàn)AErr的概率迅速增加。

(3) 隨著T的增加，Det的概率增加而Miss的概率減小。這是因?yàn)槠骄W(wǎng)絡(luò)延遲越接近CFN-Watchdog閾值，越容易出現(xiàn)kick數(shù)據(jù)包的網(wǎng)絡(luò)延遲超過閾值的情況。因此，更容易觸發(fā)bite數(shù)據(jù)包的發(fā)送。T越長，bite數(shù)據(jù)包就越有機(jī)會到達(dá)VM，這導(dǎo)致Det的概率增加而Miss的概率降低。

在表1的設(shè)置(b)下，圖11和圖12展示了Thg和Normal，F(xiàn)A，Det，Miss，F(xiàn)AErr的概率。本文將平均網(wǎng)絡(luò)延遲1 /λ的值從0.5～5，同時將其余參數(shù)的每個參數(shù)保持為固定值。

圖11顯示系統(tǒng)吞吐量首先下降到最小值，然后隨著平均網(wǎng)絡(luò)延遲從0.5～5的變化而緩慢增加。下降的主要原因是FA和FAErr的概率都有所增加，而增長的主要原因是，F(xiàn)A和FAErr的概率都緩慢遞減了。這意味著FA和FAErr事件占據(jù)整個系統(tǒng)運(yùn)行時間的時間首先增加，然后緩慢減少。

圖11 Thg隨著平均網(wǎng)絡(luò)時延的變化趨勢Fig.11 System throughput varies as mean network delay varies

圖12分別繪制了平均網(wǎng)絡(luò)延遲1 /λ在0.5～5之間變化時Normal，F(xiàn)A，Det，Miss和FAErr的概率趨勢，在此圖中，有以下觀察結(jié)果。

圖12 各種情況下事件發(fā)生的概率隨著平均網(wǎng)絡(luò)時延的變化趨勢Fig.12 Probabilities of event of each case happening vary as mean network delay varies

(1) FA和FAErr的概率均隨著1 /λ的增加先增長后遞減。當(dāng)平均網(wǎng)絡(luò)延遲小于并接近閾值時，kick數(shù)據(jù)包發(fā)生超時的概率增加，這使得bite數(shù)據(jù)包的觸發(fā)變得更加容易。因此，F(xiàn)A和FAErr的概率都首先增加。當(dāng)平均網(wǎng)絡(luò)延遲大于閾值時，即使kick數(shù)據(jù)包超時的概率較高，但bite包發(fā)生超時的概率也較高，這降低了FA和FAErr的概率。

(2) Normal的概率先降低，然后隨著1 /λ的增加而緩慢增加。原因是使用固定的perr且沒有錯誤發(fā)生時，將發(fā)生誤報事件或正常事件。因此，Normal的概率趨勢與FA的趨勢相反，F(xiàn)A的趨勢的原因已在上面說明。

(3) 隨著1 /λ的增加，Det的概率降低，而Miss的概率增加。這是因?yàn)楫?dāng)平均網(wǎng)絡(luò)延遲變大時，bite數(shù)據(jù)包將具有更高的網(wǎng)絡(luò)延遲。這意味著bite數(shù)據(jù)包將晚于時間T到達(dá)VM管理器。因此，當(dāng)1 /λ增大時，檢測事件發(fā)生的概率就會降低，而丟失檢測事件的發(fā)生概率會更高。

圖13和圖14分別繪制了Thg，Normal，F(xiàn)A，Det，Miss，F(xiàn)AErr的概率變化趨勢。通過在表1中的設(shè)置(c)進(jìn)行仿真和理論計算來獲得這些結(jié)果。在此仿真中，設(shè)置參數(shù)T，1 /λ和r，但perr的范圍為0.001～0.018，采用的值要比之前的實(shí)驗(yàn)小得多。

圖13繪制了perr在0.001～0.018之間變化時的吞吐量圖。從圖中可以看出，吞吐量隨著perr的增加而降低。原因如下：一方面，由于每次發(fā)生VM錯誤的概率非常小，因此Det，Miss和FAErr的概率非常小。但是，隨著perr的增加，接近T的高平均網(wǎng)絡(luò)延遲1 /λ導(dǎo)致Miss的概率增加，從而使吞吐量下降。另一方面，當(dāng)平均網(wǎng)絡(luò)延遲1 /λ等于閾值r時，發(fā)生虛假警報事件，這也降低了吞吐量。

圖13 Thg隨著單位時間VM出錯概率的變化趨勢Fig.13 System throughput varies as probability of VM error per unit time varies

圖14顯示了當(dāng)perr從0.001增加到0.018時，F(xiàn)A，Det，Miss和FAErr的概率趨勢，具體如下：

圖14 各種情況下事件發(fā)生的概率隨著單位時間VM出錯概率的變化趨勢Fig.14 Probabilities of event of each case happening vary as probability of VM error per unit time varies

(1) 隨著perr的增加，F(xiàn)A的概率會緩慢下降，因?yàn)殡S著perr的增加，VM沒有錯誤發(fā)生的概率會降低。

(2) 當(dāng)perr減小時，漏檢的概率增加。這是因?yàn)閂M的執(zhí)行過程中發(fā)生錯誤的概率隨perr的增加以及與T和閾值r接近的平均網(wǎng)絡(luò)延遲而增加，使得bite數(shù)據(jù)包的超時更容易發(fā)生。

(3) Det和FAErr的概率相對較小，因?yàn)榇朔抡鎸?shí)驗(yàn)中采用的perr非常小。并且隨著perr的增加，Det和FAErr的概率不斷增加，因?yàn)榘l(fā)生錯誤的概率也隨之增加。

圖15繪制了系統(tǒng)吞吐量，其中Watchdog的閾值r在1～11之間變化，其中T=12，1/λ=0.3和perr=0.01，如表1的設(shè)置(d)所示。從該圖可以看出，吞吐量首先增加到最大值，然后減小，并且有一個Watchdog的最佳閾值設(shè)置，即r=2。原因如下：在固定的平均網(wǎng)絡(luò)延遲設(shè)置為0.3的情況下，當(dāng)r≤2時，吞吐量會由于虛警事件的概率降低而增加。當(dāng)r>2時，吞吐量降低，因?yàn)閞越大，漏檢事件的概率就越高。

圖15 Thg隨著看門狗閾值的變化趨勢Fig.15 System throughput varies as threshold for watchdog varies

圖16繪制了系統(tǒng)正常完成的任務(wù)數(shù)量變化圖，該數(shù)量變化隨著單位時間VM的perr從0.01～0.15變化(如橫軸所示)。實(shí)驗(yàn)中，將設(shè)置T=12，1/λ=0.3。圖中：灰色矩形框表示無Watchdog配置情況下系統(tǒng)正常完成的任務(wù)數(shù)量(簡稱為No-Watchdog-Scheme)；藍(lán)色線條表示配置了本文所提出的Watchdog情況下系統(tǒng)正常完成的任務(wù)數(shù)量(簡稱為Watchdog-Scheme)，其中Watchdog的閾值r設(shè)置為2；帶圓圈的虛線為Watchdog-Scheme相對于No-Watchdog-Scheme的系統(tǒng)正常完成的任務(wù)數(shù)量增長比。

圖16 正常完成任務(wù)的數(shù)量隨著單位時間VM出錯概率的變化趨勢Fig.16 Amount of normally finished tasks varies as probability of VM error per unit time varies

從圖16中，可以看出：

(1) 隨著perr的增加，No-Watchdog-Scheme和Watchdog-Scheme的正常完成任務(wù)數(shù)量均減小，但Watchdog-Scheme的系統(tǒng)正常完成任務(wù)數(shù)量一直比No-Watchdog-Scheme多。這是因?yàn)閃atchdog能夠提前檢測出發(fā)生故障的VM，及時將其資源釋放用于執(zhí)行下一個任務(wù)，從而使Watchdog-Scheme能夠獲得更多正常完成的任務(wù)數(shù)量。

(2) 隨著perr的增加，Watchdog-Scheme相對于No-Watchdog-Scheme的系統(tǒng)正常完成的任務(wù)數(shù)量增長比不斷增大，當(dāng)perr達(dá)到0.15時，該比例可達(dá)0.748 1(即74.81%)。從此可看出，Watchdog-Scheme在perr增大時有顯著的優(yōu)勢，即能夠顯著增加系統(tǒng)正常完成的任務(wù)數(shù)量，使系統(tǒng)的吞吐量增加。

此外，由于仿真結(jié)果與理論結(jié)果之間的平均相對誤差在圖9，圖11，圖13和圖15中均低于0.4%，因此本文的理論模式的準(zhǔn)確性很高。

6 總結(jié)

在邊緣計算中，CFN最近被提出以加速資源調(diào)度和任務(wù)分配。它要求實(shí)時了解本地和遠(yuǎn)程計算資源的可用狀態(tài)。本文首先提出了一種名為CFN-Watchdog的集中式故障檢測協(xié)議，提供CFN所需的可見性。本文的Watchdog協(xié)議可以及時回收故障所占用的資源，并顯著地提高系統(tǒng)吞吐量。建立了一個理論模型，分析各種設(shè)計參數(shù)對系統(tǒng)吞吐量的影響。進(jìn)行了大量的仿真，驗(yàn)證了本文提出的協(xié)議非常有效，并且理論模型非常準(zhǔn)確。