一、背景

網絡測量是SDN發展的重要基礎。網絡狀態監測、網絡故障分析、網絡安全防御，乃至于網絡智能化，都依賴于網絡測量。作為網絡測量前沿研究的主流，基于sketch的高速流量網絡測量，是網絡領域頂級會議SIGCOMM近兩年的研究熱點，包括SIGCOMM’17的 SketchVisor[1] 和SIGCOMM’18的SketchLearn[2]、ElasticSketch[3]等。

[[249838]]

sketch的網絡測量與SDN結合，具有天然特性。一方面，SDN云數據中心的大量部署，需要基于sketch的高速流量網絡測量，因為sketch能進行大流和異常流的檢測，不占用過多的計算和空間資源。另一方面，SDN 轉控分離，控制器具有全局視野，能對網絡進行調度、制定策略，實時提供網絡信息，有利于sketch的應用實施。

當前的網絡流量測量，主要有抽樣技術和數據流技術兩種方法。抽樣技術為每條流維護一個獨立的計數器，較高的抽樣速率需要消耗大量的性能資源。數據流技術利用散列將龐大信息壓縮到較小的空間內，目前被廣泛應用的是基于 sketch 的網絡測量方法。

sketch 是一種基于散列的數據結構，可以在高速網絡環境中，實時地存儲流量特征信息，只占用較小的空間資源，并且具備在理論上可證明的估計精度與內存的平衡特性。基于sketch的網絡測量，目前主要有ReversibleSketch[4]、OpenSketch[5]、Sketchvisor[1]等相關改進及實現。

二、Sketch 的原理

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

1. 如何處理包

當高速網絡流量到來時，逐個記錄所有流量的信息，會帶來巨大的計算和空間資源開銷。而網絡測量往往也無需記錄所有的信息。

Count-Min sketch由多個哈希函數(f1……fn)和一張二維表組成。二維表的每個存儲空間維護了一個計數器，其中每個哈希函數分別對應表中的每一行。當一個網絡流到來時，需要經過每個哈希函數 f1……fn 的處理，根據處理得到的哈希值分別存入每一行對應哈希值的計數器。有幾個哈希函數，就要計算幾次。算完后，取這m個計數器中的最小值，作為測量的最終值。

圖1 Count-Min sketch 結構示意

2. 設計考量

測量值偏大：使用哈希的方法會產生沖突，多個網絡流數據哈希到同一個桶內，那么這個桶的計數值就會偏大。

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

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

小周是全市的快遞中轉站的負責人(SDN控制器)，他需要合理地分配人員的職責，制定分配的策略(全局調度)。他需要了解每個區的包裹數等信息(測量信息)，以便完成人員分配。起初，他把每個包裹的信息都記錄下來，并且讓百分之八十的人負責統計每個區的包裹數量。

可是這里的包裹有成千上萬之多(高速網絡環境)，統計人員算得滿頭大汗(計算資源開銷大)，記了幾十頁的紙(空間資源開銷大)，算得暈頭轉向。而另一頭，快遞員的數量太少，每個區的包裹，都沒有送完。

他意識到，記錄所有包裹的所有信息，是沒有必要的(精度要求降低)。他的目標，是合理地分配每個區的快遞員數量，他只需要了解每個區大致(估計)的包裹量即可(基于sketch的方法)。而且他發現，分類包裹這件事不應成為中轉站的負擔(減少測量開銷)，讓快遞的正常配送無法完成。

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

網絡流經過網絡結點時，需要制定合理的控制策略完成網絡流的高效調度。網絡流控制策略的制定，首先需要網絡測量提供的流量信息。當流量較小時，如果將每個流的信息都記錄下來，消耗計算和空間的資源并不大。

但是，當SDN 控制器進行全局調度時，有高速的流量通過。若將所有信息都一一記錄下來，將大大占用網絡資源，成為網絡的負擔。而且很多情況下，得到流量的估計值就足以滿足任務的需求，記錄所有信息是沒有必要的。

此時，基于 sketch 的方法，利用散列技術對網絡流進行粗粒度的分類，得出測量的估計值，滿足高速環境下實時測量的需求，節約計算和空間的開銷。

三、sketch研究熱點

sketch 是網絡測量研究領域的熱點問題，在如 SIGCOMM 等網絡領域頂級會議中，提出了一系列關于 Sketch 的解決方案 其中包括 SIGCOMM‘17 的 sketchvisor[1] 和 SIGCOMM’18 的SketchLearn[2] 和 ElasticSketch[3]，現簡單介紹基于 sketch 的研究熱點，主要分為sketch的數據結構和sketch的測量框架。

1. Sketch的數據結構

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

2. 基于Sketch的測量框架

• NSDI’13 的 OpenSketch [5]，首次將 sketch 應用在 SDN 中，是此類論文的的開山之作。
• LD-Sketch [6]將基于計數的方法和基于 sketch 的方法結合，用于檢測 heavy hitter 和 heavy changers，保持了一定的準確度和穩定性。

圖2 SketchVisor 結構示意

• SIGCOMM’17 上的 Sketchvisor [1]是基于 sketch 的測量框架，將過載流量導入 Fast Path， 完成高速環境下測量。
• SIGCOMM’18 的 SketchLearn [2]通過解耦資源配置和精確度的參數，利用自動統計推斷提取流量數據。
• 在多變的環境下，測量的性能會受到到很大的影響， SIGCOMM’18 的 ElasticSketch [3]對此設計了一個可以根據環境動態調整的測量框架，保持測量的穩定性和準確率。

四、總結

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