第三章實現(xiàn)原則

1、標題頁本章介紹作者歸納的 15 條實現(xiàn)原則。這些實現(xiàn)原則是從比較成功的協(xié)議實 現(xiàn)中歸納出來的。 其實許多實現(xiàn)者已經(jīng)有意無意地使用了這些原則， 本章只是更 清楚地將它們表達出來，以使實現(xiàn)者可以更加主動地去運用它們。3.1 運用實現(xiàn)原則的例子：更新 TCAM下面用一個例子來說明為什么要使用原則。使用 TCAM 進行 IP 地址查找圖 3.4是 TCAM 用于 IP 地址查找的例子。 IP 地址前綴是長度為 32比特的三 態(tài)字符串，通配符都在字符串的尾部。我們稍微改變一下表示法，使得* 表示任意數(shù)量的通配符。按照 TCAM 的工作原理以及最長前綴匹配的要求， TCAM 中的地址前綴必 須按照前綴長度

2、從大到小的順序排列。路由表是動態(tài)變化的，如何在 TCAM 中添加或刪除一條地址前綴，與此同 時仍然保持前綴長度從大到小的排列順序？假定在圖3.4的TCAM中需要添加一條新的前綴11*。假定TCAM是向上擴 展空間的，最樸素的方法是在長度為 2的前綴表項中插入前綴 11*，比如插在前 綴 0*的前面，為此，需將前綴 10*至前綴 010001*整體向上移動一個位置。對于 包含大量路由表項的路由器來說，這種更新的速度太慢了。有沒有快一點的方法呢？我們再來看一下圖 3.4的前綴排列方法：長度相同 的前綴排列在一起， 按照從長到短的順序排列， 相同長度的前綴還按照大小進行 了排序。事實上，相同長度前綴

3、的順序?qū)τ?TCAM 執(zhí)行最長前綴匹配不是必須的， 因為一個 IP 地址不可能同時匹配兩個相同長度的前綴。我們只需要按照前綴長 度進行排序，并不需要相同長度前綴之間排序， 因此這是一個可以利用的自由度。理解并利用自由度（ 1 ）利用該自由度，我們可將 11*插入到 00*和 111*之間。當然，如果為此將 111* 及以上前綴向上移動一個位置， 則不會有多大優(yōu)化的效果。 我們的想法是將 111* 移出，將 11*插入 1 1 1 *的位置，然后再為 111*尋找一個插入位置。 盡管這個問題 和原來的差不多，仍然要向 TCAM 中插入一條前綴，但是問題的規(guī)模縮小了一 點。理解并利用自由度（ 2）

4、我們可以將這個方法推廣：。顯然我們可以采用遞歸的思想來設計一個 算法。使用算法技術(shù) 采用遞歸實現(xiàn)的時候展開遞歸：。如果每一種長度的前綴都有（即最壞情況），需要（32-i）次訪存。對于較小 的i，訪存次數(shù)接近32。這個算法已經(jīng)比樸素的算法好了很多，但是不是最好了 呢？還能減小最壞情況下的訪存次數(shù)嗎？（想一想）我們再來看這張圖，這張圖假設空閑空間在 TCAM 的頂部，實際上空閑空 間可以放在 TCAM 的任何地方，因此空閑空間的位置也是一個設計自由度。進一步利用自由度利用這個自由度，可以將空閑空間放在中間，比如放在長度為 16 的前綴項 后面，這時最壞情況下的訪存次數(shù)可以減少一半。當然，空閑空間的

5、數(shù)量也可以是一個自由度，可以進一步減少最壞情況下的 訪存次數(shù)。除了空閑空間的位置及數(shù)量之外，還有沒有可以利用的自由度了呢？提示： 長的前綴是否一定要出現(xiàn)在短的前綴之前？比如，010*能否放在 111001*之前？完全可以，因為不可能有一個地址會同時匹配這兩項。一個更復雜的自由度是，“如果i>j，那么長度為i的前綴必須出現(xiàn)在長度為 j 的前綴之前”，這是一個充分條件，但不是必要的。一個不那么嚴格的要求是，“如果兩個前綴P和Q可能匹配同一個地址，且 P比Q長，那么P必須出現(xiàn)在 Q 之前”。這樣修改規(guī)范后，可以進一步減少最壞情況下的訪存次數(shù)。缺點是提 高了復雜度。盡管以這么復雜的方法來減少訪存

