王軍曉 齊 恒 李克秋 周曉波

1(大連理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院 遼寧大連 116024) 2 (天津大學(xué)計算機科學(xué)與技術(shù)學(xué)院 天津 300072) (wangjunxiao@mail.dlut.edu.cn)

鏈路故障檢測作為一種十分重要的網(wǎng)絡(luò)性能保障手段，目前已被廣泛應(yīng)用于大規(guī)模網(wǎng)絡(luò)環(huán)境中，例如數(shù)據(jù)中心網(wǎng)絡(luò)等[1].鏈路故障檢測可以為許多大規(guī)模在線業(yè)務(wù)例如搜索引擎、社交網(wǎng)絡(luò)、文件系統(tǒng)等提供網(wǎng)絡(luò)連通性方面的保障.隨著網(wǎng)絡(luò)規(guī)模的增長、鏈路數(shù)量的上升，如何快速地、實時地完成探測成為鏈路故障檢測中的一個重要挑戰(zhàn)[2].

傳統(tǒng)被動式的檢測辦法依賴于簡單網(wǎng)絡(luò)管理協(xié)議(simple network management protocol, SNMP)查詢網(wǎng)絡(luò)設(shè)備例如路由器或交換機中的計數(shù)器，或通過命令行界面(command line interface, CLI)登錄到網(wǎng)絡(luò)設(shè)備上查看運行信息.這些方法在網(wǎng)絡(luò)設(shè)備不發(fā)生故障的情況下可以檢測出一些問題，例如設(shè)備端口故障.但是一旦與網(wǎng)絡(luò)設(shè)備間的連接發(fā)生中斷，這些檢測方法將無法正常工作.此外，這些方法需要對網(wǎng)絡(luò)設(shè)備進(jìn)行配置，因此很難適應(yīng)網(wǎng)絡(luò)設(shè)備的升級、服務(wù)的遷移、網(wǎng)絡(luò)規(guī)模的擴展.

網(wǎng)絡(luò)功能虛擬化(network function virtualiza-tion, NFV)[3]概念的出現(xiàn)為鏈路故障檢測的實現(xiàn)方法帶來了更多的可能性.網(wǎng)絡(luò)功能虛擬化的思想由眾多運營商例如AT&T、中國移動等提出，目前已經(jīng)被逐漸應(yīng)用于簡化網(wǎng)絡(luò)服務(wù)的部署難度方面以及加快網(wǎng)絡(luò)服務(wù)的升級速度方面.從2012年起，歐洲電信標(biāo)準(zhǔn)化協(xié)會ETSI發(fā)布了一系列關(guān)于網(wǎng)絡(luò)功能虛擬化的白皮書，介紹了其面臨的機遇與挑戰(zhàn)、標(biāo)準(zhǔn)架構(gòu)以及演進(jìn)方向.網(wǎng)絡(luò)功能虛擬化的思想是利用標(biāo)準(zhǔn)IT虛擬化技術(shù)，將傳統(tǒng)網(wǎng)絡(luò)服務(wù)轉(zhuǎn)化為可運行于通用x86平臺服務(wù)器之上的軟件服務(wù).這些基于軟件驅(qū)動的網(wǎng)絡(luò)服務(wù)可以實現(xiàn)按需彈性供給，而不需要對原有設(shè)備進(jìn)行變動.網(wǎng)絡(luò)管理者可以靈活地創(chuàng)建、刪除或升級特定的網(wǎng)絡(luò)服務(wù)，大大降低了網(wǎng)絡(luò)服務(wù)的部署和維護(hù)成本.除此之外，網(wǎng)絡(luò)服務(wù)的部署方式從傳統(tǒng)的基于設(shè)備的集中式部署模式轉(zhuǎn)化為支持分布式的部署模式，部署于多個服務(wù)器上的虛擬網(wǎng)絡(luò)服務(wù)可以聯(lián)合提供一種復(fù)雜的網(wǎng)絡(luò)功能.這種分布式的部署模式有利于服務(wù)實例間的負(fù)載均衡和故障切換.

基于網(wǎng)絡(luò)功能虛擬化，一些主動式的檢測辦法出現(xiàn).Pingmesh[4]通過發(fā)送基于端到端的探針實現(xiàn)了虛擬的鏈路故障檢測功能.由于這些探針是由運行于服務(wù)器中的軟件服務(wù)進(jìn)行管理，使得該方法不涉及網(wǎng)絡(luò)設(shè)備，因此不需要對網(wǎng)絡(luò)設(shè)備進(jìn)行配置，也不需要保持與網(wǎng)絡(luò)設(shè)備之間的連接，可以更好地體現(xiàn)出對場景的適應(yīng)性，從而檢測出更多情況下的鏈路故障.然而，Pingmesh在網(wǎng)絡(luò)中每對服務(wù)器之間維護(hù)一個探針.當(dāng)網(wǎng)絡(luò)規(guī)模擴展時，需要維護(hù)的探針數(shù)量將以指數(shù)級增長，導(dǎo)致每次探測的用時過長，同時產(chǎn)生過多的帶寬負(fù)載，難以實現(xiàn)實時的、快速的探測.

我們發(fā)現(xiàn)導(dǎo)致以上問題的根本原因是缺乏對探測路徑的選擇.在如圖1所示場景，我們可以借助一些其他技術(shù)獲取到網(wǎng)絡(luò)中服務(wù)器間的路徑信息，例如借助軟件定義網(wǎng)絡(luò)(SDN)技術(shù)[5]，從管理底層網(wǎng)絡(luò)的SDN控制器集群處獲取可用路徑.但我們不依賴控制器集群對這些可用路徑進(jìn)行鏈路故障檢測(SDN控制器有時檢測到的故障是控制器與轉(zhuǎn)發(fā)設(shè)備之間的控制信道連接故障而不是真正的數(shù)據(jù)平面故障).如果我們可以僅用網(wǎng)絡(luò)中的一部分路徑而不是全部路徑作為鏈路故障檢測時的探測路徑并發(fā)送端到端探針，那么就有可能降低維護(hù)探針的代價，減少每次探測的用時，降低探測流對正常工作負(fù)載流的影響，從而實現(xiàn)一種新型的虛擬化網(wǎng)絡(luò)功能，以支持面向大規(guī)模數(shù)據(jù)中心網(wǎng)絡(luò)的鏈路故障實時檢測即服務(wù).

Fig. 1 The architecture of virtualized link fault detection function圖1 虛擬化鏈路故障檢測功能架構(gòu)

因此，我們提出一種新型的主動式的、基于網(wǎng)絡(luò)功能虛擬化的鏈路故障檢測架構(gòu)，如圖1所示.該架構(gòu)主要由3部分構(gòu)成：SDN控制器集群[6]、鏈路故障檢測控制器和探針代理.其中SDN控制器集群與底層網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)設(shè)備建立連接，從底層網(wǎng)絡(luò)獲取轉(zhuǎn)發(fā)路徑信息與鏈路拓?fù)湫畔?當(dāng)SDN控制器集群改變拓?fù)浣Y(jié)構(gòu)時，例如SDN控制器集群下發(fā)命令將轉(zhuǎn)發(fā)設(shè)備的某些端口禁用等，SDN控制器集群可以及時將這些拓?fù)涞淖兓扑徒o鏈路故障檢測控制器.故障檢測控制器作為虛擬化鏈路故障檢測功能的大腦，從SDN控制器集群獲取最新的轉(zhuǎn)發(fā)路徑信息，執(zhí)行探測路徑選擇算法，從所有底層轉(zhuǎn)發(fā)路徑中選擇一部分路徑作為探測路徑，并建立探測路徑與探針代理之間的映射.探針代理被部署在底層網(wǎng)絡(luò)的服務(wù)器中，并與故障檢測控制器保持連接.其中，被探測路徑映射到的探針代理與故障檢測控制器間的連接被激活.這些連接被激活的探針代理可以從故障檢測控制器處接收探針地址，并以自身的網(wǎng)絡(luò)地址為源地址，以探針地址為目的地址構(gòu)建并發(fā)送網(wǎng)絡(luò)探針.當(dāng)某個探針代理收到其他探針代理返回的對于自己探針的回復(fù)時，該探針代理將構(gòu)建鏈路正常的消息發(fā)送給故障檢測控制器，否則構(gòu)建發(fā)現(xiàn)故障的消息發(fā)送給故障檢測控制器.

