一、背景

網(wǎng)絡(luò)測(cè)量是SDN發(fā)展的重要基礎(chǔ)。網(wǎng)絡(luò)狀態(tài)監(jiān)測(cè)、網(wǎng)絡(luò)故障分析、網(wǎng)絡(luò)安全防御，乃至于網(wǎng)絡(luò)智能化，都依賴于網(wǎng)絡(luò)測(cè)量。作為網(wǎng)絡(luò)測(cè)量前沿研究的主流，基于sketch的高速流量網(wǎng)絡(luò)測(cè)量，是網(wǎng)絡(luò)領(lǐng)域頂級(jí)會(huì)議SIGCOMM近兩年的研究熱點(diǎn)，包括SIGCOMM’17的 SketchVisor[1] 和SIGCOMM’18的SketchLearn[2]、ElasticSketch[3]等。

[[249838]]

sketch的網(wǎng)絡(luò)測(cè)量與SDN結(jié)合，具有天然特性。一方面，SDN云數(shù)據(jù)中心的大量部署，需要基于sketch的高速流量網(wǎng)絡(luò)測(cè)量，因?yàn)閟ketch能進(jìn)行大流和異常流的檢測(cè)，不占用過多的計(jì)算和空間資源。另一方面，SDN 轉(zhuǎn)控分離，控制器具有全局視野，能對(duì)網(wǎng)絡(luò)進(jìn)行調(diào)度、制定策略，實(shí)時(shí)提供網(wǎng)絡(luò)信息，有利于sketch的應(yīng)用實(shí)施。

當(dāng)前的網(wǎng)絡(luò)流量測(cè)量，主要有抽樣技術(shù)和數(shù)據(jù)流技術(shù)兩種方法。抽樣技術(shù)為每條流維護(hù)一個(gè)獨(dú)立的計(jì)數(shù)器，較高的抽樣速率需要消耗大量的性能資源。數(shù)據(jù)流技術(shù)利用散列將龐大信息壓縮到較小的空間內(nèi)，目前被廣泛應(yīng)用的是基于 sketch 的網(wǎng)絡(luò)測(cè)量方法。

sketch 是一種基于散列的數(shù)據(jù)結(jié)構(gòu)，可以在高速網(wǎng)絡(luò)環(huán)境中，實(shí)時(shí)地存儲(chǔ)流量特征信息，只占用較小的空間資源，并且具備在理論上可證明的估計(jì)精度與內(nèi)存的平衡特性?；趕ketch的網(wǎng)絡(luò)測(cè)量，目前主要有ReversibleSketch[4]、OpenSketch[5]、Sketchvisor[1]等相關(guān)改進(jìn)及實(shí)現(xiàn)。

二、Sketch 的原理

sketch是基于散列的數(shù)據(jù)結(jié)構(gòu)，通過設(shè)置散列函數(shù)，將具有相同散列值的鍵值數(shù)據(jù)存入相同的桶內(nèi)，以減少空間開銷。桶內(nèi)的數(shù)據(jù)值作為測(cè)量結(jié)果，是真實(shí)值的近似。利用開辟二維地址空間，多重散列等技術(shù)減少散列沖突，提高測(cè)量結(jié)果的準(zhǔn)確度。Count-Min[7] 是一種典型的 sketch ，在 2004 年被提出。實(shí)際上 Count-Min sketch 用到的是分類的思想：將具有相同哈希值的網(wǎng)絡(luò)流歸為一類，并使用同一個(gè)計(jì)數(shù)器計(jì)數(shù)。

1. 如何處理包

當(dāng)高速網(wǎng)絡(luò)流量到來時(shí)，逐個(gè)記錄所有流量的信息，會(huì)帶來巨大的計(jì)算和空間資源開銷。而網(wǎng)絡(luò)測(cè)量往往也無需記錄所有的信息。

Count-Min sketch由多個(gè)哈希函數(shù)(f1……fn)和一張二維表組成。二維表的每個(gè)存儲(chǔ)空間維護(hù)了一個(gè)計(jì)數(shù)器，其中每個(gè)哈希函數(shù)分別對(duì)應(yīng)表中的每一行。當(dāng)一個(gè)網(wǎng)絡(luò)流到來時(shí)，需要經(jīng)過每個(gè)哈希函數(shù) f1……fn 的處理，根據(jù)處理得到的哈希值分別存入每一行對(duì)應(yīng)哈希值的計(jì)數(shù)器。有幾個(gè)哈希函數(shù)，就要計(jì)算幾次。算完后，取這m個(gè)計(jì)數(shù)器中的最小值，作為測(cè)量的最終值。

