如何進(jìn)行MV-Sketch的分析

如何進(jìn)行MV-Sketch的分析，針對(duì)這個(gè)問(wèn)題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問(wèn)題的小伙伴找到更簡(jiǎn)單易行的方法。

網(wǎng)絡(luò)測(cè)量是對(duì)網(wǎng)絡(luò)行為進(jìn)行特征化、對(duì)各項(xiàng)指標(biāo)進(jìn)行量化并充分理解與正確認(rèn)識(shí)互聯(lián)網(wǎng)的最基本手段，支持著SDN的發(fā)展，網(wǎng)絡(luò)管理員可以通過(guò)網(wǎng)絡(luò)測(cè)量掌握網(wǎng)絡(luò)狀態(tài)，進(jìn)而優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)、改善網(wǎng)絡(luò)服務(wù)質(zhì)量，及時(shí)診斷網(wǎng)絡(luò)故障并進(jìn)行恢復(fù)。Sketch在較小內(nèi)存下對(duì)重流（heavy flow）和heavy changer（突變流））的快速檢測(cè)有助于SDN云數(shù)據(jù)中心的大量部署。

既然提到了Sketch，那么我們就來(lái)介紹一下什么是Sketch。Sketch是一種緊湊的用于流量數(shù)據(jù)統(tǒng)計(jì)亞線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。使用Hash算法將屬于映射到Sketch中，將大量網(wǎng)絡(luò)流壓縮至小部分的內(nèi)存空間中，無(wú)需存儲(chǔ)所有網(wǎng)絡(luò)流，以達(dá)到節(jié)約內(nèi)存的目的，并通過(guò)查詢(xún)操作獲得流量統(tǒng)計(jì)數(shù)據(jù)。使用Sketch的原因是其將具有相同哈希值的流存入相同的桶內(nèi)，可以在保證準(zhǔn)確度的同時(shí)大大減少存儲(chǔ)空間。

接下來(lái)為大家介紹的是MV-SKetch，是一種高效、緊湊、可逆的Sketch，可以在小內(nèi)存下實(shí)現(xiàn)對(duì)重流的快速檢測(cè)，主要利用MJTRY算法（主票選算法）。相較于動(dòng)態(tài)分配流存儲(chǔ)空間的方式，靜態(tài)分配的方式有助于降低內(nèi)存管理開(kāi)銷(xiāo)，且可以利用SIMD加速M(fèi)V-Sketch。

MV-Sketch的數(shù)據(jù)結(jié)構(gòu)由r行 構(gòu)成，每一行有w個(gè)桶，每個(gè)桶中記錄三個(gè)元素Vi,j、Ki,j、 Ci,j。Vi,j表示哈希到這個(gè)桶內(nèi)所有流的總和，Ki,j表示當(dāng)前桶內(nèi)的重流候選，Ci,j記錄當(dāng)前桶內(nèi)重流候選的計(jì)數(shù)值，用于判斷是否繼續(xù)保留此重流候選。如下圖所示：

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

MV-SKetch所使用的MJRTY算法用于確定任意數(shù)量的候選人中，哪一個(gè)獲得了多數(shù)選票，所擁有票數(shù)高于總票數(shù)一半者，一定是主要候選人。舉例說(shuō)明：假設(shè)有三位候選人A、B和C，并假設(shè)按以下順序?qū)Υ磉M(jìn)行了投票：A A A C C B B C C C B C C

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

算法 1：MV-Sketch更新算法

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

關(guān)于如何進(jìn)行MV-Sketch的分析問(wèn)題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒(méi)有解開(kāi)，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識(shí)。