許 剛 王 展 臧大偉 安學(xué)軍

1(中國(guó)科學(xué)院計(jì)算技術(shù)研究所高性能計(jì)算機(jī)研究中心 北京 100190) 2 (中國(guó)科學(xué)院大學(xué) 北京 100049) (xugang10@ict.ac.cn)

Fig. 1 Traditional data-center topology圖1 傳統(tǒng)數(shù)據(jù)中心拓?fù)浣Y(jié)構(gòu)

隨著云計(jì)算和大數(shù)據(jù)的發(fā)展，數(shù)據(jù)中心(Internet data center, IDC)建設(shè)迎來(lái)高潮.當(dāng)前數(shù)據(jù)中心應(yīng)用如在線零售、搜索、社交網(wǎng)絡(luò)、云盤、廣告推薦系統(tǒng)等通常需要高帶寬的穩(wěn)定網(wǎng)絡(luò)，然而在網(wǎng)絡(luò)故障或路由抖動(dòng)時(shí)，這些應(yīng)用系統(tǒng)經(jīng)常會(huì)在用戶訪問(wèn)和業(yè)務(wù)服務(wù)器之間產(chǎn)生路由頻繁抖動(dòng)的情況，路由抖動(dòng)會(huì)導(dǎo)致用戶訪問(wèn)和企業(yè)收入明顯減少.

數(shù)據(jù)中心網(wǎng)絡(luò)會(huì)頻繁發(fā)生網(wǎng)絡(luò)抖動(dòng)，導(dǎo)致丟包增多、時(shí)延增大和吞吐量下降，已成為數(shù)據(jù)中心的性能瓶頸，嚴(yán)重影響業(yè)務(wù)的性能和服務(wù)質(zhì)量.當(dāng)網(wǎng)絡(luò)發(fā)生故障時(shí)，故障定位對(duì)網(wǎng)工來(lái)說(shuō)是一個(gè)非常棘手的問(wèn)題，現(xiàn)有的解決方案主要包括2種：1)通過(guò)搜集網(wǎng)絡(luò)設(shè)備上系統(tǒng)日志使用3-sigma、分段3-sigma、Holt-winters和 ARIMA等機(jī)器學(xué)習(xí)方法進(jìn)行異常檢測(cè)[1]；2)經(jīng)驗(yàn)豐富的網(wǎng)工根據(jù)自身經(jīng)驗(yàn)結(jié)合故障特征手動(dòng)解決.然而無(wú)論是通過(guò)算法還是經(jīng)驗(yàn)進(jìn)行故障發(fā)現(xiàn)和設(shè)備定位普遍都是預(yù)測(cè)性的，仍然會(huì)出現(xiàn)誤判和誤報(bào)的問(wèn)題，且實(shí)時(shí)性不高.

針對(duì)這一問(wèn)題，我們提出基于鏈路狀態(tài)數(shù)據(jù)庫(kù)(link state database, LSDB)的數(shù)據(jù)中心網(wǎng)絡(luò)異常檢測(cè)方法LSAP，通過(guò)搜集LSDB，利用改進(jìn)Dijkstra算法重計(jì)算全網(wǎng)路由形成路由擇域信息庫(kù)(routing information base, RIB)，根據(jù)LSDB快照和RIB快照比對(duì)關(guān)聯(lián)鏈路變化和路由變化進(jìn)行異常定位，發(fā)現(xiàn)網(wǎng)絡(luò)問(wèn)題.

1 背景和相關(guān)工作

1.1 數(shù)據(jù)中心的網(wǎng)絡(luò)

傳統(tǒng)數(shù)據(jù)中心網(wǎng)絡(luò)是由核心層、匯聚層和接入層3層網(wǎng)絡(luò)設(shè)備組成[2].如圖1所示，網(wǎng)絡(luò)呈現(xiàn)出由底層網(wǎng)絡(luò)的物理服務(wù)器到上層網(wǎng)絡(luò)的核心路由器所組成的3層網(wǎng)絡(luò)層次結(jié)構(gòu)，其中核心層設(shè)備接入上層網(wǎng)絡(luò)，核心層設(shè)備與匯聚層設(shè)備相連，匯聚層設(shè)備與接入層設(shè)備相連，接入層設(shè)備與底層物理服務(wù)器相連.核心層位于全局網(wǎng)絡(luò)的頂端，核心層的路由連接在整個(gè)數(shù)據(jù)中心網(wǎng)絡(luò)中起到關(guān)鍵的作用，通常會(huì)在設(shè)備之間建立冗余連接提高網(wǎng)絡(luò)穩(wěn)定性.

伴隨著業(yè)務(wù)訪問(wèn)量的增長(zhǎng)，數(shù)據(jù)中心所需的服務(wù)器數(shù)量也在持續(xù)增長(zhǎng)，為滿足用戶訪問(wèn)BAT(Baidu Alibaba Tencent)數(shù)據(jù)中心平均每月就有2 000臺(tái)以上的服務(wù)器上線.為降低數(shù)據(jù)中心計(jì)算節(jié)點(diǎn)間的通信延時(shí)，減少網(wǎng)絡(luò)中間層次、網(wǎng)絡(luò)扁平化勢(shì)在必行.如圖2所示，網(wǎng)絡(luò)扁平化后對(duì)核心設(shè)備交換能力要求降低，網(wǎng)絡(luò)既能快速收斂，又能滿足服務(wù)器快速上線的需求.

Fig. 2 Flat topology圖2 扁平拓?fù)浣Y(jié)構(gòu)

1.2 數(shù)據(jù)中心的網(wǎng)絡(luò)數(shù)據(jù)

網(wǎng)絡(luò)數(shù)據(jù)是進(jìn)行故障檢測(cè)、故障定位和流量分析的原始數(shù)據(jù)，它能夠體現(xiàn)出當(dāng)前網(wǎng)絡(luò)狀態(tài)和流量特征，通過(guò)對(duì)多維度網(wǎng)絡(luò)數(shù)據(jù)的分析、統(tǒng)計(jì)和計(jì)算，建立網(wǎng)絡(luò)模型，實(shí)時(shí)監(jiān)控網(wǎng)絡(luò)，具體數(shù)據(jù)分類如表1所示:

Table 1 Network Data Classification表1 網(wǎng)絡(luò)數(shù)據(jù)分類

1) 網(wǎng)絡(luò)探針數(shù)據(jù)[3]

2) 流數(shù)據(jù)

流數(shù)據(jù)是指通過(guò)對(duì)流經(jīng)網(wǎng)絡(luò)設(shè)備的數(shù)據(jù)包的頭部進(jìn)行分析，采集經(jīng)過(guò)設(shè)備的流信息.流數(shù)據(jù)并不檢測(cè)流經(jīng)設(shè)備的所有數(shù)據(jù)包，而是根據(jù)采樣比進(jìn)行采樣、分析和統(tǒng)計(jì).流數(shù)據(jù)主要包括數(shù)據(jù)流的源地址、目的地址、源端口、目的端口和數(shù)據(jù)大小，通過(guò)流數(shù)據(jù)能夠用來(lái)檢測(cè)異常的數(shù)據(jù)流[4-5].目前成熟的流數(shù)據(jù)采集技術(shù)包括Cisco的NetFlow技術(shù)、Huawei的NetStream技術(shù)和Juniper的sFlow技術(shù)等，NetFlow技術(shù)應(yīng)用范圍最廣，一共包括V1，V5，V7，V8，V9這5個(gè)主要的實(shí)用版本.

3) 路由協(xié)議數(shù)據(jù)

路由協(xié)議是指通過(guò)在路由器之間共享路由信息來(lái)支持可路由協(xié)議.路由信息通過(guò)在相鄰路由器之間泛洪，確保所有路由器同步路由信息并進(jìn)行路由收斂，從而知道到達(dá)目的路由器的路徑.通過(guò)與數(shù)據(jù)中心內(nèi)網(wǎng)絡(luò)設(shè)備建立連接關(guān)系，就可以采集到域內(nèi)路由信息并構(gòu)建網(wǎng)絡(luò)拓?fù)浜瞳@取設(shè)備間鏈接狀態(tài).路由協(xié)議數(shù)據(jù)能夠進(jìn)行異常檢測(cè)和故障定位，但是難點(diǎn)在于如何獲取全網(wǎng)路由信息，利用采集的路由信息檢測(cè)異常和定位.本文進(jìn)行異常檢測(cè)和故障定位的源數(shù)據(jù)就是數(shù)據(jù)中心網(wǎng)絡(luò)中鏈路狀態(tài)數(shù)據(jù)庫(kù)(LSDB)數(shù)據(jù)，通過(guò)LSDB復(fù)原路由表，比對(duì)LSDB快照和路由表快照進(jìn)行檢測(cè)和監(jiān)控.

