網(wǎng)絡(luò)傳輸態(tài)勢感知的研究與實(shí)現(xiàn)

卓瑩，龔春葉，龔正虎

（國防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院，湖南 長沙 410073）

1 引言

隨著信息網(wǎng)絡(luò)規(guī)模的迅速擴(kuò)大，系統(tǒng)復(fù)雜性也隨之增加。傳統(tǒng)的網(wǎng)絡(luò)管理中各功能單元處于獨(dú)立的工作狀態(tài)，缺少有效的信息提取和信息融合機(jī)制，無法建立網(wǎng)絡(luò)資源之間的聯(lián)系，全局信息表現(xiàn)能力差。海量的網(wǎng)管信息非但不能加強(qiáng)管理，反而增加了網(wǎng)絡(luò)管理員的負(fù)擔(dān)。現(xiàn)代網(wǎng)絡(luò)管理必須能夠提供多樣化、個性化的管理行為，提供被管對象的詳細(xì)信息，了解整個網(wǎng)絡(luò)的運(yùn)行狀況，并且能夠根據(jù)指揮人員的需求提供服務(wù)。因此，基于融合的網(wǎng)絡(luò)態(tài)勢感知必將成為網(wǎng)絡(luò)管理的發(fā)展方向[1,2]。

傳輸是網(wǎng)絡(luò)最基本的功能。網(wǎng)絡(luò)傳輸態(tài)勢感知（NTSA）是指在大規(guī)模信息網(wǎng)絡(luò)中，從傳統(tǒng)的單元網(wǎng)管獲取鏈路流量信息、資源運(yùn)行狀況、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)等能夠?qū)鬏敭a(chǎn)生影響的各種測量指標(biāo)（稱為態(tài)勢因子），評估當(dāng)前狀態(tài)、預(yù)測未來發(fā)展趨勢，并以可視化的方式進(jìn)行展示。NTSA包括獲取、評估、預(yù)測以及可視化4個環(huán)節(jié)，強(qiáng)調(diào)網(wǎng)絡(luò)元素之間的關(guān)系，決定了態(tài)勢因子的匯聚方式，給出一種有利或不利的判斷性結(jié)果。簡而言之就是態(tài)勢因子集合R與態(tài)勢空間框架θ的映射關(guān)系∶fRθ→。

NTSA的目標(biāo)是將態(tài)勢感知技術(shù)應(yīng)用于網(wǎng)絡(luò)管理，在急劇動態(tài)變化的復(fù)雜環(huán)境中，高效組織各種信息，將已有的表示網(wǎng)絡(luò)局部特征的指標(biāo)綜合化，使其能夠表示網(wǎng)絡(luò)傳輸?shù)暮暧^整體狀態(tài)，從而加強(qiáng)管理員對網(wǎng)絡(luò)的理解能力，為高層指揮人員提供決策支持。

態(tài)勢感知的研究主要包括3個方面：模型、知識表示和評估方法。其中模型研究比較完善，趨于統(tǒng)一；評估方法作為態(tài)勢感知的重點(diǎn)，理論研究相對成熟[3]；有關(guān)知識表示的研究相對較少[4]。然而現(xiàn)有的研究面向通用問題，沒有很好地將態(tài)勢感知技術(shù)運(yùn)用到網(wǎng)絡(luò)傳輸領(lǐng)域，缺少針對網(wǎng)絡(luò)傳輸具體特點(diǎn)設(shè)計(jì)的模型和評估方法；另一方面，有關(guān)網(wǎng)絡(luò)傳輸?shù)难芯窟€沒有上升到態(tài)勢的高度，仍舊停留在數(shù)據(jù)層面上，采用的指標(biāo)體系比較簡單，沒有綜合分析各種態(tài)勢因子，而層次結(jié)構(gòu)、加權(quán)函數(shù)為主流的評估方法缺少理論支持，無法展現(xiàn)網(wǎng)絡(luò)傳輸系統(tǒng)元素間錯綜復(fù)雜的關(guān)系。

本文充分利用態(tài)勢感知研究成果，結(jié)合網(wǎng)絡(luò)傳輸具體問題展開NTSA研究。首先結(jié)合空間流量分析和數(shù)據(jù)挖掘技術(shù)，提出了基于空間流量聚類的網(wǎng)絡(luò)傳輸態(tài)勢感知模型（STC模型）。接下來分別討論了特征選擇、聚類算法、拓?fù)浞治龅汝P(guān)鍵技術(shù)：證明了互信息和信息增益的等價性，并以此為基礎(chǔ)進(jìn)行態(tài)勢因子選擇，降低態(tài)勢空間規(guī)模；在分析網(wǎng)絡(luò)數(shù)據(jù)特點(diǎn)的基礎(chǔ)上，提出了一種面向傳輸模式劃分的高維數(shù)據(jù)流聚類算法（SACluster算法），并且結(jié)合聚類和粗集技術(shù)設(shè)計(jì)了網(wǎng)元傳輸態(tài)勢評估方法；以圖論為基礎(chǔ)，進(jìn)行拓?fù)渲匾苑治觯_定網(wǎng)元對傳輸態(tài)勢的影響。最后設(shè)計(jì)了NTSA系統(tǒng)邏輯結(jié)構(gòu)，實(shí)驗(yàn)和試運(yùn)行論證了系統(tǒng)的可行性和有效性，并且簡要給出相關(guān)工作以及比較結(jié)果。

2 基于空間流量聚類的NTSA模型

針對現(xiàn)有研究存在的問題，本文結(jié)合空間流量分析和數(shù)據(jù)挖掘技術(shù)，提出了基于空間流量聚類的網(wǎng)絡(luò)傳輸態(tài)勢感知模型——STC模型。首先介紹STC模型的基本思想。

