帶內網絡遙測缺失數據補全算法研究

黃 暢，劉晏嘉，羅晟庭

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

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

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

1 數據處理

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

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

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

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

1.1 刪除元組

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

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

1.2 數據補齊

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

1.2.1 均值填充（Mean/Mode Completer）

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

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

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

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

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

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

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

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

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

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

2 實驗結果

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

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

2.1 刪除元組

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

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

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

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

2.2 均值填充

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

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

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

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

2.3 EM 算法填充

EM 算法相較于刪除元組法，其沒有丟失大量的數據。相對于均值填充法，其補全數據更加貼近原始數據，但是對于缺失部位的數據變化沒有很好地反映。EM 算法的優勢在于其補全值與缺失部位周圍的數據水平比較接近，而缺失位置周圍的數據某種程度上也可以反映原始數據的信息，所以其補全數據的準確性更好。但是問題在于，如果缺失部位全部用一個數據填充會忽略缺失部位原始數據變化的特點（見圖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分別表示導出數據的原始值和丟失后的補全值，Ω 表示丟失數據的索引集合。性能指標的計算公式如表1。

表1 性能指標的計算公式

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

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

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

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

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

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

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

3 結論

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

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