網(wǎng)絡(luò)算法學(xué)：第三章 實現(xiàn)原則

第三章實現(xiàn)原則三態(tài)字符串：包括0、1及*三種字符，其中*表示可以匹配0或1。內(nèi)容可尋址存儲器CAM：一種支持快速搜索和數(shù)據(jù)存儲的存儲器，主要用于改善查表操作的性能。三態(tài)內(nèi)容可尋址存儲器TCAM：支持“0”、“1”和“*”三種狀態(tài)的CAM。3.1運(yùn)用實現(xiàn)原則的例子：更新TCAMCAM被組織成一個二維陣列：每一行（slot）長度固定，存放一個關(guān)鍵字。每一位為“0”或“1”。并行查找：處理器提供一個查找關(guān)鍵字CAM返回匹配該關(guān)鍵字的一組槽，響應(yīng)時間一般不超過100ns。Content-AddressableMemoryCAM的組織每個條目存儲一個二進(jìn)制數(shù)和一個掩碼，掩碼說明哪些比特要和查找關(guān)鍵字中的相應(yīng)比特進(jìn)行比較。TCAM并行地執(zhí)行查找，返回匹配的最小槽號。TernaryContent-AddressableMemroyTCAM中的地址前綴必須按照前綴長度從大到小的順序排列。如何在TCAM中添加或刪除一條地址前綴？使用TCAM進(jìn)行IP地址查找自由度一：相同長度的前綴之間不需要排序。方法：將長度為i的前綴插入到長度為(i+1)的前綴底部，將原來在該位置上的前綴X移走。下一步：為X尋找一個新的位置。理解并利用自由度采用遞歸的算法思想：將最后一條長度為（i+2）的前綴Y移出，X放到Y(jié)的位置用同樣的方法為Y找到插入的位置實現(xiàn)時展開遞歸，從TCAM頂部開始：將最后一條長度為32的前綴移到TCAM的頂部，將最后一條長度為31的前綴移到空出的位置；依次類推，直至長度為i的前綴插入。如果每一種長度的前綴都有（最壞情況），需要（32-i）次訪存。若i較小，訪存次數(shù)接近32。使用算法技術(shù)—采用遞歸自由度二：空閑空間可以放在TCAM的任何區(qū)域。方法：將空閑空間放在長度為16的前綴項后面，可將最壞情況下的訪存次數(shù)減少一半。進(jìn)一步利用自由度自由度二：空閑空間可以放在TCAM的任何區(qū)域。方法：空閑空間放在長度為16的前綴項后面，可將最壞情況下的訪存次數(shù)減少一半。自由度三：“如果i>j，那么長度為i的前綴必須出現(xiàn)在長度為j的前綴之前”，這不是必要的。改變規(guī)范：如果兩個前綴P和Q可能匹配同一個地址，那么如果P比Q長，P必須出現(xiàn)在Q之前。進(jìn)一步利用自由度應(yīng)用背景：入侵檢測系統(tǒng)在規(guī)定的測量周期內(nèi)檢測攻擊節(jié)點，并在確定了可疑節(jié)點后，將該節(jié)點在測量時間內(nèi)發(fā)送的全部數(shù)據(jù)包放入安全物證日志，發(fā)送給管理員。問題：當(dāng)判定一個節(jié)點為可疑節(jié)點時，如何得到它之前發(fā)送的全部數(shù)據(jù)包？３.２算法VS算法學(xué)：安全物證問題問題：如何從隊列中高效地找到屬于可疑流的包？解決方案維護(hù)一個流ID的哈希表：將每個流ID映射到一個指針列表，列表中的指針指向?qū)儆谠摿鞯臄?shù)據(jù)包。當(dāng)一個數(shù)據(jù)包放入隊列時，用其流ID查找哈希表，將數(shù)據(jù)包在隊列中的地址放入表尾。當(dāng)數(shù)據(jù)包離開隊列時，從指針列表頭部刪除其指針。問題：增加了空間復(fù)雜度：需要維護(hù)哈希表和指針列表。增加了計算復(fù)雜度：需要維護(hù)哈希表。教科書上的算法基本思想：不要試圖在確定一個流F為可疑流時，就能立即找出流F的所有數(shù)據(jù)包，僅當(dāng)包到達(dá)隊尾時才去識別。方法：當(dāng)可疑節(jié)點表非空時，每當(dāng)添加一個包到隊頭，就從隊尾移出一個包。若包的源節(jié)點在可疑節(jié)點表中，拷貝包到物證日志。LacyEvaluation：將判斷一個包是否屬于可疑流這件事拖到不得不做的時候（已有可疑節(jié)點被識別，包到達(dá)隊尾）時才做。優(yōu)點：不需要維護(hù)哈希表和指針列表，節(jié)省了大量的存儲空間，也減小了計算復(fù)雜度。系統(tǒng)的解決方案—LazyEvaluation系統(tǒng)原則（1-5）：將系統(tǒng)看成由子系統(tǒng)構(gòu)成，而不是一個黑盒子。兼顧模塊化和效率（6-10）：允許保留復(fù)雜系統(tǒng)的模塊化，與此同時給出提高性能的方法。加速（11-15）：僅加速某個關(guān)鍵例程的方法。３.３十五條實現(xiàn)原則系統(tǒng)原則（1-5）：將系統(tǒng)看成由子系統(tǒng)構(gòu)成，而不是一個黑盒子。兼顧模塊化和效率（6-10）：允許保留復(fù)雜系統(tǒng)的模塊化，與此同時給出提高性能的方法。加速（11-15）：僅加速某個關(guān)鍵例程的方法。十五條實現(xiàn)原則原則：若某個特殊的操作序列存在資源浪費，且該模式經(jīng)常出現(xiàn)，就有必要消除這種浪費。編譯器的例子：消除重復(fù)的子表達(dá)式 I:=5.1*n+2 優(yōu)化為： t:=5.1*n+2 J:=(5.1*n+2)*4 i:=t j:=t*4網(wǎng)絡(luò)的例子：操作系統(tǒng)和用戶空間之間多次數(shù)據(jù)包拷貝。P1：避免常見情形中的明顯浪費系統(tǒng)有時間和空間兩個特性：子系統(tǒng)代表了系統(tǒng)的空間特性時間特性表現(xiàn)在系統(tǒng)是在不同的時間尺度上被實例化的原則：通過在時間軸上移動計算，有時可以獲得很大的收益。P2：在時間軸上移動計算P2a：Precompute（預(yù)先計算）P2b：EvaluateLazily（延遲求值）P2c：ShareExpenses（分?jǐn)傞_銷）屬于P2的三類技術(shù)原則：提前計算好需要的值，節(jié)省運(yùn)行時的計算時間。函數(shù)計算的例子：復(fù)雜的函數(shù)計算查表操作網(wǎng)絡(luò)的例子：預(yù)先計算好一個連接上的IP頭和TCP頭，以減小運(yùn)行時寫包頭的工作量。P2a：預(yù)先計算原則：推遲在關(guān)鍵時間點上要執(zhí)行的高代價操作，寄希望于該操作在未來可能不再需要，或者可以找到較空閑的時間執(zhí)行。操作系統(tǒng)的例子：copy-on-write網(wǎng)絡(luò)的例子：若數(shù)據(jù)包的字節(jié)序與接收節(jié)點的本地字節(jié)序不同，不必立即進(jìn)行字節(jié)序轉(zhuǎn)換，而是等到實際處理數(shù)據(jù)包時才進(jìn)行轉(zhuǎn)換。P2b：延遲求值原則：充分利用系統(tǒng)其它部分執(zhí)行的高代價操作最重要的技術(shù)：批處理（batching），用延遲換吞吐量。網(wǎng)絡(luò)的例子：網(wǎng)卡在收到一批包之后，再產(chǎn)生中斷。P2c：分?jǐn)傞_銷原則：在實現(xiàn)子系統(tǒng)遇到困難時，改變某些方面的要求。P3：放寬系統(tǒng)要求P3a：TradeCertaintyforTime（犧牲確定性