本文的主要貢獻(xiàn)有4個方面：

1) 提出了一種在已知底層轉(zhuǎn)發(fā)路徑的前提下，僅基于端到端測量即可實現(xiàn)鏈路故障檢測的鏈路故障實時檢測即服務(wù)架構(gòu)；

2) 采用了基于貪婪策略的探測矩陣近似優(yōu)化算法，可以有效減少探測路徑數(shù)量，從而使實時探測成為可能；

3) 在減少探測路徑數(shù)量的基礎(chǔ)上，我們還針對探測路徑的質(zhì)量進(jìn)行分析，并結(jié)合了2種可反映探測路徑質(zhì)量的指標(biāo)，實現(xiàn)高質(zhì)量探測路徑的選擇.

4) 基于仿真的實驗結(jié)果表明，我們提出的實時探測方法與之前工作中的方法相比，在單次探測用時、網(wǎng)絡(luò)帶寬占用以及端點負(fù)載方面具有明顯優(yōu)勢，且優(yōu)化探測矩陣所帶來的開銷是可容忍的.

1 相關(guān)工作

鏈路故障的快速檢測是大規(guī)模網(wǎng)絡(luò)系統(tǒng)中的一個被廣泛關(guān)注的問題.針對這個問題，近年來許多網(wǎng)絡(luò)監(jiān)控系統(tǒng)被提出，例如Pingmesh[4]，它將整個底層網(wǎng)絡(luò)看作是一個黑盒系統(tǒng)，然后考慮如何在網(wǎng)絡(luò)邊緣的服務(wù)器之間構(gòu)建端到端的探測路徑.這種方式雖然在理論上可以測量出任何故障場景下，網(wǎng)絡(luò)邊緣端到端的鏈路故障，無論這些鏈路故障是基于軟件層面的、操作系統(tǒng)內(nèi)核層面的、網(wǎng)卡層面的、轉(zhuǎn)發(fā)設(shè)備芯片層面的、安全層面的或是線纜層面的.但是這種檢測方法在網(wǎng)絡(luò)規(guī)模大幅度擴展的情況下，相應(yīng)的探測路徑會成指數(shù)級增長.這樣會導(dǎo)致單次探測的用時無法被控制在一定范圍內(nèi)，大量的探測路徑報文傳輸和端到端探針維護(hù)工作會給底層網(wǎng)絡(luò)的帶寬以及邊緣服務(wù)器處理能力帶來顯著的壓力，并且這種常駐性負(fù)載在服務(wù)高峰時可能導(dǎo)致業(yè)務(wù)應(yīng)用相關(guān)的工作負(fù)載和傳輸受到嚴(yán)重影響.

Duffield最先提出了一種名為布爾網(wǎng)絡(luò)診斷的技術(shù)[7].隨后在這項技術(shù)的基礎(chǔ)上出現(xiàn)了許多其他工作，例如Cunha等人的工作[8]、Netdiagnoser[9]，Nguyen等人的工作[10-11]、PlanetSeer[12]還有Zhao等人的工作[13].這些工作基于的假設(shè)都是探測路徑是不變且不可控的.基于該假設(shè)，導(dǎo)致這些工作很難實現(xiàn)覆蓋整個底層網(wǎng)絡(luò)的鏈路故障檢測.NetSonar[14]則考慮探測路徑是變化的，即改變探針代理的部署從而改變探測路徑，這樣就可以實現(xiàn)對整個底層網(wǎng)絡(luò)的鏈路故障檢測，但由于該方法考慮特殊的骨干網(wǎng)應(yīng)用場景，導(dǎo)致該方法的擴展性較差.

與基于端到端探針實現(xiàn)的探測方法不同，Sharma等人利用網(wǎng)絡(luò)編碼的方式實現(xiàn)探測[15]，類似的工作還有Yao等人[16]、Kandula等人[17]以及Herodotou等人[18]的網(wǎng)絡(luò)診斷工作.其中，有些工作借助轉(zhuǎn)發(fā)設(shè)備的日志信息實現(xiàn)探測，還有一些工作借助多播技術(shù)實現(xiàn)探測.在網(wǎng)絡(luò)監(jiān)控方面，Pivot Tracing[19]考慮以分布式的方式從底層網(wǎng)絡(luò)中收集數(shù)據(jù)并進(jìn)行分析從而找到造成鏈路故障的根本原因.LossRadar[20]提出一種基于轉(zhuǎn)發(fā)設(shè)備實現(xiàn)的監(jiān)控手段，該方法需要可編程設(shè)備支持.文獻(xiàn)[21]提出一種基于OpenFlow協(xié)議的鏈路故障檢測方案，與本文方法相比，其檢測到的故障有可能來自控制器與轉(zhuǎn)發(fā)設(shè)備之間的控制信道連接故障而不是真正的數(shù)據(jù)平面故障.

綜合來看，現(xiàn)有相關(guān)工作中缺乏對大規(guī)模網(wǎng)絡(luò)場景下實時探測的關(guān)注.這一研究現(xiàn)狀驅(qū)動我們?nèi)ピO(shè)計一種能夠?qū)崟r快速檢測故障鏈路的方法.

2 最少探測路徑數(shù)量問題

本節(jié)主要介紹如何用矩陣的方式去定義一個最少探測路徑數(shù)量問題，并說明該問題的解決思想.

2.1 基于轉(zhuǎn)發(fā)設(shè)備故障的探測矩陣

我們將任意底層網(wǎng)絡(luò)G定義為

G=(P,N)，

(1)

其中，P是網(wǎng)絡(luò)G中所有轉(zhuǎn)發(fā)路徑的集合，N是G中所有轉(zhuǎn)發(fā)設(shè)備的集合.我們將轉(zhuǎn)發(fā)路徑與轉(zhuǎn)發(fā)設(shè)備之間的關(guān)系矩陣R定義為

(2)

其中，當(dāng)轉(zhuǎn)發(fā)設(shè)備位于轉(zhuǎn)發(fā)路徑之上時，關(guān)系矩陣R中對應(yīng)位置的值為1，否則值為0.關(guān)系矩陣R可以看成由多個行向量構(gòu)成的集合，其中每個行向量對應(yīng)一條轉(zhuǎn)發(fā)路徑.探測矩陣是由行向量所構(gòu)成的矩陣，其中探測路徑由轉(zhuǎn)發(fā)路徑構(gòu)成.根據(jù)探測矩陣可以確定探針依次經(jīng)過哪些轉(zhuǎn)發(fā)設(shè)備.