6、次數(shù)有點不劃算， 但它指出了一個重要的 原則，即放寬要求。 我們經(jīng)常將一個大的問題劃分為較小的子問題， 然后將子問 題及相關的規(guī)范交由相關人員去解決。比如， TCAM 的硬件設計人員可能將更 新問題交給寫微代碼的人去完成， 要求將長的前綴放在短前綴的前面。 但是這個 規(guī)范可能不是解決原始問題的唯一方法，改變規(guī)范（ P3 放寬要求）可能產(chǎn)生更 有效的解決方案。 當然，這需要有具有好奇心和自信的設計人員， 他理解整個大 問題，并且足夠勇敢來提出危險的問題。這個例子其實是告訴我們，要去尋找和利用自由度來優(yōu)化實現(xiàn)。3.2 算法 vs 算法學如果認為這個例子基本上是算法層面上的，不要求系統(tǒng)思維，那么下面

7、再舉 一個例子來說明算法與算法學的差異。舉例：安全物證問題假設一個入侵檢測系統(tǒng)通過統(tǒng)計流量來檢測異常節(jié)點， 比如在一個測量周期 內(nèi)發(fā)現(xiàn)一個節(jié)點向網(wǎng)絡中的不同機器發(fā)送了 10 萬個包，就確定這個節(jié)點在進行 端口掃描攻擊。 當判定某個節(jié)點為攻擊源時， 要將該節(jié)點在測量周期內(nèi)發(fā)送的包 寫入安全物證日志，供管理員進一步分析。如何檢測攻擊不是我們要討論的，我們關心的是當判定某個節(jié)點為攻擊源 時，如何得到它已經(jīng)發(fā)送過的那些包。解決方案為實現(xiàn)此目的，我們維護一個包隊列，當一個數(shù)據(jù)包被轉(zhuǎn)發(fā)時，路由器將該 包放入隊頭。為限制隊列的長度（路由器的內(nèi)存是有限的） ，當隊列滿時，刪除 隊尾的包。該方案的主要困難是，當

8、檢測到一個可疑流時，該流已經(jīng)有大量的數(shù)據(jù)包在 隊列中了， 并且和大量其它的包混在一起。 如何高效地從隊列中找到屬于可疑流 的所有包？最相素的方法是順序搜索隊列， 這顯然非常低效。 我們一般會采用什么方法， 快速找到流 F 的數(shù)據(jù)包呢？教科書上的算法教科書上的算法會構(gòu)造某個索引結(jié)構(gòu)來快速搜索流 ID 。比如，我們可以維護 一個流ID的哈希表。但是該算法仍有問題。它需要額外的空間來維護哈希表和指針列表，而對于 高速實現(xiàn)來說存儲空間是非常寶貴的。 它還增加了包處理的復雜度， 需要維護哈 希表。這個算法的問題在哪里？就是我們潛意識里假設每一個流都有可能是可疑 流，因此，每一個包到來時都將其分到相應的流

9、中。這樣，一旦某個流被認定是 可疑流，立即就可以得到屬于該流的所有數(shù)據(jù)包。但事實上，可疑流只是少數(shù)， 這里面我們做了許多無用的處理， 將屬于正常流的包也都組織在哈希表中了。 比 如，10萬個流中只有一個流是異常的，但我們將 10 萬個流的包都做了歸類，這 是顯而易見的浪費。那么我們怎么可以避免做無用功呢？聯(lián)想到我們前面舉過的例子 （檢測異常URL）,我們可以采用推遲計算來解決這個問題。系統(tǒng)的解決方案 基本思想：將判斷一個包是否屬于可疑流這件事情，拖到不得不做（發(fā)現(xiàn)可 疑流，且包將移出隊列）時再去做。什么時候不得不做？（ 1）發(fā)現(xiàn)了可疑流；（2）數(shù)據(jù)包將移出隊列令路由器轉(zhuǎn)發(fā)包時統(tǒng)計每個流（節(jié)點）

10、發(fā)送的包數(shù)。當流 F 發(fā)送的包數(shù)超過一個閾值（如10萬）時，將流F添加到可疑節(jié)點列表中。當可疑節(jié)點列表非空 且隊列滿時， 每當往隊列中添加一個包， 就從隊尾中移出一個包， 判斷該包是否 屬于F。若屬于F,將該包（或指針）拷貝到物證日志中；若否，將該包丟棄。該方案不需要維護哈希表和指針列表，節(jié)省了大量的存儲空間和計算開銷。3.3 十五條設計原則第一章的例子（設計一個檢測異常 URL 的芯片）和前面這兩個例子給了我 們有關網(wǎng)絡算法學的一些初步體驗， 下面介紹作者歸納的 15條原則，這 15條原 則我們會不斷地使用。這 15 條原則可以分為三類：1）系統(tǒng)原則：第 1-5 條原則利用了系統(tǒng)思想，它將系

