網(wǎng)絡(luò)設(shè)備的兩種基本類型

1、網(wǎng)絡(luò)設(shè)備的兩種基本類型 那么網(wǎng)絡(luò)設(shè)備都有些什么性能瓶頸呢？這里， 我們首先要對(duì)網(wǎng)絡(luò)設(shè)備做一個(gè)分類， 因?yàn)?不同的網(wǎng)絡(luò)設(shè)備， 性能瓶頸產(chǎn)生的原因及解決方案都是不同的。 本書的作者將網(wǎng)絡(luò)設(shè)備分為 端節(jié)點(diǎn)和路由器兩種基本類型。端節(jié)點(diǎn)性能瓶頸的產(chǎn)生 下面我們看一下端節(jié)點(diǎn)和路由器的性能瓶頸分別是怎么產(chǎn)生的？ 對(duì)于為通用計(jì)算而設(shè)計(jì)的端節(jié)點(diǎn)來(lái)說(shuō)， 主要的性能瓶頸來(lái)自結(jié)構(gòu)化開銷。 （ 1）為方便軟 件開發(fā)，大多數(shù)操作系統(tǒng)都按照分層原則來(lái)組織， 比如硬件抽象層、資源管理層、 資源分配 及調(diào)度等。（2）為了保護(hù)操作系統(tǒng)不受應(yīng)用程序的破壞，操作系統(tǒng)都實(shí)現(xiàn)了一組保護(hù)機(jī)制。 （3）為適應(yīng)盡可能多的應(yīng)用，核心操作系統(tǒng)的例

2、程（如調(diào)度器、內(nèi)存分配器等）使用一般 機(jī)制來(lái)寫成。軟件分層、 保護(hù)機(jī)制和過(guò)度一般化這三者結(jié)合起來(lái)， 就使得網(wǎng)絡(luò)軟件運(yùn)行很慢， 哪怕是 運(yùn)行在一個(gè)高速處理器上。對(duì)于提供網(wǎng)絡(luò)服務(wù)的服務(wù)器（如 web 服務(wù)器）來(lái)說(shuō)，性能瓶頸還來(lái)自用戶規(guī)模。許多 操作系統(tǒng)使用的是只能支持少量連接的低效的數(shù)據(jù)結(jié)構(gòu)和算法， 而現(xiàn)在一臺(tái)服務(wù)器要求同時(shí) 服務(wù)一百萬(wàn)個(gè)并發(fā)客戶，低效的實(shí)現(xiàn)使其運(yùn)行很慢。路由器性能瓶頸的產(chǎn)生和端節(jié)點(diǎn)不同， 路由器是網(wǎng)絡(luò)專用設(shè)備， 因此路由器內(nèi)部的結(jié)構(gòu)開銷很少。 它只使用一 個(gè)非常輕量級(jí)的操作系統(tǒng)， 以及一個(gè)完全由硬件實(shí)現(xiàn)的轉(zhuǎn)發(fā)路徑。 路由器瓶頸一般由規(guī)模和 服務(wù)引起。規(guī)模主要指鏈路帶寬（流量）和網(wǎng)

3、絡(luò)規(guī)模（網(wǎng)絡(luò)數(shù)量、用戶數(shù)量）。 80 年代到 90 年代之間， 網(wǎng)絡(luò)設(shè)備廠商主要解決這兩個(gè)規(guī)模問(wèn)題， 因?yàn)樵絹?lái)越多的商業(yè)應(yīng)用搬到了網(wǎng)絡(luò)上， 越 來(lái)越多的網(wǎng)絡(luò)加入因特網(wǎng)中。接下來(lái)的十年甚至更長(zhǎng)時(shí)間， 關(guān)注點(diǎn)開始轉(zhuǎn)向?yàn)檫@些網(wǎng)絡(luò)應(yīng)用提供服務(wù)質(zhì)量、 安全性和 可靠性方面的保證， 如實(shí)時(shí)流媒體、 入侵檢測(cè)、內(nèi)容過(guò)濾等。 這些服務(wù)都要求復(fù)雜的網(wǎng)絡(luò)包 處理。高速實(shí)現(xiàn)這些新的服務(wù)是路由器制造商面臨的主要挑戰(zhàn)?，F(xiàn)在，以上挑戰(zhàn)并存，鏈路速率已達(dá)到 40Gbps 甚至更高。解決瓶頸的技術(shù)：網(wǎng)絡(luò)算法學(xué) 如何解決以上瓶頸？本課程會(huì)談及許多具體的技術(shù)， 如減少中斷開銷、 消除拷貝、 時(shí)間 輪等。 但是，我們不能僅停留在這