換時間）P3b：TradeAccuracyforTime（犧牲精度

換時間）P3c：ShiftComputationinSpace（在空間中

移動計算）放寬系統(tǒng)要求的三種技術(shù)原則：當(dāng)確定性算法太慢時，可以考慮隨機(jī)化策略。以太網(wǎng)的例子：使用隨機(jī)回退解決信道沖突檢測超級節(jié)點的例子：基于對網(wǎng)絡(luò)流量的隨機(jī)采樣統(tǒng)計，檢測網(wǎng)絡(luò)中的超級節(jié)點。P3a：犧牲確定性換時間圖像壓縮的例子：MPEG利用離散余弦變換實時壓縮視頻，代價是圖像質(zhì)量有一些損失。第1章中檢測異常URL的例子：將字符比例門限用2的冪次近似表示，從而可以用簡單快速的移位運(yùn)行代替復(fù)雜耗時的除法運(yùn)算。P3b：犧牲精度換時間原則：將計算從一個子系統(tǒng)移動到另一個子系統(tǒng)，以使系統(tǒng)性能更好。網(wǎng)絡(luò)的例子：IPv6將分片的功能從路由器移到源節(jié)點，簡化了路由器的實現(xiàn)，但提高了源節(jié)點的實現(xiàn)復(fù)雜度。P3c：在空間中移動計算原則：性能關(guān)鍵的組件通常部分地采用“自底向上”的方法構(gòu)建。有三種這樣的技術(shù)：P4a：ExploitLocality（利用局部性）P4b：TradeMemoryforSpeed（用空間換速

