黃 暢，劉晏嘉，羅晟庭

（北京交通大學，北京 100044）

隨著網(wǎng)絡應用服務不斷更新迭代和網(wǎng)絡用戶流量規(guī)模劇烈增長，傳統(tǒng)網(wǎng)絡管控手段已經(jīng)難以應對現(xiàn)有網(wǎng)絡“高速率、大規(guī)模、多接入、不可預期”等特點帶來的管控挑戰(zhàn)。此研究相對于傳統(tǒng)網(wǎng)絡監(jiān)測及故障排除方法更加具有創(chuàng)造性和革新性，能夠應對網(wǎng)絡狀態(tài)測量、網(wǎng)絡故障檢測、故障精準定位與及時恢復網(wǎng)絡性能等場景的網(wǎng)絡管控，此解決方案對于網(wǎng)絡管理者而言已是迫在眉睫。與傳統(tǒng)網(wǎng)絡測量方案不同，帶內(nèi)測量將數(shù)據(jù)包轉(zhuǎn)發(fā)和網(wǎng)絡測量相結合，通過路徑中間交換節(jié)點對數(shù)據(jù)包依次插入元數(shù)據(jù)的方式完成網(wǎng)絡狀態(tài)采集。相較于傳統(tǒng)網(wǎng)絡測量方案，帶內(nèi)測量能夠?qū)W(wǎng)絡拓撲、網(wǎng)絡性能和網(wǎng)絡流量實現(xiàn)端到端測量。

帶內(nèi)網(wǎng)絡遙測是網(wǎng)絡數(shù)據(jù)平面可編程的重要應用場景，拓展了傳統(tǒng)網(wǎng)絡測量邊界?，F(xiàn)階段帶內(nèi)網(wǎng)絡遙測的相關研究多集中于遙測架構和應用上，處于“能測就行”的起步階段，缺少對帶內(nèi)網(wǎng)絡遙測缺失數(shù)據(jù)補全算法的研究。帶內(nèi)網(wǎng)絡遙測通過用戶數(shù)據(jù)包承載遙測數(shù)據(jù)，用戶數(shù)據(jù)包的丟包會導致網(wǎng)絡遙測數(shù)據(jù)缺失。帶內(nèi)網(wǎng)絡遙測數(shù)據(jù)本質(zhì)是時間序列數(shù)據(jù)，網(wǎng)絡遙測數(shù)據(jù)缺失往往屬于隨機數(shù)據(jù)缺失，而這種丟包現(xiàn)象是不可避免的，每當發(fā)生丟包，勢必會引起網(wǎng)絡層面上的一些重大故障，導致測量結果的不準確，故在遙測方向的背景下缺失數(shù)據(jù)的處理，本文通過多種方法對缺失的數(shù)據(jù)進行補全并對補全效果進行研究。

1 數(shù)據(jù)處理

首先，在對帶內(nèi)網(wǎng)絡遙測過程中缺失的網(wǎng)絡狀態(tài)測量值進行處理之前，了解相關網(wǎng)絡節(jié)點測量值缺失機制及其類別是必要的。如果在測量過程中得到的數(shù)據(jù)中不包含任何缺失值，則將其稱為完全變量，若測量得到的數(shù)據(jù)中含有任一缺失數(shù)據(jù)則稱其為不完全變量，Roderick J.A.Little和Donald B.Rubin 定義了如下三種數(shù)據(jù)缺失機制：

（1）完全隨機缺失（Missing Completely at Random，MCAR）[1]。數(shù)據(jù)的缺失與完全變量和不完全變量都無關；隨機缺失（Missing at Random，MAR）。數(shù)據(jù)的缺失僅僅與完全變量有關；非隨機不可忽略缺失（Not Missing at Random，NMAR[2]，or Non-ignorable）。不完全變量中數(shù)據(jù)的缺失依賴于它自身的特性，這種缺失在實際應用中不可忽略。