4、些技術(shù)的表面， 而要去領(lǐng)會(huì)和掌握這些技術(shù)后面更重要的 觀念 -網(wǎng)絡(luò)算法學(xué)，即運(yùn)用系統(tǒng)的方法去組織網(wǎng)絡(luò)實(shí)現(xiàn)。系統(tǒng)方法中一個(gè)重要的觀察是， 我們通?？梢酝ㄟ^(guò)在時(shí)間及空間上移動(dòng)一個(gè)子系統(tǒng)中的 某些功能來(lái)設(shè)計(jì)出高效的子系統(tǒng)。比如，可以將協(xié)議處理從 CPU 轉(zhuǎn)移到網(wǎng)卡，包緩沖區(qū)可 以被預(yù)分配。在某種程度上說(shuō)， 網(wǎng)絡(luò)算法學(xué)的執(zhí)行者是一個(gè)不擇手段的機(jī)會(huì)主義者， 他可以改變游戲 規(guī)則，唯一的約束就是整個(gè)系統(tǒng)提供的功能是滿足用戶需要的?？紤]一下網(wǎng)絡(luò)實(shí)現(xiàn)者面對(duì)的問(wèn)題： 越來(lái)越高的鏈路速度， 越來(lái)越復(fù)雜的處理任務(wù)， 越來(lái) 越大的網(wǎng)絡(luò)規(guī)模，少量的高速內(nèi)存（ cache），比計(jì)算時(shí)間長(zhǎng)得多的訪存延遲。設(shè)計(jì)者必須使 用各

5、種可能的手段（使用硬件、改變系統(tǒng)假設(shè)、設(shè)計(jì)新算法） ，只要能夠解決問(wèn)題。一個(gè)熱身的例子下面我們通過(guò)一個(gè)熱身的例子來(lái)直觀地感受一下網(wǎng)絡(luò)算法學(xué)。有一種常見(jiàn)的攻擊類型 內(nèi)存溢出攻擊，入侵者將惡意代碼放置在數(shù)據(jù)包頭中的某個(gè) 域。如果目標(biāo)計(jì)算機(jī)為該域分配的存儲(chǔ)空間太小， 又沒(méi)有進(jìn)行邊界檢查， 就會(huì)發(fā)生數(shù)據(jù)溢出， 惡意代碼溢出到目標(biāo)機(jī)器的堆棧中。 通過(guò)一些巧妙的設(shè)計(jì)， 入侵者可以使得目標(biāo)機(jī)器去執(zhí)行 惡意代碼。入侵者經(jīng)常使用的域是 HTTP 消息中的 URL 域。我想原因可能是三個(gè)： 一是 Web 應(yīng)用 很普遍，防火墻一般開放端口 80 ；二是 URL 域可以放置任意的字符串，服務(wù)器一般不會(huì)進(jìn) 行有效性檢查

6、；三是很長(zhǎng)的 URL 也很普遍，不太容易引起懷疑。IDS 如何檢測(cè)一個(gè) URL 可能攜帶了惡意代碼呢？通過(guò)觀察發(fā)現(xiàn)包含惡意代碼的 URL 通 常很長(zhǎng)，并且包含大量在 URL 中不常出現(xiàn)的字符，如 #。假定安全分析員以 URL 太長(zhǎng)、并 且字符出現(xiàn)比例異常作為攻擊特征，要求芯片設(shè)計(jì)師設(shè)計(jì)一個(gè)硬件來(lái)對(duì)包含可疑 URL 的包 作標(biāo)記。一個(gè)簡(jiǎn)單的方案檢查 URL 的長(zhǎng)度很簡(jiǎn)單，我們重點(diǎn)研究如何檢測(cè)可疑字符的出現(xiàn)比例。一種簡(jiǎn)單的方法是維護(hù)兩個(gè)長(zhǎng)度為256的數(shù)組T和C,數(shù)組中的每一個(gè)元素對(duì)應(yīng)一個(gè)ASCII 字符。 T 數(shù)組保存各個(gè)字符在一個(gè) URL 中可接受的出現(xiàn)比例，如果某個(gè)字符在一個(gè)URL 中出現(xiàn)的比