度）P4c：ExploitHardwareFeature（利用硬件

特性）P4：利用系統(tǒng)組件原則：將相關(guān)聯(lián)的數(shù)據(jù)存放在連續(xù)的位置，存儲器硬件可提供高效的訪問。應(yīng)用的例子：在檢測異常URL的例子中，將G[i]、T[i]和C[i]放在一個SRAM字中。P4a：利用局部性用較大的空間換來速度的提升：比如，將函數(shù)計算變?yōu)椴楸肀热纾枚喾种rie提高IP地址的查找速度用較小的空間換來速度的提升：比如，壓縮很大的數(shù)據(jù)結(jié)構(gòu)，使其可以放入cache，或者大部分可以放入cache。P4b：用空間換速度編譯器的例子：使用strengthreduction消除循環(huán)中的乘法運(yùn)算，因為乘法運(yùn)算比加法運(yùn)行代價高很多。

P4c：利用硬件特性過度使用P4原則，系統(tǒng)的模塊化將受到損害。運(yùn)用P4原則需注意以下兩點：如果利用其它系統(tǒng)特性只是為了提高性能，那么對那些系統(tǒng)特性的改變應(yīng)當(dāng)只影響性能，不影響正確性。僅對確認(rèn)為是系統(tǒng)瓶頸的組件運(yùn)用該原則。運(yùn)用P4原則需注意的問題原則：當(dāng)所有方法都不奏效時，增加硬件是更簡單和有效的方法。理想情況：關(guān)鍵算法用軟件實現(xiàn)，通過處理器升級獲得速度提升。對硬件與軟件的傳統(tǒng)看法：硬件靈活性差，設(shè)計周期長，適合完成簡單、固定的功能。軟件靈活性好，適合完成復(fù)雜的功能。可重構(gòu)計算的出現(xiàn)使得以上界線變得模糊。P5：增加硬件提高性能P5a：使用內(nèi)存交錯和流水線P5b：使用寬字并行P5c：結(jié)合DRAM和SRAM經(jīng)常用于網(wǎng)絡(luò)ASIC芯片的硬件技術(shù)系統(tǒng)原則（1-5）：將系統(tǒng)看成由子系統(tǒng)構(gòu)成，而不是一個黑盒子。兼顧模塊化和效率（6-10）：允許保留復(fù)雜系統(tǒng)的模塊化，與此同時給出提高性能的方法。加速（11-15）：僅加速某個關(guān)鍵例程的方法。十五條實現(xiàn)原則原則：一個針對大多數(shù)情形設(shè)計的通用例程有時很低效，針對重要情形設(shè)計定制例程很有必要。數(shù)據(jù)庫的例子：許多數(shù)據(jù)庫應(yīng)用設(shè)計專門的緩存例程，替換操作系統(tǒng)中基于LRU策略的緩存例程。P6：用高效的定制例程代替低效的通用例程P7：避免不必要的一般性設(shè)計抽象的、一般性的子系統(tǒng)可能導(dǎo)致不必要的或者很少使用的特性。原則：移除一些不必要的特性來提高性能。P8：不要受參考實現(xiàn)的束縛參考實現(xiàn)只是為了解釋概念，并不關(guān)注效率。原則：實現(xiàn)者可以自由修改參考實現(xiàn)，只要兩種實現(xiàn)的外部效果相同。P9和P10：傳遞線索（hint）P9：PassHintsinModuleInterfacesP10：PassHintsinProtocolHeaders線索是客戶（模塊或節(jié)點）傳遞給服務(wù)（模塊或節(jié)點）的信息，如果正確的話，可以避免服務(wù)執(zhí)行開銷較大的計算。如果大部分情況下線索是正確的，傳遞線索可以提高性能。系統(tǒng)原則（1-5）：將系統(tǒng)看成由子系統(tǒng)構(gòu)成，而不是一個黑盒子。兼顧模塊化和效率（6-10）：允許保留復(fù)雜系統(tǒng)的模塊化，與此同時給出提高性能的方法。加速（11-15）：僅加速某個關(guān)鍵例程的方法。十五條實現(xiàn)原則原則：多數(shù)情況下系統(tǒng)行為是可預(yù)期的，有必要優(yōu)化常見情形，哪怕可能使得非預(yù)期情形的處理變得低效。啟發(fā)式方法：優(yōu)化常見情形的方法稱為啟發(fā)式方法，啟發(fā)式方法在實際系統(tǒng)中被大量使用。體系結(jié)構(gòu)的例子：使用cache優(yōu)化指令的執(zhí)行。網(wǎng)絡(luò)的例子：利用TCP頭部預(yù)測加快TCP包處理。P11：優(yōu)化預(yù)期情形原則：如果一個操作的代價很高，可以考慮增加額外的狀態(tài)或利用已有的狀態(tài)來加速該操作。數(shù)據(jù)庫的例子：建立輔助索引（增加狀態(tài)）網(wǎng)絡(luò)的例子：IP頭校驗的增量計算（利用已有的狀態(tài)）P12：增加或利用狀態(tài)自由度：可以由實現(xiàn)者控制的變量。原則：通過優(yōu)化變量（自由度）來最大化系統(tǒng)性能舉例：使用多分支trie優(yōu)化IP地址查找自由度一：層數(shù)自由度一：不同層上的查找步長對于給定的吞吐量，通過動態(tài)規(guī)劃確定層數(shù)及每一層的查找步長，以最小化內(nèi)存需求。P13：優(yōu)化自由度原則：處理小規(guī)模問題時，使用特殊技術(shù)而不是通用技術(shù)。操作系統(tǒng)的例子：頁表使用的是簡單的索引表，沒有構(gòu)造哈希表或使用二分查找P14：針對有限規(guī)模問題使用特殊技術(shù)P15：使用算法技術(shù)構(gòu)造高效的數(shù)據(jù)結(jié)構(gòu)在運(yùn)用P1~P14對系統(tǒng)進(jìn)行優(yōu)化后，剩下的才是算法問題。算法方法包括使用標(biāo)準(zhǔn)的數(shù)據(jù)結(jié)構(gòu)以及一般的算法技術(shù)，如分治和隨機(jī)化。算法可能隨著系統(tǒng)結(jié)構(gòu)和技術(shù)的變化而失效，真正的技術(shù)突破來自算法思維的運(yùn)用，而不僅僅只是重用已有的算法。