（2）缺失值插補針對兩種類型：單一插補（single imputation）[3]以及多重插補（multiple imputation）。單一插補指使用特定方法，對因為無響應造成的缺失值僅構造一個合理替代值，并將該替代值插補到原缺失數(shù)據(jù)位置，從而構造出完整數(shù)據(jù)集。多重插補是一種基于重復模擬的處理缺失數(shù)據(jù)的方法。它從一個包含缺失數(shù)據(jù)的數(shù)據(jù)集中生成一組完整的數(shù)據(jù)集，每個數(shù)據(jù)集中的缺失數(shù)據(jù)用蒙特·卡羅法來填補。從缺失數(shù)據(jù)的所屬類別上看，如果所有的缺失數(shù)據(jù)為同一類型，這種缺失稱為單值缺失；如果缺失數(shù)據(jù)屬于不同類型，為任意缺失。對于時間序列類的數(shù)據(jù)，可能存在隨著時間的缺失，這種缺失稱為單調(diào)缺失，分析可以得出，網(wǎng)絡遙測數(shù)據(jù)的缺失是一種單值單調(diào)的隨機數(shù)據(jù)缺失。

故在本文研究中，利用目前數(shù)據(jù)平面帶內(nèi)網(wǎng)絡遙測主要研究之一，P4 聯(lián)盟主導的帶內(nèi)網(wǎng)絡遙測（In-band Network Telemetry，INT）[4]模擬現(xiàn)實中網(wǎng)絡情況，將一段時間的時間序列數(shù)據(jù)導出，得到時間戳及其相應時間上所對應的網(wǎng)絡的逐跳延遲等若干數(shù)據(jù)，然后人為進行數(shù)據(jù)的隨機丟失處理，接著使用不同方法進行缺失數(shù)據(jù)的填充，比較驗證各類數(shù)據(jù)補全方法在帶內(nèi)網(wǎng)絡遙測領域的有效性與可靠性。

1.1 刪除元組

刪除元組法是將缺失的數(shù)據(jù)直接刪除，得到完備的信息集合，集合中數(shù)據(jù)為完整原始的測量數(shù)據(jù)，但是被刪除數(shù)據(jù)所包含信息和其缺失所帶來的影響不可忽視。如果樣本容量足夠大，這個方法是有效的，然而這種方法卻有很大的局限性。它以減少部分測量數(shù)據(jù)來換取數(shù)據(jù)集合的完備性，造成測量資源以及測量時間的大量浪費，增加測量成本負擔。此外，丟棄的這些包含缺失數(shù)據(jù)的對象中還隱藏著大量的測量信息，這些數(shù)據(jù)的丟棄對測量的準確性和客觀性帶來了影響，同時對后續(xù)的測量結果分析工作也造成了一定的困難。在樣本容量不足的情況下，刪除少量數(shù)據(jù)就足以嚴重影響到測量結果的準確性，性能非常差。因此，當缺失數(shù)據(jù)所占百分比較大，特別是當缺失數(shù)據(jù)服從隨機分布時，這種方法容易導致數(shù)據(jù)發(fā)生大偏差，進而在分析測量結果的過程中可能會得出錯誤結論。

而在本實驗過程中，我們將人為隨機丟失的部分數(shù)據(jù)直接進行刪除的操作，可以看出刪除元組法在準確性上具有較大的局限，與原有數(shù)據(jù)存在極大的偏離，在實際帶內(nèi)網(wǎng)絡遙測領域中，這種程度的誤差范圍是我們所不能接受的，會引起諸如增大網(wǎng)絡開銷、遙測精度降低等一系列性能問題。

1.2 數(shù)據(jù)補齊

這類方法是通過一些分析方法得出較為合適的數(shù)據(jù)去填充缺失數(shù)據(jù)，從而使數(shù)據(jù)集完整化。一般基于統(tǒng)計學原理，根據(jù)未缺失數(shù)據(jù)取值的分布情況以及數(shù)據(jù)之間內(nèi)在聯(lián)系對缺失數(shù)據(jù)進行合理補齊，在遙測仿真網(wǎng)絡中所提取到的部分性能數(shù)據(jù)恢復完整數(shù)據(jù)的質(zhì)量，依賴于此統(tǒng)計技術，而當下常用的有以下幾種填充方法：

1.2.1 均值填充（Mean/Mode Completer）

為了盡可能保證涉及到所有數(shù)據(jù)，平均數(shù)考慮了每一個個體對總體的貢獻，給每個測量數(shù)據(jù)賦予相同或不同的權重占比。平均數(shù)：