我們假設(shè)某一底層網(wǎng)絡(luò)G的拓?fù)淙鐖D2所示.根據(jù)探測矩陣的定義，可以寫出G的含有2條探測路徑的探測矩陣D為

(3)

這2條探測路徑分別依次經(jīng)過N1，N2，N5三個轉(zhuǎn)發(fā)設(shè)備以及N1，N3，N6三個轉(zhuǎn)發(fā)設(shè)備.假設(shè)我們分別在這2條探測路徑的源頭發(fā)送探針，一段時間后如果我們能收到探測路徑另一側(cè)回復(fù)的探針，就說明這條探測路徑上的轉(zhuǎn)發(fā)設(shè)備及其鏈路是正常的，否則就說明這條探測路徑上發(fā)生了鏈路故障.如果N2對應(yīng)的轉(zhuǎn)發(fā)設(shè)備發(fā)生了單點故障，那么第1條路徑上的探測結(jié)果應(yīng)為故障，第2條路徑結(jié)果應(yīng)為正常.同理，如果N5對應(yīng)的轉(zhuǎn)發(fā)設(shè)備發(fā)生了單點故障，2條路徑上的探測結(jié)果也是相同的.通過觀察可以發(fā)現(xiàn)，造成這2種情況下探測結(jié)果相同的根本原因是N2和N5對應(yīng)的轉(zhuǎn)發(fā)設(shè)備在探測矩陣中的列向量是完全相同的.

Fig. 2 The example network圖2 示意網(wǎng)絡(luò)圖

引理1. 如果某個轉(zhuǎn)發(fā)設(shè)備在探測矩陣中的列向量與其他轉(zhuǎn)發(fā)設(shè)備的列向量都不相同，那么當(dāng)該轉(zhuǎn)發(fā)設(shè)備發(fā)生單點故障時，相應(yīng)的鏈路故障可被探針檢測到.

根據(jù)引理1可以發(fā)現(xiàn)，N1對應(yīng)的轉(zhuǎn)發(fā)設(shè)備在探測矩陣中的列向量與其他轉(zhuǎn)發(fā)設(shè)備的列向量都不相同，因此當(dāng)N1對應(yīng)的轉(zhuǎn)發(fā)設(shè)備發(fā)生單點故障時，相應(yīng)的鏈路故障可被探針檢測到.雖然N4對應(yīng)的轉(zhuǎn)發(fā)設(shè)備在探測矩陣中的列向量也與其他轉(zhuǎn)發(fā)設(shè)備的列向量都不相同，但由于沒有探測路徑經(jīng)過該轉(zhuǎn)發(fā)設(shè)備，因此也無法根據(jù)探測結(jié)果推斷其是否發(fā)生故障.

如果我們將列向量相同的轉(zhuǎn)發(fā)設(shè)備歸為一組，那么可以認(rèn)為上面的探測矩陣將轉(zhuǎn)發(fā)設(shè)備分成了4組，分別是(N1)，(N2,N5)，(N3,N6)以及(N4,N7)，其中N7對應(yīng)的轉(zhuǎn)發(fā)設(shè)備是我們虛構(gòu)的轉(zhuǎn)發(fā)設(shè)備，用來代指探測路徑不可達(dá)的轉(zhuǎn)發(fā)設(shè)備.

引理2. 如果探測矩陣中的每個列向量都不相同，那么在每個轉(zhuǎn)發(fā)設(shè)備發(fā)生單點故障時，相應(yīng)的鏈路故障都可被探針檢測到.且這種功能的探測矩陣可以從初始探測矩陣(一般為關(guān)系矩陣)中構(gòu)建.

下面以一個例子對引理2展開進(jìn)一步說明.如圖2所示，分別以N1和N4對應(yīng)的轉(zhuǎn)發(fā)設(shè)備為探測路徑的源頭，構(gòu)建一個初始的探測矩陣：

(4)

根據(jù)引理2可知，該初始探測矩陣可以探測出所有轉(zhuǎn)發(fā)設(shè)備的單點故障.那么接下來，我們從中選擇探測矩陣式(3)的2條探測路徑構(gòu)成一個新的探測矩陣：

(5)

該探測矩陣中的轉(zhuǎn)發(fā)設(shè)備被分成了4組，分別是(N1)，(N2,N5)，(N3,N6)以及(N4,N7).從初始探測矩陣中其余的探測路徑中選擇一條加入該探測矩陣，新加入的探測路徑應(yīng)使得分組被分解得更為分散.根據(jù)這個原則，進(jìn)一步構(gòu)建探測矩陣：

(6)

該探測矩陣中的轉(zhuǎn)發(fā)設(shè)備被分成了7組，分別是(N1)，(N2)，(N3)，(N4)，(N5)，(N6)，(N7).根據(jù)引理2可知，該探測矩陣具備和初始探測矩陣一致的功能，且與初始探測矩陣相比，探測路徑的數(shù)量由初始的9條減少到現(xiàn)在的3條.

2.2 基于端口連接故障的探測矩陣

2.1節(jié)介紹的探測矩陣是基于轉(zhuǎn)發(fā)設(shè)備單點故障的.現(xiàn)在，我們考慮基于端口連接單點故障的探測矩陣.即假設(shè)在任意時間內(nèi)只有一條端口連接發(fā)生故障，我們可以通過探測結(jié)果推斷出故障點是哪條端口連接.

首先，我們將前面提到的任意底層網(wǎng)絡(luò)G中的每個轉(zhuǎn)發(fā)設(shè)備看成一條端口連接，將每條端口連接看成一個轉(zhuǎn)發(fā)設(shè)備，并進(jìn)行如圖3所示的轉(zhuǎn)換.將轉(zhuǎn)換后的底層網(wǎng)絡(luò)定義為

(7)

(8)

(9)

我們將該關(guān)系矩陣作為初始探測矩陣，圖3(b)中L4對應(yīng)的端口連接是我們虛構(gòu)的端口連接，用來代指探測路徑不可達(dá)的端口連接.

Fig. 3 The example of transformation圖3 轉(zhuǎn)換示意圖

引理3. 如果探測矩陣中的每個列向量都不相同，那么在每個端口連接發(fā)生單點故障時，相應(yīng)的鏈路故障都可被探針檢測到.且這種功能的探測矩陣可以從初始探測矩陣(一般為關(guān)系矩陣)中構(gòu)建.

如圖3所示，任何一個基于端口連接的探測矩陣都可以找到與其對應(yīng)的基于轉(zhuǎn)發(fā)設(shè)備的探測矩陣，其中，轉(zhuǎn)換方式是將底層網(wǎng)絡(luò)中的每個轉(zhuǎn)發(fā)設(shè)備看成一條端口連接，將每條端口連接看成一個轉(zhuǎn)發(fā)設(shè)備.根據(jù)引理2可知，轉(zhuǎn)換后的探測矩陣滿足引理3的性質(zhì)，從而可以證明引理3的正確性.

根據(jù)引理3可以發(fā)現(xiàn)，上面的初始探測矩陣將端口連接分成了4組，分別是(L1)，(L2)，(L3)，(L4)，因此在任意時間內(nèi)只有一條端口連接發(fā)生故障的前提下，該探測矩陣可根據(jù)探測結(jié)果推斷出故障點是哪條端口連接.

事實上，我們還可以構(gòu)建包含更少探測路徑的探測矩陣，例如構(gòu)建只包含第1條探測路徑和第2條探測路徑的探測矩陣：

(10)

