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

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

2、一般化：為適應(yīng)各種應(yīng)用，核心例程（如調(diào)度器、內(nèi)存分配器等）使用一般機(jī)制完成o對于提供網(wǎng)絡(luò)服務(wù)的節(jié)點而言，性能瓶頸還來自用戶規(guī)模：n許多OS使用只能支持少量連接的低效算法和數(shù)據(jù)結(jié)構(gòu)o主要性能瓶頸：n數(shù)據(jù)拷貝，上下文切換，系統(tǒng)調(diào)用，中斷處理，定時器管理，協(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查表，包分類，交換，排隊，測量，安全檢查解決瓶頸的技術(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è)備看成是一個系統(tǒng)，其各個部分不是孤立的n某些功能可以在時間及空間上移動，以達(dá)到提高性能的目的一個熱身的例子：檢測異常URL的硬件o應(yīng)用背景：檢測利用HTTP報文中的URL域?qū)嵤┑膬?nèi)存溢出攻擊o攻擊特征：URL很長，且字符出現(xiàn)比例異常o設(shè)計要求：要求芯片設(shè)計師設(shè)計一個硬件，對包含可疑URL的包進(jìn)行標(biāo)記。o假設(shè)：安全分析員已經(jīng)給出了每個字符的異常比例門限樸素的解決方案o維護(hù)兩個長度為256的數(shù)組 T 和 C ：n數(shù)組T：保存正常的URL中各個字符出現(xiàn)比例的上限n數(shù)組C：統(tǒng)計各個字符在當(dāng)前URL中出現(xiàn)

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

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

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

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

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

9、正在處理的數(shù)據(jù)包，其世代號為hn當(dāng)讀入字符“i”時，從聯(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：未被使用的計數(shù)器，在其世代號發(fā)生回繞前必須被清除 o基本思想：n芯片需要一個額外的清洗循環(huán)，將世代號過時的Ci置0，但該循環(huán)只需在8個分組的時間內(nèi)完成。使用長周期的清洗循環(huán)清理Co改進(jìn)方法：n芯片需要兩個狀態(tài)，scrub和normal。每當(dāng)掃描完一個URL，芯片切換到scrub狀態(tài)。 n另外維護(hù)一個寄存器，指向下一個要清洗的表項s。n在scrub狀態(tài)，每當(dāng)收到一個非URL字節(jié)，讀入表項s，如果Gs g，設(shè)置Gs = g 和 Cs=0。網(wǎng)絡(luò)算法學(xué)的特性o網(wǎng)絡(luò)算法學(xué)是跨學(xué)科的n跨學(xué)科的思維有助于產(chǎn)生出最好的設(shè)計 o網(wǎng)絡(luò)算法學(xué)肯定系統(tǒng)思維的重要性 n放寬要求和將工作從一個子