4) 網(wǎng)絡(luò)管理協(xié)議數(shù)據(jù)

網(wǎng)絡(luò)管理協(xié)議是一種提供給網(wǎng)絡(luò)管理員用于網(wǎng)絡(luò)監(jiān)控的工具，具體包括鏈路狀態(tài)信息、網(wǎng)絡(luò)流量統(tǒng)計(jì)、設(shè)備信息、網(wǎng)絡(luò)參數(shù)等多維度全方面信息，是進(jìn)行異常檢測(cè)中普遍使用的監(jiān)測(cè)數(shù)據(jù).由于該類型數(shù)據(jù)能夠提供詳細(xì)的網(wǎng)絡(luò)信息，因而通過(guò)將不同設(shè)備間的網(wǎng)絡(luò)管理協(xié)議數(shù)據(jù)進(jìn)行關(guān)聯(lián)分析就能夠進(jìn)行異常檢測(cè)[6-9].簡(jiǎn)單網(wǎng)絡(luò)管理協(xié)議(SNMP)是基于TCPIP的網(wǎng)絡(luò)上使用最為廣泛網(wǎng)絡(luò)管理模型，既可以管理最簡(jiǎn)單的網(wǎng)絡(luò)實(shí)現(xiàn)基本的管理功能，又滿足大型復(fù)雜網(wǎng)絡(luò)的管理需求.SNMP是由一系列協(xié)議組和規(guī)范組成的，提供了一種從網(wǎng)絡(luò)設(shè)備中收集網(wǎng)絡(luò)管理信息的方法.

1.3 相關(guān)工作

近年來(lái)，國(guó)內(nèi)外在路由異常檢測(cè)及分析方面的研究工作有很多，相關(guān)方向的研究、文章有很多.現(xiàn)在數(shù)據(jù)中心中還沒有成熟的路由異常檢測(cè)和分析工具，在路由異常定位方面相關(guān)研究也非常有限.國(guó)外的公司和大學(xué)如Google,Facebook,AT&T、哥倫比亞大學(xué)大學(xué)等高校已經(jīng)對(duì)路由檢測(cè)開展了一些研究，國(guó)內(nèi)清華大學(xué)、國(guó)防科技大學(xué)等大學(xué)在協(xié)議主動(dòng)測(cè)試和被動(dòng)測(cè)試方面進(jìn)行了大量的研究和開發(fā)，阿里巴巴數(shù)據(jù)中心和百度數(shù)據(jù)中心也在進(jìn)行路由異常檢測(cè)方面相關(guān)研究.從這些研究成果中總結(jié)出以下3種路由檢測(cè)方法：

1) 基于SNMP協(xié)議的網(wǎng)絡(luò)監(jiān)測(cè)系統(tǒng)利用SNMP MIB庫(kù)提供的網(wǎng)絡(luò)信息構(gòu)建網(wǎng)絡(luò)拓?fù)浜捅O(jiān)控端口等，使用trap功能實(shí)現(xiàn)異常發(fā)現(xiàn)和告警.現(xiàn)在比較成熟產(chǎn)品包括Tivoli NetView和MasterScope等，該類產(chǎn)品優(yōu)勢(shì)在于能夠?qū)崿F(xiàn)拓?fù)錁?gòu)建、網(wǎng)絡(luò)性能分析和異常告警，但是路由異常功能在異常檢測(cè)中實(shí)現(xiàn)的功能較少，未實(shí)現(xiàn)路由異常定位且需要使用日志信息和其他監(jiān)測(cè)工具輔助，增加了網(wǎng)絡(luò)負(fù)擔(dān)和部署負(fù)擔(dān).

2) Shaikh等人[10-11]和Zhang等人[12]在IGP(內(nèi)部路由協(xié)議)路由異常檢測(cè)方面貢獻(xiàn)突出，分別闡述了IGP內(nèi)路由檢測(cè)方法并進(jìn)行了實(shí)驗(yàn)驗(yàn)證.Shaikh在OSPF協(xié)議方面進(jìn)行大量研究，他首先從運(yùn)行OSPF協(xié)議的大型網(wǎng)絡(luò)中學(xué)習(xí)OSPF協(xié)議運(yùn)行行為，主要是對(duì)鏈路狀態(tài)通告行為的分析.在進(jìn)行大量實(shí)驗(yàn)后，Shaikh開始研究利用OSPF協(xié)議構(gòu)建網(wǎng)絡(luò)拓?fù)洌ㄟ^(guò)被動(dòng)監(jiān)聽網(wǎng)絡(luò)數(shù)據(jù)流構(gòu)建拓?fù)浣Y(jié)構(gòu)，最后比較了利用OSPF協(xié)議構(gòu)建拓?fù)浜屠肧NMP協(xié)議構(gòu)建拓?fù)湓诳煽啃院蛯?shí)時(shí)性上的差異[10]，總結(jié)出由拓?fù)浣Y(jié)構(gòu)改變或其他原因產(chǎn)生的網(wǎng)絡(luò)異常信息，并提出一種OSPF路由監(jiān)測(cè)系統(tǒng)的實(shí)現(xiàn)方法.Shaikh等人[10-11]指出該系統(tǒng)能夠有效地發(fā)現(xiàn)網(wǎng)絡(luò)中的拓?fù)洚惓?但是Shaikh等人[10-11]只是通過(guò)協(xié)議獲得了網(wǎng)絡(luò)拓?fù)湫畔?，并只能發(fā)現(xiàn)拓?fù)涓淖儯诠δ苌虾托阅苌喜荒芡耆脕?lái)檢測(cè)路由異常.

3) 在域間路由協(xié)議(border gateway protocol, BGP)路由異常監(jiān)測(cè)工作中，以O(shè)regon大學(xué)的Route Views項(xiàng)目[13]、RIPE NCC的RIS項(xiàng)目[14]、UCLA的Zhang[15]以及哥倫比亞大學(xué)的Al-Musawi等人[16]為代表主要進(jìn)行域間路由異常檢測(cè)工作，這些工作主要面向公共的BGP 路由數(shù)據(jù)服務(wù)、BGP路由動(dòng)態(tài)行為的可視化、基本的安全監(jiān)測(cè)服務(wù)3個(gè)方面.

本文研究與上述研究不同之處主要存在于4個(gè)方面：

1) 提出一種新型方法導(dǎo)出數(shù)據(jù)中心OSPF和ISIS網(wǎng)絡(luò)內(nèi)的全網(wǎng)路由信息，為復(fù)原路由表提供原始鏈路狀態(tài)信息.

2) 利用改進(jìn)Dijkstra算法復(fù)原路由表，提出改進(jìn)算法并給予理論驗(yàn)證.

3) 相比于Shaikh等人[10-11]、Zhang等人[12]、Al- Musawi等人[16]研究的內(nèi)容都是路由異常問(wèn)題，本文研究?jī)?nèi)容基于數(shù)據(jù)中心內(nèi)部路由異常，而不是域間路由異常；與Shaikh等人[10-11]和Zhang等人[12]不同的是不僅僅能夠發(fā)現(xiàn)路由異常，還能夠迅速進(jìn)行異常源頭定位.

4) 除路由異常檢測(cè)外，利用鏈路狀態(tài)數(shù)據(jù)庫(kù)實(shí)現(xiàn)路由攻擊和異常定位.

2 LSAP系統(tǒng)設(shè)計(jì)

本節(jié)主要介紹如何通過(guò)LSAP進(jìn)行路由異常檢測(cè).如圖3所示系統(tǒng)的主要組成部分.首先通過(guò)軟件路由器或者開啟BGP-LS協(xié)議采集網(wǎng)絡(luò)路由信息，導(dǎo)出IGP協(xié)議中的LSDB，由于在每個(gè)區(qū)域內(nèi)路由器定期同步鏈路狀態(tài)數(shù)據(jù)庫(kù)，因而我們只需要采集所有區(qū)域而不是所有路由設(shè)備的LSDB，采集方案我們優(yōu)先選擇BGP-LS，軟件路由器作為備選采集方案，然后根據(jù)改進(jìn)的Dijkstra算法計(jì)算路由表(RIB)，最后比對(duì)LSDB 快照和RIB快照進(jìn)行快速發(fā)現(xiàn)鏈路狀態(tài)變化和路由變化等.