可見，在只有一條端口連接發(fā)生故障的情況下，我們可通過優(yōu)化探測矩陣的方式，將探測路徑的數(shù)量由初始的3條減少到現(xiàn)在的2條.

值得注意的是:對于大部分?jǐn)?shù)據(jù)中心底層網(wǎng)絡(luò)，特別是冗余端口連接較多的底層網(wǎng)絡(luò)，例如fat-tree拓?fù)?，端口連接的數(shù)量通常大于轉(zhuǎn)發(fā)設(shè)備的數(shù)量.因此，通過對比2.1節(jié)和2.2節(jié)可以發(fā)現(xiàn)，同基于轉(zhuǎn)發(fā)設(shè)備的探測相比，基于端口連接進(jìn)行探測往往需要構(gòu)建包含更多探測路徑的探測矩陣，但同時也帶來了更細(xì)粒度的基于端口級別的探測.

2.3 探測矩陣優(yōu)化

從2.1節(jié)和2.2節(jié)中分析可知，無論是基于轉(zhuǎn)發(fā)設(shè)備的探測矩陣還是基于端口連接的探測矩陣，都可以通過對探測矩陣的優(yōu)化實現(xiàn)探測路徑數(shù)量的減少.因此，我們考慮如何優(yōu)化探測矩陣才能實現(xiàn)最少的探測路徑數(shù)量，從而降低探測的代價.以2.1節(jié)中的基于轉(zhuǎn)發(fā)設(shè)備故障的探測矩陣為例(基于端口連接故障同理)，可以定義轉(zhuǎn)發(fā)設(shè)備的初始集合：

S0={{N1,N2,N3,N4,N5,N6,N7}}，

(11)

我們從其初始探測矩陣中選擇一條探測路徑：

(12)

構(gòu)建一個只含有該探測路徑的探測矩陣，轉(zhuǎn)發(fā)設(shè)備因此被該探測矩陣分解為(N1,N2,N5)和(N3,N4,N6,N7)兩部分.通過觀察，該探測路徑經(jīng)過(N1,N2,N5)，但不經(jīng)過(N3,N4,N6,N7).可知，被該探測路徑經(jīng)過的部分形成了一個子集，沒有被該探測路徑經(jīng)過的部分形成了另外一個子集：

S1={{N1,N2,N5},{N3,N4,N6,N7}}，

(13)

接下來，向該探測矩陣中加入一條探測路徑：

(14)

轉(zhuǎn)發(fā)設(shè)備被該探測矩陣分解為(N1)，(N2,N5)，(N3,N6)以及(N4,N7)四部分.通過觀察，可以發(fā)現(xiàn)這4組分別表示2條探測路徑都經(jīng)過、第1條路徑經(jīng)過而第2條路徑不經(jīng)過、第1條路徑不經(jīng)過而第2條路徑經(jīng)過以及2條路徑都不經(jīng)過.可知，(N1,N2,N5)中被新的探測路徑經(jīng)過的部分形成了一個子集，沒有被新的探測路徑經(jīng)過的部分形成了另外一個子集.同理，(N3,N4,N6,N7)中也根據(jù)有沒有被新的探測路徑經(jīng)過形成了2個子集：

S2={{N1},{N2,N5},{N3,N6},{N4,N7}}，

(15)

最后，再向該探測矩陣中加入一條探測路徑：

(16)

同理，(N1)，(N2,N5)，(N3,N6)以及(N4,N7)中分別根據(jù)有沒有被新的探測路徑經(jīng)過各形成了2個子集：

S3={{N1},{N2},{N5},{N3},{N6},
{N4},{N7}}，

(17)

分解過程進(jìn)行到這一步，如果仍存在子集不由單個元素構(gòu)成，那么還需繼續(xù)向探測矩陣中添加新的探測路徑，直至所有形成的子集都是由單個元素構(gòu)成.

通過這種故障點集合分解的方法，我們可以獲得一個由初始探測矩陣(一般為關(guān)系矩陣)中探測路徑的子集構(gòu)成的探測矩陣，但這并不能保證該探測矩陣中包含的探測路徑數(shù)量是最優(yōu)的.并且，我們還發(fā)現(xiàn)當(dāng)探測路徑的數(shù)量達(dá)到最優(yōu)時，對應(yīng)的最優(yōu)探測矩陣可能并不是唯一的.

無論是基于轉(zhuǎn)發(fā)設(shè)備的探測矩陣還是基于端口連接的探測矩陣.假設(shè)探測路徑的數(shù)量是m，那么探測結(jié)果最多為2m種,并且其中有一種探測結(jié)果為無故障發(fā)生.假設(shè)需要檢測的故障點有n個，且在任意時間點只可能發(fā)生單點故障的情況下，理想上檢測所需的探測路徑數(shù)量為

(18)

當(dāng)然，具體數(shù)量還與底層網(wǎng)絡(luò)拓?fù)溆嘘P(guān).搜索最優(yōu)探測矩陣的過程中可以使用指數(shù)時間復(fù)雜度的窮舉搜索算法.但由于時間復(fù)雜度過高，在大規(guī)模場景下并不實用.因此，我們采用一種基于貪婪策略的近似算法對最優(yōu)探測矩陣進(jìn)行搜索.該近似算法的思想是：每次向探測矩陣中添加新的探測路徑時，選擇產(chǎn)生最大信息熵的探測路徑進(jìn)行添加.我們以一個例子來說明該近似算法的原理.假如，在第2次添加探測路徑時，選擇的探測路徑產(chǎn)生了情況的分解：

(19)

即使該分解可使3個子集只由單個元素組成，但由于其后還必須再添加至少2條探測路徑才能使所有子集都由單個元素構(gòu)成.相較之下，

S2={{N1},{N2,N5},{N3,N6},{N4,N7}}，

(20)

該分解雖然只能使一個子集由單個元素組成，但由于其后可能只需要再添加一條探測路徑就能使所有子集都由單個元素構(gòu)成，因此我們認(rèn)為它具有更大的混亂度，即信息熵，使得分解更接近于最終狀態(tài).進(jìn)而我們認(rèn)為后者探測路徑的優(yōu)先級比前者更高.

假設(shè)選擇并添加某條探測路徑后所對應(yīng)的分解M由i個子集構(gòu)成，那么將這i個子集分解到最終狀態(tài)還必須再添加的探測路徑可表示為

(21)

同時，這也是該探測路徑所對應(yīng)的信息熵的倒數(shù).

假設(shè)初始探測矩陣(一般為關(guān)系矩陣)中行向量的數(shù)量為x，那么當(dāng)每次選擇并添加探測路徑時，需要與其余候選的探測路徑所對應(yīng)的信息熵進(jìn)行比較，因此該算法的時間復(fù)雜度可表示為

(22)

3 探測路徑質(zhì)量問題

在本節(jié)中，我們主要介紹如何定義一條探測路徑的質(zhì)量，并說明如何找到滿足質(zhì)量的探測路徑.

3.1 探測路徑質(zhì)量標(biāo)準(zhǔn)

在減少探測路徑數(shù)量的基礎(chǔ)上，我們還需要針對探測路徑的質(zhì)量進(jìn)行分析，為此我們首先給出2個用于反映探測路徑質(zhì)量的指標(biāo).

定義1.Θ并發(fā)的探測矩陣.如果存在這樣的探測矩陣，在任意時間點至多有Θ個故障點同時發(fā)生故障的情況下，仍能夠根據(jù)探測結(jié)果推斷出故障點.我們將這樣的探測矩陣定義為Θ并發(fā)的探測矩陣.

