摘要：
識(shí)別“heavy hitter”數(shù)據(jù)流或數(shù)據(jù)平面中具有大流量的數(shù)據(jù)流對(duì)于多種應(yīng)用（例如，知道流量大小的路由彤守，DoS檢測(cè)和流量工程）來(lái)說(shuō)非常重要诽凌。
然而矾瑰，數(shù)據(jù)平面中的測(cè)量受到線速處理（10-100Gb / s）和交換硬件中有限內(nèi)存需求的限制。
提出了HashPipe酵镜，這是一種使用新興的可編程數(shù)據(jù)平面的heavy hitter檢測(cè)算法碉碉。HashPipe實(shí)現(xiàn)了哈希表的管道，該哈希表保留了重流的計(jì)數(shù)器淮韭，同時(shí)隨著時(shí)間的推移逐出了較輕的計(jì)數(shù)器垢粮。
背景/問(wèn)題：
許多網(wǎng)絡(luò)管理應(yīng)用程序可以從發(fā)現(xiàn)對(duì)鏈路貢獻(xiàn)大量流的流量中受益：例如，減輕鏈路擁塞靠粪，規(guī)劃網(wǎng)絡(luò)容量蜡吧，檢測(cè)網(wǎng)絡(luò)異常和攻擊，或緩存轉(zhuǎn)發(fā)表?xiàng)l目占键。
此外昔善，在較小的時(shí)間尺度上（與流量變化相比較）識(shí)別此類(lèi)“heavy hitter”可以實(shí)現(xiàn)重流的動(dòng)態(tài)路由和動(dòng)態(tài)流量調(diào)度。人們希望始終在網(wǎng)絡(luò)中的所有交換機(jī)上運(yùn)行重流監(jiān)視畔乙，以快速響應(yīng)短期流量變化君仆。
在交換機(jī)中處理數(shù)據(jù)包時(shí)，是否可以識(shí)別屬于高流量的數(shù)據(jù)包牲距，以便交換機(jī)可以對(duì)其進(jìn)行特殊處理返咱？現(xiàn)有的監(jiān)視heavy hitter的方法很難以可接受的開(kāi)銷(xiāo)獲得合理的準(zhǔn)確性。
NetFlow的形式進(jìn)行數(shù)據(jù)包采樣在軟件中處理采樣數(shù)據(jù)包的CPU和帶寬開(kāi)銷(xiāo)使其無(wú)法以足夠高的速率進(jìn)行采樣嗅虏。而另一種方法洛姑，sketch需要大量的內(nèi)存開(kāi)銷(xiāo)來(lái)檢索heavy hitter。
新興的可編程交換機(jī)使我們不僅可以進(jìn)行采樣皮服，哈希和計(jì)數(shù)楞艾，還為在交換機(jī)上運(yùn)行新穎算法提供了機(jī)會(huì)参咙。
當(dāng)在10-100個(gè)端口上以每個(gè)端口10-100 Gbps的線速運(yùn)行時(shí)，可以對(duì)這些交換機(jī)進(jìn)行編程硫眯，以維持多個(gè)數(shù)據(jù)包的狀態(tài)蕴侧，例如，將流標(biāo)識(shí)符作為keys帶著計(jì)數(shù)器两入。
但是交換機(jī)受到保持高分組處理吞吐量的需求的約束：
- 確定性的小時(shí)間預(yù)算（1 ns）净宵，用于在每個(gè)階段處理狀態(tài)和處理數(shù)據(jù)包
- 每個(gè)階段對(duì)內(nèi)存存儲(chǔ)狀態(tài)的訪問(wèn)次數(shù)有限，通常只有一次readmodify-write
- 每個(gè)階段可用的內(nèi)存量有限
- 需要僅將大部分?jǐn)?shù)據(jù)包通過(guò)管道移動(dòng)一次裹纳，以避免停頓和降低吞吐量
解決辦法：
我們提出了HashPipe择葡，該算法可在可編程交換機(jī)的功能和約束范圍內(nèi)以高精度跟蹤最重的k個(gè)流量。
HashPipe在哈希表的流水線中維護(hù)流標(biāo)識(shí)符（“鍵”）和交換機(jī)中的重流計(jì)數(shù)剃氧。
當(dāng)數(shù)據(jù)包散列到流水線第一級(jí)中的某個(gè)位置時(shí)敏储，如果有命中（或空插槽），則將更新（或初始化）其計(jì)數(shù)器朋鞍。如果有遺漏已添，則以現(xiàn)有密鑰為代價(jià)插入新密鑰 。
在所有下游階段滥酥，隨包一起攜帶剛剛收回的物品的密鑰和數(shù)量更舞，在哈希表中查找的與攜帶的密鑰之間，具有較大計(jì)數(shù)的密鑰將保留在哈希表中坎吻，而另一個(gè)密鑰則與數(shù)據(jù)包一起攜帶到下一個(gè)階段缆蝉，或者如果密鑰被攜帶，在最后階段則將從交換機(jī)中完全刪除數(shù)據(jù)包禾怠。
因此返奉，HashPipe使用流水線操作對(duì)哈希表中的多個(gè)位置進(jìn)行采樣，并使用較輕的鍵代替較重的鍵吗氏，從而在有限的可用內(nèi)存中“清除”沉重的鍵芽偏，并且每個(gè)階段僅更新一個(gè)位置。
Hashpipe算法實(shí)現(xiàn)細(xì)節(jié)：
節(jié)省空間：
要跟蹤k個(gè)最重的項(xiàng)目弦讽，節(jié)省空間的方法是使用一個(gè)具有m個(gè)（為O（k））插槽的表污尉，每個(gè)插槽都標(biāo)識(shí)一個(gè)不同的流的密鑰及其計(jì)數(shù)器
當(dāng)數(shù)據(jù)包到達(dá)時(shí)，如果表中還沒(méi)有對(duì)應(yīng)的流往产，并且表中還有剩余空間被碗，則空間節(jié)省功能將插入新的流，計(jì)數(shù)為1仿村。如果表中存在流锐朴，算法將更新相應(yīng)的流計(jì)數(shù)器。但是蔼囊，如果表已滿(mǎn)焚志，并且在表中找不到流衣迷，則該算法將表中具有最小計(jì)數(shù)器值的流條目替換為傳入數(shù)據(jù)包的流，并遞增此最小值計(jì)數(shù)器酱酬。
最小值采樣：
我們要做的是查看隨機(jī)選擇的計(jì)數(shù)器的較小的恒定數(shù)量d的最小值壶谒，而不是整個(gè)表，將每個(gè)數(shù)據(jù)包的最壞情況的存儲(chǔ)器訪問(wèn)次數(shù)限制為較小的固定常數(shù)d膳沽。
算法2中顯示了修改后的版本HashParallel汗菜。
與算法1相比，主要變化在于檢查了一組表插槽（在查找或更新任何鍵時(shí)）挑社，該表插槽現(xiàn)在是通過(guò)對(duì)表哈希進(jìn)行哈希處理而獲得的d個(gè)插槽集合陨界，使用d個(gè)獨(dú)立哈希函數(shù)的傳入密鑰。
實(shí)際上滔灶，我們對(duì)表進(jìn)行采樣以使用幾個(gè)位置來(lái)估計(jì)最小值普碎。但是吼肥，只有d個(gè)插槽的最小值可能會(huì)與整個(gè)m個(gè)插槽表的最小值相距甚遠(yuǎn)录平。最小值的設(shè)定值可能會(huì)影響有用的錯(cuò)誤保證，以節(jié)省空間缀皱。
哈希表的多個(gè)階段：
為了減少對(duì)內(nèi)存的讀取次數(shù)斗这，以方便以線路速率進(jìn)行操作，我們將計(jì)數(shù)器表T拆分為d個(gè)不相交的表啤斗，并且每個(gè)表正好讀取一個(gè)插槽表箭。
由于不同的數(shù)據(jù)包可以同時(shí)訪問(wèn)不同的表，因此該設(shè)計(jì)可以使對(duì)d表的內(nèi)存訪問(wèn)的流水線化钮莲，但是免钻，數(shù)據(jù)包可能需要通過(guò)此流水線兩次：一次確定d個(gè)時(shí)隙中最小值的計(jì)數(shù)器，第二次更新該計(jì)數(shù)器崔拥。
前饋包處理：
現(xiàn)在极舔，我們使用兩個(gè)關(guān)鍵思想來(lái)減輕通過(guò)交換管道多次處理數(shù)據(jù)包的需求。
首先链瓦，跟蹤滾動(dòng)最小值：通過(guò)將計(jì)數(shù)器和密鑰作為包元數(shù)據(jù)在管道中移動(dòng)拆魏，我們跟蹤當(dāng)數(shù)據(jù)包穿過(guò)管道時(shí)到目前為止看到的最小計(jì)數(shù)器值（及其密鑰）。
其次是始終插入第一階段：如果在管道的第一個(gè)階段中找不到傳入密鑰慈俯，則沒(méi)有關(guān)聯(lián)的計(jì)數(shù)器值可與該表中的密鑰進(jìn)行比較渤刃。在這里，我們選擇始終在第一個(gè)階段插入新的流贴膘，并將現(xiàn)有的密鑰和計(jì)數(shù)器逐出數(shù)據(jù)包元數(shù)據(jù)卖子，在該階段之后，分組可以以上述通常的方式跟蹤后續(xù)階段的最小滾動(dòng)刑峡。
其實(shí)整個(gè)HashPipe的結(jié)構(gòu)都可以用圖三的算法表示出來(lái)洋闽。