所謂空間流量分析[5]，相對時間流量分析而言，不僅僅分析單條鏈路流量的時間行為，而是綜合考慮鏈路流量特征和互連方式，分析跨越多條鏈路或全網(wǎng)鏈路的流量模式，支持全網(wǎng)視圖。空間流量分析利用“所有網(wǎng)絡(luò)事件都會在流量上有所反映”這一基本假設(shè)[6]，實(shí)現(xiàn)了網(wǎng)絡(luò)拓?fù)浜土髁刻卣鞯慕换ィ軌蚪⒏叨雀爬ǖ耐暾木W(wǎng)絡(luò)態(tài)勢視圖。

空間流量分析最大的挑戰(zhàn)在于缺少先驗(yàn)知識。傳輸態(tài)勢涉及的測量指標(biāo)眾多，單一指標(biāo)對傳輸產(chǎn)生的影響不同，指標(biāo)之間也存在復(fù)雜的關(guān)系相互影響，加之相關(guān)研究很少，沒有對傳輸模式進(jìn)行劃分的成果可以借鑒。如果通過領(lǐng)域?qū)＜覍鬏斈Ｊ竭M(jìn)行劃分，不可避免帶有主觀色彩，而且很難公平準(zhǔn)確地判斷每一個指標(biāo)對態(tài)勢做出的貢獻(xiàn)。聚類作為數(shù)據(jù)挖掘的主要方法，屬于無監(jiān)督機(jī)器學(xué)習(xí)方法，具備獲取知識、揭示規(guī)律的能力。聚類分析能夠根據(jù)海量網(wǎng)絡(luò)數(shù)據(jù)自動完成對傳輸態(tài)勢的模式劃分，提取典型態(tài)勢特征，不需要任何先驗(yàn)知識，科學(xué)客觀。

STC模型彌補(bǔ)了簡單指標(biāo)、單條鏈路的不足，既能夠融合多種影響傳輸態(tài)勢的因素，揭示各種已知和未知的異常事件，避免了采用層次結(jié)構(gòu)和權(quán)重分析方法的缺陷；又能夠綜合考慮拓?fù)浣Y(jié)構(gòu)的影響，揭示網(wǎng)絡(luò)元素間錯綜復(fù)雜的關(guān)系，實(shí)現(xiàn)全網(wǎng)傳輸態(tài)勢感知，體現(xiàn)了態(tài)勢整體性和宏觀性的特點(diǎn)；而且模式聚類擴(kuò)展靈活、適用性強(qiáng)，不局限于流量特征。

結(jié)合空間流量數(shù)據(jù)的特點(diǎn)，對網(wǎng)絡(luò)傳輸態(tài)勢感知進(jìn)行建模：STC(Topo, Traffic)，其中Topo代表拓?fù)湫畔ⅲ琓raffic代表流量信息。

拓?fù)湫畔ňW(wǎng)絡(luò)元素及其之間的連接關(guān)系，表示為Topo(ID, Time, Node, Link, ψ)。其中，ID代表某一次拓?fù)浒l(fā)現(xiàn)的標(biāo)識，是唯一的。Time代表此次拓?fù)浒l(fā)現(xiàn)的時間。Node代表節(jié)點(diǎn)集合，使用四元組(IDN, C, W, Dsc)來表示；其中，IDN是節(jié)點(diǎn)的唯一標(biāo)識；C代表節(jié)點(diǎn)處理能力；W代表節(jié)點(diǎn)的重要性權(quán)值，由網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以及節(jié)點(diǎn)處理能力決定；Dsc用于描述節(jié)點(diǎn)相關(guān)信息，是一個可擴(kuò)展項(xiàng)。Link代表鏈路集合，與節(jié)點(diǎn)集合類似，統(tǒng)一使用四元組(IDL,C,W,Dsc)來表示，不同之處在于C代表鏈路容量。ψ 代表連接關(guān)系，ψ ? N ode× N ode 。

流量信息包括通過流量分析挖掘所獲取的有關(guān)態(tài)勢感知的各類信息和知識，表示為 Traffic(ID,Time, Trace, IS, SF, SP, AR)。其中：ID為某個網(wǎng)元（節(jié)點(diǎn)或者鏈路統(tǒng)稱為網(wǎng)絡(luò)元素，簡稱網(wǎng)元）的標(biāo)識。Time代表流量發(fā)生時間。Trace代表流量采集獲得的原始報(bào)文信息。IS代表指標(biāo)體系（index system），通過對Trace進(jìn)行流量分析獲得反映網(wǎng)絡(luò)傳輸態(tài)勢的特征的集合。IS={a1,a2,…,an}，其中，ai為流量特征。SF代表態(tài)勢因子（situation factor），經(jīng)過特征選擇獲得能夠引起網(wǎng)絡(luò)態(tài)勢發(fā)生變化的重要因素的集合；SF={f1,f2,…,fd}，其中，fk為態(tài)勢因子，fk∈IS。SF是指標(biāo)體系的子集，SFIS?。SP代表態(tài)勢模式（situation pattern），依據(jù)態(tài)勢因子的取值，通過聚類對傳輸態(tài)勢模式進(jìn)行劃分；每種態(tài)勢模式形如：

其中，vk為態(tài)勢因子 fk的取值。AR代表評估規(guī)則（assessment rule），在態(tài)勢模式劃分的基礎(chǔ)上，確定每種模式的態(tài)勢取值，生成態(tài)勢評估規(guī)則。

基于 STC模型進(jìn)行傳輸態(tài)勢感知建模的流程如下：

{ 對拓?fù)鋽?shù)據(jù)進(jìn)行建模 }

step1 拓?fù)浒l(fā)現(xiàn) TopoDiscovery，獲取拓?fù)湫畔?Topo(ID, Time, Node, Link, ψ)；

step2 拓?fù)渫评?TopoReference(Node, Link,ψ)，修正拓?fù)湫畔ⅲ?/p>

step3 拓?fù)浞治?TopoAnalysis(ψ, C)，確定鏈路的重要性W；

{ 對流量數(shù)據(jù)進(jìn)行建模 }

step4 流量采集TrafficCollection，獲取原始流量數(shù)據(jù)Trace；

step5 流量分析 TrafficAnalysis(Trace)，建立指標(biāo)體系IS；