少量的缺失數(shù)據(jù)能夠直接刪除處理。除此之外，由于均值很好地保留并反映了樣本或總體的集中特點，以均值作為填充數(shù)據(jù)來填補缺失位置也是一個合適的方式。在本次實驗中，帶內(nèi)網(wǎng)絡遙測仿真環(huán)境所導出的數(shù)據(jù)類型是一個二維數(shù)組，具體是不同時間戳下所對應遙測網(wǎng)絡中節(jié)點的逐跳時延，由于空值是屬于數(shù)值型的，故我們采用的是逐跳延遲的平均值進行填充，在此處我們還進行了一項改進，如果取的是丟失數(shù)據(jù)補集的所有元素平均值來進行填充的話，無法反映出數(shù)據(jù)在其時間戳上的特殊性，所以我們將區(qū)間盡可能縮小，從而讓填充值與時間的對應關系盡可能貼近原有數(shù)據(jù)，并能夠恢復出一定的變化趨勢，但由于本次實驗導出的逐跳延遲數(shù)據(jù)性質(zhì)具有一定的隨機性，在某些跳變大的區(qū)間內(nèi)恢復精度會受到影響。

數(shù)學方法可以在一定程度上實現(xiàn)丟失遙測數(shù)據(jù)的填充，但是很大程度上忽視了數(shù)據(jù)間以及局部數(shù)據(jù)與整體數(shù)據(jù)之間的內(nèi)在聯(lián)系。為了實現(xiàn)網(wǎng)絡性能數(shù)據(jù)模型中數(shù)據(jù)更好的交互，當下國內(nèi)外已有許多學者使用張量模型對網(wǎng)絡流量數(shù)據(jù)進行填充，充分利用了數(shù)據(jù)的多重相關性（即隱藏的時空相關性），其通常將源節(jié)點、目的節(jié)點和時間間隔的特征投影到一個空間中，利用該空間的潛在因子向量的內(nèi)積表示三者間的內(nèi)在聯(lián)系。這一分析過程是基于三者間的聯(lián)系是線性的假設，然而實際的網(wǎng)絡遙測過程中很大部分的數(shù)據(jù)之間并不是簡單的線性關系，往往存在比較復雜的非線性關系。因此，在實際情況下，不能只用簡單的線性關系來理解數(shù)據(jù)間的關聯(lián)，進而導致數(shù)據(jù)恢復的精度受限。因此，我們引入了深度神經(jīng)網(wǎng)絡學習。

深度神經(jīng)網(wǎng)絡學習在自然語言處理、計算機視覺、語音識別等領域上取得了巨大的成就，因此可以類比這些處理方式，將深度學習應用于遙測數(shù)據(jù)的補全上，通過大量數(shù)據(jù)的學習，找尋不同時間戳下逐跳時延值的內(nèi)在規(guī)律及關系。此處，我們只采用了一種EM 算法進行實驗，諸如決策樹、向量機等深度學習算法也是可行的，在結果上存在細微的差別，但從整體上的還原效果大致類似。

1.2.2 期望值最大化方法（Expectation maximuzation，EM）

隨著網(wǎng)絡日益復雜化，細粒度網(wǎng)絡監(jiān)控的可靠性、靈活性等面臨著前所未有的挑戰(zhàn)。相比于傳統(tǒng)的監(jiān)控方式和處理手段，通過機器學習的方式則可以做出更優(yōu)化的決策。在隨機性缺失的情況下，假設該模型對于一個完整樣品來說都是正確和合適的，那么我們就可以通過觀察數(shù)據(jù)邊沿的分布來對其中一些未知的參數(shù)做出極大似然性估計，將之稱為忽略缺失值的極大似然估計，在實際應用過程中經(jīng)常采取的一種計算方式是預測期望值的最大化（Expectation Maximization，EM）[5]。該方法較之于刪除元組法和簡單的多值插入法更符合一個整體的數(shù)據(jù)集，原因在于這種算法適用于大樣本數(shù)據(jù)集，適用于本次帶內(nèi)網(wǎng)絡遙測實驗中。有效樣本數(shù)量足夠來保障其估計值是漸近無偏的且符合正態(tài)分布，然而該算法可能會陷入局部極值，收斂速度不快，計算較復雜。

EM 算法是一種在不完全數(shù)據(jù)情況下計算極大似然估計或者后驗分布的迭代算法。在每一迭代循環(huán)過程中交替執(zhí)行兩個步驟：E 步（Expectationstep，期望步）和M步（Maximzation step，極大化步），算法在E 步和M 步之間不停交替迭代直到收斂為止，即在兩次迭代中所得到的參數(shù)之差小于一個提前設定的閾值之時，迭代結束，其實施過程如下：

