第一章網(wǎng)絡(luò)算法學(xué)概述

1、第一章 網(wǎng)絡(luò)算法學(xué)概述網(wǎng)絡(luò)算法學(xué)要解決什么問題？o網(wǎng)絡(luò)算法學(xué)要解決的問題：n由于實(shí)現(xiàn)不佳導(dǎo)致的網(wǎng)絡(luò)系統(tǒng)性能瓶頸o網(wǎng)絡(luò)系統(tǒng)有哪些性能瓶頸？n取決于網(wǎng)絡(luò)設(shè)備的類型網(wǎng)絡(luò)設(shè)備的兩種基本類型o端節(jié)點(diǎn)：n網(wǎng)絡(luò)終端，包括PC機(jī)、工作站、服務(wù)器等n針對(duì)通用計(jì)算而設(shè)計(jì)n運(yùn)行全功能的操作系統(tǒng)o路由器：n代表一類通用的網(wǎng)絡(luò)互聯(lián)設(shè)備，包括網(wǎng)橋、交換機(jī)、網(wǎng)關(guān)等n網(wǎng)絡(luò)專用設(shè)備n運(yùn)行一個(gè)很輕量級(jí)的OS，以及一個(gè)完全由硬件實(shí)現(xiàn)的轉(zhuǎn)發(fā)路徑端節(jié)點(diǎn)性能瓶頸的產(chǎn)生o主要的性能瓶頸來自結(jié)構(gòu)化開銷：n軟件分層：OS按照分層原則組織（硬件抽象層，資源管理層，資源分配及調(diào)度層等）n保護(hù)機(jī)制：OS實(shí)現(xiàn)了一組保護(hù)機(jī)制，以免遭應(yīng)用程序的破壞n過度

2、一般化：為適應(yīng)各種應(yīng)用，核心例程（如調(diào)度器、內(nèi)存分配器等）使用一般機(jī)制完成o對(duì)于提供網(wǎng)絡(luò)服務(wù)的節(jié)點(diǎn)而言，性能瓶頸還來自用戶規(guī)模：n許多OS使用只能支持少量連接的低效算法和數(shù)據(jù)結(jié)構(gòu)o主要性能瓶頸：n數(shù)據(jù)拷貝，上下文切換，系統(tǒng)調(diào)用，中斷處理，定時(shí)器管理，協(xié)議解復(fù)用，協(xié)議處理路由器性能瓶頸的產(chǎn)生o規(guī)模：nBandwidth scaling：鏈路速度不斷提高nPopulation scaling：因特網(wǎng)規(guī)模不斷增大o服務(wù)：n為網(wǎng)絡(luò)應(yīng)用提供服務(wù)質(zhì)量、安全性和可靠性保證o主要性能瓶頸：n查表，包分類，交換，排隊(duì)，測(cè)量，安全檢查解決瓶頸的技術(shù)：網(wǎng)絡(luò)算法學(xué)o網(wǎng)絡(luò)算法學(xué)是解決這些瓶頸的一組基本技術(shù)o網(wǎng)絡(luò)算法學(xué)是

3、一種跨學(xué)科的方法：n涉及體系結(jié)構(gòu)、操作系統(tǒng)、硬件、算法等領(lǐng)域o網(wǎng)絡(luò)算法學(xué)是一種系統(tǒng)的方法：n將網(wǎng)絡(luò)設(shè)備看成是一個(gè)系統(tǒng)，其各個(gè)部分不是孤立的n某些功能可以在時(shí)間及空間上移動(dòng)，以達(dá)到提高性能的目的一個(gè)熱身的例子：檢測(cè)異常URL的硬件o應(yīng)用背景：檢測(cè)利用HTTP報(bào)文中的URL域?qū)嵤┑膬?nèi)存溢出攻擊o攻擊特征：URL很長(zhǎng)，且字符出現(xiàn)比例異常o設(shè)計(jì)要求：要求芯片設(shè)計(jì)師設(shè)計(jì)一個(gè)硬件，對(duì)包含可疑URL的包進(jìn)行標(biāo)記。o假設(shè)：安全分析員已經(jīng)給出了每個(gè)字符的異常比例門限樸素的解決方案o維護(hù)兩個(gè)長(zhǎng)度為256的數(shù)組 T 和 C ：n數(shù)組T：保存正常的URL中各個(gè)字符出現(xiàn)比例的上限n數(shù)組C：統(tǒng)計(jì)各個(gè)字符在當(dāng)前URL中出現(xiàn)