step6 對每一個指標(biāo) ai∈IS，進(jìn)行離散化Discretization(ai)和標(biāo)準(zhǔn)化Standardization(ai)；

step7 流量特征選擇 FeatureSelection(IS)，建立態(tài)勢因子集合SF；

step8 在態(tài)勢因子集合上進(jìn)行模式劃分PatternMining(Trace,SF)，建立態(tài)勢模式SP；

step9 依據(jù)態(tài)勢模式劃分結(jié)果進(jìn)行規(guī)則設(shè)計(jì)RuleDesign(SP)，建立態(tài)勢評估規(guī)則AR；

{ 人機(jī)交互，專家分析和確認(rèn) }

step10 模式分析PatternAnalysis(SP)；

step11 模型調(diào)整ModelAdjustment(W，AR)；

{迭代}

step12 判斷模型是否有效，如果不再適用，重復(fù)以上步驟進(jìn)行建模。

其中，拓?fù)浞治觯╯tep 3）執(zhí)行拓?fù)渲匾苑治觯_定網(wǎng)元對傳輸態(tài)勢的影響；特征選擇（step 7）執(zhí)行態(tài)勢因子選擇，縮小指標(biāo)體系的規(guī)模，建立精簡的態(tài)勢空間；模式挖掘（step 8）執(zhí)行傳輸態(tài)勢模式劃分，通過聚類分析提取網(wǎng)元傳輸模式。下面將對上述STC模型的3個關(guān)鍵技術(shù)，逐一進(jìn)行深入討論。規(guī)則設(shè)計(jì)（step 9）通過引入粗集分析，自動生成態(tài)勢評估規(guī)則，相關(guān)內(nèi)容已經(jīng)另文敘述[7]。其他技術(shù)或者來自傳統(tǒng)的網(wǎng)絡(luò)管理，例如拓?fù)浒l(fā)現(xiàn)和推理（step1和step2）、流量采集和分析（step4和step5）；或者可以借鑒成熟的研究成果，例如數(shù)據(jù)標(biāo)準(zhǔn)化和離散化（step 6）；或者需要領(lǐng)域?qū)＜业膮⑴c，例如模式分析和模型調(diào)整（step10和step11），本文不作介紹。

3 關(guān)鍵技術(shù)

3.1 基于IG/MI的態(tài)勢因子選擇

降低數(shù)據(jù)空間的維度主要有2種方法。①特征提取方法，或者稱為維度約簡，通過線性或者非線性組合原始維度產(chǎn)生新的維度，把原始數(shù)據(jù)空間映射到使用新維建立的低維空間，最具代表性的是主成分分析PCA。②特征選擇方法，即從維度空間中選擇一個維度子集，往往需要用戶指定。由于流量指標(biāo)都有明確的意義，揭示了流量的某種特征；但是新維的含義則很難給出解釋[8]。考慮到評估結(jié)果易于理解，本文選擇后者。

常用的特征選擇方法包括文檔頻率(DF, document frequency)、信息增益(IG, information gain)和互信息(MI, mutual information)等，在文本分類中得到深入研究并廣泛應(yīng)用[9]。由于態(tài)勢評估盡可能采用便于監(jiān)測的指標(biāo)，又經(jīng)過level 1融合和level 2數(shù)據(jù)標(biāo)準(zhǔn)化，因此數(shù)據(jù)比較完整，使得DF失去作用，本文只討論IG和MI。

不同于文本分類，一個特征只區(qū)分出現(xiàn)與否 2種情況；高維數(shù)據(jù)的每一維可以有多個不同的取值，需要綜合所有取值對分類的作用。為此，對IG和MI的定義進(jìn)行如下修改。

定義1 設(shè)態(tài)勢模式S共有n種，記作Sk(k=1,2, …, n)。令表示樣本總數(shù)，則模式Sk的概率用p(Sk)=Sk/S估計(jì)，簡記為pk。為簡單起見，沒有區(qū)分態(tài)勢模式的名稱和數(shù)量|Sk|，統(tǒng)一記作Sk。

態(tài)勢因子F共有d個，對于某一個因子Fi(i=1, 2, …,d)可能有m種取值，記作vj(j=1, 2, …, m)。則互信息定義為：

信息增益定義為： I G( F ) = I( S ) - E ( F)。

盡管已有的實(shí)驗(yàn)結(jié)果表明：IG是最有效的特征選擇方法之一；DF的效果稍差，但和IG基本相似；而MI相對較差。然而筆者發(fā)現(xiàn)，考慮特征取值的影響對原有定義進(jìn)行修改之后，IG和MI 2種方法對于特征的評價是一致的。下面給出IG和MI等價性的證明。

證明

無論是信息增益還是互信息，都是衡量2個隨機(jī)變量相互之間獨(dú)立程度的測度，反映了態(tài)勢因子f導(dǎo)致態(tài)勢模式S不確定度的縮減量。由定義可知，IG/MI的取值越大，f和S之間的相關(guān)性越強(qiáng)，f越重要。由于缺少態(tài)勢模式的先驗(yàn)知識，態(tài)勢因子選擇只能在聚類的基礎(chǔ)上，計(jì)算F和S之間的IG/MI。

3.2 面向傳輸模式劃分的聚類算法

考慮到網(wǎng)絡(luò)傳輸?shù)奶攸c(diǎn)，對聚類算法提出了更高的要求，具體分析如下。① 網(wǎng)絡(luò)數(shù)據(jù)是一種典型的數(shù)據(jù)流，數(shù)據(jù)量大，潛在無限，到達(dá)速率不確定，只能按到達(dá)順序訪問且僅能被掃描一次或有限幾次，因此要求聚類算法滿足一遍掃描，有限內(nèi)存，輸入順序不敏感等原則。② 網(wǎng)絡(luò)測量數(shù)據(jù)具有連續(xù)性、動態(tài)變化，要求聚類算法既能夠跟上流的速度，又能夠反映流的演化情況。③ 指標(biāo)體系龐大、維數(shù)眾多，要求聚類算法可以解決高維數(shù)據(jù)聚類問題，并且具有良好的可擴(kuò)展性。④ 高維數(shù)據(jù)的稀疏性，導(dǎo)致數(shù)據(jù)在低維子空間形成聚類，而在高維空間沒有聚類特征。⑤ 網(wǎng)絡(luò)測量數(shù)據(jù)是結(jié)構(gòu)化數(shù)據(jù)，測量指標(biāo)既有連續(xù)型又有離散型，要求聚類算法可以處理混合屬性數(shù)據(jù)。

