[论文笔记] Sigcomm 2018 Elastic Sketch: Adaptive and Fast Network-wide Measurements
先附上論文的GitHub鏈接
做實驗的話真的得看這篇，有那么多可以實驗的角度。
文章目錄
- introduction
- available bandwidth
- packet arrival rate
- flow size distribution
- our solution
- key contribution
- Basic version中的OStracism
- accuracy analysis
- adaptive to bandwidth
- Compression of Sketches
- Merging of Sketches 多個不同的sketch進行合并
- adaptive to packet error
- adaptive to flow size distribution
- optimization
- light part部分優化
- 硬件版本優化——multiple sub-tables
- 軟件版本優化——multiple key-value pairs
- application
- flow size estimation
- heavy hitter detection
- heavy change detection
- flow size distribution，entropy，and cardinality
- implementation
- P4 implementation
- FPGA implementation
- GPU Implementation
- Software Version Implementations
- experimental results
- Experimental Setup
- Accuracy
- observed worst cases
- heavy hitter detection
- memory and bandwidth usage
- elasticity
- Adaptivity to Bandwidth
- Adaptivity to Packet Rate
- Adaptivity to Traffic Distribution
除了basic version的方式分離象流和鼠流，以及MM合并的一個bound
其他都沒給出數學上的證明。（居然在技術報告里）
我簡直有毒，在heavyguardian里面，除了算法，什么都寫了。
再次強調不要犯懶，復習的時候真的只想看自己的博客，不想點開別人的了。一定要把一些事情的意義寫上去。
基于sketch的網絡測量方法介紹
別人的大四VS我的大四orz
introduction
網絡測量對數據中心和骨干網的network operations, quality of service, capacity planning, network accounting and billing, congestion control, anomaly detection都是必不可少的。
由于基于sketch的解決方法比抽樣方法準確率要高，因此它們被廣泛采用。主要是尋求accuracy、speed、和內存的平衡。
最前沿的算法UnivMon還關注于generality，即用一個sketch來實現多種任務。
但是他們都沒有將sketch設計的符合網絡的變化，網絡測量在網絡遭遇問題的時候重要性尤為凸顯，網絡特性急劇變化會極大降低測量性能。
available bandwidth
在數據中心，管理員更關注網絡全局狀態（network-wide measurements），他們可以在網絡中部署很多測量節點，周期性地向controller報告，發送這些測量信息和用戶流量是共享數據平面帶寬的。但是擁塞經常發生，It can happen frequently within a single second [19] and be as large as more than half of the network bandwidth [9].
Network measurements should not be a burden for the network.
A good solution is to actively compress the sketch with little accu- racy loss, thereby reducing bandwidth usage.
省略省略，總之就是測量很重要，擁塞時更加需要測量來發現問題解決問題，但是擁塞時又沒有帶寬留給測量，因此應該壓縮sketch、
Besides passive compression during congestion, network operators need to proactively control the measurement tasks as well. For example, to keep service- level agreements (SLA) during maintenance or failures [28], operators tend to reduce measurements and leave the band- width for critical user traffic.
packet arrival rate
當網絡被掃描或者受到DDoS攻擊時，包會很小很多. The processing speed of existing sketches on software platforms is fixed in terms of packet rate. 因此包到達率突然增大的時候不work，不能記錄一些重要的信息。因此要加速sketch的處理速度。
state-of-art solution：SketchVisor，使用fast path組件absorb excessive traffic at high packet rate.但是在最壞情況下要遍歷整個數據結構，雖然更新復雜度是O(1)。要多次訪問內存。本文算法只需要一次
flow size distribution
鼠流和象流應該分開，但是flow size distribution一直在變，導致分配多大的內存存儲需要跟著變化。預測是不OK的，預測一小時內象流的數量可能很簡單，但是ms級別或是s級就很難[39]，因此設計了動態分配合適內存給象流的方法。
Besides them, there are three other requirements in measurements: 1) generic, 2) fast, and 3) accurate
已有的generic的算法是UnivMon和FlowRadar，本文實驗中發現UnivMon準確度不太好，FlowRadar消耗大量內存。
FlowRadar在Bloom Filter和Invertible Bloom Lookup table （可逆式布魯姆查找表）里面記錄了所有的流ID和大小。為了減少內存消耗，踢出network-wide decoding，但是內存消耗還是比sketch要高。
UnivMon的關鍵技術是universal streaming，準確度由它來保證。它是第一個generic的，性能還不錯，但是不適應多變的網絡。
our solution
Ostracism分離鼠流和象流
elastic：
generic：
- 保存每個包所有必要信息，丟棄鼠流的ID信息(耗內存且無用)
- 提出軟件和硬件版本的改進，為P4量身設計了一個版本
Owing to the separation and discarding of unnecessary information, our sketch is accurate and fast: experimental results show that our sketch achieves 44.6~45.2 times faster speed and 2.0 ~273.7 smaller error rate than the state-of-the-art UnivMon
key contribution
簡而言之
Basic version中的OStracism
given a high-speed network stream, how to use only one bucket to select the largest flow?
看到 ostracism 的時候，感覺和
數據流基本問題–確定頻繁元素（一） 中提到的，我覺得思想是一致的，然后引入一個λ\lambdaλ
λ的作用是什么呢？
flag的作用是判斷bucket里面是否evicted過
如果兩個大象流碰撞了，或者三個，那么其中一個就有可能被evicted入light part，那么信息就沒有得到很好的保存
如果我就用編程之美中提到的方法，那么cold item的信息是就全沒有，而且hot item的信息會被預估的小？（不考慮碰撞的話）lambda越大，存的vote+應該就越準
它這相當于λ=1\lambda=1λ=1就驅逐
accuracy analysis
f^i?fi+?∥fl∥14<fi+?∥f∥1\hat{f}_{i} \leqslant f_{i}+\epsilon\left\|f_{l}\right\|_{1}^{4}<f_{i}+\epsilon\|f\|_{1}f^?i??fi?+?∥fl?∥14?<fi?+?∥f∥1?
where fL denotes the size vector of the sub-stream recorded by light part
∥x∥1\|\mathbf{x}\|_{1}∥x∥1? is the first moment of vector x,\mathbf{x},x, i.e., ∥x∥1=∑xi\|\mathbf{x}\|_{1}=\sum x_{i}∥x∥1?=∑xi?
準確度最差的情況：象流發生了碰撞，如果象流碰撞，那么一個象流會被放入light part，使得鼠流被大幅度over-estimated
elephant collision rate PhcP_{hc}Phc?：定義為發生碰撞的桶數除以總桶數。
Phc=1?(Hw+1)e?HwP_{h c}=1-\left(\frac{H}{w}+1\right) e^{-\frac{H}{w}}Phc?=1?(wH?+1)e?wH?
H是象流數目，w是桶數
解決象流碰撞問題的辦法（其實就是減少哈希碰撞）：by using multi- ple sub-tables (see Section 4.2); 2) by using multiple key-value pairs in one bucket
adaptive to bandwidth
發的sketch太大會影響時延和用戶流量
Compression of Sketches
兩步走 先group，然后把同一組中的merge
合并的時候有兩個選擇，取sum，那么和直接存的accuracy是一樣的，本文使用的是maximum，使用了原先sketch更多的信息，也有更高的效率
compress light
分組相當于什么叭，數論里面的完全什么什么集 {0} {1} … {r-1}
mod 3為1的放入一組，選擇組中最大的，然后你mod 3為1就能找回這個數據。按照原圖去找，要找到之前的位置是3k+1，在3k+1里面選擇最大的去保留
merge就是在同組里面選最大的。生成B之后還是d個hash function，映射之后找最小的。會有over-estimate error
這個所謂的同樣的accuracy是指什么？
他這里的同樣的accuracy，指的是用一個大S1,1/2小S2的accuracy 和只用一個大S1，然后把它/2 是一樣的
這是非常直觀的，你想hash入更小的sketch，可不就是直接相加嗎？
難點在于如何讓后者有更高的accuracy。選擇采用MAX 而不是SUM，因為MAX能留住更多的信息。（原話是這么翻譯過來的）
MAX的誤差界限：
Pr?{n^j?nj+?N}?{1?(1?1?zw)[1?Nzw(nj+?N)]z?1}d\operatorname{Pr}\left\{\hat{n}_{j} \geqslant n_{j}+\epsilon N\right\} \leqslant\left\{1-\left(1-\frac{1}{\epsilon z w}\right)\left[1-\frac{N}{z w\left(n_{j}+\epsilon N\right)}\right]^{z-1}\right\}^ze8trgl8bvbqPr{n^j??nj?+?N}?{1?(1??zw1?)[1?zw(nj?+?N)N?]z?1}d
這居然也能數學證明，數學厲害死了。
- MC比SC(sum compression)的誤差界更緊一點
- 證明使用MC，只有over-estimation錯誤，沒有under-estimation錯誤
- 使用SIMD（single Instruction and multiple data）加速5~8倍
- 沒有解壓縮的必要
- 壓縮不需要額外的數據結構
以上在technical report都有證明
Merging of Sketches 多個不同的sketch進行合并
在合并的過程中選擇max，可以避免under-estimation error
adaptive to packet error
現有的sketch方案的processing speed是常數（應該不能這么翻譯emm），但是處理一個包需要不小于10 memory access。設計目標是在packet rate low的時候兩次存取，high的時候一次存取。但是難以維持高準確率。
賣點：只需要一次內存存取。
概括：插入的時候只對heavy part進行操作。注意并不是丟棄light part，因為查詢的時候還要用到。
packet rate變得很high，插入時：如果fff被f′f^{'}f′代替，f′f^{'}f′的大小被置為fff的大小。這樣，每次插入只需要訪問一次bucket。在插入的時候是不訪問light part的。
當速度慢下來，就用之前的算法。
我想知道accuracy降低了多少
This means that only information recorded by the light part when high packet rate occurs is lost. This strategy does not affect much the query accuracy in most cases, since the packet rate is usually low.
adaptive to flow size distribution
hard to predict[39]
概括：copy operation
flow size distribution的一個關鍵指標是大象流的個數，它經常變，因此我們需要動態調整Heavy part的大小。如果bucket中記錄的流大小超過T2的流數超過T1，就啟動copy operation：將heavy part直接復制一份，copied和之前的合起來。那么之前的有一半的需要移動。怎么理解呢？比如說我原先是h%4， 我現在size由4變成8，現在是h%8，但是h%8結果中會包含h%4的部分，因此這部分bucket不需要移動，但是值為5-7的部分需要后移。算法執行a lazy elimination，插入的時候如果出現碰撞，才把原先的移出，新的插進去。
比如f′f^{'}f′應該被插入bucket A，檢查bucket A中其他的flow，這些flow應該有一半是不屬于這個bucket了，然后把這些給removed。對這部分代碼有疑問。每次插入都去檢查，豈不是很浪費時間？
還有當我來一個新的f′f^{'}f′的是時候，我怎么知道fff是應該直接被remove還是按照正常流程增加它的negative vote，然后把它移入light part。我還是要檢查一下fff，是新插入的還是之前
而且從之前的heavyGuardian中來看，并沒有存hash值。
Overhead：由于heavy part一般很小（150KB），復制花的時間可以忽略不計
把多鍵值對和單鍵值對的情況混在一起講很難理解啊(#`O′)
不僅可以enlarge heavy part，也可以壓縮heavy part，合并的buckets。比較兩個buckets里面記錄的flow的頻次，保留大的那個，將小的驅逐進light part來釋放內存。
這里又有一個問題了，如果是using multiple key-value pairs in one bucket的防碰撞機制，如何壓縮？
不同的平臺用不同的防碰撞方法
看了視頻里三個提問
1、如何得到flow ID
2、如何合并compressed和non compressed sketch
3、如何做cardinality estimation 線性那個啥
不同種類的sketch的影響，CU的accuracy會更高，為什么沒用呢？因為硬件不支持某個操作
同時CU好像不支持刪除操作sketch調研
optimization
light part部分優化
使用的hash函數個數減少為1，因為accuracy已經夠高了，更關注實現的可行性和速度
硬件版本優化——multiple sub-tables
每個子表的操作都和basic version相同，但是用不同的hash函數。大象流的碰撞概率隨著子表的個數呈指數遞減。
每個子表操作相同，因此適合各種硬件平臺。
插入和之前沒啥區別，查找的時候要把所有表加起來。注意他是按順序的先第一張表，再第二張表，這意味著可能第二張表存了f4,第一張表之后f4來的時候剛好evict走一個別的，因此要把兩個heavy part都查詢了然后加起來。
根據實驗，使用4張表能夠在準確度和可實現性上達到很好的平衡
軟件版本優化——multiple key-value pairs
一個bucket里存多個flow的數據，bucket size會比a machine word大，存取會成為瓶頸。幸運的是，可以使用SIMD在CPU平臺上加速該過程，因此這種優化方式適合軟件平臺。
所有的流共享negative vote，比值超過λ\lambdaλ驅逐的時候驅逐size最小的flow，然后把共享的negative vote置為0。
application
generic：
知道IDs和flow size，可以處理以下任務。
據觀察，鼠流的ID不需要
flow size estimation
本文中用包數作為flow size，也可以策略bytes數（假設最小包64byte，如果一個包是120bytes，向上取整我們就認為是2個包）
heavy part里面flag=false的流的大小都是準確的。more than 56.6% flows in the heavy part have no error when using 600KB memory for 2.5M packets
heavy hitter detection
查詢heavy part，如果flow size大于一個固定的閾值，就報告為heavy hitter。只有小部分與light part進行交換過的有誤差。
heavy change detection
沒啥好說的 和hitter差不多
flow size distribution，entropy，and cardinality
這些任務不僅僅關注大象流，還關注鼠流。在heavy part里的信息直接獲取，在light part里的部分，根據counter distribution獲得需要的信息。在每個時間窗的末尾，收集counter distribution信息，即值為i的counter有多少個。然后把heavy part和壓縮后的light part以及記錄counter distribution的array一起發給collector。
MRAC
還有web traffic 和 DNS traffic 的
不想看MRAC的論文，下次下次。
HeavyGuardian是以概率驅逐，這個是給一個閾值，這個估計流的分布為什么不能按照heavyguardian的方式呢？這兩種估計方式的優劣何在？
是基于flow size distribution的，沒啥好說的
關于cardinality estimation，這里突然插入？如果多的話我就放另一個博客~ 另一個博客見，反正是數學的天下。
其他任務比如說DDoS，SuperSpreader會在以后討論。
implementation
we briefly describe the implementation of hardware and software versions of the Elastic sketch on P4, FPGA, GPU platforms, and CPU, multi-core CPU, OVS platforms, respectively.
P4 implementation
不懂硬件，不懂P4 orz
在基礎的switch上構建了Elastic sketch的P4原型。在硬件版本里寄存器實現了heavy part和light part，而不是match-action表，因為需要直接從數據平面更新條目。We leverage the Stateful Algorithm and Logi- cal Unit (Stateful ALU) in each stage to lookup and update the entries in register array. 但是Stateful ALU資源有限，每一個Stateful ALU只能更新一對32bit的寄存器，但是硬件版本的Elastic需要插入時存取4個fields。為了解決這個問題，將Elastic sketch修改了一下以適應P4交換機，精度損失了一點。
在hard-ware版本的基礎上做了如下變動：
- We only store three fields in two physical stages：vote all,and?(key,?vote?+),\left.^{a l l}, \text { and (key, vote }^{+}\right),all,?and?(key,?vote?+), where vote all^{a l l}all指的是正投票和負投票的和。
- 當voteallvote+?λ′\frac{v o t e^{a l l}}{v o t e^{+}} \geqslant \lambda^{\prime}vote+voteall??λ′時，采取驅逐策略 λ′=32\lambda^{\prime}=32λ′=32,原因在技術報告section B里面。
- As mentioned in Section 4.2, we recommend using 4 subtables in the hardware version. In this way, we only need 4*2=8 stages for the heavy part, and 1 stage for the light part, and thus in total 9 stages. ？？stage指的是什么
四個版本的elastic sketch性能對比
FPGA implementation
We implement the Elastic sketch on a Stratix V family of Altera FPGA (model 5SEEBF45I2). The capacity of the on-chip RAMs (Block RAM) is 54,067,200 bits. The resource usage information is as follows: 1) We use 1,978,368 bits of Block RAM, 4% of the total on-chip RAM. 2) We use 36/840 pins, 4% of the total 840 pins. 3) We use 2939 logics, less than %1 of the 359,200 total available. The clock frequency of our implemented FPGA is 162.6 MHz, meaning processing speed of 162.6 Mpps.
GPU Implementation
We use the CUDA toolkit [64] to write programs on GPU to accelerate the insertion time of Elastic sketch. Two techniques, batch processing and multi- streaming, are applied to achieve the acceleration. We use an NVIDIA GPU (GeForce GTX 1080, the frequency is 1607 MHz. It has 8 GB GDDR5X memory and 2560 CUDA cores).
Software Version Implementations
CPU, multi-core CPU, and OVS
experimental results
Experimental Setup
Traces：四個一小時的公共流trace collected in Equinix-Chicago monitor from CAIDA，將這些traces劃分成不同的時間間隔（1s, 5s, 10s, 30s, and 60s）。比方說一個小時的traces可以劃分為720個5s的子trace，we plot 10th and 90th percentile error bars across these 720 sub-traces.我們用5s間隔的trace作為默認trace，which contains 1.1M to 2.8M packets with 60K to 110K flows (SrcIP)。由于空間限制，只展示source IP作為flow ID的結果。the results are qualitatively similar for other flow IDs (e.g., destination IP, 5-tuple).
metrics
- ARE: 1n∑i=1n∣fi?fi^∣fi\frac{1}{n} \sum_{i=1}^{n} \frac{\left|f_{i}-\widehat{f_{i}}\right|}{f_{i}}n1?∑i=1n?fi?∣fi??fi??∣? fif_{i}fi?是實際的流大小，fi^\widehat{f_{i}}fi??是估計的流大小，使用ARE來評判flow size (FS) estimation and heavy hitter detection。Note that the value of ARE for ?ow size estimation could be larger than anticipated, since the sizes of mouse flows are often over-estimated while they are in the denominator of the ARE formula, leading to large average value of relative error
- F1 score: 2×PR×RRPR+RR\frac{2 \times P R \times R R}{P R+R R}PR+RR2×PR×RR?
PR refers to the ratio of true instances reported
RR refers to the ratio of reported true instances 這個英語絕了，上面強調reported，下面強調true instances - WMRE（weighted mean relative error）：∑i=1z∣ni?n^i∣∑i=1z(ni+n^i2)\frac{\sum_{i=1}^{z}\left|n_{i}-\widehat{n}_{i}\right|}{\sum_{i=1}^{z}\left(\frac{n_{i}+\widehat{n}_{i}}{2}\right)}∑i=1z?(2ni?+ni??)∑i=1z?∣ni??ni?∣? z是流的最大size，nin_ini?是大小為i的流的真實個數， n^i\widehat{n}_{i}ni?是大小為i的流的預估個數。用這個指標來估計flow size distribution(FSD)的精度
- RE（relative error）∣True-Estimated∣True\frac{| \text {True-Estimated} |}{\text {True}}True∣True-Estimated∣? 用來衡量熵和基數估計的精度
- Throughput：每秒百萬個包，衡量6個任務的處理速度。
和別的算法對比的時候，用軟件版本的，在heavy part存儲7 flows和一個vote?^-?,light part使用一個hash函數和8bit計數器，每個任務的默認內存大小是600K。heavy part只在測試adaptivity to traffic distribution的時候會動態擴展。
Accuracy
the ARE of Elastic is about 3.8, 2.5, and 7.5 times lower than the one of CM, CU, and Count.
We find that our compression algorithm significantly improves the accuracy of CM sketch, making it nearly approach the accuracy of Elastic.
observed worst cases
測量誤差來源：
- 象流被踢到了light part
- 一些流在light part產生碰撞
In our experiments, over different traces, we observe that at most 2 flows have under-estimation error, and the maximum absolute error is 254 (i.e., a flow with size 1 is mapped to an overflowed counter). In each trace, there are about 110,000 flows and the maximum flow size is about 17,000. It means Elastic has small relative errors even in the worst case.
heavy hitter detection
Observed Worst Cases: Here, we show the observed worst cases of Elastic in the flow size estimation, instead of the average errors shown in the above flgures. Notice that the estimation error of Elastic comes from two parts: 1) Some elephant flows are recorded in the light part due to the hash collisions in the heavy part, and this may incur overflows of counters in the light part. 2) Some flows collide at the same counter in the light part. In our experiments, over different traces, we observe that at most 2 flows have under-estimation error, and the maximum absolute error is 254 (i.e., a flow with size 1 is mapped to an overflowed counter). In each trace, there are about 110,000 flows and the maximum flow size is about 17,000. It means Elastic has small relative errors even in the worst case.
- 因為碰撞象流進入了light part，象流導致overflow
- light part發生碰撞over different traces, we observe that at most 2 flows have under-estimation error
memory and bandwidth usage
We measure the memory and bandwidth usage of different algorithms to achieve a fixed target accuracy, using different traces and different monitoring time intervals.
memory指的是給測量算法起初分配的內存大小
bandwidth指的是每個測量周期需要被傳輸的數據量
測量bandwidth時（16MBwith 500KB heavy part）
When measuring the bandwidth usage of Elastic, we set the original memory to 16MBwith 500KB heavy part, run the maximum compression algorithm (§3.2.1), and measure the memory usage after compression (as the bandwidth usage) to achieve the fixed target accuracy
對于其他測量算法，memory=bandwidth
通過改變Monitoring time intervals 和Traces來進行測量
elasticity
Adaptivity to Bandwidth
Adaptivity to Packet Rate
Adaptivity to Traffic Distribution
讓我們來瞅瞅 heavy part是如何實現的
總結
以上是生活随笔為你收集整理的[论文笔记] Sigcomm 2018 Elastic Sketch: Adaptive and Fast Network-wide Measurements的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java期末复习速成（一）
- 下一篇： SIEBEL配置学习笔记