IP骨干網(wǎng)絡(luò)的流量推斷技術(shù)研究.pdf

1、隨著互聯(lián)網(wǎng)的快速發(fā)展，和新型網(wǎng)絡(luò)應(yīng)用的快速部署，IP網(wǎng)絡(luò)規(guī)模呈指數(shù)式擴(kuò)張，網(wǎng)絡(luò)業(yè)務(wù)呈爆炸式增長(zhǎng)。IP網(wǎng)絡(luò)已演變成為目前這樣一種高度異構(gòu)、開(kāi)放的復(fù)雜系統(tǒng)。網(wǎng)絡(luò)中的非關(guān)鍵業(yè)務(wù)流量的泛濫導(dǎo)致網(wǎng)絡(luò)的帶寬資源被大量地消耗，影響了其他關(guān)鍵網(wǎng)絡(luò)業(yè)務(wù)的正常運(yùn)行。為了更好的進(jìn)行網(wǎng)絡(luò)規(guī)劃、網(wǎng)絡(luò)設(shè)計(jì)、網(wǎng)絡(luò)監(jiān)控、路由優(yōu)化、流量檢測(cè)、負(fù)載均衡和網(wǎng)絡(luò)故障診斷等網(wǎng)絡(luò)管理任務(wù)，迫切需要掌握網(wǎng)絡(luò)流量方面的信息。網(wǎng)絡(luò)流量數(shù)據(jù)通常被排列為多維陣列(multidimensio

2、nal array)的形式（例如，矩陣和張量）。在給定的測(cè)量采樣時(shí)間周期內(nèi)，網(wǎng)絡(luò)中所有從源節(jié)點(diǎn)傳輸?shù)侥康墓?jié)點(diǎn)的流量形成一個(gè)二維矩陣。隨著采樣時(shí)間的演化，即多個(gè)采樣周期，網(wǎng)絡(luò)流量數(shù)據(jù)形成一個(gè)三維陣列。流量矩陣(Traffic Matrix，TM)描述網(wǎng)絡(luò)中所有源目的（Original-Destination，OD）節(jié)點(diǎn)之間流動(dòng)的流量，它是流量工程，容量規(guī)劃，異常檢測(cè)等網(wǎng)絡(luò)工程任務(wù)的關(guān)鍵輸入?yún)?shù)。然而，盡管流量矩陣很重要，但是獲得精確而完整

3、的流量矩陣通常很困難或甚至不可行。由于數(shù)據(jù)收集成本驅(qū)動(dòng)的預(yù)算約束，海量數(shù)據(jù)存儲(chǔ)設(shè)施的過(guò)載，流量測(cè)量系統(tǒng)本身的缺陷和數(shù)據(jù)收集系統(tǒng)可能的失敗，大規(guī)模網(wǎng)絡(luò)的流量測(cè)量經(jīng)常有大量的數(shù)據(jù)丟失。如何處理經(jīng)常出現(xiàn)在流量測(cè)量中的丟失數(shù)據(jù)一直是個(gè)挑戰(zhàn)。
　　最近幾年，壓縮感知技術(shù)、矩陣填充理論、張量填充方法和張量恢復(fù)方法取得了廣泛的應(yīng)用?，F(xiàn)有的解決方案在網(wǎng)絡(luò)流量推斷方面恢復(fù)性能較差，其主要原因是在真實(shí)網(wǎng)絡(luò)環(huán)境中，流量數(shù)據(jù)的丟失模式具有結(jié)構(gòu)化、非隨機(jī)性

4、。這些特征違反了這些方法被設(shè)計(jì)運(yùn)行和證明是最佳的數(shù)學(xué)條件。當(dāng)數(shù)據(jù)丟失率高的時(shí)候，它們的恢復(fù)精度往往會(huì)顯著降低。為了克服上述的困難，本文利用流量模型，流量數(shù)據(jù)的多線性結(jié)構(gòu)及流量時(shí)空特征，針對(duì)多數(shù)據(jù)源、測(cè)量誤差、流量異常等情況，圍繞以提高恢復(fù)精度為主要目標(biāo)對(duì)網(wǎng)絡(luò)流量推斷方法展開(kāi)深入研究。從基于二階流量矩陣推斷方法到基于三階流量張量推斷方法，所取得的主要研究成果有:
　　1.基于壓縮感知和流量時(shí)間穩(wěn)定性、空間自相似特征，提出了一種空間自