根據(jù)以上分析，提出了一種面向傳輸模式劃分的聚類(SACluster)算法。SACluster算法首先對數(shù)據(jù)空間進(jìn)行“網(wǎng)格”劃分，在此基礎(chǔ)上，進(jìn)行全空間聚類，通過合并相連密集網(wǎng)格形成簇。緊接著進(jìn)行子空間聚類，對不滿足密度閾值的簇采用自頂向下的策略、兼顧密度與維度雙重標(biāo)準(zhǔn)進(jìn)行2次聚類：通過降低聚類空間的維度，使不滿足密度閾值的簇實(shí)現(xiàn)相連，從而建立所有可能包含投影簇的子空間；然后進(jìn)行迭代，在候選子空間中逐一搜索最優(yōu)投影簇，直到發(fā)現(xiàn)所有滿足密度閾值的投影簇，并且采用滑動窗口技術(shù)實(shí)現(xiàn)增量更新，動態(tài)維護(hù)聚類結(jié)果。所謂最優(yōu)投影簇，是指簇中的點(diǎn)盡可能多，簇的維度盡可能高，即投影簇質(zhì)量函數(shù)取值最大。

SACluster算法描述如下：

step1 聚類空間網(wǎng)格劃分；

step2 一遍掃描數(shù)據(jù)流，統(tǒng)計(jì)網(wǎng)格密度信息；

step3 合并相連密集網(wǎng)格（密度大于 τg），在全空間建立簇；

step4 輸出滿足密度閾值τc的簇；

step5 合并任意 2 個密度滿足[τs,τc)的簇，建立最高維度候選投影簇；

step6 搜索不滿足密度閾值τc的簇，統(tǒng)計(jì)候選投影簇的密度信息；

step7 從候選投影簇中選出一個最優(yōu)投影簇；

step8 如果最優(yōu)投影簇滿足密度閾值τc，輸出該投影簇；

step9 重復(fù)step 6～step 8，直到?jīng)]有滿足密度閾值τc的投影簇或者達(dá)到終止條件；

step10 如果到達(dá)更新間隔，增量更新聚類結(jié)果。

SACluster算法結(jié)合密度和網(wǎng)格2種方法，有效降低大規(guī)模數(shù)據(jù)流聚類空間的規(guī)模，擴(kuò)展靈活，能夠處理混合屬性數(shù)據(jù)，產(chǎn)生任意形狀的簇，且對噪聲和輸入順序不敏感。子空間方法使用原始維而非新維建立子空間，簡單、易理解，同時有效解決了高維數(shù)據(jù)稀疏性問題。自頂向下的搜索策略充分利用網(wǎng)絡(luò)數(shù)據(jù)的分布特征，滿足數(shù)據(jù)流一遍掃描的需求，而且實(shí)現(xiàn)了在不同維度的不同子空間搜索投影簇。增量更新既能夠反映數(shù)據(jù)流的演化過程；又以較短的時間間隔更新結(jié)果，滿足在線聚類對響應(yīng)時間的要求。借助滑動窗口技術(shù)，有效降低算法復(fù)雜性的同時，保證參與聚類的樣本量，維護(hù)模式劃分穩(wěn)定性。增量更新算法已經(jīng)另文敘述[10]。

SACluster是一個高效的高維數(shù)據(jù)流子空間聚類算法。假設(shè)有n個數(shù)據(jù)點(diǎn)，分布在g個網(wǎng)格中，則全空間聚類的時間復(fù)雜度為O(n+g2)；簇個數(shù)c，不滿足密度閾值τc的簇個數(shù)近似取c（略小于 c），候選子空間的個數(shù)s，投影簇的個數(shù)p，則子空間聚類的時間復(fù)雜度為O(c2+pcs)。可以通過限制參與聚類的密集網(wǎng)格的密度 τg以及建立子空間的候選簇的密度τs來降低算法復(fù)雜度。如果態(tài)勢因子d個，增量更新維護(hù)w個窗口，則算法的空間復(fù)雜度為O(wdg)。

3.3 基于圖論的拓?fù)渲匾苑治?/h3>

評估整個網(wǎng)絡(luò)的傳輸態(tài)勢，還需要了解每個網(wǎng)元對網(wǎng)絡(luò)傳輸態(tài)勢的影響，即鏈路/節(jié)點(diǎn)的拓?fù)渲匾裕饕ňW(wǎng)元對網(wǎng)絡(luò)拓?fù)涞呢暙I(xiàn)以及網(wǎng)元自身的傳輸能力2個方面。本文運(yùn)用圖論中有關(guān)“容量網(wǎng)絡(luò)”的理論[11]，進(jìn)行網(wǎng)元的拓?fù)渲匾苑治觥?/p>

在圖論中，網(wǎng)絡(luò)是指具有2個特定頂點(diǎn)：發(fā)點(diǎn)（source）x和收點(diǎn)（sink）y的加權(quán)連通圖，記作N=(Dxy, w)。若N為非負(fù)的容量函數(shù)c，則稱網(wǎng)絡(luò)N=(Dxy, c)為容量網(wǎng)絡(luò)（capacity network）。對應(yīng)到傳輸網(wǎng)絡(luò)，圖論中的“容量網(wǎng)絡(luò)”是指網(wǎng)絡(luò)中2個節(jié)點(diǎn)：源（source）和目的（destination）之間所有路徑（path）組成的包含傳輸能力信息的連接圖。為了避免混淆，下文中全部采用傳輸網(wǎng)絡(luò)術(shù)語。假設(shè)傳輸網(wǎng)絡(luò) N(node, link, ψ, c)，由 v 個節(jié)點(diǎn)（node）、ε條鏈路（link）組成，ψ表示節(jié)點(diǎn)到鏈路的關(guān)聯(lián)函數(shù)（incident function），c表示網(wǎng)元傳輸能力，即容量函數(shù)；則網(wǎng)絡(luò)中包含r種連接，r=v(v-1)/2，即任意2個節(jié)點(diǎn)之間的連接，記作Rxy。