11、統(tǒng)看成是由子系統(tǒng)構(gòu) 成，而不是一個黑盒子。2）兼顧模塊化和效率：第 6-10 條原則允許保留復雜系統(tǒng)的模塊化，與此同 時給出提高性能的方法。3）加速：第 11-15 條原則提出了加速某個關鍵功能的技術(shù)（僅考慮該功能 本身）。每條原則會用一個例子來說明，具體細節(jié)將在后續(xù)章節(jié)中討論。P1:避免常見情形中的明顯浪費在一個系統(tǒng)中，在一些特殊的操作序列中可能存在資源浪費。如果這些模式 經(jīng)常出現(xiàn)，就有必要去除這個浪費，這樣可以從整體上降低系統(tǒng)的開銷。編譯器的例子:消除重復的子表達式。經(jīng)典的網(wǎng)絡例子:操作系統(tǒng)和用戶空間之間多次數(shù)據(jù)包拷貝（第五章介紹） 。 這條原則看起來容易做起來難，最難的是如何發(fā)現(xiàn)明顯的浪

12、費。這里，每一 步操作孤立地來看沒有浪費， 是由于特殊的操作序列導致了浪費。 顯然，暴露的 上下文越大，越可能發(fā)現(xiàn)產(chǎn)生浪費的操作序列，因而這里需要系統(tǒng)思維。P3:放寬系統(tǒng)要求當一個系統(tǒng)從上到下進行設計時，先將功能在子系統(tǒng)間劃分。在確定了子系 統(tǒng)的需求和接口后， 再設計每一個子系統(tǒng)。 當遇到實現(xiàn)困難時， 有些方面的要求 要改變。如圖 3.8所示，一個系統(tǒng)由兩個子系統(tǒng)組成，子系統(tǒng) 2 對子系統(tǒng) 1 的實現(xiàn)要 求稱為規(guī)范S。如果子系統(tǒng)1實現(xiàn)困難，有時可以降低對其的實現(xiàn)要求，要求子 系統(tǒng) 1 遵循較為寬松的規(guī)范 W。在第 1 章的例子中，由于設計除法電路（ subsystem 1）比較復雜，改用移位

13、代替除法，也就是放寬了子系統(tǒng)1的實現(xiàn)規(guī)范（S->W）:子系統(tǒng)1只需實現(xiàn)移位 操作而不是任意的除法操作。其代價是子系統(tǒng) 2 必須遵循更強的特性（ P->Q）： 門限須用 2 的冪次表示，而不是一個任意的浮點數(shù)。P3a：犧牲確定性換時間超級節(jié)點的檢測：確定性的方法是統(tǒng)計以每一個節(jié)點作為源（或目的）的數(shù) 據(jù)包數(shù)量，這需要檢查每個包的源地址（或目的地址）進行統(tǒng)計，這在高速網(wǎng)絡 中是做不到的。 隨機化方法是每隔一定數(shù)量的包統(tǒng)計一次， 雖然不能保證百分之 百正確，但在很大概率上是正確的。P3b:犧牲精度換時間圖像壓縮是一種很耗時的操作，對于實時視頻要求壓縮速度很快。離散余弦 變換可將信號能量集

14、中在少數(shù)幾個變換系數(shù)上， 然后只需對主要的變換系數(shù)進行 量化編碼，達到快速壓縮的目的。但是圖像質(zhì)量（精度）會受到一些影響。P3c：在空間中移動計算在空間中移動計算是指將計算從一個子系統(tǒng)移動到另一個子系統(tǒng) （注意和前 兩條原則的不同）。比如，數(shù)據(jù)包分片會影響路由器的吞吐量， IPv6 將分片的功 能從路由器移到了源節(jié)點。為此，源節(jié)點主動探測端到端路徑上的 MTU ，確定 合適的分組大小， 路由器不再提供分片的功能。 這樣就簡化了路由器的實現(xiàn)。 當 然，這里的移動已經(jīng)超出了一個網(wǎng)絡設備的限制， 是在整個網(wǎng)絡中的移動 （如果 將網(wǎng)絡看成一個系統(tǒng)，則路由器、主機就是子系統(tǒng)） 。P4:利用系統(tǒng)組件系統(tǒng)設