前面提到的探測矩陣都是基于任意時間點只有一個故障點發(fā)生故障的，即在Θ=1的情況下，現(xiàn)在我們需要將這個前提進(jìn)行推廣.為此，我們以2.2節(jié)中底層網(wǎng)絡(luò)的關(guān)系矩陣為例進(jìn)行考慮，假設(shè)我們想要檢測出L1和L3對應(yīng)的端口連接可能同時發(fā)生故障，則需要構(gòu)建一個擴展的關(guān)系矩陣：

(23)

其中，最后一個列向量是對L1和L3對應(yīng)故障點列向量中的元素依次執(zhí)行或運算所生成的.通過這種構(gòu)建額外列向量的方式，我們可以在探測矩陣中表示可能同時發(fā)生的多個故障.假設(shè)需要檢測的故障點為n個，為了保證探測矩陣是Θ并發(fā)的，初始化階段應(yīng)額外構(gòu)建的列向量數(shù)目為

(24)

其中，全部故障點都發(fā)生故障與都正常同屬于Θ=1情況下.接下來，我們只需對構(gòu)建了額外列向量的關(guān)系矩陣實施2.3節(jié)中介紹的Θ=1情況下的分解步驟，最終就可以得到滿足Θ并發(fā)的探測矩陣.

定義2.Γ冗余的探測矩陣.如果每個故障點都被至少Γ條探測路徑經(jīng)過，滿足這樣條件的探測矩陣，我們將它定義為Γ冗余的探測矩陣.Γ冗余決定了故障點的探測可靠性，當(dāng)Γ>1時，有多條探測路徑經(jīng)過故障點，即使其中部分探測路徑失效(如轉(zhuǎn)發(fā)設(shè)備的緩存溢出導(dǎo)致探針丟失等)，也能使故障被正常檢測出來.

此外，通過Γ冗余還可以使探測路徑更為均勻地分布在需要檢測的故障點上，從而使鏈路故障檢測所帶來的額外負(fù)載能夠均衡分布在底層網(wǎng)絡(luò)中.為此，我們?yōu)槊恳粭l候選探測路徑設(shè)置了一個參數(shù)Φ：

(25)

其中，參數(shù)Φ表示分解過程中添加該探測路徑的優(yōu)先級；參數(shù)Δ是每個故障點的一個屬性，用于保障探測路徑的冗余性；參數(shù)Υ表示分解過程中與該探測路徑產(chǎn)生交集的子集數(shù)量.如果探測路徑的參數(shù)Φ較小，一方面說明它所經(jīng)過的故障點被已添加的探測路徑所覆蓋的程度較小，另一方面說明添加它對于分解過程所帶來的信息熵較大.可見，這樣設(shè)置既可保證探測的可靠性，又可保證探測負(fù)載的均衡性，還可保證探測路徑數(shù)量的最少化.

3.2 探測路徑選擇

基于以上2方面的探測路徑質(zhì)量指標(biāo)，我們采用了一種基于貪心策略的探測矩陣的近似優(yōu)化算法，如算法1所示.首先，算法1會根據(jù)Θ值構(gòu)建底層網(wǎng)絡(luò)的擴展關(guān)系矩陣，從而將Θ>1情況下的問題轉(zhuǎn)換為Θ=1情況下可以解決的問題.在每輪向探測矩陣中添加探測路徑之前，需要更新所有待選路徑的Φ值并以正序排列，然后選擇排序中第1條待選路徑作為探測路徑，并把它添加到探測矩陣中.最后，更新已選路徑上所有故障點的Δ值.算法1輸出探測矩陣的條件為，經(jīng)過若干輪路徑選擇后，所有故障點的Δ值都大于Γ且所有子集都由單個元素構(gòu)成.如果添加完所有路徑后仍然不能滿足條件，算法1將輸出找不到合適的探測矩陣.

算法1. 探測矩陣構(gòu)建算法.

輸入：關(guān)系矩陣R、并行度Θ、冗余度Γ、故障點集N；

輸出：探測矩陣D.

④ while (num≠|(zhì)N|‖points≠?) &&

paths≠? do

⑤ fori∈pathsdo

⑦ end for

⑨P←P∪{i}；

⑩paths←paths{i}；

引理4. 在探測路徑的數(shù)量最少化方面，該基于貪心策略的探測矩陣優(yōu)化算法的近似比為

(26)

其中，e為自然對數(shù).證明時，首先定義一個函數(shù)f：

(27)

由于探測路徑經(jīng)過的故障點數(shù)量應(yīng)大于分解過程中與該探測路徑產(chǎn)生交集的子集數(shù)量.可知：

(28)

(29)

根據(jù)式(28)(29)，Φ(Pi)的非負(fù)性得證.又因為：

f(s)≥0，

(30)

0≤f(S)≤f(S∪s)，

(31)

根據(jù)式(30)(31)，f的非負(fù)性得證，且f為單調(diào)非遞減.由于我們的目標(biāo)是最小化S的模，此時原目標(biāo)可以被轉(zhuǎn)換為最小化f.

由于越多的路徑被選擇，分解所產(chǎn)生的子集數(shù)量就會變得越多，同時與新加入路徑產(chǎn)生交集的子集數(shù)量也會變得越多.因此可以得到：

f(s|S)≤f(s|T)，

(32)

f(s|S)=f(S∪s)-f(S)，

(33)

其中，T?S.根據(jù)式(32)(33)，f的子模性得證.由于目標(biāo)的非負(fù)性、單調(diào)性以及子模性都可以得到證明，因此該近似算法的近似比可以得到證明.

由于該算法的時間復(fù)雜度為關(guān)系矩陣中轉(zhuǎn)發(fā)路徑數(shù)量的平方級，因此如何有效降低算法的執(zhí)行時間是一個需要考慮的問題.我們選擇從2個方面進(jìn)行優(yōu)化:

1) 基于底層網(wǎng)絡(luò)的關(guān)系矩陣構(gòu)建一張二分圖，圖中的一個點集代表故障點，另一個點集代表轉(zhuǎn)發(fā)路徑，兩點之間若存在邊則代表故障點位于轉(zhuǎn)發(fā)路徑之上.如果某2條轉(zhuǎn)發(fā)路徑所經(jīng)過的故障點完全不同，則形成更小規(guī)模的子圖以及子關(guān)系矩陣.經(jīng)過這樣的處理，原問題可被拆分為多個獨立的子問題，在每個子問題中算法可以并行執(zhí)行.通過線性時間的算法可實現(xiàn)對二分圖的一次遍歷以及對子問題的拆分.

2) 基于數(shù)據(jù)中心底層網(wǎng)絡(luò)的拓?fù)鋵ΨQ性，當(dāng)某條轉(zhuǎn)發(fā)路徑被添加到探測矩陣時，其對稱路徑也會被加入.經(jīng)過這樣的處理，原問題的規(guī)?？梢员贿M(jìn)一步降低.為此，我們需要在探測開始之前一次性計算出關(guān)系矩陣中的對稱路徑.

4 實驗與結(jié)果

在本節(jié)中，我們針對探測矩陣的探測性能與計算開銷展開仿真實驗，并根據(jù)實驗結(jié)果進(jìn)行分析.

4.1 實驗環(huán)境設(shè)置