首先討論鏈路的重要性。對于源s到目的d的連接 Rsd，當(dāng)連接中的所有鏈路正常運(yùn)行時，該連接可以達(dá)到最大傳輸容量CN(Rsd)；若某一鏈路l失效，最大傳輸容量將受到影響而減小，記作CN-{l}(Rsd)。CN(Rsd)和 CN-{l}(Rsd)的差別反映了鏈路l對連接Rsd的影響。由此定義鏈路l對連接Rsd的重要性LIl,Rsd：

進(jìn)而定義鏈路l對整個傳輸網(wǎng)絡(luò)的重要性LIl：

其中l(wèi)=1, 2, …, ε。式（2）CN(Ri)的計(jì)算建立在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上，充分考慮了鏈路l的拓?fù)渲匾浴７帜窩N(Ri)-CN-{l}(Ri)表示鏈路l為連接Ri提供的傳輸能力，以鏈路容量為依據(jù)，體現(xiàn)了鏈路對傳輸?shù)呢暙I(xiàn)。

接下來討論節(jié)點(diǎn)的重要性。節(jié)點(diǎn)重要性同樣考慮拓?fù)渲匾院吞幚砟芰?個方面。若節(jié)點(diǎn)失效，則以該節(jié)點(diǎn)為頂點(diǎn)的鏈路也會失效，可見節(jié)點(diǎn)的重要性受到與之關(guān)聯(lián)的所有鏈路重要性的影響，前者應(yīng)該是后者重要性之和。同時考慮到節(jié)點(diǎn)處理能力t和關(guān)聯(lián)鏈路傳輸容量存在差別，若前者小于后則，則該節(jié)點(diǎn)將會成為瓶頸限制網(wǎng)絡(luò)傳輸能力。據(jù)此分析定義容量因子Fn：

則節(jié)點(diǎn)重要性NIn定義如下：

式（4）中Fn反映節(jié)點(diǎn)處理能力對傳輸?shù)挠绊懀溌吠負(fù)渲匾砸约肮?jié)點(diǎn)的度隱含地體現(xiàn)了節(jié)點(diǎn)的拓?fù)渲匾浴?/p>

分析了鏈路/節(jié)點(diǎn)重要性之后，只需對重要性進(jìn)行簡單的歸一化處理（令），即可獲得網(wǎng)元重要性權(quán)值。

圖論中計(jì)算最大傳輸容量的方法比較成熟，例如標(biāo)號法[12,13]。對網(wǎng)元傳輸能力c為非負(fù)整數(shù)的整容量網(wǎng)絡(luò)，標(biāo)號法是有效算法，復(fù)雜度為O(vε2)。

4 系統(tǒng)設(shè)計(jì)與實(shí)驗(yàn)分析

本文在STC模型的基礎(chǔ)上，結(jié)合網(wǎng)絡(luò)傳輸這一具體應(yīng)用，提出了網(wǎng)絡(luò)傳輸態(tài)勢感知系統(tǒng)結(jié)構(gòu)。如圖1所示，NTSA體系結(jié)構(gòu)堅(jiān)持closing-the-loop的理念，始終將人作為NTSA中的一個重要環(huán)節(jié)，突出動態(tài)循環(huán)的本質(zhì)，強(qiáng)調(diào)反饋的重要作用，體現(xiàn)了DFIG模型的6層結(jié)構(gòu)以及Endsley模型對態(tài)勢感知的細(xì)化。該體系結(jié)構(gòu)包括通信模塊、知識發(fā)現(xiàn)模塊、評估模塊、預(yù)測模塊、可視化模塊、人機(jī)交互模塊、自主管理模塊以及模式表。

不同于DFIG模型的信息總線結(jié)構(gòu)，本文采用基于Web服務(wù)的信息交換機(jī)制構(gòu)建通信平臺，作為各級融合進(jìn)行信息交換和互操作的方式，實(shí)現(xiàn)了NTSA原型系統(tǒng)。

圖1 網(wǎng)絡(luò)傳輸態(tài)勢感知系統(tǒng)結(jié)構(gòu)

為了驗(yàn)證 STC模型，本節(jié)對所提出的算法以及原型系統(tǒng)進(jìn)行測試。實(shí)驗(yàn)平臺配置如下：AMD Athlon Dual Core 4200+GHz/2GB，Windows XP，所用代碼均用ActivePerl（5.8.8）實(shí)現(xiàn)。實(shí)驗(yàn)所使用的數(shù)據(jù)有2種，第1種是來源于 MIT Lincoln實(shí)驗(yàn)室的 KDDCup’99入侵檢測數(shù)據(jù)集[14]，第2種數(shù)據(jù)來源于美國應(yīng)用網(wǎng)絡(luò)研究國家實(shí)驗(yàn)室(NLANR)被動測量和分析工作組(PMA)在 HPC網(wǎng)絡(luò)中設(shè)置多個測量點(diǎn)被動測量Internet數(shù)據(jù)[15]。

4.1 實(shí)驗(yàn)1：SACluster算法和態(tài)勢因子選擇

由于缺少有關(guān)網(wǎng)絡(luò)傳輸態(tài)勢的研究作為比較，本文采用通用的測試數(shù)據(jù)集KDDCup’99驗(yàn)證聚類SACluster算法。KDDCup’99記錄了4 898 431條流（flow）記錄，分為正常模式和22種入侵模式，每條記錄點(diǎn)包括1維連接模式（正常或者入侵）和41維屬性，其中連續(xù)型屬性33維，離散型屬性8維注1①注 1 在KDDCup’99描述文檔中，特征su_attempted的類型被標(biāo)記為離散型，實(shí)際在數(shù)據(jù)集中特征su_attempted記錄了嘗試“su root”命令的次數(shù)，取值0，1，2，應(yīng)該屬于連續(xù)型。。KDDCup’99數(shù)據(jù)集來自真實(shí)的網(wǎng)絡(luò)，和本文研究的網(wǎng)絡(luò)傳輸數(shù)據(jù)具有相似性，故可以用來做測試數(shù)據(jù)。