3.4需要注意的問題在運(yùn)用原則前，必須理解重要的性能指標(biāo)，確定系統(tǒng)瓶頸。在完成改進(jìn)后，必須通過實驗來驗證改進(jìn)是確有成效的。

案例一：減少網(wǎng)頁下載時間客戶欲從web服務(wù)器獲取內(nèi)嵌有圖像的一個網(wǎng)頁：客戶先發(fā)送對網(wǎng)頁的GET請求針對內(nèi)嵌的每個圖像，客戶分別發(fā)送GET請求運(yùn)用原則P1：為什么服務(wù)器不能自動將圖像發(fā)送給客戶，而要等待客戶的請求？

修改效果分析效果：網(wǎng)頁下載延遲幾乎沒有改變。原因：與TCP的相互作用：

TCP的慢啟動機(jī)制限制了服務(wù)器連續(xù)發(fā)送，其結(jié)果與服務(wù)器等待客戶請求無異。與內(nèi)容緩存的相互作用：客戶端的緩存功能使得服務(wù)器主動發(fā)送圖像可能是多余的。教訓(xùn)：如果不了解系統(tǒng)各個部分之間的相互作用，改進(jìn)的效果可能達(dá)不到我們的預(yù)期。案例二：加速基于特征的入侵檢測Snort根據(jù)系統(tǒng)中安裝的一組規(guī)則來檢測攻擊。Snort規(guī)則由動作、協(xié)議、源網(wǎng)絡(luò)、源端口、目的網(wǎng)絡(luò)、目的端口、提示消息、TCP標(biāo)志位、特征字符串等組成。84%的snort規(guī)則中包含字符串；字符串匹配是snort中開銷最大的操作。Snort的規(guī)則匹配方法規(guī)則集先按照協(xié)議分為TCP、UDP和ICMP三個組；每個組按照動作pass、alert和log再分組。每一組規(guī)則組織成一個二維結(jié)構(gòu)：第一個維度是規(guī)則使用的過濾器，用于匹配地址及端口。第二個維度是匹配了過濾器的一組規(guī)則，每個規(guī)則包含一個或多個字符串。規(guī)則匹配方法：先用包頭與過濾器匹配，得到一組候選規(guī)則；對于每一條規(guī)則，使用單字符串匹配算法（BM）檢查數(shù)據(jù)包載荷中是否包含規(guī)定的字符串。應(yīng)用P1的效果對P1原則的應(yīng)用：用多字符串查找算法替換單字符串查找算法。將新算法應(yīng)用到snort的整個規(guī)則集上，使用隨機(jī)生成的字符串測試，性能提高了50倍。將新算法集成到snort中，并用包trace文件進(jìn)行測試，性能幾乎沒有改進(jìn)。原因和教訓(xùn)原因：實驗使用的包trace文件，數(shù)據(jù)包很少需要匹配多個字符串，因此，字符串匹配不是瓶頸。多字符串查找所需的數(shù)據(jù)結(jié)構(gòu)隨