摘要：

當(dāng)網(wǎng)絡(luò)出現(xiàn)擁塞，掃描攻擊，DDoS攻擊等問(wèn)題時(shí)，測(cè)量比平常重要得多。 在這種情況下，包括可用帶寬，數(shù)據(jù)包速率和流量大小分布在內(nèi)的流量特性將發(fā)生巨大變化，從而嚴(yán)重降低測(cè)量性能。

為了解決這個(gè)問(wèn)題，我們提出了Elastic sketch。 它適應(yīng)當(dāng)前的流量特征，并且它對(duì)于測(cè)量任務(wù)和平臺(tái)是通用的。

背景/問(wèn)題：

由于基于sketch的解決方案與采樣方法相比具有更高的準(zhǔn)確性，因此已經(jīng)在網(wǎng)絡(luò)測(cè)量中得到了廣泛接受，現(xiàn)有的測(cè)量解決方案主要集中在精度，速度和內(nèi)存使用之間的良好權(quán)衡。

盡管現(xiàn)有工作做出了巨大貢獻(xiàn)，但它們并沒(méi)有關(guān)注一個(gè)基本需求——無(wú)論流量特性如何變化，都可以實(shí)現(xiàn)準(zhǔn)確的網(wǎng)絡(luò)測(cè)量。當(dāng)網(wǎng)絡(luò)出現(xiàn)問(wèn)題，例如網(wǎng)絡(luò)擁塞，掃描和DDoS攻擊時(shí)，流量特性會(huì)急劇變化，從而大大降低測(cè)量性能，因此這種情況下的測(cè)量尤為重要。

因此，當(dāng)流量特性變化很大時(shí)，需要實(shí)現(xiàn)精確的網(wǎng)絡(luò)測(cè)量。

第一個(gè)流量特征是可用帶寬，第二個(gè)特征是數(shù)據(jù)包到達(dá)率，第三個(gè)特征是流量大小分布。

這要求sketch具有彈性：適應(yīng)帶寬，包速率和流大小分布。

除此之外，測(cè)量還有其他三個(gè)要求：通用、快速、準(zhǔn)確。

首先，每個(gè)測(cè)量節(jié)點(diǎn)通常必須執(zhí)行多個(gè)任務(wù)。如果我們?yōu)槊總€(gè)任務(wù)構(gòu)建一個(gè)數(shù)據(jù)結(jié)構(gòu)，則處理每個(gè)傳入數(shù)據(jù)包都需要更新所有數(shù)據(jù)結(jié)構(gòu)，這既浪費(fèi)時(shí)間又占用空間。因此，需要一種用于所有任務(wù)的通用數(shù)據(jù)結(jié)構(gòu)。

其次，要快速，每個(gè)數(shù)據(jù)包的處理時(shí)間應(yīng)小而恒定。

第三，準(zhǔn)確意味著在使用給定數(shù)量的內(nèi)存時(shí)錯(cuò)誤率應(yīng)該足夠小。

在所有現(xiàn)有解決方案中，沒(méi)有解決方案具有彈性。

解決辦法：

提出了一種新穎的sketch，即Elastic sketch，它由兩部分組成：heavy part和light part。

我們提出了一種分離技術(shù)，稱(chēng)為“種族歧視”，以使大象流在heavy part流動(dòng)，而老鼠在light part流動(dòng)。

為了使其具有“彈性”，我們執(zhí)行以下操作：

• 為了適應(yīng)帶寬，我們提出了壓縮和合并sketch的算法。將sketch壓縮為合適的大小以適合當(dāng)前的可用帶寬，使用服務(wù)器合并sketch并減少帶寬使用。

  
  
• 當(dāng)數(shù)據(jù)包速率較高時(shí)，改變處理方法：每個(gè)數(shù)據(jù)包僅訪問(wèn)大部分以專(zhuān)門(mén)記錄大象流的信息，而丟棄鼠標(biāo)流的信息，這樣可以以合理的精度下降為代價(jià)實(shí)現(xiàn)更快的處理速度。
• 隨著大象流的數(shù)量變化并且事先未知，我們提出了一種算法來(lái)動(dòng)態(tài)增加heavy part的內(nèi)存大小

為了使我們的解決方案“通用”，我們執(zhí)行以下操作：

• 為了進(jìn)行一般的測(cè)量任務(wù)，保留了每個(gè)數(shù)據(jù)包的所有必要信息，但丟棄了鼠流的ID，這是基于我們的觀察——鼠流的ID占用內(nèi)存，但實(shí)際上沒(méi)有用。
• 為了在平臺(tái)方面具有通用性，我們提出了Elastic sketch的軟件和硬件版本，以使我們的sketch易于在軟件和硬件平臺(tái)上實(shí)施。