7、例超過(guò)了設(shè)定的門限，該分組應(yīng)被標(biāo)記。 C 數(shù)組記錄每個(gè)字符在一個(gè) URL 中出現(xiàn)的次數(shù)。算法分析在分析算法之前， 我們先來(lái)看一下對(duì)這個(gè)硬件有什么性能上的要求。 一個(gè)最基本的要求 是必須來(lái)得及處理按鏈路速率到來(lái)的流量， 這稱為線速處理要求。 線速處理要求在網(wǎng)絡(luò)中是 非常常見(jiàn)的，即一個(gè)分組必須在下一個(gè)分組到來(lái)之前處理完，否則在最壞情況下會(huì)丟包。為滿足線速處理要求， 理想情況下， 芯片對(duì)于每個(gè)掃描的字節(jié)應(yīng)當(dāng)只做少量的操作。 假 定 Ci 加 1 可以在每個(gè)字節(jié)到來(lái)的時(shí)間內(nèi)完成。注意到這個(gè)算法對(duì)數(shù)組有兩次遍歷， 一次是掃描新包前的初始化， 另一次是掃描完 URL 后檢查各個(gè)字符的出現(xiàn)比例是否超限，兩次

8、遍歷至少需要 768 次讀/寫操作（ C 數(shù)組讀、寫 各一次， T 數(shù)組讀一次） ?？紤]最壞情況： 僅包含 HTTP 請(qǐng)求頭的包連續(xù)到來(lái)。 在當(dāng)前 URL 結(jié)束至下一個(gè)包的 URL 開始，只有幾十個(gè)字節(jié)的時(shí)間，每個(gè)字節(jié)的時(shí)間內(nèi)需要完成一百多次的讀/寫操作，這是不可能完成的，即達(dá)不到線速處理的要求。因此，優(yōu)化的關(guān)鍵是減少或消除這兩次遍歷。算法優(yōu)化：取消 URL 結(jié)束后的一次遍歷直觀上看， 在掃描完 URL 后對(duì) C 和 T 數(shù)組的遍歷是不必要的。 因?yàn)樾酒皇且獦?biāo)記數(shù) 據(jù)包中是否有任何字符的出現(xiàn)比例過(guò)高， 并不需要給出究竟是哪些字符超標(biāo)， 所以為什么要 檢查所有的字符呢？一種想法是我們只需跟蹤最

9、高的相對(duì)出現(xiàn)次數(shù)， 看它是否超標(biāo)。 注意， 這里不是跟蹤最 高出現(xiàn)次數(shù)，因?yàn)椴煌址某霈F(xiàn)比例上限是不同的。這樣當(dāng)URL 掃描結(jié)束，處理也完成了。我們看到，該方法消除了一次遍歷，其代價(jià)是每個(gè)字節(jié)時(shí)間內(nèi)的處理增加了。 這個(gè)方案存在什么問(wèn)題呢？利用硬件特性：消除除法運(yùn)算新的算法消除了 URL 掃描結(jié)束后的遍歷，但是掃描每個(gè)字節(jié)時(shí)需要一次除法運(yùn)算。除 法運(yùn)算不管是軟件實(shí)現(xiàn)還是硬件實(shí)現(xiàn)， 都是開銷比較大的。 因此， 這里的問(wèn)題是能否消除這 個(gè)除法運(yùn)算？我們知道有一種特殊的情形， 除法的實(shí)現(xiàn)非常簡(jiǎn)單， 即是除數(shù)為 2 的冪次的情況， 這時(shí) 除法可以用移位來(lái)實(shí)現(xiàn)。然而， Ti 不一定是 2 的冪次。再回到

10、問(wèn)題的開始。 我們認(rèn)為每個(gè)字符的門限值不見(jiàn)得必須是一個(gè)精確的浮點(diǎn)數(shù)，安全分析員不太可能精確地估計(jì)這個(gè)值， 因此完全可以用一個(gè)小于給定值的近似值來(lái)代替。比如，用 1/32 來(lái)代替 1/29 。當(dāng)然這個(gè)改變必須征得安全分析員的同意。當(dāng)做了這樣的改變后，除法運(yùn)算可以轉(zhuǎn)化為簡(jiǎn)單的移位運(yùn)算。比如，若 Ti=1/32 ，則Ci/Ti 只需要將 Ci 向左移 5 位。同時(shí)，數(shù)組 T 可以存放移位的次數(shù)（整數(shù)） ，而不是一個(gè) 分?jǐn)?shù)。改進(jìn)后的處理過(guò)程如下：讀入一個(gè)新字符“i ”后， Ci 加 1，然后左移 Ti 位，若移位后的值大于 Max,更新Max。當(dāng)URL掃描結(jié)束后，如果 MaxL,標(biāo)記分組。大家看看這個(gè)