在仿真實驗中，我們基于Java開發(fā)環(huán)境實現(xiàn)了基于探測矩陣的鏈路故障檢測方法BPM-N以及BPM-L.其中，BPM-N是基于故障點為轉(zhuǎn)發(fā)設(shè)備的，BPM-L是基于故障點是端口連接的.我們考慮的鏈路故障為所有經(jīng)過故障點的報文全部無法被對端收到(中途被轉(zhuǎn)發(fā)設(shè)備丟棄、報文丟失或轉(zhuǎn)發(fā)表配置錯誤路由到錯誤的目的地后被丟棄).在探測矩陣構(gòu)建時，我們考慮Θ=1，Γ=2的情況.

我們采用了2種底層網(wǎng)絡(luò)設(shè)置分別是一個FatTree(12)拓?fù)浜鸵粋€VL2(20,12,20)拓?fù)洌则炞C我們的方法在不同拓?fù)浣Y(jié)構(gòu)和規(guī)模下的效果.其中，F(xiàn)atTree和VL2拓?fù)涠际菑V泛應(yīng)用的，且具有冗余傳輸鏈路的數(shù)據(jù)中心內(nèi)部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).這2種拓?fù)渲械牧髁哭D(zhuǎn)發(fā)路徑具有一定規(guī)律，所有從源服務(wù)器中發(fā)送的流量會先經(jīng)過一個ToR交換機，之后再經(jīng)過匯聚層交換機或核心層交換機到達(dá)目的服務(wù)器所在的ToR交換機.相同Pod內(nèi)的流量只經(jīng)過匯聚層交換機，不經(jīng)過核心層交換機；而不同Pod之間的流量則需要先經(jīng)過匯聚層交換機上傳至核心層，再由核心層下傳至匯聚層.我們考慮每條轉(zhuǎn)發(fā)路徑都是雙向的，即探針回復(fù)時的路徑與探針發(fā)送時的路徑相同.因此部分鏈路故障可能不是在探針發(fā)送時被檢測出來，而是在探針回復(fù)時被檢測到.

關(guān)系矩陣中的轉(zhuǎn)發(fā)路徑由所有接入層ToR交換機之間的鏈路構(gòu)成.在一個FatTree(12)拓?fù)渲?，轉(zhuǎn)發(fā)路徑中包含180個轉(zhuǎn)發(fā)設(shè)備(共612個節(jié)點)以及864條端口連接(共1 296條鏈路)，而在一個VL2(20,12,20)拓?fù)渲?，轉(zhuǎn)發(fā)路徑中包含82個轉(zhuǎn)發(fā)設(shè)備(共1 282個節(jié)點)以及240條端口連接(共1 440條鏈路).我們選擇進(jìn)行對比的方法是Pingmesh中提出的探測方法.它是一種對底層網(wǎng)絡(luò)不進(jìn)行感知的鏈路故障檢測方法，即將整個底層網(wǎng)絡(luò)視為一個黑盒系統(tǒng)，并基于服務(wù)器之間進(jìn)行端到端的網(wǎng)絡(luò)探測.該方法產(chǎn)生的探針數(shù)量由Pod內(nèi)部以及Pod之間2種情況組成，在Pod內(nèi)部，由所有的服務(wù)器以完全圖的方式彼此發(fā)送探針；而在Pod之間，則是由所有的ToR交換機以完全圖的方式彼此發(fā)送探針，其中，ToR交換機之間探針的發(fā)送也是由服務(wù)器實現(xiàn)的.在一個FatTree(12)拓?fù)渲?，該方法產(chǎn)生的探針數(shù)量為20 232，而在一個VL2(20,12,20)拓?fù)渲?，該方法產(chǎn)生的探針數(shù)量為26 340.我們選取了BPM-N，BPM-L以及Pingmesh這3種方法下10個探測周期的數(shù)據(jù)進(jìn)行比較.

4.2 探測性能對比

為了檢驗我們提出的實時探測方法與之前工作中提出的方法在探測性能上的差別，我們分別針對單次探測用時、網(wǎng)絡(luò)帶寬占用以及端點負(fù)載3個指標(biāo)在2種拓?fù)湎逻M(jìn)行了對比仿真實驗.

評價指標(biāo)中的單次探測用時包括3部分的用時：1)中央控制器(鏈路故障檢測控制器)激活探測過程中涉及的所有服務(wù)器的探針代理所需的時間;2)探針代理發(fā)送網(wǎng)絡(luò)探針并等待回復(fù)的時間;3)探針代理將探測結(jié)果上傳到中央控制器所需的時間.其中，探針代理每隔固定一段時間就發(fā)送一個探針(而不是一直等待直到收到上輪探針的回復(fù)后再發(fā)送下一輪探針)，每個探針上用時間戳和自增序號進(jìn)行標(biāo)記，探針代理確認(rèn)回復(fù)的時間存在閾值，一旦計時器檢測到超過，就會向中央控制器發(fā)送鏈路故障消息.在任意時隙內(nèi)，如果中央控制器已收到大部分探測結(jié)果(例如95%)，就認(rèn)為當(dāng)前一個探測周期已經(jīng)完成，并進(jìn)入下一個探測周期.

在單次探測用時方面，F(xiàn)atTree(12)拓?fù)湎碌膶嶒灲Y(jié)果如圖4所示，可以看出我們采用的BPM-L和BPM-N的探測周期遠(yuǎn)遠(yuǎn)低于Pingmesh的探測周期，差距最大處接近47倍.造成這樣結(jié)果的主要原因是BPM-L和BPM-N使用的探測路徑的數(shù)量要遠(yuǎn)遠(yuǎn)小于Pingmesh使用的.另一方面，BPM-N的探測周期整體低于BPM-L的探測周期，差距最大處接近2.5倍.造成這樣結(jié)果的主要原因是，BPM-N探測矩陣中故障點數(shù)小于BPM-L中的.但同時BPM-L帶來了更細(xì)粒度的基于端口級別的探測.

Fig. 4 The results of FatTree on detection period圖4 FatTree探測周期結(jié)果圖

Fig. 5 The results of VL2 on detection period圖5 VL2探測周期結(jié)果圖

VL2(20,12,20)拓?fù)湎碌膯未翁綔y用時的實驗結(jié)果如圖5所示，可以看出在VL2拓?fù)湎?，BPM-L和BPM-N的探測周期與Pingmesh的差距更加明顯，差距最大處已經(jīng)接近89倍.造成這樣結(jié)果的主要原因是由于BPM-N和BPM-L的探針數(shù)量分別是受轉(zhuǎn)發(fā)設(shè)備以及端口連接數(shù)目影響的，而Pingmesh的探針數(shù)量則是受服務(wù)器數(shù)量影響的.與FatTree(12)拓?fù)湎啾?，VL2(20,12,20)拓?fù)渲械霓D(zhuǎn)發(fā)設(shè)備與端口連接數(shù)目更少，而服務(wù)器數(shù)量更多.在VL2拓?fù)渲蠦PM-N的探測周期同樣整體低于BPM-L的探測周期，差距最大處接近1.5倍.