5、相似和時(shí)間改進(jìn)的壓縮感知算法重構(gòu)流量矩陣。為了減小流量數(shù)據(jù)的恢復(fù)誤差，本工作首先對(duì)真實(shí)流量數(shù)據(jù)進(jìn)行了深入的研究與分析，揭示出流量矩陣具有三個(gè)特征，即低秩結(jié)構(gòu)，時(shí)間穩(wěn)定性特征，空間自相似特征。然后，基于流量矩陣這些特征，提出了一種空間自相似和時(shí)間改進(jìn)的壓縮感知算法重構(gòu)流量矩陣。該方法綜合使用部分測(cè)量的NetFlow數(shù)據(jù)和SNMP鏈路負(fù)載這兩種數(shù)據(jù)源。最后，使用真實(shí)的流量數(shù)據(jù)集開(kāi)展大量實(shí)驗(yàn)對(duì)所提出的算法進(jìn)行重構(gòu)性能評(píng)估。實(shí)驗(yàn)結(jié)果表明該算法能

6、夠精確恢復(fù)丟失的流量數(shù)據(jù)，即使當(dāng)98％的數(shù)據(jù)丟失，流量矩陣能以約32％的誤差重構(gòu)。
　　2.基于流量矩陣的多高斯模型，提出了一種貝葉斯方法的流量矩陣填充算法推斷丟失數(shù)據(jù)。為了精確恢復(fù)丟失的流量數(shù)據(jù)，本工作首先在真實(shí)流量數(shù)據(jù)分析的基礎(chǔ)上，揭示出流量具有時(shí)空特征，即時(shí)間穩(wěn)定性特征、空間相關(guān)性特征。然后，基于流量空間相關(guān)性特征，建模流量矩陣為多高斯模型。接著，受貝葉斯推斷的啟發(fā)，提出了一種新的多高斯模型貝葉斯流量矩陣填充算法。該算法考慮

7、了流量測(cè)量誤差，并建模誤差為高斯模型。最后，利用流量時(shí)間穩(wěn)定性特征，進(jìn)一步優(yōu)化流量矩陣填充結(jié)果。實(shí)驗(yàn)結(jié)果表明，所提算法能夠精確恢復(fù)丟失的流量數(shù)據(jù)，即使當(dāng)98％的數(shù)據(jù)丟失，數(shù)據(jù)的恢復(fù)誤差小于24％。
　　3.基于流量張量模型和張量分解的因子矩陣的低維表示，提出了一種時(shí)空張量填充算法推斷丟失數(shù)據(jù)。為了精確恢復(fù)丟失的流量數(shù)據(jù)，本工作建模流量數(shù)據(jù)為流量張量模型。通過(guò)利用張量CP分解及其因子矩陣的低維表示，并引入時(shí)空單維因子正則化，提出了時(shí)

8、空張量填充算法估計(jì)丟失的流量數(shù)據(jù)。該問(wèn)題被闡述成為一個(gè)凸優(yōu)化問(wèn)題。基于交替最小二乘法，求解得到張量的因子矩陣，并重構(gòu)出流量張量。使用真實(shí)的流量數(shù)據(jù)集開(kāi)展大量實(shí)驗(yàn)對(duì)所提出的算法進(jìn)行恢復(fù)性能評(píng)估。實(shí)驗(yàn)結(jié)果表明該算法能夠精確恢復(fù)丟失的流量數(shù)據(jù)，即使當(dāng)95％的數(shù)據(jù)丟失，流量張量能以約20％的誤差重構(gòu)。
　　4.針對(duì)網(wǎng)絡(luò)流量數(shù)據(jù)丟失和網(wǎng)絡(luò)流量異常情況，提出了一種魯棒時(shí)空張量恢復(fù)算法推斷丟失數(shù)據(jù)。由于測(cè)量系統(tǒng)的缺陷和在網(wǎng)絡(luò)中發(fā)起的攻擊，比如，

9、拒絕式服務(wù)攻擊，蠕蟲(chóng)擴(kuò)散和突發(fā)攻擊流，流量數(shù)據(jù)丟失和網(wǎng)絡(luò)流量異常不可避免。本工作利用時(shí)空性質(zhì)正則化張量分解過(guò)程來(lái)恢復(fù)丟失的數(shù)據(jù)和去除異常。首先，為了完全利用流量數(shù)據(jù)的多線性結(jié)構(gòu)，張量被引入建模時(shí)間序列的空間流量矩陣，這樣不僅保存了流量數(shù)據(jù)的多維性而且從高階的視角能更好地理解信息背后的關(guān)系。然后，通過(guò)利用流量的時(shí)空特征，提出了一種新的魯棒時(shí)空張量恢復(fù)方法處理丟失數(shù)據(jù)和異常，并把該問(wèn)題闡述成為一個(gè)用交替方向增廣拉格朗日求解的凸優(yōu)化問(wèn)題。最后