Fig. 3 Anomaly detection process of LSAP圖3 LSAP異常檢測(cè)流程

2.1 LSDB導(dǎo)出

在本文中我們優(yōu)先選擇BGP-LS，軟件路由器作為備選采集方案導(dǎo)出LSDB，數(shù)據(jù)中心網(wǎng)絡(luò)按區(qū)域劃分收集.數(shù)據(jù)中心通常會(huì)維護(hù)一張網(wǎng)絡(luò)設(shè)備信息表，包括設(shè)備名、路由協(xié)議類型、區(qū)域號(hào)、設(shè)備型號(hào)、設(shè)備廠商、部署時(shí)間等.在本系統(tǒng)部署之前我們會(huì)要求設(shè)備廠商提供部署B(yǎng)GP-LS協(xié)議的設(shè)備型號(hào)集合B.設(shè)：

Ii={ISIS第i個(gè)區(qū)域內(nèi)路由器集合}=
{Dk|Dk∈R且Dk擁有相同區(qū)域號(hào)}；
I={ISIS區(qū)域所有路由器集合}=∪Ii；

Oi={OSPF第i個(gè)區(qū)域內(nèi)路由器集合}=
{Dk|Dk∈R且Dk擁有相同區(qū)域號(hào)}；
O={OSPF區(qū)域所有路由器集合}=∪Oi.

算法1. LSDB采集算法.

① 遍歷所有ISIS區(qū)域；

② 遍歷判斷ISIS區(qū)域內(nèi)設(shè)備類型是否屬于B；

③ 記錄設(shè)備的采集類型，1表示采集方案為BGP-LS,0表示采集方案為Zebra的采集方案；

④ 遍歷所有OSPF區(qū)域；

⑤ 遍歷判斷OSPF區(qū)域內(nèi)設(shè)備類型是否屬于B；

⑥ 記錄設(shè)備的采集類型，1表示采集方案為BGP-LS，0表示采集方案為Zebra的采集方案.

2.2 路由表復(fù)原

現(xiàn)存的路由表獲取方法大致分為3種：登錄路由器CLI收集、廠商提供和網(wǎng)絡(luò)收集.登錄路由器查看往往需要手工輔助，受限于數(shù)據(jù)中心內(nèi)路由器數(shù)量龐大和不同廠商路由器的路由表格式不同，該方式獲取路由表可行性較低；廠商提供往往需要配置專用路由器提供對(duì)外輸出路由表接口，該方式獲取的路由表精確快速，但是價(jià)格較為昂貴，非專用路由器無(wú)法直接導(dǎo)出路由表數(shù)據(jù)；網(wǎng)絡(luò)收集主要是利用網(wǎng)絡(luò)內(nèi)泛洪鏈路狀態(tài)信息，利用路由計(jì)算算法復(fù)原路由，該方式性價(jià)比較高，提供較為準(zhǔn)確的路由表，速度上僅低于專用路由器.

在導(dǎo)出的LSDB可以獲取各區(qū)域中的拓?fù)滏溄雨P(guān)系以及連接權(quán)值Metric，即可形成賦權(quán)圖G=(V,E,W)，設(shè)節(jié)點(diǎn)v0，v1，…，vm∈V，邊e1，e2，…，en∈E，W為邊(i,j)∈V對(duì)應(yīng)的wi j的集合.加權(quán)圖用鄰接矩陣A表示，規(guī)定：若vi和vj之間沒有鏈接，則ai j=∞；若vi和vj之間存在鏈接，則ai j=wi j，即為相連路由器之間Metric值；若i=j，則ai j=0.在用鏈路鄰接矩陣是指行到列之間路徑條數(shù).在用鏈路鄰接矩陣U表示，規(guī)定：若vi和vj之間沒有鏈接，則Ui j=0；若vi和vj之間存在鏈接，則Ui j表示相連路由器之間Metric為ai j的條數(shù).

2.2.1 Dijkstra算法的基本思想

Dijkstra算法是指在一個(gè)賦權(quán)圖查詢2個(gè)指定頂點(diǎn)vi和vj之間的最短路徑.該算法是一個(gè)求解最短路問(wèn)題的算法，不僅能夠找到最短的(vi,vj)路徑，而且可以給出vi到G中所有頂點(diǎn)最短路徑.

最短路徑的計(jì)算步驟如下：

設(shè)S表示已求得的從vi出發(fā)的最短路徑的終點(diǎn)集合；

m階標(biāo)識(shí)矩陣R，存儲(chǔ)已求得的從vi到其他頂點(diǎn)vj的所有最短路徑上的此頂點(diǎn)的前驅(qū)頂點(diǎn).

① 初始化S和R，S={vi}，R=(ri j).

② 選擇vm，使得：

aim=min {aik|vk∈V-S}，令S=S∪{vm}.

③ 修改從vi出發(fā)到集合V-S中所有節(jié)點(diǎn)vk的最短路徑長(zhǎng)度.

如果：amk> 0且aim+amk

則修改為aik=aim+amk.

④ 重復(fù)操作②③共n-1次，即可求得從vi到其余各定點(diǎn)vj的最短路徑長(zhǎng)度.

但是，Dijkstra算法只能求得節(jié)點(diǎn)間一條最短路徑，不能保存所有最短路徑且②③操作需重復(fù)n-1次，本文首先優(yōu)化Dijkstra算法，解決大規(guī)模網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路過(guò)多路由計(jì)算時(shí)間過(guò)長(zhǎng)的問(wèn)題.

2.2.2 Dijkstra算法的優(yōu)化

在網(wǎng)絡(luò)中心的網(wǎng)絡(luò)模型有2個(gè)特點(diǎn)：

1) 由于數(shù)據(jù)中心網(wǎng)絡(luò)配置現(xiàn)狀，同一層次路由器間接口鏈路的Metric值通常是相等的(存在不相等情況)；

2) 鑒于特點(diǎn)1和數(shù)據(jù)中心冗余鏈路的存在，節(jié)點(diǎn)之間總度量相等鏈路具有多條；從單節(jié)點(diǎn)到其余節(jié)點(diǎn)總度量相等的個(gè)數(shù)有多個(gè).

優(yōu)化采取的方案是：

優(yōu)化的目標(biāo)是提高集合S的效率，最大程度地加快增加S中與最短距離路徑相關(guān)的頂點(diǎn)的計(jì)算和減少S中與最短距離路徑無(wú)關(guān)的頂點(diǎn)的計(jì)算.

選擇新節(jié)點(diǎn)加入S時(shí)，不僅只選擇一條最短路徑的節(jié)點(diǎn)加入S，而是將最短路徑相等的所有節(jié)點(diǎn)加入S；

選擇新節(jié)點(diǎn)加入S時(shí)，不僅只選擇離vi最近的頂點(diǎn)加入集合S，而是向著從vi到vj最短路徑不斷逼近的目標(biāo)而選擇頂點(diǎn)加入集合S.

標(biāo)識(shí)矩陣R用來(lái)存儲(chǔ)從vi到其余各頂點(diǎn)的所有最短路徑的此頂點(diǎn)的前驅(qū)頂點(diǎn)，即若從vi到vj的一條最短路徑為vi,v2,v4,…,vj，在此路徑中，v2是v4的前驅(qū)頂點(diǎn)，則R[2][4]=1，否則R[2][4]=0.

優(yōu)化最短路徑的計(jì)算步驟如下：

① 初始化S和R，S={vi}，R=(ri j).

② 選擇aim相等的所有節(jié)點(diǎn)vm，S′={vm}且S′?V-S使得aim+hopsm×metricmin=min {aik+hopsk×metricmin|vk∈V-S}，令S=S∪S′.

hopsm：vm至vj節(jié)點(diǎn)之間的跳數(shù)，目前數(shù)據(jù)中心內(nèi)多種業(yè)務(wù)并存，通過(guò)即時(shí)通信客戶端運(yùn)行主動(dòng)探測(cè)工具ping和traceroute命令獲取數(shù)據(jù)中心內(nèi)部節(jié)點(diǎn)間時(shí)延數(shù)據(jù)和跳數(shù)；