在網(wǎng)絡(luò)帶寬占用方面，F(xiàn)atTree(12)拓?fù)湎碌膶嶒灲Y(jié)果如圖6所示.我們考慮每條鏈路上的帶寬數(shù)量是一定的，其中一定比例(如90%)的帶寬需要傳輸工作負(fù)載，那么剩余比例(如10%)的帶寬中，每條探測路徑會消耗其中的一部分(如1%)，而且消耗的部分越多，越有可能對工作負(fù)載的傳輸造成不良影響.從實驗結(jié)果可以看出我們采用的BPM-L和BPM-N的平均帶寬占用遠(yuǎn)遠(yuǎn)低于Pingmesh的平均帶寬占用，差距最大處接近9倍.同理，造成這樣結(jié)果的主要原因是BPM-L和BPM-N使用的探測路徑的數(shù)量要遠(yuǎn)遠(yuǎn)小于Pingmesh使用的探測路徑數(shù)量.此外，BPM-N的平均帶寬占用也同樣低于BPM-L，差距最大處接近2倍.這也是由于BPM-N探測矩陣中的故障點數(shù)小于BPM-L中的故障點數(shù)所造成的結(jié)果.

Fig. 6 The results of FatTree on average bandwidth usage圖6 FatTree平均帶寬占用結(jié)果圖

VL2(20,12,20)拓?fù)湎碌钠骄鶐捳加玫膶嶒灲Y(jié)果如圖7所示，可以看出在VL2拓?fù)湎拢珺PM-L和BPM-N的平均帶寬占用與Pingmesh的差距更加明顯，差距最大處已經(jīng)接近17倍.由于我們考慮的是Γ=2情況下的BPM-L，因此在Fat-Tree和VL2兩種拓?fù)湎翨PM-L的平均帶寬占用的結(jié)果非常接近.在VL2拓?fù)渲蠦PM-N的平均帶寬占用同樣整體低于BPM-L的平均帶寬占用，差距最大處接近3倍.

Fig. 7 The results of VL2 on average bandwidth usage圖7 VL2平均帶寬占用結(jié)果圖

評價指標(biāo)中的端點負(fù)載，與網(wǎng)絡(luò)帶寬占用相似，指的是網(wǎng)絡(luò)邊緣的服務(wù)器運行探針代理所產(chǎn)生的代價.我們考慮服務(wù)器中可用于運行探針代理的CPU利用率是一定比例(如5%)以內(nèi)的，單位時隙內(nèi)，每維護(hù)一個探針會占用一定比例(如0.5%)的CPU利用率，而且占用的部分越多，越有可能對其他應(yīng)用進(jìn)程的運行造成不良影響.在我們的方法中，所有探針代理產(chǎn)生的端點負(fù)載可以在ToR交換機下屬的所有服務(wù)器間進(jìn)行負(fù)載均衡.而在Pingmesh的方法中，僅有Pod之間情況下的端點負(fù)載可以在ToR交換機下屬的所有服務(wù)器間進(jìn)行負(fù)載均衡.

Fig. 8 The results of FatTree on average serverCPU usage圖8 FatTree服務(wù)器平均CPU占用結(jié)果圖

在端點負(fù)載方面，F(xiàn)atTree(12)拓?fù)湎碌膶嶒灲Y(jié)果如圖8所示.可以看出我們采用的BPM-L和BPM-N的服務(wù)器平均CPU占用遠(yuǎn)遠(yuǎn)低于Pingmesh的平均CPU占用，差距最大處接近4.5倍.造成這樣結(jié)果的主要原因是BPM-L和BPM-N在服務(wù)器間需要維護(hù)的探針數(shù)量要遠(yuǎn)遠(yuǎn)小于Pingmesh的.另一方面的原因是，在BPM-L和BPM-N中，由于所有的ToR交換機下屬的服務(wù)器之間都可以進(jìn)行負(fù)載均衡，從而可以進(jìn)一步降低服務(wù)器平均CPU占用.BPM-N在服務(wù)器平均CPU占用方面仍然低于BPM-L，差距最大處接近1.5倍.說明由于基于端口連接的故障點數(shù)更多，導(dǎo)致對BPM-L的探針維護(hù)和端點負(fù)載的影響更大.

VL2(20,12,20)拓?fù)湎碌亩它c負(fù)載的實驗結(jié)果如圖9所示，可以看出在VL2拓?fù)湎?，BPM-L和BPM-N的端點平均CPU占用與Pingmesh之間仍存在差距，且差距最大處接近4倍，這與FatTree(12)拓?fù)渲械慕Y(jié)果相比有所下降.VL2拓?fù)湎碌腂PM-N的服務(wù)器平均CPU占用同樣整體低于BPM-L的，差距最大處接近1.5倍.

Fig. 9 The results of VL2 on average server CPU usage圖9 VL2服務(wù)器平均CPU占用結(jié)果圖

綜合來看，我們采用的BPM-L和BPM-N鏈路故障檢測方法在單次探測用時(探測周期)、網(wǎng)絡(luò)帶寬占用(平均帶寬占用)和端點負(fù)載(服務(wù)器平均CPU占用)3方面與之前的工作Pingmesh相比較，具有顯著的優(yōu)勢，主要原因是我們采用的方法可以根據(jù)已獲取的底層網(wǎng)絡(luò)轉(zhuǎn)發(fā)路徑構(gòu)建近似最優(yōu)的探測矩陣，從而減少探測路徑和端到端探針的數(shù)量，進(jìn)而降低單次探測用時、網(wǎng)絡(luò)帶寬占用以及端點負(fù)載，實現(xiàn)實時快速的虛擬故障鏈路檢測功能.

4.3 探測矩陣計算開銷

雖然探測矩陣在每次網(wǎng)絡(luò)更新之后只需要進(jìn)行一次優(yōu)化，但每次對探測矩陣進(jìn)行優(yōu)化的過程中都存在一定的計算開銷，該開銷包括計算時間上的開銷以及計算內(nèi)存上的開銷.在時間開銷方面，我們考慮了算法1基于BPM-L的探測矩陣構(gòu)建方法DMO，以及另外2種基于DMO并進(jìn)一步優(yōu)化了算法時間復(fù)雜度的構(gòu)建方法.其中，DMO-S是考慮了子問題拆分后的改進(jìn)方法，DMO-T則是考慮了拓?fù)鋵ΨQ性后的改進(jìn)方法.我們分別在FatTree(12)和VL2(12,20,12)兩種拓?fù)湎聦?種不同的探測矩陣構(gòu)建方法的時間開銷進(jìn)行了仿真實驗.

仿真實驗的結(jié)果如圖10所示.其中，未經(jīng)過任何優(yōu)化的DMO在FatTree(12)中的運行時間與它在VL2(12,20,12)中的運行時間分別為224.7 s和23.2 s.而經(jīng)過DMO-S優(yōu)化后的運行時間是6.8 s和24.3 s，可見DMO-S在Fat-Tree拓?fù)湎碌男Ч黠@.經(jīng)過DMO-T優(yōu)化后的運行時間是1.1 s和1.9 s，說明在對稱的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)渲?，DMO-T的效果最好.基于BPM-N的探測矩陣構(gòu)建方法由于具有更少的故障點數(shù)量，因此與BPM-L相比，其運行時間會更短.

Fig. 10 The results on algorithm running time圖10 算法運行時間結(jié)果圖

在內(nèi)存開銷方面，我們考慮了BPM-L與BPM-N在FatTree(12)和VL2(12,20,12)兩種拓?fù)湎玛P(guān)系矩陣的內(nèi)存消耗，仿真實驗的結(jié)果如圖11所示.其中，我們在Java中使用int類型保存關(guān)系矩陣中的位值.由于該類型包含4個字節(jié)即32 b，因此理論上測得的結(jié)果是最低內(nèi)存開銷的32倍.對比結(jié)果顯示，關(guān)系矩陣在FatTree(12)下的內(nèi)存占用更大，差不多是VL2(12,20,12)下的2.5倍；而在同一拓?fù)渲校珺PM-L的內(nèi)存占用更小，差不多是BPM-N的45.