極大似然估計已知一個樣本集符合某種概率分布，但是該分布的某些參數(shù)未知，通過尋找使得樣本重復的概率最大化的參數(shù)作為未知參數(shù)的估計值，假設未知參數(shù)為X，與參數(shù)X 有關的隱含量Z。

首先隨機估計一個X 值，接著進行E 步：在固定參數(shù)X 后，使下界拉升的函數(shù)Q（Z）的計算公式為條件概率，基于這個論斷，就解決了Q（Z）如何抉擇的問題，建立了樣本集的聯(lián)合概率L（X）的下界。之后，對于每一個i，依據(jù)上一次迭代的模型參數(shù)來計算出隱性變量的后驗概率即隱性變量的期望，以此作為隱藏變量的估計值。然后進行M 步：在給定Q（Z）后，調(diào)整參數(shù)X，極大化L（X）的下界。

如此循環(huán)重復，不停迭代，直到收斂就可以得到使似然函數(shù)L（X）最大化的參數(shù)X 了。

2 實驗結果

數(shù)據(jù)描述：本文利用目前數(shù)據(jù)平面帶內(nèi)網(wǎng)絡遙測主要研究之一，P4 聯(lián)盟主導的帶內(nèi)網(wǎng)絡遙測（In-band Network Telemetry，INT）模擬現(xiàn)實中網(wǎng)絡情況，將一段時間的時間序列數(shù)據(jù)導出，得到時間戳及其相應時間戳所對應的網(wǎng)絡中逐跳延遲的若干數(shù)據(jù)，然后進行數(shù)據(jù)的隨機丟失處理操作?？紤]到缺口處的大小可能會對實驗結果產(chǎn)生一定的影響，所以在丟失數(shù)據(jù)操作時，對缺口數(shù)據(jù)量也進行了一定的控制，在一定數(shù)據(jù)范圍內(nèi)設置了五處缺口位置，根據(jù)每處缺失數(shù)據(jù)量的區(qū)間大小分為三組，第一組每處缺失1 個數(shù)據(jù)，第二組每處缺失5 個數(shù)據(jù)，第三組每處缺失10 個數(shù)據(jù)。分別采用刪除元組法，均值填補法以及EM 算法進行數(shù)據(jù)補全，最后通過計算并對比誤差大小來判斷各類方法的特點。

通過數(shù)據(jù)補全后作圖，將逐跳延遲數(shù)據(jù)丟失前以及補全后的對比展示如下。

2.1 刪除元組

通過對比相同缺失位置，不同缺失量之間的差別，我們可以看出，刪除元組法對于數(shù)據(jù)的處理效果隨著丟失數(shù)據(jù)數(shù)量的增加逐漸變差，當數(shù)據(jù)丟失較多時，這樣的處理方式會導致大量數(shù)據(jù)丟失，一些關鍵起伏點的缺失如果用這種方法進行處理的話，會導致測量的準確度大幅下降。而通過對比相同缺失量，不同缺失位置之間的差異，我們可以得出，刪除元組法對于變化趨勢相對穩(wěn)定，起伏不明顯的缺失位置的處理效果要優(yōu)于對有較大變動、變化趨勢變化較明顯的位置的處理效果。這種方法的優(yōu)勢在于操作簡單、計算成本較低，但是會造成數(shù)據(jù)的缺失，對于大量數(shù)據(jù)缺失的場景處理效果并不理想（見圖1-圖3）。

圖1 第一組刪除元組方法補全效果圖

圖2 第二組刪除元組方法補全效果圖

圖3 第三組刪除元組方法補全效果圖

2.2 均值填充

由實驗結果可以看出，均值補全法相對于刪除元組法，其補全的數(shù)據(jù)更加貼近于原始數(shù)據(jù)的起伏變化，盡可能不丟失原始數(shù)據(jù)，對于較多數(shù)據(jù)缺失的情況也可以較好恢復。雖然其補全的數(shù)據(jù)可以更大程度地接近原始數(shù)據(jù)的變化趨勢，但是有部分數(shù)據(jù)補全后與原始數(shù)據(jù)相差較大，這也使得補全數(shù)據(jù)的總體誤差上升。這種方法的優(yōu)勢在于可以較好地還原原始數(shù)據(jù)的變化趨勢，然而補全數(shù)據(jù)的準確性還有待提高（見圖4-圖6）。