metricmin：區(qū)域內(nèi)最小Metric值，相同區(qū)域內(nèi)Metric值相差不大.

③ 修改從vi出發(fā)到集合V-S中所有節(jié)點(diǎn)vk的最短路徑長(zhǎng)度.

如果：amk>0且aim+amk

則修改為aik=aim+amk.

④ 重復(fù)操作②③直至求出最小ai j，即可求得從vi到其余各定點(diǎn)vj最短路徑長(zhǎng)度.

⑤ 將最短路徑按照前驅(qū)節(jié)點(diǎn)規(guī)則添加到R中.

從優(yōu)化最短路徑的計(jì)算步驟中可以發(fā)現(xiàn)，優(yōu)化算法是相似于Dijkstra算法的，但對(duì)頂點(diǎn)的選擇是不同的.在Dijkstra算法中，不斷選擇離vi最近的一個(gè)頂點(diǎn)加入到集合S，而沒有考慮最短路徑的頂點(diǎn)個(gè)數(shù)和把vi，vj同時(shí)聯(lián)系起來(lái)考慮.在優(yōu)化算法中，向著vi和vj最短路徑的不斷逼近的目標(biāo)而選擇頂點(diǎn)加入集合S中，因此，在集合S包含的是在vi和vj最短路徑局部范圍內(nèi)的部分節(jié)點(diǎn)，而并不計(jì)算全部節(jié)點(diǎn).在這種情況下，優(yōu)化算法的集合S和②③迭代次數(shù)相較Dijkstra算法的集合S和②③迭代次數(shù)小得多、少得多.

2.2.3 Dijkstra改進(jìn)算法正確性證明

Fig. 4 Shortest path graph from vi to vj圖4 vi到vj最短路徑

在改進(jìn)算法中vj加入S時(shí)：

1) 若mqS時(shí)

已求得最短距離A(vi,mq)+(hops(mq,vj)×metricmin)≥A(vi,vj)+0=A(vi,vj),由于hops(mq,vj)×metricmin≤A(mq,vj)=a(mq,vj)，因此可以推出A(vi,vq)+a(mq,vj)≥A(vi,vj).

2) 若mq∈S時(shí)

當(dāng)mq加入S時(shí)A(vi,vj)=min {A(vi,vj),A(vi,mq)+A(mq,vj)}=min {A(vi,vj),A(vi,mq)+a(mq,vj)},記為A1(vi,vj).

由Dijkstra改進(jìn)算法可知vp加入S時(shí)修改了A(vi,vj)值，因而當(dāng)vp加入S時(shí)A(vi,vj)=min {A(vi,vj),A(vi,vp)+A(vp,vj)}=A(vi,vp)+a(vp,vj)，A(vi,vj)即為改進(jìn)算法求取的最終vi到vj的最短距離.

① 當(dāng)mq先于vp加入S時(shí)，vp加入S時(shí)修改了A(vi,vj)，A(vi,vj)=A(vi,vp)+A(vp,vj)

② 當(dāng)mq后于vp加入S時(shí)，vp為最短路徑的最后節(jié)點(diǎn)，mq加入S時(shí)并未修改A(vi,vj)，A1(vi,vj)=A(vi,vj)≤A(vi,mq)+a(mq,vj).

綜上所述，不論mq何時(shí)加入S中，可得

A(vi,vj)≤A(vi,mq)+a(mq,vj).

(1)

根據(jù)假設(shè)在vi到vj存在的最短路徑為vim1m2m3…mqvj，最短路徑為A′(vi,vj).

A′(vi,vj)=A′(vi,mq)+A′(mq,vj)=
A′(vi,mq)+a(mq,vj).

(2)

因?yàn)楦倪M(jìn)算法求出最短路徑為A(vi,vj)，根據(jù)假設(shè)已知最短路徑為A′(vi,vj)，因而

A′(vi,vj)

(3)

將式(1)(2)帶入式(3)，可以推出：

A′(vi,mq)+a(mq,vj)=A′(vi,vj)A(vi,mq)+a(mq,vj)，

可得：

A′(vi,mq)

(4)

根據(jù)式(4)可以推出在優(yōu)化算法中mq未求得正確的最短路徑，還存在另外一條距離小于最短距離A(vi,mq)的更短路徑.因此根據(jù)反證法假設(shè)可以推出未正確求出正確vi到vj最短路徑的原因在于未求出正確vi到mq最短路徑.將mq替換vj重復(fù)上述證明可以推出未正確求出正確vi到vj最短路徑的原因在于未求出正確vi到mq-1最短路徑，以此類推：改進(jìn)算法未求出正確vi到m2最短路徑的原因在于未求出正確vi到m1最短路徑.根據(jù)Dijkstra算法已知節(jié)點(diǎn)vi與節(jié)點(diǎn)m1是直接相連，因而d(vi,m1)=a(vi,m1)，在改進(jìn)算法中節(jié)點(diǎn)vi與節(jié)點(diǎn)m1最短距離是正確的.

因此與假設(shè)相矛盾，假設(shè)是不成立的，證明了本文Dijkstra改進(jìn)算法是正確的.

2.3 異常檢測(cè)

本文重點(diǎn)關(guān)注路由異常的檢測(cè)，主要涉及路由黑洞攻擊、鏈路異常和路由異常，如表2所示:

Table 2 Network Anomaly Classification表2 網(wǎng)絡(luò)異常分類

2.3.1 路由黑洞攻擊檢測(cè)算法

路由黑洞攻擊是指在區(qū)域網(wǎng)絡(luò)的路由器中注入惡意路由，惡意路由是由誤配置或者網(wǎng)絡(luò)攻擊造成的，當(dāng)惡意路由最終擴(kuò)散至所有區(qū)域路由器后，發(fā)往某個(gè)特定網(wǎng)絡(luò)的數(shù)據(jù)包的傳輸流向?qū)⒈粣阂飧?，?shù)據(jù)將被發(fā)送到黑客指定的目的地，這個(gè)目的地就像“黑洞”一樣將發(fā)往某個(gè)特定網(wǎng)絡(luò)的數(shù)據(jù)包吸引過(guò)來(lái)，因此稱這種攻擊為“黑洞攻擊”.

路由黑洞攻擊檢測(cè)方法是采集所有路由器宣告網(wǎng)段(宣告網(wǎng)段是指路由器對(duì)外宣告直接相連的網(wǎng)段，以網(wǎng)絡(luò)子網(wǎng)號(hào)形式表示)，正常情況下所有路由器宣告網(wǎng)段是具有唯一性的，否則會(huì)導(dǎo)致“黑洞”，因而通過(guò)判斷宣告網(wǎng)段的包含關(guān)系可以檢測(cè)出路由黑洞攻擊.

具體算法如下所示：

算法2. 路由黑洞攻擊檢測(cè)算法.

設(shè)路由器宣告網(wǎng)段遞增排序?yàn)閜1,p2,…,pq，t0代表路由更新時(shí)間(t0非固定值).

① 遍歷p1,p2,…,pq，初始化i=2，標(biāo)識(shí)路由p′=p1以及集合S；

② 取出pi，判斷pi是否是p′子網(wǎng)段，若是則pi加入S中，i=i+1跳至②循環(huán)執(zhí)行；否則判斷S個(gè)數(shù)，card(S)≠0時(shí)將p′加入S，存儲(chǔ)S集合至消息隊(duì)列同時(shí)清空S；

③ 判斷i+1≥n，是則跳至步驟④，否則p′=pi+1，i=i+2跳至步驟②執(zhí)行；

④ 推送消息隊(duì)列至管理員.

算法3. 算法2步驟②中判斷子網(wǎng)包含關(guān)系算法.

函數(shù)netXInNetY(longx,intxmask,longy,intymask)

① 驗(yàn)證子網(wǎng)關(guān)系，ymask>xmask時(shí)返回否；

② 根據(jù)x和xmask得出子網(wǎng)號(hào)xnet；

③ 根據(jù)y和ymask得出子網(wǎng)號(hào)ynet；

④xnet與ynet進(jìn)行與運(yùn)算，與運(yùn)算結(jié)果即為包含關(guān)系.

2.3.2 鏈路異常檢測(cè)算法

本文提供一種基于路由的鏈路狀態(tài)檢測(cè)方法，通過(guò)LSDB快照快速發(fā)現(xiàn)鏈路狀態(tài)變更，主動(dòng)上報(bào)中央控制端.