15、計采用黑盒視圖，就是將系統(tǒng)分解為若干子系統(tǒng)，然后獨立地設計每 一個子系統(tǒng)， 而不去關心其它子系統(tǒng)的內(nèi)部細節(jié)。 盡管這種自頂向下的方法具有 很好的模塊化， 但實際上，性能關鍵的組件在構(gòu)建時通常部分地采用 “自底向上” 的方法構(gòu)建。比如，要在一個硬件上設計算法，通常要讓算法適應硬件的特性， 而不是讓硬件來適應算法。P4b:用空間換速度一個顯而易見的技術(shù)是用較大的空間來減少計算時間， 比如將函數(shù)計算變?yōu)?查表。一個不那么顯而易見的技術(shù)是用較小的空間來提高速度。比如，把一個很大 的數(shù)據(jù)結(jié)構(gòu)壓縮到可以放入cache,或者大部分可以放入cache，可以極大地提升 系統(tǒng)速度。當一個表的規(guī)模很大時，該技術(shù)特別

16、有效。有人可能會問，空間和時間都節(jié)省了，怎么會有這樣的好事？事實上，計算 復雜度是增加的。比如，訪問壓縮的數(shù)據(jù)結(jié)構(gòu)，其處理復雜度是提高的。但由于 現(xiàn)代處理器的計算速度比訪存速度快得多得多，在多核處理器上這個差距更大。 在這種情況下， 適當增加計算復雜度并不會使處理器成為瓶頸， 卻因為提升了訪 存速度使得系統(tǒng)整體性能得到提升。 這是實踐中用得很多的一種優(yōu)化技術(shù)。 這也 啟示我們， 在優(yōu)化系統(tǒng)時一定要搞清楚瓶頸在什么地方， 如果計算不是瓶頸， 那么減少計算并不能提高系統(tǒng)速度如果 P4 原則使用過度，系統(tǒng)的模塊化將受到損害。為此，需要注意兩個問 題：（1）如果我們利用其它系統(tǒng)特性只是為了提高性能，那

17、么對那些系統(tǒng)特性 的改變應當只影響性能，不影響正確性。（2）我們僅對確認為是系統(tǒng)瓶頸的組件運用該技術(shù)。 以上表明，對系統(tǒng)的優(yōu)化要有一定的度，不是越多越好。對系統(tǒng)修改越多， 可能產(chǎn)生的不可預知的相互作用就會增多， 可能會對系統(tǒng)的正確性產(chǎn)生影響， 所 以應當只對系統(tǒng)做最小的修改（不提倡大刀闊斧的改） 。P5:增加硬件提高性能當所有的方法都不奏效時， 增加硬件（如使用更快的處理器、 存儲器、 總線、 鏈路等）可能是更簡單和有效的方法。然而，硬件畢竟成本比較高，即使需要增 加硬件，我們也希望只增加最少的硬件。 這就要求充分挖掘軟件的潛力， 把軟件 的性能做得極至。隨著處理器的速度越來越高， 存儲容量越

18、來越大， 特別是多核處理器的出現(xiàn)， 我們發(fā)現(xiàn)軟件算法設計得好的話， 也是可以運行得很快的。 因此，一種比較理想 的情況是，用軟件實現(xiàn)關鍵的算法， 然后通過處理器的升級自然獲得速度的提升。 當然這不是一件輕而易舉的事。將功能在硬件和軟件之間劃分是一門藝術(shù)。 一般認為， 硬件（不包括處理器） 缺乏靈活性（不容易增加新的功能） ，且設計成本高、周期長，適合完成較簡單 的、較固定的功能。 軟件靈活性好，可以很容易地移植到新的、 更快的處理器上， 獲得性能提升。但是動態(tài)可重構(gòu)技術(shù)的出現(xiàn)使得這種界線在逐漸模糊，利用動態(tài)可重構(gòu)FPGA 實現(xiàn)的系統(tǒng)，既有硬件的執(zhí)行速度，又有軟件的可編程性，可以執(zhí)行復雜 的功能