4、的次數(shù)o每當(dāng)開始一個(gè)新的數(shù)據(jù)包時(shí)，對(duì)數(shù)組C清零o確定URL的起始位置后：n每讀入一個(gè)字符 “ i ”，Ci加1n掃描到URL終結(jié)符時(shí)，得到URL的長(zhǎng)度Lo遍歷T和C：n對(duì)于任何一個(gè)“j”，如果Cj L* Tj，標(biāo)記該分組 算法分析o線速處理：一個(gè)分組必須在下一個(gè)分組到來之前處理完o假定Ci加1可以在每個(gè)字節(jié)到來的時(shí)間內(nèi)完成o算法對(duì)數(shù)組有兩次遍歷：n新的數(shù)據(jù)包開始時(shí)，初始化C為零。n掃描完URL后，檢查各個(gè)字符的出現(xiàn)比例是否超限 o兩次遍歷至少需要768次讀/寫操作：nC數(shù)組讀、寫各一次nT數(shù)組讀一次 算法優(yōu)化：取消URL結(jié)束后的遍歷o直觀上，掃描完URL后檢查每個(gè)字符的出現(xiàn)比例是不必要的o基本

5、思想：只跟蹤相對(duì)出現(xiàn)次數(shù)最高的算法優(yōu)化：取消URL結(jié)束后的遍歷o基本思想：只跟蹤最高的相對(duì)出現(xiàn)次數(shù)o方法：n使用一個(gè)寄存器記錄到目前為止最高的相對(duì)出現(xiàn)次數(shù)：Max = maxCi/Tin每讀入一個(gè)新字符 “ i ”，oCi加1o若Ci/TiMax, Max= Ci/TinURL掃描結(jié)束后，若Max L，標(biāo)記分組問題和分析oQ：除法邏輯比較復(fù)雜，能否避免除法運(yùn)算？oA：若除數(shù)為2-k，除法可以用移位實(shí)現(xiàn)oQ：Ti不一定是2-koA：放寬系統(tǒng)要求，對(duì)于每個(gè)Ti，用不大于Ti的近似值（1/2k）表示利用硬件特性：消除除法運(yùn)算o改進(jìn)后的處理過程：nTi中存放移位的次數(shù)n讀入新字符“i”后：oCi加1o

6、左移Ti位o若移位后的值大于Max, 更新Maxn當(dāng)URL掃描結(jié)束后，如果Max L，標(biāo)記分組問題和分析oQ：與樸素方案相比，每處理一個(gè)字節(jié)增加了一次讀操作，能否不增加讀/寫次數(shù)？o基本思路：將C數(shù)組和T數(shù)組合并到一個(gè)數(shù)組中，將2次讀操作合并為1次讀操作。利用硬件：合并對(duì)T和C的讀操作o改進(jìn)方法：n使用較長(zhǎng)寬度的字，每個(gè)字中保存Ci和Tin比如，Ci使用15比特，Ti使用14比特o可行性：n使用硬件取出合并到一個(gè)字中的域是很簡(jiǎn)單的o到目前為止，我們成功消除了URL掃描結(jié)束后對(duì)數(shù)組T和C的遍歷，并消除了該方法產(chǎn)生的除法問題以及URL掃描過程中多一次訪問T數(shù)組的問題 初始化C的開銷能不能降下來？o