鏈路異常檢測(cè)方法是通過(guò)比對(duì)路由更新信息前鏈路狀態(tài)和路由更新信息后鏈路狀態(tài)進(jìn)行快照比對(duì)，即可得出鏈路變化(鏈路權(quán)值變化和鏈路連接變化).

具體算法如下所示：

根據(jù)2.2.2節(jié)中可知,A和U表明時(shí)刻t加權(quán)圖鄰接矩陣和在用鏈路鄰接矩陣，A′和U′表明時(shí)刻t′加權(quán)圖鄰接矩陣和在用鏈路鄰接矩陣.在用鏈路鄰接矩陣表示行節(jié)點(diǎn)到列節(jié)點(diǎn)之間路徑條數(shù).t′-t代表路由更新時(shí)間.

算法4. 鏈路異常檢測(cè)算法.

1) 初始化A和U，A′和U′；

2) 計(jì)算鏈路改變矩陣Achange=A′-A，

3) 計(jì)算用鏈路鄰接矩陣Uchange=U′-U，

4) 判斷achange和uchange：

①achange>0,uchange>0：權(quán)值增加且使用鏈路增加；

②achange>0,uchange<0：權(quán)值增加且使用鏈路減少；

③achange>0,uchange=0：權(quán)值增加且使用鏈路未改變；

④achange<0,uchange>0：權(quán)值減少且使用鏈路增加；

⑤achange<0,uchange<0：權(quán)值減少且使用鏈路減少；

⑥achange<0,uchange=0：權(quán)值減少且使用鏈路未改變；

⑦achange=0,uchange>0：權(quán)值未改變但使用鏈路增加；

⑧achange=0,uchange<0：權(quán)值未改變但使用鏈路減少.

achange>0說(shuō)明鏈路所在節(jié)點(diǎn)權(quán)值增加，可能引流至其他節(jié)點(diǎn)；achange<0說(shuō)明鏈路所在節(jié)點(diǎn)權(quán)值降低，可能引流至該鏈路相連節(jié)點(diǎn).

2.3.3 路由異常檢測(cè)算法

路由異常包括設(shè)備連接不通和路由頻繁變化2種情況.

設(shè)備連接不通檢測(cè)方法是采集數(shù)據(jù)中心內(nèi)所有區(qū)域的鏈路狀態(tài)數(shù)據(jù)庫(kù)，畫出完整的網(wǎng)絡(luò)拓?fù)鋱D，通過(guò)改進(jìn)的Dijkstra算法計(jì)算端到端的路由表，從而得出以自身為根節(jié)點(diǎn)的無(wú)環(huán)路最短路徑樹，通過(guò)判斷其他節(jié)點(diǎn)是否在最短路徑樹上即可判斷設(shè)備連接狀態(tài)：所有在最短路徑樹上的節(jié)點(diǎn)為可達(dá)節(jié)點(diǎn)，不在最短路徑上節(jié)點(diǎn)為不可達(dá)節(jié)點(diǎn).

由于數(shù)據(jù)中心內(nèi)路由設(shè)備配置和設(shè)備連接關(guān)系是相對(duì)穩(wěn)定的，因此網(wǎng)絡(luò)路由表是穩(wěn)定的.對(duì)于維護(hù)人員來(lái)說(shuō)，未主動(dòng)修改路由器配置的路由變化就屬于異常變化，是需要檢查排除故障.路由變化是指路由信息更新后，由于節(jié)點(diǎn)間連接關(guān)系和權(quán)值改變導(dǎo)致路徑或者路徑開銷值發(fā)生改變.

路由異常與路由定位檢測(cè)方法是首先通過(guò)快照比對(duì)設(shè)備路由更新前后標(biāo)識(shí)矩陣R，從而獲取路由信息更新后設(shè)備到其他節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)變化，根據(jù)前驅(qū)節(jié)點(diǎn)變化即可獲得設(shè)備到其他節(jié)點(diǎn)的路徑變化(包括路徑增加和路徑減少)，其次計(jì)算比對(duì)更新前后的完整路徑和總開銷值，最后通過(guò)關(guān)聯(lián)鏈路變化和路徑變化關(guān)系發(fā)現(xiàn)路由變化和進(jìn)行路由定位.

算法5. 路由異常檢測(cè)算法.

1) 初始化矩陣標(biāo)識(shí)矩陣R+，R-為0.

2) 遍歷i(1≤i≤n)，n為節(jié)點(diǎn)個(gè)數(shù)并初始化，臨時(shí)矩陣tmpi=0.

tmpi[a][b]=0前驅(qū)節(jié)點(diǎn)沒有變化，時(shí)刻t，va是vb的前驅(qū)節(jié)點(diǎn)；時(shí)刻t′，va也是vb的前驅(qū)節(jié)點(diǎn)；或者時(shí)刻t，va不是vb的前驅(qū)節(jié)點(diǎn)；時(shí)刻t′，va也不是vb的前驅(qū)節(jié)點(diǎn)；

tmpi[a][b]=1代表時(shí)刻t，va不是vb的前驅(qū)節(jié)點(diǎn)；時(shí)刻t′，va是vb的前驅(qū)節(jié)點(diǎn)；tmpi[a][b]=-1代表時(shí)刻t，va是vb的前驅(qū)節(jié)點(diǎn)；時(shí)刻t′，va不是vb的前驅(qū)節(jié)點(diǎn).

4) 遍歷矩陣tmpi列，從第j(初始化j=1)列開始.

當(dāng)矩陣tmpi中第b列值只有0和-1值時(shí)，該變化類型設(shè)為2，可以確認(rèn)的是t′時(shí)沒有增加路徑，只是減少了路徑，引起該類型路由變化原因是由于保留鏈路或減少鏈路的Metric減小增加造成的；判斷減少鏈路∑|achange|<任一保留鏈路∑|achange|，是則所有保留鏈路中{achange|achange<0}造成路由變化；否則減少鏈路{achange|achange>0}造成路由變化；判定變化原因后，記錄鏈路獨(dú)有變化詳情；

當(dāng)矩陣tmpi中第b列同時(shí)存在±1值時(shí)，該變化類型設(shè)為4，假設(shè)q為增加路徑的前驅(qū)節(jié)點(diǎn)，判斷增加鏈路∑|achange|<減少鏈路∑|achange|，減少鏈路中{achange|achange>0}造成路由變化；否則增加鏈路中{achange|achange<0}影響路由變化；判定變化原因后，記錄鏈路變化詳情.

注：增加鏈路有多條時(shí)，或減少鏈路有多條時(shí)，該算法仍然適應(yīng).

5)j=j+1；判斷j>n，是跳至步驟6，否則判斷j是否在步驟4已掃描，是跳至第步驟5，否則跳至步驟4.

6)i=i+1；判斷i>n，是跳至步驟7，否則跳至步驟2.

7) 根據(jù)路由變化對(duì)象統(tǒng)計(jì)各個(gè)設(shè)備鏈路狀態(tài)帶來(lái)的路由變化，影響路由數(shù)量由多到少依次排列，并通過(guò)消息提示網(wǎng)絡(luò)管理員.

通過(guò)上述算法將鏈路狀態(tài)變化和路由變化相關(guān)聯(lián)，給出整個(gè)網(wǎng)絡(luò)變化信息，并以列表的形式提供給網(wǎng)絡(luò)管理員，當(dāng)發(fā)現(xiàn)路由異常時(shí)，能夠進(jìn)行異常定位，從而能夠快速恢復(fù)網(wǎng)絡(luò).

3 路由異常檢測(cè)實(shí)驗(yàn)驗(yàn)證

我們部署LSAP到多業(yè)務(wù)的數(shù)據(jù)中心內(nèi)，該數(shù)據(jù)中心業(yè)務(wù)主要包含即時(shí)通信、電商業(yè)務(wù)、金融業(yè)務(wù)、搜索、廣告、云計(jì)算等多業(yè)務(wù).主要驗(yàn)證了系統(tǒng)路由異常檢測(cè)在數(shù)據(jù)中心效果.

3.1 改進(jìn)Dijkstra與傳統(tǒng)Dijkstra算法比較