11、改進(jìn)后的方案，還有什么地方可以改進(jìn)？ 提示：與樸素的方案相比，在每個(gè)字節(jié)的時(shí)間內(nèi)增加了一次讀 Ti 的操作（樸素的方案 對(duì) Ci 分別讀、寫一次） 。目前最快的片上存儲(chǔ)器訪問(wèn)耗時(shí)1-2ns,慢的需要10ns,都比硬件邏輯慢。單個(gè)門電路的延遲在 ps 量級(jí)，移位邏輯不需要太多的門延遲，因此處理瓶頸在于訪存次數(shù)。當(dāng)我們?cè)?提出一種優(yōu)化措施時(shí)，一般不希望引入新的問(wèn)題。問(wèn)題：能否不增加讀 /寫內(nèi)存的次數(shù)呢？利用硬件特性：合并對(duì) T 和 C 的讀操作 方法是使用較長(zhǎng)寬度的字，每個(gè)字中保存 Ci 和 Ti ，比如用 15 比特統(tǒng)計(jì)字符的出現(xiàn) 次數(shù)（可允許32K的URL），用14比特表示移位次數(shù)。需要注意的

12、是，用軟件方法抽取出合并到一個(gè)字中的域很煩人，但用硬件實(shí)現(xiàn)很容易， 只需在寄存器之間合理連線或使用多路復(fù)用器。到目前為止，我們成功地消除了URL掃描結(jié)束后對(duì)數(shù)組 T和C的遍歷，并消除了該方法產(chǎn)生的除法問(wèn)題以及 URL 掃描過(guò)程中多一次訪問(wèn) T 數(shù)組的問(wèn)題。Lazy Evaluation ：消除對(duì) C 的初始化 我們現(xiàn)在還剩下一個(gè)初始化 C 數(shù)組的循環(huán)。注意到，在相鄰兩個(gè) URL 之間只有幾十個(gè)字節(jié)，若以40字節(jié)（UDP頭+IP頭）計(jì)算，在該空閑時(shí)間內(nèi)初始化256字節(jié)的數(shù)組，平均每個(gè)字節(jié)時(shí)間需要完成 6 次以上的操作（ 256/40 > 6）。大家考慮一下這個(gè)問(wèn)題：我們是否有必要在每開始一

13、個(gè)新的數(shù)據(jù)包時(shí)，清除整個(gè)C 數(shù)組？比如，一個(gè) URL 可能只有幾十種字符，清除那些未使用的字符計(jì)數(shù)器是否多余？從道理上說(shuō)，芯片不需要初始化 Ci ，直到一個(gè)新的數(shù)據(jù)包需要使用該 Ci 時(shí)（第一次 訪問(wèn)該 Ci ）。也就是說(shuō)，從道理上我們可以僅在需要使用一個(gè)字符計(jì)數(shù)器時(shí)再去清除該計(jì) 數(shù)器。這種將工作拖到不得不做的時(shí)候才去做（寄希望于可能不要做）的方法叫做lazyevaluation 。如果以上想法可以實(shí)現(xiàn)，那么當(dāng)芯片掃描到一個(gè)新的URL、并且第一次遇到字符”i”時(shí)，設(shè)置Ci=1，此后再掃描到字符”i”時(shí)，只需將Ci加1。但是，芯片如何知道它是第一次看到字符“i”呢？換句話說(shuō)，當(dāng)芯片根據(jù) ”i”找

14、到Ci時(shí)，它怎么知道這個(gè)計(jì)數(shù)器統(tǒng)計(jì)的是當(dāng)前URL中的”，還是之前某個(gè)URL中的”？為此，我們可以給每個(gè)數(shù)據(jù)包賦一個(gè)代號(hào)，該數(shù)據(jù)包使用的計(jì)數(shù)器具有與數(shù)據(jù)包相同的代號(hào)。 這么做有問(wèn)題嗎？使用長(zhǎng)周期的清洗循環(huán)清理 C為避免 g 回繞產(chǎn)生歧義， 所有未被使用的計(jì)數(shù)器在其世代號(hào)發(fā)生回繞前必須被清除。也就是說(shuō)，芯片需要有一個(gè)主動(dòng)清洗的循環(huán)，依次讀入數(shù)組的表項(xiàng)，將那些代號(hào)過(guò)時(shí)的Ci置 0。為保證正確性，每處理 8 個(gè)分組，芯片必須執(zhí)行完一次完整的清洗循環(huán)。假定每個(gè)分組有 40 個(gè)非 URL 字節(jié)， 8 個(gè)分組就有 320 個(gè)非 URL 字節(jié)，這些時(shí)間完全 夠用來(lái)初始化 256 個(gè)元素的數(shù)組（每個(gè)字節(jié)完成一次