Fig.11 The results on algorithm memory usage圖11 算法內(nèi)存占用結(jié)果圖

事實上，一般數(shù)據(jù)中心網(wǎng)絡(luò)的層數(shù)都在3層以內(nèi)，以最廣泛應(yīng)用的FatTree和VL2拓?fù)錇槔?，每條路徑最多包含5個故障點(基于端口連接的情況下為4個)，一個商用大規(guī)模12階FatTree拓?fù)渲械穆窂娇倲?shù)為184 032，而一個商用大規(guī)模(20,12,20)的VL2拓?fù)渲械穆窂娇倲?shù)為70 800.這2種拓?fù)湎聠吸c故障的初始探測矩陣(基于關(guān)系矩陣)的大小可以計算出來分別為920 160 b和354 000 b，即115.02 KB和44.25 KB，一般被認(rèn)為是可以忍受的內(nèi)存開銷.

綜合來看，我們采用的BPM-L和BPM-N鏈路故障檢測方法在構(gòu)建探測矩陣的過程中所產(chǎn)生的計算開銷是完全可以容忍的.在常見的商用大規(guī)模數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)渲?，計算時間開銷經(jīng)過優(yōu)化后可以達(dá)到秒級，計算內(nèi)存開銷可以維持在MB級別.

5 總 結(jié)

本文通過對已有的鏈路故障檢測工作中存在的問題進(jìn)行分析，發(fā)現(xiàn)了最少化探測路徑數(shù)量對于提升檢測速度具有重要的意義.因此，我們采用優(yōu)化探測矩陣的方法，以此來構(gòu)建數(shù)量最少化、質(zhì)量最大化的探測路徑集合.在解決該問題的過程中，我們給出了探測矩陣的定義和探測矩陣的優(yōu)化方法，在提升探測路徑的質(zhì)量方面，我們定義了2種質(zhì)量指標(biāo)，并給出了結(jié)合質(zhì)量指標(biāo)的探測矩陣優(yōu)化方法.最后，我們通過仿真實驗的方式驗證了該實時檢測方法在單次探測用時、網(wǎng)絡(luò)帶寬占用以及端點負(fù)載3方面比之前工作中的方法具有顯著優(yōu)勢，且優(yōu)化探測矩陣所帶來的開銷是可容忍的.

[1]Al-Fares M, Loukissas A, Vahdat A. A scalable, commodity data center network architecture[C]Proc of ACM SIGCOMM’08. New York: ACM, 2008: 63-74

[2]Govindan R, Minei I, Kallahalla M, et al. Evolve or die: High-availability design principles drawn from Googles network infrastructure[C]Proc of ACM SIGCOMM’16. New York: ACM, 2016: 58-72

[3]Han B, Gopalakrishnan V, Ji L, et al. Network function virtualization: Challenges and opportunities for innovations[J]. IEEE Communications Magazine, 2015, 53(2): 90-97

[4]Guo Chuanxiong, Yuan Lihua, Xiang Dong, et al. Pingmesh: A large-scale system for data center network latency measurement and analysis[C]Proc of ACM SIGCOMM’15. New York: ACM, 2015: 139-152

[5]Kreutz D, Ramos F M V, Verissimo P J E, et al. Software-defined networking: A comprehensive survey[J]. Proceedings of the IEEE, 2014, 103(1): 10-13

[6]Berde P, Gerola M, Hart J, et al. ONOS: Towards an open, distributed SDN OS[C]Proc of ACM HotSDN’14. New York: ACM, 2014: 1-6

[7]Duffield N. Network tomography of binary network performance characteristics[J]. IEEE Trans on Information Theory, 2006, 52(12): 5373-5388

[8]Cunha í, Teixeira R, Feamster N, et al. Measurement methods for fast and accurate blackhole identification with binary tomography[C]Proc of ACM IMC’09. New York: ACM, 2009: 254-266

[9]Dhamdhere A, Teixeira R, Dovrolis C, et al. Netdiagnoser: Troubleshooting network unreachabilities using end-to-end probes and routing data[C]Proc of ACM CoNEXT’07. New York: ACM, 2007: 18-30

[10]Nguyen H X, Teixeira R, Thiran P, et al. Minimizing probing cost for detecting interface failures: Algorithms and scalability analysis[C]Proc of IEEE INFOCOM’09. Piscataway, NJ: IEEE, 2009: 1386-1394

[11]Nguyen H X, Thiran P. The Boolean solution to the congested IP link location problem: Theory and practice[C]Proc of IEEE INFOCOM’07. Piscataway, NJ: IEEE, 2007: 2117-2125

[12]Zhang M, Zhang C, Pai V S, et al. PlanetSeer: Internet path failure monitoring and characterization in wide-area services[C]Proc of USENIX OSDI’04. Berkeley, CA: USENIX Association, 2004: 167-182

[13]Zhao Yao, Chen Yan, Bindel D. Towards unbiased end-to-end network diagnosis[C]Proc of ACM SIGCOMM’06. New York: ACM, 2006: 219-230

[14]Zeng Hongyi, Mahajan R, Mckeown N, et al. Measuring and troubleshooting large operational multipath networks with gray box testing, MSR-TR-2015-55[R]. Redmond: Microsoft Research Lab, 2015

[15]Sharma G, Jaggi S, Dey B K. Network tomography via network coding[C]Proc of IEEE ITA’08. Piscataway, NJ: IEEE, 2008: 151-157

[16]Yao Hongyi, Jaggi S, Chen Minghua. Network coding tomography for network failures[C]Proc of IEEE INFOCOM’10. Piscataway, NJ: IEEE, 2010: 91-95

[17]Kandula S, Mahajan R, Verkaik P, et al. Detailed diagnosis in enterprise networks[C]Proc of ACM SIGCOMM’09. New York: ACM, 2009: 243-254

[18]Herodotou H, Ding B, Balakrishnan S, et al. Scalable near real-time failure localization of data center networks[C]Proc of ACM KDD’14. New York: ACM, 2014: 1689-1698

[19]Mace J, Roelke R, Fonseca R. Pivot tracing: Dynamic causal monitoring for distributed systems[C]Proc of ACM SOSP’15. New York: ACM, 2015: 378-393

[20]Li Yuliang, Miao Rui, Kim C, et al. LossRadar: Fast detection of lost packets in data center networks[C]Proc of ACM CoNEXT’16. New York: ACM, 2016: 481-495

[21]Hou Le, Wang Shuo, Lin Yikai, et al. Link failure recovery based on SDN[J]. Telecommunications Science, 2015, 31(6): 18-23 (in Chinese)(侯樂, 汪碩, 林毅凱, 等. 基于SDN的鏈路故障恢復(fù)[J]. 電信科學(xué), 2015, 31(6): 18-23)WangJunxiao, born in 1991. PhD candidate at Dalian University of Technology. His main research interests include software defined networking, network function virtualization, and cloud computing.

QiHeng, born in 1981. PhD. Associate professor at Dalian University of Technology. Member of CCF. His main research interests include computer network, future Internet technology and multimedia computing.

LiKeqiu, born in 1971. PhD. Professor and PhD supervisor at Dalian University of Technology. Distinguished member of CCF. His main research interests include data center networks, cloud computing and wireless networks.

ZhouXiaobo, born in 1984. PhD. Associate professor at Tianjin University. Member of CCF. His man research interests include network information theory, cloud computing, and software defined networking.