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

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

換時(shí)間）P3b：TradeAccuracyforTime（犧牲精度

換時(shí)間）P3c：ShiftComputationinSpace（在空間中

移動計(jì)算）放寬系統(tǒng)要求的三種技術(shù)原則：當(dāng)確定性算法太慢時(shí)，可以考慮隨機(jī)化策略。以太網(wǎng)的例子：使用隨機(jī)回退解決信道沖突檢測超級節(jié)點(diǎn)的例子：基于對網(wǎng)絡(luò)流量的隨機(jī)采樣統(tǒng)計(jì)，檢測網(wǎng)絡(luò)中的超級節(jié)點(diǎn)。P3a：犧牲確定性換時(shí)間圖像壓縮的例子：MPEG利用離散余弦變換實(shí)時(shí)壓縮視頻，代價(jià)是圖像質(zhì)量有一些損失。第1章中檢測異常URL的例子：將字符比例門限用2的冪次近似表示，從而可以用簡單快速的移位運(yùn)行代替復(fù)雜耗時(shí)的除法運(yùn)算。P3b：犧牲精度換時(shí)間原則：將計(jì)算從一個(gè)子系統(tǒng)移動到另一個(gè)子系統(tǒng)，以使系統(tǒng)性能更好。網(wǎng)絡(luò)的例子：IPv6將分片的功能從路由器移到源節(jié)點(diǎn)，簡化了路由器的實(shí)現(xiàn)，但提高了源節(jié)點(diǎn)的實(shí)現(xiàn)復(fù)雜度。P3c：在空間中移動計(jì)算原則：性能關(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]放在一個(gè)SRAM字中。P4a：利用局部性用較大的空間換來速度的提升：比如，將函數(shù)計(jì)算變?yōu)椴楸肀热?，用多分支trie提高IP地址的查找速度用較小的空間換來速度的提升：比如，壓縮很大的數(shù)據(jù)結(jié)構(gòu)，使其可以放入cache，或者大部分可以放入cache。P4b：用空間換速度編譯器的例子：使用strengthreduction消除循環(huán)中的乘法運(yùn)算，因?yàn)槌朔ㄟ\(yùn)算比加法運(yùn)行代價(jià)高很多。

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

案例一：減少網(wǎng)頁下載時(shí)間客戶欲從web服務(wù)器獲取內(nèi)嵌有圖像的一個(gè)網(wǎng)頁：客戶先發(fā)送對網(wǎng)頁的GET請求針對內(nèi)嵌的每個(gè)圖像，客戶分別發(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)各個(gè)部分之間的相互作用，改進(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三個(gè)組；每個(gè)組按照動作pass、alert和log再分組。每一組規(guī)則組織成一個(gè)二維結(jié)構(gòu)：第一個(gè)維度是規(guī)則使用的過濾器，用于匹配地址及端口。第二個(gè)維度是匹配了過濾器的一組規(guī)則，每個(gè)規(guī)則包含一個(gè)或多個(gè)字符串。規(guī)則匹配方法：先用包頭與過濾器匹配，得到一組候選規(guī)則；對于每一條規(guī)則，使用單字符串匹配算法（BM）檢查數(shù)據(jù)包載荷中是否包含規(guī)定的字符串。應(yīng)用P1的效果對P1原則的應(yīng)用：用多字符串查找算法替換單字符串查找算法。將新算法應(yīng)用到snort的整個(gè)規(guī)則集上，使用隨機(jī)生成的字符串測試，性能提高了50倍。將新算法集成到snort中，并用包trace文件進(jìn)行測試，性能幾乎沒有改進(jìn)。原因和教訓(xùn)原因：實(shí)驗(yàn)使用的包trace文件，數(shù)據(jù)包很少需要匹配多個(gè)字符串，因此，字符串匹配不是瓶頸。多字符串查找所需的數(shù)據(jù)結(jié)構(gòu)隨