聚類準(zhǔn)確性：本文使用聚類純度[16]和分類正確率2個指標(biāo)衡量聚類質(zhì)量。

定義2 聚類純度。聚類純度定義為簇/投影簇中主體類別i的數(shù)據(jù)點(diǎn)在簇/投影簇中所占的比例，形式化描述，c為簇的個數(shù)。

定義 3 分類正確率。分類正確率定義為在參與聚類的數(shù)據(jù)點(diǎn)中最終被正確劃分到真實(shí)分類的比例，形式化描述如下，n為數(shù)據(jù)點(diǎn)總數(shù)。

聚類純度由簇純度和投影簇純度共同決定，如圖2所示，簇純度全部達(dá)到100%，投影簇純度隨數(shù)據(jù)點(diǎn)個數(shù)的增加逐漸降低，但由于投影簇覆蓋的數(shù)據(jù)點(diǎn)個數(shù)較少，對純度的影響也較小，故純度始終保持較高水平，均在98%以上。

圖2 聚類純度

由于非密集網(wǎng)格不參與聚類，使得非密集網(wǎng)格覆蓋的數(shù)據(jù)點(diǎn)沒有被劃分到簇/投影簇中，因此分類正確率受到網(wǎng)格密度閾值的限制，不可能超過密集網(wǎng)格覆蓋數(shù)據(jù)點(diǎn)的比例，如圖 3所示，τg=0.01%。

圖3 分類正確率

時間復(fù)雜性：SACluster的初始化聚類包括統(tǒng)計(jì)網(wǎng)格（grid）分布以及合并相連網(wǎng)格形成簇（cluster）2個階段，圖4顯示了指數(shù)坐標(biāo)下算法運(yùn)行時間，τc=0.01, τg=0.01τc, τs=0.10τc。結(jié)果表明，隨著數(shù)據(jù)點(diǎn)個數(shù)的增加，grid時間線性增加，而cluster時間增長較慢。說明算法具有良好的規(guī)模可擴(kuò)展性。

圖4 執(zhí)行效率

態(tài)勢因子選擇的效果：從KDDCup’99選擇10組數(shù)據(jù)，每組100 000個數(shù)據(jù)點(diǎn)，分別根據(jù)聚類結(jié)果以及連接模式信息計(jì)算每一維特征與記錄類型之間的互信息，并對各組數(shù)據(jù)取平均值。如圖5所示，2條曲線極其吻合，說明根據(jù)聚類結(jié)果計(jì)算的近似互信息與已知分類情況獲得的互信息一致，如實(shí)反映了特征與模式之間的相關(guān)性，顯示了特征對聚類的重要程度，因此根據(jù)聚類結(jié)果獲得的互信息能夠作為態(tài)勢因子選擇的依據(jù)。同時還注意到，根據(jù)聚類結(jié)果計(jì)算的互信息偏高，這是因?yàn)樵诨诰W(wǎng)格的聚類結(jié)果中去除了噪聲以及低密度網(wǎng)格的影響，故每一維特征包含的有關(guān)模式劃分的信息量增大。

圖5 特征與類型之間的互信息

維度可擴(kuò)展性：緊承上一實(shí)驗(yàn)，驗(yàn)證 SACluster算法的維度可擴(kuò)展性，實(shí)驗(yàn)數(shù)據(jù)保持不變。根據(jù)態(tài)勢因子選擇的結(jié)果，選取不同數(shù)量的特征，分別取2、7、17、19、22、26、41維特征。聚類運(yùn)行時間如圖 6所示，仍舊分成grid和cluster 2個階段。可以看到，隨著數(shù)據(jù)點(diǎn)個數(shù)的增加，grid時間線性增加，而cluster時間趨于平緩。說明算法具有良好的維度可擴(kuò)展性。

圖6 維度可擴(kuò)展性

態(tài)勢因子選擇（維度）對聚類準(zhǔn)確性的影響：如圖7所示，隨著聚類空間維度的增加，聚類純度略有增加，但由于純度始終保持較高水平，故增加不明顯；分類正確率首先明顯提升，繼而緩慢下降，這是由于維度的增加，使得密集網(wǎng)格的個數(shù)有所減少，密集網(wǎng)格覆蓋記錄點(diǎn)的比例也隨之減少，分類正確率因?yàn)槭艿骄W(wǎng)格密度閾值的限制有所降低。

4.2 實(shí)驗(yàn)2：NTSA原型系統(tǒng)

圖7 特征選擇對精度的影響

圖8 Abilene骨干網(wǎng)

為了檢驗(yàn) NTSA原型系統(tǒng)的效果，本文采用NLANR提供的Abilene網(wǎng)絡(luò)流量數(shù)據(jù)。Abilene[17]網(wǎng)絡(luò)是美國教育科研網(wǎng)，如圖8所示，其核心網(wǎng)絡(luò)拓?fù)浒?1個節(jié)點(diǎn)和14條雙向鏈路。NLANR數(shù)據(jù)采集Abilene網(wǎng)絡(luò)的報(bào)文信息，每天采樣8次，每次90s。并且于2001年7月～9月、2003年1月、2004年1月記錄了Code Red Worm、Slammer worm、W32 Mydoom的爆發(fā)。