為驗(yàn)證改進(jìn)版Dijkstra算法的可行性，分析了與傳統(tǒng)Dijkstra算法運(yùn)行時(shí)間對(duì)比，本文針對(duì)數(shù)據(jù)中心內(nèi)不同拓?fù)浼线M(jìn)行了實(shí)驗(yàn).實(shí)驗(yàn)數(shù)據(jù)如表3所示，共有5組實(shí)驗(yàn)數(shù)據(jù)，數(shù)據(jù)集的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)在592～12 965之間，弧段數(shù)在916～32 658之間，節(jié)點(diǎn)數(shù)和弧段數(shù)之比在0.3～0.7之間.實(shí)驗(yàn)從每個(gè)數(shù)據(jù)集合中隨機(jī)選取100組源點(diǎn)和終點(diǎn)，測(cè)試不同網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量和弧段數(shù)量下傳統(tǒng)Dijkstra算法和本文算法運(yùn)行時(shí)間對(duì)比,如表3所示:

Table 3 Algorithm Performance Statistics表3 算法性能統(tǒng)計(jì)

為了測(cè)試算法的效率，分別采用不同的節(jié)點(diǎn)數(shù)和弧段數(shù)對(duì)比傳統(tǒng)Dijkstra算法和改進(jìn)Dijkstra算法最短路徑計(jì)算時(shí)間.我們發(fā)現(xiàn)當(dāng)節(jié)點(diǎn)數(shù)(592和1 980)較少時(shí)，改進(jìn)Dijkstra算法計(jì)算時(shí)間比傳統(tǒng)Dijkstra算法的計(jì)算時(shí)間長(zhǎng)一點(diǎn)，原因在于改進(jìn)Dijkstra算法的初始化時(shí)間會(huì)增加且添加了優(yōu)化頂點(diǎn)選擇處理；當(dāng)節(jié)點(diǎn)數(shù)(≥3 517)增加時(shí)，我們會(huì)發(fā)現(xiàn)改進(jìn)Dijkstra算法的計(jì)算時(shí)間相比于傳統(tǒng)Dijkstra算法少很多；節(jié)點(diǎn)數(shù)和弧段數(shù)越多，改進(jìn)Dijkstra算法的改進(jìn)效果越明顯.本文所論述的改進(jìn)算法在傳統(tǒng)Dijkstra算法的基礎(chǔ)上加以改進(jìn)，優(yōu)化最短路徑的計(jì)算過(guò)程，減少了算法的執(zhí)行時(shí)間.

3.2 數(shù)據(jù)中心環(huán)境

該數(shù)據(jù)中心包括5 000 000臺(tái)以上服務(wù)器、15 000臺(tái)路由設(shè)備并運(yùn)行9 800多應(yīng)用程序.服務(wù)器操作系統(tǒng)主要采用的是自主研發(fā)的Linux系統(tǒng)，每臺(tái)服務(wù)器平均CPU16核，內(nèi)存80 GB.路由設(shè)備涉及Cisco、華為、H3C、中興設(shè)備等，數(shù)據(jù)中心網(wǎng)絡(luò)架構(gòu)以3層網(wǎng)絡(luò)架構(gòu)為主，主要架構(gòu)如圖5所示：

在本系統(tǒng)從2016年4月開始試運(yùn)行并持續(xù)運(yùn)行半年多時(shí)間，主要測(cè)試了2個(gè)區(qū)域數(shù)據(jù)中心間骨干網(wǎng)絡(luò)(圖5中大矩形代表區(qū)域)和主業(yè)務(wù)區(qū)域網(wǎng)絡(luò)(圖5中小矩形代表區(qū)域).骨干網(wǎng)絡(luò)主要負(fù)責(zé)8個(gè)不同地區(qū)的數(shù)據(jù)中心之間的數(shù)據(jù)傳輸，共包括156臺(tái)高性能路由器，不同地區(qū)間路由器相連通過(guò)專線連接；主業(yè)務(wù)區(qū)域網(wǎng)絡(luò)涉及電商業(yè)務(wù)，本文調(diào)研的華東機(jī)房涉及主機(jī)4 992臺(tái)，機(jī)房路由器和接入層路由器共計(jì)58臺(tái).

3.3 數(shù)據(jù)中心路由變化

在本節(jié)中將主要介紹在數(shù)據(jù)中心內(nèi)測(cè)試的詳細(xì)數(shù)據(jù)，包括數(shù)據(jù)中心內(nèi)不同區(qū)域路由變化詳情、詳細(xì)數(shù)據(jù)和LSPLSA異常變化的規(guī)律.

3.3.1 路由變化詳情

圖6是通過(guò)LSAP生成的路由更新信息變化圖，顯示了運(yùn)行ISIS協(xié)議的骨干網(wǎng)絡(luò)與運(yùn)行OSPF協(xié)議的主業(yè)務(wù)區(qū)域網(wǎng)絡(luò)6個(gè)月的域內(nèi)路由信息變化量，給出了該數(shù)據(jù)中心內(nèi)路由變化的概括圖.從圖6我們可以看出，在大部分時(shí)間內(nèi)骨干網(wǎng)絡(luò)的LSP變化還是維持在一個(gè)較低的水平上，但是在5月底6月初和8月底9月初時(shí)路由變化數(shù)量增長(zhǎng)較快，最高能夠超過(guò)2 000，需要說(shuō)明的是當(dāng)網(wǎng)絡(luò)進(jìn)行擴(kuò)容或壓縮時(shí)，路由變化數(shù)會(huì)有提升，但是通常不會(huì)大幅度提升路由變化數(shù)目，路由攻擊和路由交換機(jī)端口的不穩(wěn)定(如頻繁的UPDOWN)通常是引起路由更新變化頻繁的根本原因.路由更新變化數(shù)量代表網(wǎng)絡(luò)收斂速度，變化量越小代表網(wǎng)絡(luò)越穩(wěn)定，變化量越大則代表網(wǎng)絡(luò)更多時(shí)間處于抖動(dòng)之中.

ASR-1.DC8在2016-05-31T03:00:00-05:00:00路由變化，通過(guò)圖7我們可以發(fā)現(xiàn)ASR-1.DC8的鏈路是間歇性變化的，其中 (03:15:00-03:30:00)，(03:54:00-04:03:00)，(04:18:00-04:33:00)三個(gè)時(shí)刻LSA變化最為頻繁，經(jīng)過(guò)與網(wǎng)絡(luò)管理員的確認(rèn)，發(fā)現(xiàn)是由于該設(shè)備的上線時(shí)間較短，查看該設(shè)備當(dāng)時(shí)日志文檔并未發(fā)現(xiàn)端口頻繁UpDown的報(bào)告，最終發(fā)現(xiàn)是連接該端口物理連線接觸問(wèn)題造成該情況的產(chǎn)生.

Fig. 7 Number of changes of LSA on the device ASR-1.DC8圖7 設(shè)備ASR-1.DC8的LSA變化個(gè)數(shù)

表4列出了鏈路狀態(tài)變化的典型類型，包括鏈路變化和Metric變化.鏈路UpDown如表4第2～6行數(shù)據(jù)所示，↑代表添加路由，↓代表取消路由，圖示可以看出在03:24:03時(shí)序列號(hào)為0x0001781f的LSA宣告路由42.120.244.430；在下一時(shí)刻更新的LSA報(bào)文(序列號(hào)+1)可以看出取消宣告42.120.244.430，該端口關(guān)閉；03:24:11時(shí)該端口重新開啟宣告42.120.244. 430，端口頻繁的開啟關(guān)閉導(dǎo)致對(duì)外重復(fù)宣告和取消路由42.120.244.430.鏈路連接變化如表4第7，8行數(shù)據(jù)所示，在03:24:03時(shí)該路由器與ASR-14.DC8是相連接的，在03:24:06時(shí)刻路由器斷開與ASR-14.DC8的連接，建立了與ASR-21.DC8的連接，鏈路連接變化直接導(dǎo)致路由拓?fù)涞淖兓?

Table 4 Schematic Diagram of Link-State Change表4 鏈路狀態(tài)變化示意圖

“↑”means adding routing; “↓”means canceling routing.