15、讀和一次寫操作）。如果需要的話，可以通過(guò)增大世代號(hào)的長(zhǎng)度來(lái)獲得更寬松的處理時(shí)間，代價(jià)是增大了一點(diǎn)點(diǎn)數(shù)組的存儲(chǔ)空間。改進(jìn)的方法如下。這是最終的改進(jìn)方案。分析：每個(gè)表項(xiàng)中增加 3比特的世代號(hào)后， 減少了初始化處理的周期數(shù) （用存儲(chǔ)換計(jì)算） 。 在 URL 字節(jié)的處理過(guò)程中，增加的初始化檢查（對(duì) Gi 的檢查）不會(huì)增加訪存（三個(gè)域一 次讀入），只是增加了一些處理邏輯（判斷 Gi）。另外，芯片需要2個(gè)寄存器用來(lái)保存 g和 s,增加了一點(diǎn)點(diǎn)空間開銷。比較一下最初的簡(jiǎn)單方案（普通人的方案）和最終的方案（技術(shù)專家的方案），差距一目了然。 如果抽去中間的過(guò)程, 直接給出最終方案, 估計(jì)很少有人能夠理解為什么要

16、這么設(shè) 計(jì)？設(shè)計(jì)者是怎么想到這個(gè)方案的？通過(guò)這個(gè)例子我想說(shuō)的是, 我們要學(xué)會(huì)的就是這樣一種分析問(wèn)題和解決問(wèn)題的方法,怎樣運(yùn)用我們學(xué)過(guò)的計(jì)算機(jī)知識(shí), 不斷地去發(fā)現(xiàn)實(shí)現(xiàn)中的問(wèn)題, 不斷地求精, 一步一步得到一 個(gè)最好的方案。 當(dāng)然光靠這門課不能讓你們獲得這種能力, 但你們要有這個(gè)目標(biāo), 就是要把 自己培養(yǎng)成有這種能力的人。網(wǎng)絡(luò)算法學(xué)的特性 以上例子說(shuō)明了網(wǎng)絡(luò)算法學(xué)的三個(gè)重要方面。（ 1）網(wǎng)絡(luò)算法學(xué)是跨學(xué)科的 這個(gè)例子用到了算法的知識(shí)和硬件的知識(shí)。 面對(duì)高速數(shù)據(jù)包的處理壓力, 不使用硬件是 很困難的。以上例子利用了硬件的好幾個(gè)特性： 256 個(gè)元素的數(shù)組可以放入片上存儲(chǔ),移位 比除法簡(jiǎn)單,內(nèi)存訪問(wèn)是瓶頸,任意長(zhǎng)度的字寬是容易做到的,增加幾個(gè)寄存器是可行的, 很容易增加一些邏輯將 URL 處理和初始化結(jié)合起來(lái)。對(duì)于不熟悉硬件設(shè)計(jì)的讀者來(lái)說(shuō),無(wú)法理解這些設(shè)計(jì),更想不到這些設(shè)計(jì)。因此, 跨學(xué)科的思維有助于產(chǎn)生出最好的設(shè)計(jì)。（ 2）網(wǎng)絡(luò)算法學(xué)肯定系統(tǒng)思維的重要性放寬對(duì)門限的要求, 允許用 2 的冪次來(lái)表示門限, 簡(jiǎn)化了硬件設(shè)計(jì)。 放寬要求和將工作 從一個(gè)子系統(tǒng)遷移到另一個(gè)子系統(tǒng)是極其常見(jiàn)的系統(tǒng)技術(shù), 但并不被當(dāng)今大學(xué)的教育實(shí)踐所 支持。在當(dāng)今的大學(xué)教育中,算法、操作系統(tǒng)、網(wǎng)絡(luò)被放在不同的課程中孤立地教,這會(huì)鼓 勵(lì)那種“黑盒思維” ,而不是整體或系統(tǒng)思維,不能得到全局