19、（可重構(gòu)處理器） ，設計工具的出現(xiàn)也使得硬件設計周期大大縮短了。當 然現(xiàn)在用 FPGA 構(gòu)造系統(tǒng)還比較貴，成本可能會是一個考慮的因素?？傊?，在是否增加硬件、增加什么硬件方面，我們的決策是隨著技術(shù)的發(fā)展 而變化的。以下特殊的硬件技術(shù)通常用于網(wǎng)絡 ASIC 芯片中。P6:用高效的定制例程替換低效的通用例程通用性和高性能通常是一對矛盾。通用性要求兼顧大多數(shù)情形，一般來說就 不會針對某種情形進行特殊設計。所以，一個“放之四海皆宜”的東西一定不是 最高效的。比如，操作系統(tǒng)的cache替換策略是LRU，將最長時間未被訪問的數(shù)據(jù)記錄替換出去，這么做符合一般的程序運行模式（局部性原理） 。然而，考慮一個查 詢

20、處理例程， 它在處理一個數(shù)據(jù)庫查詢請求時， 需要依次地處理一系列的數(shù)據(jù)庫 記錄。在這種情形下， 最近使用過的數(shù)據(jù)庫記錄恰恰是最不會被再次訪問的， 因 此應當選擇這樣的記錄替換出去。 正因為如此， 許多數(shù)據(jù)庫應用都用定制的緩存 例程替換了操作系統(tǒng)的緩存例程。為避免代碼膨脹，最好只對關鍵的例程進行定制化。P7:避免不必要的一般性 設計抽象的、一般性的子系統(tǒng)可能導致不必要的或者很少使用的特性。我們 可以移除一些不必要的特性來提高性能， 當然這要求例程的使用者能夠接受該限 制。P8:不要受參考實現(xiàn)的束縛 我們實現(xiàn)一個協(xié)議或系統(tǒng)時，都要遵循相應的規(guī)范。規(guī)范是解釋性的，主要 解釋概念、功能、流程等，并不包

21、括實現(xiàn)。規(guī)范應當使用規(guī)范語言來書寫，但是 因為規(guī)范語言用得不普遍，許多規(guī)范會用命令式語言（如 C 語言）給出，即參 考實現(xiàn)。這些參考實現(xiàn)給出了如何實現(xiàn)功能的代碼。這會帶來兩個副作用，一是描述過于詳細（規(guī)范應當只是說明要做什么，不 應包括怎么做），二是實現(xiàn)者可能直接將參考實現(xiàn)代碼拷貝到自己的系統(tǒng)中。但 是，參考實現(xiàn)代碼只是為了解釋概念， 并不關注效率， 因此直接使用參考實現(xiàn)會 非常低效。P9 和 P10:這里暫不舉例（沒有找到可以三言兩語講清楚的例子） ，下一章結(jié)合具體的 例子再解釋。P11:優(yōu)化預期情形 盡管系統(tǒng)可能會呈現(xiàn)出很多種行為，但是大部分情況下，系統(tǒng)的行為是可預 期的。比如，一個設計良

22、好的系統(tǒng)大部分時間工作在無故障的狀態(tài)； 網(wǎng)絡中的數(shù) 據(jù)包大部分情況是按序到達的， 并且沒有出錯。 我們有必要去優(yōu)化這些常見的情 形，哪怕使得非預期情形的處理變得低效。優(yōu)化常見情形的方法通常稱為啟發(fā)式方法。啟發(fā)式方法一般不被理論家待 見，他們更傾向于那些能夠用平均指標或最壞指標精確量化的機制。 然而，在實 際的計算機系統(tǒng)中，啟發(fā)式方法被大量使用。 （性能才是硬道理）確定常見情形主要依靠設計人員的直覺， 也可以通過測量工具來發(fā)現(xiàn)。 通常， 每個數(shù)據(jù)包都要進行的操作可視為常見情形。P12：增加或利用狀態(tài) 如果一個操作的代價很高，可以考慮維護額外的（冗余的）狀態(tài)來加速該操 作。數(shù)據(jù)庫中的一個典型例子是