圖1 Count-Min sketch 結(jié)構(gòu)示意

2. 設(shè)計(jì)考量

測(cè)量值偏大：使用哈希的方法會(huì)產(chǎn)生沖突，多個(gè)網(wǎng)絡(luò)流數(shù)據(jù)哈希到同一個(gè)桶內(nèi)，那么這個(gè)桶的計(jì)數(shù)值就會(huì)偏大。

• 為什么允許有誤差：在高速網(wǎng)絡(luò)條件下，若把所有信息都準(zhǔn)確地記錄下來，要消耗大量計(jì)算和空間開銷，無法滿足實(shí)時(shí)性;而且在很多情況下，并不需要非常精確的測(cè)量數(shù)據(jù)，在一定程度上可靠的估計(jì)值，便足以滿足需求。
• 為什么要設(shè)置多個(gè)哈希函數(shù)：如果只設(shè)置一個(gè)哈希函數(shù)，多個(gè)流數(shù)據(jù)存入同一個(gè)桶，誤差就會(huì)很大。通過設(shè)計(jì)多個(gè)哈希函數(shù)，減少哈希值的沖突，以減少誤差。每個(gè)流都要經(jīng)過所有哈希函數(shù)的處理，存入不同的計(jì)數(shù)器中。計(jì)數(shù)器的最小值雖然還是大于等于真實(shí)值，但最接近真實(shí)值。這也是 “ Count-Min ”的由來。
• 哈希函數(shù)個(gè)數(shù)：哈希函數(shù)越多，沖突越少，測(cè)量值越精確，但計(jì)算開銷大。需要權(quán)衡測(cè)量精度和準(zhǔn)確度，來設(shè)置合適的哈希函數(shù)個(gè)數(shù)。

為了幫助理解sketch的原理，這里從一個(gè)例子講起：

小周是全市的快遞中轉(zhuǎn)站的負(fù)責(zé)人(SDN控制器)，他需要合理地分配人員的職責(zé)，制定分配的策略(全局調(diào)度)。他需要了解每個(gè)區(qū)的包裹數(shù)等信息(測(cè)量信息)，以便完成人員分配。起初，他把每個(gè)包裹的信息都記錄下來，并且讓百分之八十的人負(fù)責(zé)統(tǒng)計(jì)每個(gè)區(qū)的包裹數(shù)量。

可是這里的包裹有成千上萬之多(高速網(wǎng)絡(luò)環(huán)境)，統(tǒng)計(jì)人員算得滿頭大汗(計(jì)算資源開銷大)，記了幾十頁的紙(空間資源開銷大)，算得暈頭轉(zhuǎn)向。而另一頭，快遞員的數(shù)量太少，每個(gè)區(qū)的包裹，都沒有送完。

他意識(shí)到，記錄所有包裹的所有信息，是沒有必要的(精度要求降低)。他的目標(biāo)，是合理地分配每個(gè)區(qū)的快遞員數(shù)量，他只需要了解每個(gè)區(qū)大致(估計(jì))的包裹量即可(基于sketch的方法)。而且他發(fā)現(xiàn)，分類包裹這件事不應(yīng)成為中轉(zhuǎn)站的負(fù)擔(dān)(減少測(cè)量開銷)，讓快遞的正常配送無法完成。

于是，他只留下幾個(gè)人，讓其他人負(fù)責(zé)配送包裹。相同區(qū)的包裹記在同一個(gè)區(qū)(計(jì)入同一個(gè)桶內(nèi))，并且只需大致計(jì)算每個(gè)區(qū)的包裹數(shù)即可(近似)。這樣一來，統(tǒng)計(jì)速度明顯快了許多，用了一兩張紙就把數(shù)據(jù)記完了。得出數(shù)據(jù)后，得知 A 區(qū)的包裹數(shù)最多，而 B 區(qū)的最少，小周將 B 區(qū)的大部分快遞員分配到 A 區(qū)，不僅完成了昨天的配送，今天的配送也早早地完成(實(shí)時(shí)性)。

網(wǎng)絡(luò)流經(jīng)過網(wǎng)絡(luò)結(jié)點(diǎn)時(shí)，需要制定合理的控制策略完成網(wǎng)絡(luò)流的高效調(diào)度。網(wǎng)絡(luò)流控制策略的制定，首先需要網(wǎng)絡(luò)測(cè)量提供的流量信息。當(dāng)流量較小時(shí)，如果將每個(gè)流的信息都記錄下來，消耗計(jì)算和空間的資源并不大。