圖4 第一組均值填充方法補全效果圖

圖5 第二組均值填充方法補全效果圖

圖6 第三組均值填充方法補全效果圖

2.3 EM 算法填充

EM 算法相較于刪除元組法，其沒有丟失大量的數(shù)據(jù)。相對于均值填充法，其補全數(shù)據(jù)更加貼近原始數(shù)據(jù)，但是對于缺失部位的數(shù)據(jù)變化沒有很好地反映。EM 算法的優(yōu)勢在于其補全值與缺失部位周圍的數(shù)據(jù)水平比較接近，而缺失位置周圍的數(shù)據(jù)某種程度上也可以反映原始數(shù)據(jù)的信息，所以其補全數(shù)據(jù)的準確性更好。但是問題在于，如果缺失部位全部用一個數(shù)據(jù)填充會忽略缺失部位原始數(shù)據(jù)變化的特點（見圖7-圖9）。

圖7 第一組EM 算法填充方法補全效果圖

圖8 第二組EM 算法填充方法補全效果圖

圖9 第三組EM 算法填充方法補全效果圖

2.4 誤差分析

使用圖像進行對比判斷分析是一種直接但較為定性的方法，所以我們還引入了三個性能指標從而細致地分析實驗結果，分別是：誤差率（Error Ratio，ER）、平均絕對誤差（Mean Absolute Error，MAE）、均方根誤差（Root Mean Square Error，RMSE）。

其中Xij和X?ij分別表示導出數(shù)據(jù)的原始值和丟失后的補全值，Ω 表示丟失數(shù)據(jù)的索引集合。性能指標的計算公式如表1。

表1 性能指標的計算公式

由于刪除元組法不滿足性能指標的計算要求，故只能從圖像上進行定性的分析。

以下是均值補全和EM 算法補全的性能指標對比（圖10-圖12）。

圖10 均值補全和EM 算法補全的性能指標對比

圖11 均值補全和EM 算法補全的性能指標對比

圖12 均值補全和EM 算法補全的性能指標對比

通過三個性能指標對不同補全方法的定量分析可以得出與之前對數(shù)據(jù)補全前后圖像的定性分析相似的結果，EM 算法填充所得到的補全數(shù)據(jù)相對于均值填充準確性更高，誤差更小。

通過對三種方法定性、定量的分析，我們可以直觀地得出他們的優(yōu)缺點。顯然，單獨運用一種方法并不能達到我們預期的數(shù)據(jù)補全效果，因此，我們可以將三種數(shù)據(jù)處理方式結合，面對不同類型的缺失數(shù)據(jù)采取與之對應的處理方法。

3 結論

在帶內(nèi)網(wǎng)絡遙測領域中，隨著數(shù)據(jù)丟失缺口的增大，補全難度也隨之大幅增大，效果降低；在采用的四種方法中，刪除元組法較為局限，只適用于缺失數(shù)據(jù)占比小且缺失部位數(shù)據(jù)變化趨勢較平緩的情況，而均值填充和EM算法在圖像對比中可以看出，兩者補全效果均較為理想，相對而言均值填充能夠更好地反映圖像的變化特性，而EM 算法填充數(shù)據(jù)更加準確。從三個性能指標中不難分辨，EM 算法無論是誤差率，平均絕對誤差還是均方根誤差都明顯小于均值填充法，證明其補全穩(wěn)定性及準確性在本次實驗中優(yōu)于均值填充法。

基于以上實驗結果和理論分析，我們可以得出以下結論。在數(shù)據(jù)缺失數(shù)量較少的情況下，如果成本為主要考慮因素的話，可以采用刪除元組法，直接刪除丟失數(shù)據(jù)以換取較完備的數(shù)據(jù)集；如果準確性為主要考慮因素的話，可以采用EM 算法進行填充。當缺失數(shù)據(jù)占比大，數(shù)據(jù)波動不明顯時，可以采用EM 算法或者均值填充進行補全。而當數(shù)據(jù)波動顯著時，可以結合EM 算法和均值填充法進行補全，先通過EM 算法確定缺失部位的數(shù)據(jù)水平，然后根據(jù)此數(shù)據(jù)水平對均值填充得到的數(shù)據(jù)集進行調(diào)整，以達到既能很好地反映數(shù)據(jù)變化缺失，又能準確還原數(shù)據(jù)的目的。