7、Q：有必要在每開始一個(gè)新的數(shù)據(jù)包時(shí)，清除整個(gè)C數(shù)組嗎？ oA：從道理上說，Ci不需要被清除，直到一個(gè)新的數(shù)據(jù)包需要使用它。（lazy evaluation）n當(dāng)芯片掃描到一個(gè)新的URL、并且第一次遇到字符 “i”時(shí)，設(shè)置Ci=1n此后再掃描到字符“i”時(shí)，Ci加1初始化C的開銷能不能降下來？oQ：有必要在每開始一個(gè)新的數(shù)據(jù)包時(shí)，清除整個(gè)C數(shù)組嗎？ oA：從道理上說，Ci不需要被清除，直到一個(gè)新的數(shù)據(jù)包需要使用它。（lazy evaluation）oQ：芯片如何知道Ci統(tǒng)計(jì)的是當(dāng)前URL中的“i”，還是之前某個(gè)URL中的“i”？初始化C的開銷能不能降下來？oQ：有必要在每開始一個(gè)新的數(shù)據(jù)包時(shí)，清

8、除整個(gè)C數(shù)組嗎？ oA：從道理上說，Ci不需要被清除，直到一個(gè)新的數(shù)據(jù)包需要使用它。（lazy evaluation）oQ：芯片如何知道Ci統(tǒng)計(jì)的是當(dāng)前URL中的”i”，還是之前某個(gè)URL中的”i”？oA：給每個(gè)數(shù)據(jù)包賦一個(gè)世代號(hào)，該數(shù)據(jù)包使用的計(jì)數(shù)器具有與數(shù)據(jù)包相同的世代號(hào) Lazy Evaluation：消除對(duì)：消除對(duì)C的初始化的初始化 o改進(jìn)方法：n每個(gè)表項(xiàng)擴(kuò)展一個(gè)世代域（generation number）Gi，比如3比特n另外維護(hù)一個(gè)寄存器g，記錄當(dāng)前數(shù)據(jù)包的世代號(hào)n每當(dāng)一個(gè)新的數(shù)據(jù)包到來，g = (g+1) mod 8n每當(dāng)Ci初始化時(shí)，Gi也要更新消除對(duì)C的初始化（續(xù)）o假定一個(gè)

9、正在處理的數(shù)據(jù)包，其世代號(hào)為hn當(dāng)讀入字符“i”時(shí)，從聯(lián)合數(shù)組中讀Gi、Ci和Tio若Gi h，寫Ci = 1，并設(shè)Gi = ho若Gi = h，Ci加1nCi左移Ti位n若移位后的值大于Max，更新MaxnURL掃描結(jié)束后，如果Max L，標(biāo)記分組 問題與分析oQ：g回繞怎么辦？oA：未被使用的計(jì)數(shù)器，在其世代號(hào)發(fā)生回繞前必須被清除 o基本思想：n芯片需要一個(gè)額外的清洗循環(huán)，將世代號(hào)過時(shí)的Ci置0，但該循環(huán)只需在8個(gè)分組的時(shí)間內(nèi)完成。使用長(zhǎng)周期的清洗循環(huán)清理Co改進(jìn)方法：n芯片需要兩個(gè)狀態(tài)，scrub和normal。每當(dāng)掃描完一個(gè)URL，芯片切換到scrub狀態(tài)。 n另外維護(hù)一個(gè)寄存器，指向下一個(gè)要清洗的表項(xiàng)s。n在scrub狀態(tài)，每當(dāng)收到一個(gè)非URL字節(jié)，讀入表項(xiàng)s，如果Gs g，設(shè)置Gs = g 和 Cs=0。網(wǎng)絡(luò)算法學(xué)的特性o網(wǎng)絡(luò)算法學(xué)是跨學(xué)科的n跨學(xué)科的思維有助于產(chǎn)生出最好的設(shè)計(jì) o網(wǎng)絡(luò)算法學(xué)肯定系統(tǒng)思維的重要性 n放寬要求和將工作從一個(gè)子