但是，當(dāng)SDN 控制器進(jìn)行全局調(diào)度時(shí)，有高速的流量通過。若將所有信息都一一記錄下來，將大大占用網(wǎng)絡(luò)資源，成為網(wǎng)絡(luò)的負(fù)擔(dān)。而且很多情況下，得到流量的估計(jì)值就足以滿足任務(wù)的需求，記錄所有信息是沒有必要的。

此時(shí)，基于 sketch 的方法，利用散列技術(shù)對(duì)網(wǎng)絡(luò)流進(jìn)行粗粒度的分類，得出測(cè)量的估計(jì)值，滿足高速環(huán)境下實(shí)時(shí)測(cè)量的需求，節(jié)約計(jì)算和空間的開銷。

三、sketch研究熱點(diǎn)

sketch 是網(wǎng)絡(luò)測(cè)量研究領(lǐng)域的熱點(diǎn)問題，在如 SIGCOMM 等網(wǎng)絡(luò)領(lǐng)域頂級(jí)會(huì)議中，提出了一系列關(guān)于 Sketch 的解決方案 其中包括 SIGCOMM‘17 的 sketchvisor[1] 和 SIGCOMM’18 的SketchLearn[2] 和 ElasticSketch[3]，現(xiàn)簡(jiǎn)單介紹基于 sketch 的研究熱點(diǎn)，主要分為sketch的數(shù)據(jù)結(jié)構(gòu)和sketch的測(cè)量框架。

1. Sketch的數(shù)據(jù)結(jié)構(gòu)

• Count-min sketch[7] 通過設(shè)置多個(gè)散列函數(shù)減少散列沖突，將計(jì)數(shù)器的最小值作為測(cè)量結(jié)果，是一種典型的 sketch。
• 基于 sketch 的方法常常被用來檢測(cè)大流和異常流，但是無法根據(jù)測(cè)量信息推出信息來源。而Reversible sketch[4] 可以解決這個(gè)問題，推斷出信息的來源。
• SeqHash [8]應(yīng)用于入侵防御、大流檢測(cè)，優(yōu)點(diǎn)是快速精確，資源開銷小。
• top-k[9] 應(yīng)用于檢測(cè)數(shù)據(jù)流中最常見元素，優(yōu)點(diǎn)是空間開銷小，速度快。

2. 基于Sketch的測(cè)量框架

• NSDI’13 的 OpenSketch [5]，首次將 sketch 應(yīng)用在 SDN 中，是此類論文的的開山之作。
• LD-Sketch [6]將基于計(jì)數(shù)的方法和基于 sketch 的方法結(jié)合，用于檢測(cè) heavy hitter 和 heavy changers，保持了一定的準(zhǔn)確度和穩(wěn)定性。

圖2 SketchVisor 結(jié)構(gòu)示意

• SIGCOMM’17 上的 Sketchvisor [1]是基于 sketch 的測(cè)量框架，將過載流量導(dǎo)入 Fast Path， 完成高速環(huán)境下測(cè)量。
• SIGCOMM’18 的 SketchLearn [2]通過解耦資源配置和精確度的參數(shù)，利用自動(dòng)統(tǒng)計(jì)推斷提取流量數(shù)據(jù)。
• 在多變的環(huán)境下，測(cè)量的性能會(huì)受到到很大的影響， SIGCOMM’18 的 ElasticSketch [3]對(duì)此設(shè)計(jì)了一個(gè)可以根據(jù)環(huán)境動(dòng)態(tài)調(diào)整的測(cè)量框架，保持測(cè)量的穩(wěn)定性和準(zhǔn)確率。

四、總結(jié)

• 高管理能力對(duì)網(wǎng)絡(luò)測(cè)量的性能、準(zhǔn)確率、資源開銷提出了更高的要求。
• Sketch 是一種基于散列的數(shù)據(jù)結(jié)構(gòu)，可以在高速網(wǎng)絡(luò)環(huán)境中，實(shí)時(shí)地存儲(chǔ)流量特征信息，只占用較小的空間資源，并且具備在理論上可證明的估計(jì)精度與內(nèi)存的平衡特性。
• Count-min [7]是一種典型的 sketch ，用到的是分類的思想：將具有相同哈希值的網(wǎng)絡(luò)流歸為一類，并使用同一個(gè)計(jì)數(shù)器計(jì)數(shù)。
• 基于 Sketch 的方法是當(dāng)下主流和熱門的網(wǎng)絡(luò)測(cè)量方法，有著廣泛的應(yīng)用和前景。