Metric變化通常代表鏈路的開銷值，↑代表開銷值增加，↓代表開銷值降低，如表4所示03:28:50時(shí)宣告140.205.19.8030網(wǎng)段的端口Metric從2 000增加10 000；同樣，3:30:15時(shí)宣告61.237.112.830網(wǎng)段的端口Metric從10 000降低到1 000.Metric變化和鏈路變化會(huì)觸發(fā)Dijkstra算法計(jì)算最短路徑樹，Metric變化通常是由網(wǎng)絡(luò)配置觸發(fā)的，鏈路變化的原因則比較多，設(shè)備老化、網(wǎng)線連接、網(wǎng)絡(luò)配置、路由攻擊都是造成鏈路變化的原因，鏈路狀態(tài)的頻繁變化通常是由于設(shè)備老化、網(wǎng)線接觸或路由攻擊等造成端口頻繁UpDown的，因而通過(guò)我們的分析結(jié)果就可以輔助網(wǎng)絡(luò)管理員查找鏈路狀態(tài)不穩(wěn)定的設(shè)備，進(jìn)行路由異常發(fā)現(xiàn)、定位和排除.

Fig. 8 Types of changes of LSP and LSA 圖8 LSPLSA變化類型

在LSAP統(tǒng)計(jì)的變化規(guī)律中我們發(fā)現(xiàn)3種類型的變化：偶爾變化、間歇變化和頻繁變化.經(jīng)統(tǒng)計(jì)，偶爾變化是所有路由器上最普遍的變化類型，在圖8所示偶爾變化中1臺(tái)路由設(shè)備的典型變化，我們會(huì)發(fā)現(xiàn)該路由器在1 d中主要在2個(gè)時(shí)間區(qū)間有LSPLSA變化，其他時(shí)間內(nèi)基本沒有任何變化，變化時(shí)間主要在10:00:00-13:00:00和19:00:00-22:00:00這2個(gè)時(shí)間段內(nèi).對(duì)于無(wú)固定時(shí)間段內(nèi)的偶爾變化類型的路由器，通過(guò)查看設(shè)備日志信息發(fā)現(xiàn)大多數(shù)是由于端口宣告開啟和關(guān)閉造成,造成端口偶爾開啟關(guān)閉的原因是多樣的，如設(shè)備故障、線路老化、路由攻擊等.對(duì)于圖示中具有明顯時(shí)間痕跡的變化，我們發(fā)現(xiàn)10:00:00-13:00:00和19:00:00-22:00:00正是該數(shù)據(jù)中心訪問(wèn)量最大的時(shí)間，且設(shè)備日志并未記錄端口故障信息，把線路老化原因排除后，通過(guò)netflow數(shù)據(jù)發(fā)現(xiàn)該時(shí)間段內(nèi)都是數(shù)據(jù)流通過(guò)該設(shè)備的頂峰時(shí)間和snmp記錄的端口丟包率發(fā)現(xiàn)引起LSPLSA變化的原因是由于網(wǎng)絡(luò)擁塞造成的.

對(duì)于間歇變化的路由器，我們會(huì)發(fā)現(xiàn)這些路由器的共性是變化不規(guī)律、變化量和變化數(shù)不定、間歇變化且從某時(shí)刻間后持續(xù)的間斷進(jìn)行變化.該類型變化通常是由于設(shè)備或線路老化造成端口不穩(wěn)定引起的.在圖8所示頻繁變化路由設(shè)備的典型例子，通過(guò)該折線圖我們可以看出該路由器在1 d時(shí)間內(nèi)是持續(xù)變化的，可以看出該路由器以平均320次h的頻率持續(xù)宣告路由端口狀態(tài)改變.對(duì)于該類型的路由器我們發(fā)現(xiàn)主要是由于鏈路問(wèn)題和網(wǎng)絡(luò)誤配置(如設(shè)備ID設(shè)置相同)造成的.

3.4 異常檢測(cè)和異常定位

在本節(jié)中將主要介紹通過(guò)LSAP在數(shù)據(jù)中心異常檢測(cè)的結(jié)果，通過(guò)本節(jié)內(nèi)容能夠明確路由變化的根本原因，從而輔助網(wǎng)絡(luò)管理員修復(fù)異常或故障.

3.4.1 異常檢測(cè)

表5展示了通過(guò)LSAP在骨干網(wǎng)中的統(tǒng)計(jì)數(shù)據(jù)，主要包括鏈路變更數(shù)、鏈路異常、路由變更、路由異常和路由攻擊事件等.如4月份統(tǒng)計(jì)數(shù)據(jù)，171 (23)代表鏈路變更數(shù)為171次，包括連接關(guān)系改變、端口開啟關(guān)閉、Metric變化等；23代表是由網(wǎng)絡(luò)管理員為網(wǎng)絡(luò)管理需要而人為配置造成的狀態(tài)改變，屬于正常變更，異常鏈路變更數(shù)為171-23=148.975(163)代表路由變更數(shù)為975條，路由變化既包括路徑改變也包括鏈路開銷值改變；其中163代表由人為配置造成造成的路由變化，則異常路由變更數(shù)為975-163=812，其中4月份骨干網(wǎng)總共遭受了2次路由攻擊，由網(wǎng)絡(luò)誤配置造成的路由攻擊記錄為0，從所有記錄中我們可以看出數(shù)據(jù)中心內(nèi)部由于防火墻和流量清洗中心的存在，數(shù)據(jù)中心遭受外界直接路由攻擊的數(shù)量還是非常少的，絕大多數(shù)的路由變化是由于內(nèi)部設(shè)備引起的.

Table 5 Link-Change and Route-Change Statistics of

同時(shí)我們統(tǒng)計(jì)每條鏈路異常導(dǎo)致的路由異常，具體信息如表5所示.鏈路變更'指的是對(duì)路由產(chǎn)生影響的個(gè)數(shù)，對(duì)路由影響既包括路由路徑也包括鏈路開銷值.從表5推算得出60.1%的鏈路變化并未引起路由變化，39.9%的鏈路變化'引起了路由變化，平均影響一半?yún)^(qū)域節(jié)點(diǎn).

3.4.2 異常定位

在本節(jié)，通過(guò)利用14個(gè)節(jié)點(diǎn)的NSFNET網(wǎng)絡(luò)實(shí)例來(lái)驗(yàn)證LSAP算法是如何進(jìn)行異常定位的.圖9是NSFNET原始拓?fù)浼訖?quán)圖，圖10是路由更新后加權(quán)圖.下面我們將具體說(shuō)明異常定位過(guò)程，實(shí)例是根據(jù)節(jié)點(diǎn)4到其他節(jié)點(diǎn)的最短路徑的變化情況推出路由變化，根據(jù)Dijkstra算法可算出圖9，10所示拓?fù)涔?jié)點(diǎn)4到其他節(jié)點(diǎn)的最短路徑，如表6所示.

Fig. 9 Initial network topological graph of NSFNET圖9 NSFNET網(wǎng)絡(luò)初始拓?fù)鋱D

Fig. 10 Network topological graph of NSFNET after updating圖10 路由更新后NSFNET網(wǎng)絡(luò)拓?fù)鋱D

DestinationShortestPathinFig.9CostofFig.9ShortestPathinFig.10CostofFig.1014→2→136004→2→14→2→3→1360024→215004→2150034→2→327004→2→3270054→512004→5260064→5→636004→2→3→64→5→6500074→5→724004→5→7380084→5→7→839004→5→7→8530094→5→7→8→954004→11→12→96700104→5→6→104→5→7→1057004→2→3→6→104→5→6→107100114→1139004→115300124→11→1251004→11→126500134→5→6→7→8→9→134→11→1360004→11→12→9→137300144→5→6→144→5→7→8→1445004→5→6→146800

根據(jù)2.3節(jié)路由異常檢測(cè)算法，可以計(jì)算出tmp4:

遍歷矩陣tmp4列向量，初始化j=1.

與第2列相同，第3列無(wú)變化，則j=j+1=4.

第7，8列與第5列相同，新增路由變化對(duì)象唯一區(qū)別在于影響路由不同，分別為4→7，4→8；j=j+1=6，跳至步驟4.

第9列存在±1，既新增1條路由，又減少1條路由.新增路徑4→11→12→9和減少路徑4→5→7→8→9，經(jīng)計(jì)算增加鏈路∑|achange|=1 800和減少鏈路∑|achange|=1 400，增加鏈路∑|achange|>減少鏈路∑|achange|，則可以判定引起該類型路由變換是由增加鏈路中{achange|achange<0}即a12,9變小造成的.路由變化對(duì)象鏈路：12-9，影響路由：4→9，Metric變化：是，變化類型：4；j=j+1=10，跳至步驟4.