NTSA原型系統(tǒng)選擇了報(bào)文個數(shù)、帶寬、估計(jì)延遲、報(bào)文長度分布、報(bào)文協(xié)議分布、帶寬協(xié)議分布、新流個數(shù)、活動流個數(shù)、流平均時長、流平均報(bào)文數(shù)、流平均字節(jié)數(shù)、流協(xié)議分布、TCP標(biāo)志位分布等多個指標(biāo)評估傳輸態(tài)勢，圖9顯示了某鏈路2天的評估結(jié)果，時間間隔選擇1min。從圖中可以看到評估結(jié)果既反映了傳輸狀態(tài)以24h為單位的周期性變化，也體現(xiàn)出流量的異常變化。

圖9 2天態(tài)勢評估

NTSA原型系統(tǒng)在Code Red Worm、Slammer worm和W32 Mydoom爆發(fā)的3個時段進(jìn)行傳輸態(tài)勢評估。如圖 10所示，當(dāng)網(wǎng)絡(luò)異常發(fā)生時，態(tài)勢曲線發(fā)生明顯變化，取值相對較大。

圖10 注入異常

NTSA原型系統(tǒng)不僅能夠很好地反映網(wǎng)絡(luò)異常，而且能夠檢測未知異常并及時提取異常特征。為了全面細(xì)節(jié)地揭示異常的特征，展現(xiàn)異常發(fā)生時各種態(tài)勢因子的表現(xiàn)，采用雷達(dá)圖繪制態(tài)勢因子圖譜，如圖 11所示。在雷達(dá)圖上，各種異常的特征一目了然，不僅能夠同時表現(xiàn)多種態(tài)勢因子，而且便于不同異常以及正常狀態(tài)之間的比較。

圖11 態(tài)勢因子圖譜

4.3 相關(guān)工作和比較

自1999年Tim Bass提出網(wǎng)絡(luò)態(tài)勢感知的概念以來，網(wǎng)絡(luò)態(tài)勢感知已經(jīng)成為網(wǎng)絡(luò)管理和網(wǎng)絡(luò)安全領(lǐng)域的熱點(diǎn)，絕大多數(shù)研究圍繞安全態(tài)勢展開[2,18～20]，也有少量涉及傳輸態(tài)勢、信息優(yōu)勢、生存性等。有關(guān)傳輸態(tài)勢感知的研究，集中在態(tài)勢可視化階段。Lau等提出的Internet級網(wǎng)絡(luò)流量可視化工具，在三維空間（例如選擇IP地址和端口號建立IP-IP-port邏輯空間）用點(diǎn)來表示網(wǎng)絡(luò)流量信息，提供整個網(wǎng)絡(luò)的態(tài)勢感知，易于發(fā)現(xiàn)網(wǎng)絡(luò)攻擊行為，提取攻擊行為特征[21～24]。國內(nèi)一些關(guān)于網(wǎng)絡(luò)傳輸性能評價的研究和網(wǎng)絡(luò)傳輸態(tài)勢感知關(guān)系比較緊密，其中楊雅輝建立了網(wǎng)絡(luò)性能指標(biāo)體系，并給出形式化描述框架[25]，林闖、江勇等以評價函數(shù)作為標(biāo)準(zhǔn)展開網(wǎng)絡(luò)傳輸控制的性能評價[26,27]，張冬艷等以權(quán)重分析為基礎(chǔ)評價網(wǎng)絡(luò)性能[28,29]。

表1 相關(guān)工作比較

本文是對傳輸態(tài)勢感知的第一次嘗試，側(cè)重于揭示網(wǎng)絡(luò)運(yùn)行狀況，結(jié)合流量和拓?fù)湫畔?chuàng)新性的提出了 STM 模型。由于和現(xiàn)有研究差異較大，因此從數(shù)據(jù)來源、態(tài)勢因子、評估方法、結(jié)果形式等幾方面進(jìn)行簡單比較，結(jié)果見表1。

從結(jié)果可以看出，本文方法擴(kuò)展靈活、科學(xué)客觀、運(yùn)行效率高。安全態(tài)勢感知和本文思路比較接近，不同之處在于側(cè)重點(diǎn)不同，因此選擇的數(shù)據(jù)源也不同。而流量可視化和性能評價等方法，或者停留在數(shù)據(jù)層面上，或者采用公式法分析少數(shù)指標(biāo)，都沒有上升到態(tài)勢的高度。

5 結(jié)束語

本文面向網(wǎng)絡(luò)管理需求，結(jié)合態(tài)勢感知的先進(jìn)技術(shù)，建立了基于空間流量聚類的網(wǎng)絡(luò)傳輸態(tài)勢感知模型，證明了信息增益和互信息用于態(tài)勢因子選擇的等價性，提出了一種面向傳輸模式劃分的高維數(shù)據(jù)流聚類算法，設(shè)計(jì)了基于圖論的拓?fù)渲匾苑治龇椒ā?shí)驗(yàn)分析證明了算法的準(zhǔn)確性、時空可行性以及可擴(kuò)展性，原型系統(tǒng)能夠綜合各種單元網(wǎng)管信息，從宏觀上把握網(wǎng)絡(luò)態(tài)勢，體現(xiàn)了系統(tǒng)的應(yīng)用價值和現(xiàn)實(shí)意義。本文是對網(wǎng)絡(luò)傳輸態(tài)勢感知的一次嘗試，相關(guān)研究還有巨大的發(fā)展空間。在接下來的工作中，將關(guān)注態(tài)勢感知的理論方法，深化關(guān)鍵技術(shù)研究，同時利用 CPU雙核的特點(diǎn)，進(jìn)一步提高模式聚類的精度和效率。

[1] BASS T. Multisensor data fusion for next generation distributed intrusion detection systems[A]. 1999 IRIS National Symposium on Sensor and Data Fusion[C]. Laurel, 1999. 24-27.

[2] BASS T. Intrusion detection systems and multisensor data fusion[J].Communications of the ACM, 2000, 43(4)∶ 99-105.

[3] HINMAN M. Some computational approaches for situation assessment and impact assessment[A]. ISIF[C]. New York, USA, 2002.687-693.

[4] ZHUO Y, ZHANG Q, GONG Z H. Cyberspace situation representation based on niche theory[A]. ICIA[C]. Zhangjiajie, China, 2008.1400-1405.