23、使用輔助索引。比如，銀行記錄可能使用客戶的 身份證號作為主鍵進行存儲和查找，但是很多時候需要根據(jù)客戶名字進行查詢。 為了加快這種操作，需要利用客戶名字建立另外一個索引（如哈希表、B-樹）。維護額外的狀態(tài)意味著當狀態(tài)有變化的時候，額外的狀態(tài)也要更新。有時候可以不增加新的狀態(tài)， 而是利用已有的狀態(tài)， 這種技術(shù)稱為增量計算。 比如，在計算 IP 頭檢驗時，頭部只有幾個域有變化，可以進行增量計算（不需 要對所有的域計算檢查和） 。P13:優(yōu)化自由度知道哪些變量在我們的控制之下，對于我們進行系統(tǒng)優(yōu)化是很有幫助的。我 們的問題就變成了: 優(yōu)化這些變量以最大化性能。 在這里變量就是自由度， 就是 可以由我們

24、改變的因素。使用多分支trie優(yōu)化IP地址查找就是一個例子。這里有兩個自由度：（1）不 同層的步長（檢查的前綴位數(shù)）可以不同； （ 2）每一層上檢查幾個比特可以通過 動態(tài)規(guī)劃來確定（對于給定的吞吐量，最小化內(nèi)存的需求） 。P15:利用算法技術(shù)構(gòu)造高效的數(shù)據(jù)結(jié)構(gòu)在有些情形中，高效的算法肯定可以極大地提高系統(tǒng)的性能。 但是必須注意， 在任何算法問題成為瓶頸前，需要先運用 P 1 P 1 4原則對系統(tǒng)進行優(yōu)化。換句話 說，在其它問題沒有解決前，算法通常不是瓶頸。因此我們在科研實踐中，通常 先考慮數(shù)據(jù)路徑上其它方面的優(yōu)化。 在所有其它問題都解決后， 剩下的才是算法 問題。經(jīng)常有學生覺得，不做算法就不算

25、做研究，做的工作就沒有技術(shù)含量。事實 上，真正的高手解決問題往往是四兩撥千斤， 用最少的修改把問題解決好。 比如， 通過改變幾行代碼的順序就明顯提高系統(tǒng)性能 （只是這樣的工作寫起論文來不如 算法漂亮）。在系統(tǒng)領域，簡潔優(yōu)雅的解決方案最受高水平會議的青睞，因為這 樣的工作離實用最接近。 所以我們在做系統(tǒng)優(yōu)化時， 遵循的一個原則是修改越少 越好；在達到相同效果的前提下， 方法越簡單越好。 這也是操作系統(tǒng)中很少用復 雜算法的原因，太復雜的算法會影響系統(tǒng)的穩(wěn)定性和可靠性。算法方法包括使用標準的數(shù)據(jù)結(jié)構(gòu)， 以及一般的算法技術(shù)， 如分治和隨機化。 然而，算法設計者必須做好這樣的心理準備， 就是其設計的算法

26、可能隨著系統(tǒng)結(jié) 構(gòu)和技術(shù)的變化而被淘汰。 真正的技術(shù)突破可能來自算法思維的運用， 而不僅僅 是重用已有的算法。3.4 一些警告在運用原則前，必須理解重要的性能指標，確定系統(tǒng)瓶頸。在完成改進后， 必須通過實驗來確認改進的效果。下面用兩個例子進行說明。案例一：減少網(wǎng)頁下載時間在圖3.8中，web客戶欲從服務器獲取內(nèi)嵌有圖像的一個網(wǎng)頁。典型地，客 戶先發(fā)送對網(wǎng)頁的GET請求，然后針對內(nèi)嵌的每個圖像分別發(fā)送 GET請求。對原則P1(消除明顯的浪費)的自然運用是：為什么服務器不自動將圖像和 網(wǎng)頁一起發(fā)送給客戶，而要等待客戶的請求呢？這應當可以減少網(wǎng)頁的下載延 遲。為了測試這個猜想， 作者修改了服務器軟件

27、， 令服務器自動發(fā)送圖像給客戶， 然后測量性能。出乎意料的是，網(wǎng)頁下載延遲的改進很微小。使用一個基于tcpdump的網(wǎng)絡分析工具，作者發(fā)現(xiàn)有兩個原因?qū)е逻@個看似 不錯的改進方法是個壞主意。(1) 與TCP的相互作用：web傳輸建立在TCP之上。TCP在新建立的連接 上使用慢啟動發(fā)送數(shù)據(jù)包：首先發(fā)送一個 TCP 段，在收到確認后發(fā)送兩個 TCP 段，在收到 ACK 后逐步提高發(fā)送速度。因此，即使令服務器主動發(fā)送圖像，發(fā) 送端 TCP 也必須等待 ACK 來提高發(fā)送速度， 這和等待客戶的圖像請求沒有多大 的區(qū)別。(2) 與內(nèi)容緩存的相互作用：許多客戶端有緩存功能，一些常用的圖像會 緩存在本地， 因