第10列只有0和-1值，減少路徑4→5→7→10，則減少鏈路∑|achange|=1 700；選擇保留路徑4→5→6→10，則保留鏈路∑|achange|=1 400；減少鏈路∑|achange|>保留鏈路∑|achange|，則可以判定引起路由變換原因是由于減少鏈路{achange|achange>0}即a45，a7,10變大造成的，由于a45非獨(dú)有性變化因而路由變換根本原因是由a7,10造成的.路由變化對(duì)象鏈路：7-10，影響路由：4→10，Metric變化：是，變化類型：2；j=j+1=11，跳至步驟4.

第11，12列與第5列相同，新增路由變化對(duì)象唯一區(qū)別在于影響鏈路：4-11，影響路由分別為4→11，4→12；j=j+1=13，跳至步驟4.

與第10列相同，第13列只有0和-1值，減少鏈路∑|achange|<保留鏈路∑|achange|，則可以判定引起路由變換原因是由于保留鏈路{achange|achange<0}即a12,9變小造成的.路由變化對(duì)象鏈路：12-9，影響路由：4→13，Metric變化：是，變化類型：2；j=j+1=14，跳至步驟4.

與第10列相同，第14列只有0和-1值，路由變化對(duì)象鏈路：6-14，影響路由：4→14，Metric變化：是，變化類型：2；j=j+1=15，j>14退出.

路由變化對(duì)象列表如表7所示:

Table 7 Association Table of Link-change and Route-change表7 鏈路變化與路由變化關(guān)聯(lián)表

根據(jù)統(tǒng)計(jì)結(jié)果可以看出節(jié)點(diǎn)4，5之間鏈路變化影響范圍最為廣泛，影響到4個(gè)節(jié)點(diǎn)，由于該鏈路變化，導(dǎo)致3條路由總開銷值變化和1條路由路徑變化；節(jié)點(diǎn)4，11和12，9之間影響了2個(gè)節(jié)點(diǎn)路由，其余節(jié)點(diǎn)只影響了1個(gè)節(jié)點(diǎn)路由.在數(shù)據(jù)中心，我們經(jīng)常會(huì)遇到2點(diǎn)之間訪問(wèn)延遲增大，通過(guò)2.3節(jié)路由異常檢測(cè)和定位算法就能夠給出延遲增大的根本原因.假設(shè)4節(jié)點(diǎn)為網(wǎng)絡(luò)訪問(wèn)入口，14為核心業(yè)務(wù)相連路由器，業(yè)務(wù)方報(bào)告業(yè)務(wù)訪問(wèn)延遲，請(qǐng)求網(wǎng)絡(luò)管理員進(jìn)行排查，此時(shí)網(wǎng)絡(luò)管理員只需要從路由變化對(duì)象中提取影響路由4-14的變化信息即可，我們發(fā)現(xiàn)變化類型為2，說(shuō)明路徑變少了，變少的根本原因是節(jié)點(diǎn)6與節(jié)點(diǎn)14間Metric減少了100.想要恢復(fù)路由，只需要重設(shè)Metric值即可.

通過(guò)表7我們能夠清晰地掌握每條鏈路異常變化帶來(lái)的網(wǎng)絡(luò)變動(dòng)詳情，而不是簡(jiǎn)單地獲知網(wǎng)絡(luò)變化數(shù)目，在LSAP試運(yùn)行期間能夠有效地幫助網(wǎng)絡(luò)管理員分析每條鏈路變化，進(jìn)行路由異常檢測(cè)和異常定位.

4 結(jié) 論

眾所周知，數(shù)據(jù)中心路由異常、路由抖動(dòng)普遍存在，路由更新頻繁，但是缺乏有效的方法監(jiān)控，發(fā)現(xiàn)異常后無(wú)法進(jìn)行故障定位.本文中，我們提出了一種基于LSDB的數(shù)據(jù)中心網(wǎng)絡(luò)分析器LSAP，不僅通過(guò)被動(dòng)的搜集路由更新報(bào)文獲取拓?fù)渥兓?，而且通過(guò)改進(jìn)的Dijkstra算法快速計(jì)算路由表，統(tǒng)計(jì)分析所有路由變化、關(guān)聯(lián)拓?fù)渥兓c路由變化，先于業(yè)務(wù)發(fā)現(xiàn)網(wǎng)絡(luò)故障、路由攻擊.LSAP對(duì)網(wǎng)絡(luò)改動(dòng)很少，被動(dòng)搜集數(shù)據(jù)不影響網(wǎng)絡(luò)自身穩(wěn)定性，因而適合于對(duì)穩(wěn)定性要求較高的數(shù)據(jù)中心部署.

致謝感謝中國(guó)科學(xué)院國(guó)有資產(chǎn)經(jīng)營(yíng)有限責(zé)任公司對(duì)本文的大力支持!感謝華為公司的曹政博士對(duì)本論文的技術(shù)指導(dǎo)！

[1]Bhattacharyya D, Kalita J. Network anomaly detection:A machine learning perspective[J]. Network Anomaly Detection, 2013, 45(45): 455-463

[2]Li Dan, Chen Guihai, Ren Fengyuan. Data center network research progress and trengs[J]. Chinese Journal of Computers, 2014, 25(7): 87-89 (in Chinese)(李丹, 陳貴海, 任豐原. 數(shù)據(jù)中心網(wǎng)絡(luò)的研究發(fā)展與趨勢(shì)[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 25(7): 87-89)

[3]Zeng Hongyi, Kazemian P, Varghese G, et al. Automatic test packet generation[J]. IEEEACM Trans on Networking, 2014, 22(2): 554-566

[4]Hofstede R, Celeda P, Trammell B, et al. Flow monitoring explained: From packet capture to data analysis with netflow and IPFIX[J]. IEEE Communications Surveys & Tutorials, 2014, 16(4): 2037-2064

[5]Balabine I, Velednitsky A. Method and system for confident anomaly detection in computer network traffic: EU, EP3138008[P]. 2017-03-08

[6]Kim Y I, Park S J, Kim Y J, et al. Development of AMI NMS (network management system) using SNMP for network monitoring of meter reading devices[J]. KEPCO Journal on Electric Power and Energy, 2016, 2(2): 259-268

[7]Jubinville J, Teachman M, Anderson D. Energy monitoring system using network management protocols: US, EP2186258[P]. 2010-05-19

[8]Sonawane V R, Singh L L, Nunse P R, et al. Visual monitoring system using simple network management protocol[C]Proc of the 11th Int Conf on Computational Intelligence and Communication Networks. Piscataway, NJ: IEEE, 2015: 197-200

[9]Ahmed M, Mahmood A N, Hu J. A survey of network anomaly detection techniques[J]. Journal of Network & Computer Applications, 2016, 60: 19-31

[10]Shaikh A, Goyal M, Greenberg A, et al. An OSPF topology server: Design and evaluation[J]. IEEE Journal on Selected Areas in Communications, 2006, 20(4): 746-755

[11]Shaikh A, Greenberg A. OSPF monitoring: Architecture, design and deployment experience[C]Proc of the 1st Conf on Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2004: 5-5

[12]Zhang Shu, Kobayashi K. Rtanaly: A system to detect and measure IGP routing changes[C]Proc of the 5th Int Workshop on IP Operations and Management. Berlin: Springer, 2005: 162-172

[13]Mayer D. University of oregon route views project[EBOL]. Eugene, Oregon: University of Oregon, 2005 [2017-03-17]. http:www.routeviews.org

[14]Axel P. RIPE RIS project[EBOL]. Amsterdam, Netherlands: RIPE Network Coordination Centre, 2002 [2016-09-30]. http:data.ris.ripe.net

[15]Lad M, Massey D, Pei D, et al. PHAS: A prefix hijack alert system[C]Proc of Conf on USENIX Security Symp. Berkeley, CA: USENIX Association, 2006: 153-166

[16]Al-Musawi B, Branch P, Armitage G. BGP anomaly detection techniques: A survey[J]. IEEE Communications Surveys & Tutorials, 2017, 19(1): 377-396

XuGang, born in 1988. PhD candidate, engineer. His main research interests include datacenter networks, electronicoptical hybrid network and SDN.

WangZhan, born in 1986. PhD. His main research interests include computer architecture, high performance computing, interconnection network, optical networking.

ZangDawei, born in 1988. PhD. His main research interests include computer architecture and datacenter networks.

AnXuejun, born in 1966. PhD, senior engineer. Senior member of CCF. His main research interests include computer architecture, high performance interconnectio (axj@ncic.ac.cn).