[5] CROVELLA M, KOLACZYK E. Graph wavelets for spatial traffic analysis[A]. Infocom[C]. 2003. 1848-1857.

[6] LAKKARAJU K. NVisionIP∶ netflow visualizations of system state for security situational awareness[A]. ACM Workshop Visualization and Data Mining for Computer Security[C]. New York, USA, 2004.65-72.

[7] ZHUO Y, ZHANG Q, GONG Z H. Network situation assessment based on RST[A]. PACIIC[C]. Wuhan, China, 2008. 502-506.

[8] AGRAWAL R, GEHRKE J, GUNOPULOS D. Automatic subspace clustering of high dimensional data for data mining applications[A].SIGMOD[C]. 1998. 94-105.

[9] 徐燕,李錦濤,王斌.基于區(qū)分類別能力的高性能特征選擇方法[J].軟件學(xué)報(bào),2008,19(1)∶82-89.XU Y, LI J T, WANG B. A category resolve power-based feature selection method[J]. Journal of Software. 2008, 19(1)∶ 82-89.

[10] ZHUO Y, ZHANG Q, GONG Z H. Research and implementation of network transmission situation awareness[A]. CSIE[C]. Los Angeles,USA, 2009. 210-214.

[11] 許俊明.圖論及其應(yīng)用[M]. 合肥∶ 中國科學(xué)技術(shù)大學(xué)出版社,2004.XU J M. Graph Theory and Its Application[M]. Hefei∶ Publishing House of University of Science and Technology of China, 2004.

[12] FORD L R J, FULKERSON D R. A simple algorithm for finding maximal network flows and an application to the hitchcock problem[J].Canada J Math, 1957, 9∶ 210-218.

[13] EDMONDS J, KARP R M. Theoretical improvements[J]. J Assoc Compute Math, 1972, 19∶ 248-264.

[14] KDD Cup 1999 Data[EB/OL]. http∶//kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.

[15] NLANR. http∶//pma.nlanr.net/Traces/Traces/long/auck/8/[EB/OL].

[16] LU Y. A Grid-based clustering algorithm for high-dimensional data streams[A]. Proc of the 1st International Conference on Advanced Data Mining and Applications[C]. LNCS, 2005. 824-831.

[17] Internet2. http∶//www.internet2.edu[EB/OL].

[18] BASS T. Defense-in-depth revisited∶ qualitative risk analysis methodology for complex network-centric operations[A]. Military Communications Conference (MILCOM), Communications for Network Centric Operations∶ Creating the Information Force[C]. 2001. 64-70.

[19] 陳秀真,鄭慶華,管曉宏.層次化網(wǎng)絡(luò)安全威脅態(tài)勢量化評估方法[J].軟件學(xué)報(bào), 2006,17(4)∶885-897.CHEN X Z, ZHENG Q H, GUAN X H. Quantitative hierarchical threat evaluation model for network security[J]. Journal of Software.2006, 17(4)∶ 885-897.

[20] 韋勇,連一峰,馮登國.基于信息融合的網(wǎng)絡(luò)安全態(tài)勢評估模型[J].計(jì)算機(jī)研究與發(fā)展,2009,46(3)∶353-362.WEI Y, LIAN Y F, FENG G D. A network security situational awareness model based on information fusion[J]. Journal of Computer Research and Development, 2009, 46(3)∶ 353-362.

[21] LAU S. The spinning cube of potential doom[EB/OL]. http∶//www.nersc.gov/nusers/security/TheSpinningCube.php, 2003.

[22] CONTI G, ABDULLAH K. Passive visual fingerprinting of network attack tools[A]. Proceedings of 2004 ACM Workshop on Visualization and Data Mining for Computer Security[C]. New York, USA, 2004.45-54.

[23] KRASSER S, CONTI G, GRIZZARD J. Real-time and forensic network data analysis using animated and coordinated visualization[A].Proceedings of the 2005 IEEE Workshop on Information Assurance[C].2005. 42-49.

[24] Carnegie Mellon’s SEI. system for internet level knowledge(SILK)[EB/OL]. http∶//silktools.sourceforge.net, 2005.

[25] 楊雅輝,李小東.IP 網(wǎng)絡(luò)性能指標(biāo)體系的研究[J].通信學(xué)報(bào),2002,23(11)∶1-7.YANG Y H, LI X D. The study of a framework for IP network performance metrics[J]. Journal on Communications, 2002, 23(11)∶ 2-7.

[26] 江勇,林闖,吳建平.網(wǎng)絡(luò)傳輸控制的綜合性能評價標(biāo)準(zhǔn)[J]. 計(jì)算機(jī)學(xué)報(bào), 2002,25(8)∶870-887.JIANG Y, LIN C, WU J P. Integrated performance evaluation criteria for network traffic control[J]. Chinese Journal Computers, 2002, 25(8)∶869-877.

[27] 林闖,周文江,田立勤.IP網(wǎng)絡(luò)傳輸控制的性能評價標(biāo)準(zhǔn)研究[J]. 電子學(xué)報(bào),2002,30(12A)∶1973-1977.LIN C, ZHOU W J, TIAN L Q. Research on performance evaluation criteria for IP network traffic control[J]. Acta Electronica Sinica. 2002,30(12A)∶ 1973-1977.

[28] 張冬艷, 胡銘曾, 張宏莉. 基于測量的網(wǎng)絡(luò)性能評價方法研究[J].通信學(xué)報(bào), 2006,27(10)∶74-79.ZHANG D Y, HU M Z, ZHANG H L. Study on network performance evaluation method based on measurement[J]. Journal on Communications, 2006, 27(10)∶ 74-79.

[29] 蔣序平.網(wǎng)絡(luò)性能綜合評估方法IEMoNP的設(shè)計(jì)和實(shí)現(xiàn)[J].海軍工程大學(xué)學(xué)報(bào),2006,18(5)∶74-78.JIANG X P. Design and realization of an integrated evaluation method of network performance[J]. Journal of Naval University of Engineering, 2006, 18(5)∶ 74-78.