28、此令服務器主動發(fā)送已經(jīng)緩存在本地的圖像是對帶寬的浪費。 如 果讓客戶發(fā)送請求，則客戶對于已經(jīng)緩存在本地的圖像不會發(fā)送 GET 請求。從這個例子我們了解到， 系統(tǒng)優(yōu)化的困難之一是系統(tǒng)的各個部分之間存在相 互作用。如果對這些相互作用沒有清楚的了解， 則優(yōu)化的效果可能達不到我們的 預期。但這里最困難的地方也就是很多時候不能清楚地理解復雜的相互作用， 這 時候?qū)嶒烌炞C就很重要了。案例二：加速基于特征的入侵檢測 許多網(wǎng)站安裝有入侵檢測系統(tǒng)，目前最流行的入侵檢測系統(tǒng)是snort。 Snort根據(jù)系統(tǒng)中安裝的一組規(guī)則來檢測攻擊。圖示為 snort的一條規(guī)則，包括如下幾 個部分：動作：包括 pass、aler

29、t、log 三種。協(xié)議：包括 TCP、UDP、ICMP 三種。 源網(wǎng)絡：通常是除本地網(wǎng)絡之外的所有網(wǎng)絡。 源端口：本規(guī)則為 any。目的網(wǎng)絡：通常是本地網(wǎng)絡 目的端口：本規(guī)則為 80。 Msg :如果匹配該條規(guī)則，則給出該條提示。 Flags：匹配該規(guī)則的TCP包，這些標志必須置位。 Co ntent:包載荷中包含的特征字符串，可能不止一個。 Nocase表示特征串是大小寫無關的和防火墻的過濾規(guī)則只匹配 IP 地址、端口號、協(xié)議、 TCP 標志位等不同，snort的規(guī)則還要匹配數(shù)據(jù)包載荷中指定的字符串。經(jīng)統(tǒng)計，84%的snort規(guī)則中包含字符串。實驗表明，字符串匹配是 snort中開銷最大的操

30、作，占整個執(zhí)行時 間的 31%。Snort 匹配規(guī)則的方法作者發(fā)現(xiàn)，匹配某個過濾器的規(guī)則數(shù)可能很多，比如匹配 80 端口的規(guī)則多 達310條（大量攻擊是利用web進行的），逐條規(guī)則地運用BM算法查找字符串， 開銷很大。P1 原則的簡單應用作者將規(guī)則集中所有的字符串抽出來組織到一個自動機中， 修改了 BM 算法， 使得用包內(nèi)容作為輸入，一遍掃描就能找出所有匹配的字符串（給出字符串編 號）。作者將這個新算法應用到snort的整個規(guī)則集上，發(fā)現(xiàn)其性能為snort中算法 的50倍。然而，當作者將這個新算法集成到snort中，并用一個包蹤跡文件（用 tcpdump從網(wǎng)絡中抓真實的包，存在文件中）進行測試

31、時，發(fā)現(xiàn)新算法在性能上 幾乎沒有改進！作者仔細分析后，認為有兩個方面的原因可以解釋該問題：（1）實驗使用的包蹤跡文件包含了很少的 web 流量，在匹配了過濾器后只 有很少的數(shù)據(jù)包還要匹配多條規(guī)則，因此多字符串匹配在該蹤跡文件上不是瓶頸。當作者換用僅包含 web流量的包蹤跡文件進行測試時，性能提高非常明顯。 也就是說，算法性能與流量模式有很大的關系，不是所有時候都有效。（2） cache的影響：多字符串查找需要使用一個數(shù)據(jù)結(jié)構(gòu)（如trie），其大小 隨字符串數(shù)量的增大而增大。 研究發(fā)現(xiàn)，當字符串數(shù)量超過 100條時，數(shù)據(jù)結(jié)構(gòu) 已經(jīng)大到無法放入cache中，而Snort中包含的字符串數(shù)量達到幾千條。也就是 說，算法性能還和規(guī)則集的大小有關，僅僅將單字符串匹配換成多字符串匹配， 并不能一定提高性能。教訓：有時候聲稱的改進可能沒有針對真正的瓶頸（如大多數(shù)情況是單串匹 配），也可能與系統(tǒng)的其它部分有相互作用（如 c