如何進行MV-Sketch的分析

如何進行MV-Sketch的分析，針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

網絡測量是對網絡行為進行特征化、對各項指標進行量化并充分理解與正確認識互聯網的最基本手段，支持著SDN的發展，網絡管理員可以通過網絡測量掌握網絡狀態，進而優化網絡結構、改善網絡服務質量，及時診斷網絡故障并進行恢復。Sketch在較小內存下對重流（heavy flow）和heavy changer（突變流））的快速檢測有助于SDN云數據中心的大量部署。

既然提到了Sketch，那么我們就來介紹一下什么是Sketch。Sketch是一種緊湊的用于流量數據統計亞線性數據結構。使用Hash算法將屬于映射到Sketch中，將大量網絡流壓縮至小部分的內存空間中，無需存儲所有網絡流，以達到節約內存的目的，并通過查詢操作獲得流量統計數據。使用Sketch的原因是其將具有相同哈希值的流存入相同的桶內，可以在保證準確度的同時大大減少存儲空間。

接下來為大家介紹的是MV-SKetch，是一種高效、緊湊、可逆的Sketch，可以在小內存下實現對重流的快速檢測，主要利用MJTRY算法（主票選算法）。相較于動態分配流存儲空間的方式，靜態分配的方式有助于降低內存管理開銷，且可以利用SIMD加速MV-Sketch。

MV-Sketch的數據結構由r行 構成，每一行有w個桶，每個桶中記錄三個元素Vi,j、Ki,j、 Ci,j。Vi,j表示哈希到這個桶內所有流的總和，Ki,j表示當前桶內的重流候選，Ci,j記錄當前桶內重流候選的計數值，用于判斷是否繼續保留此重流候選。如下圖所示：

當數據包到來時，MV-Sketch利用 r 個獨立的哈希函數，將數據包分別映射到1 - r 行，所映射列序j由哈希值hi(x)決定。哈希到某個桶之后，根據MJRTY算法來更新重流候選。查詢時，根據新流和桶內重流候選是否一致來決定估計值，最后返回所有行中估計值最小值。在一個周期結束時，MV-Sketch以是否大于設定的閾值為標準來判斷重流。

MV-SKetch所使用的MJRTY算法用于確定任意數量的候選人中，哪一個獲得了多數選票，所擁有票數高于總票數一半者，一定是主要候選人。舉例說明：假設有三位候選人A、B和C，并假設按以下順序對代表進行了投票：A A A C C B B C C C B C C

記錄完第三張選票后，A以3票領先。在處理接下來的三張選票時，將三張A票與三張其他票（兩張C票，一張B票）配對（抵消）。記錄所有選票之后，C成為主要候選人。

算法 1：MV-Sketch更新算法

MV-Sketch借鑒MJRTY算法,在執行更新操作時（算法1[2])，先累加Vi,j = Vi,j + vx (Vi,j增加新流字節數)，再將新流x與當前桶內重流候選Ki,j進行比較，若相同，那么計數器Ci,j增加新流的字節數，否則相應地減少；若減少至零下（即Ci,j <0)，則x取代Ki,j，且Ci,j取絕對值。在實際中，由于少數重流所帶流量在桶內所有流量中占主導地位，因而在一個周期結束時，MV-Sketch可以在桶內保持準確的重流候選。

關于如何進行MV-Sketch的分析問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。