【文章內(nèi)容簡介】 ? 但是， A認(rèn)為 B有一條通向 D長度為 2的路徑，通過 B經(jīng)過 3個結(jié)點可到達(dá) D。類似， B也這樣認(rèn)為。于是兩個結(jié)點每交換一次信息，到達(dá) D的距離就增加 1，直至加大無窮。 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 鏈路狀態(tài)路由算法 ? 距離向量路由算法的主要問題 ? 由于延遲度量僅僅是隊列長度，在選擇路由時沒有考慮線路帶寬。 ? 即使使用了水平分裂，路由收斂速度依然慢。 ? 在 1979年前， ARPANET上都采用距離向量路由算法，但是之后，即為鏈路狀態(tài)路由算法所替代。 ? 鏈路狀態(tài)路由算法的簡單步驟 ? 發(fā)現(xiàn)鄰居結(jié)點，并學(xué)習(xí)它們的網(wǎng)絡(luò)地址。 ? 測量到每個鄰居結(jié)點的延遲或開銷。 ? 將所有學(xué)習(xí)到的內(nèi)容封裝成一個分組。 ? 將這個分組發(fā)送給所有其它路由器。 ? 計算到每個其它路由器的最短路徑。 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 步驟 1：發(fā)現(xiàn)鄰居結(jié)點 ? 發(fā)現(xiàn)鄰居結(jié)點，并學(xué)習(xí)它們的網(wǎng)絡(luò)地址。 ? 路由器啟動后，通過發(fā)送 HELLO分組，并得到鄰居路由器的響應(yīng)來發(fā)現(xiàn)鄰居結(jié)點。 ? 路由器的名稱必須是唯一的。 ? 當(dāng)兩個或多個路由器連在一個 LAN時，引入人工結(jié)點。 ? 圖例。 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 步驟 2/3：測量線路開銷和封裝分組 ? 測量到每個鄰居結(jié)點的延遲或開銷，一種直接的方法是：發(fā)送一個要對方立即響應(yīng)的 ECHO分組，來回時間除以 2即為延遲時間。 ? 如果在測量延遲時間的時候，考慮負(fù)載，會是什么情況？（自學(xué)） ? 將所有學(xué)習(xí)到的內(nèi)容封裝成一個分組，即在信息收集完畢后，構(gòu)造一個包含所有數(shù)據(jù)的分組。 ? 該分組的結(jié)構(gòu)為：發(fā)送方的標(biāo)識符、序號、年齡、鄰居結(jié)點列表（鄰居結(jié)點標(biāo)識符，線路開銷值）。 ? 創(chuàng)建鏈路狀態(tài)分組的時機(jī)：一是定期創(chuàng)建，一是在發(fā)生重大事件后創(chuàng)建。 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 步驟 4：發(fā)布鏈路狀態(tài)分組 ? 鏈路狀態(tài)分組的發(fā)布算法 ? 基本思想：洪泛鏈路狀態(tài)分組。 ? 為控制洪泛，每個分組中增加一個序號域，每次發(fā)送新分組時加 1。 ? 路由器記錄信息對 (源路由器，序號 )，當(dāng)一個鏈路狀態(tài)分組到達(dá)時，若是新的，則分發(fā)；若是重復(fù)的，則丟棄；若序號比路由器記錄中的最大序號小，則認(rèn)為過時而丟棄。 ? 基本算法所產(chǎn)生的問題 ? 序號循環(huán)使用會混淆。 ? 路由器崩潰后，所有的序號丟失，從 0開始記，以后所有的新到分組都可能被當(dāng)作重復(fù)分組而被拒絕。 ? 序號在發(fā)送出去后出現(xiàn)錯誤。 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 步驟 4：發(fā)布鏈路狀態(tài)分組 ? 基本算法的改進(jìn)方案 ? 為了避免序號重復(fù)，使用 32位的序號。 ? 解決序號丟失和出錯的方法是增加年齡 (age)域，每秒鐘年齡減 1，至零則丟棄。 ? 鏈路狀態(tài)分組到達(dá)后，延遲一段時間 (被放置在一個保持區(qū)中 )，并與其它已到達(dá)的來自同一路由器的鏈路狀態(tài)分組比較序號，丟棄重復(fù)分組和超齡分組。 ? 為了防止鏈路出錯，所有的鏈路狀態(tài)分組都需要應(yīng)答。 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 步驟 5：計算新路由 ? 在路由器積累了一整套網(wǎng)絡(luò)的鏈路狀態(tài)分組后，就可以通過計算得到整個網(wǎng)絡(luò)的結(jié)構(gòu)?？梢岳?Dijkstra算法 計算得到每個其它路由器的最短路徑。 ? 基于鏈路狀態(tài)的路由協(xié)議 ? Open Shortest Path First (OSPF) ? Intermediate SystemIntermediate System (ISIS) 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 分級路由 ? 網(wǎng)絡(luò)規(guī)模增長帶來的問題 ? 路由器中的路由表增大。 ? 路由器為選擇路由而占用的內(nèi)存、 CPU時間和網(wǎng)絡(luò)帶寬增大。 ? 解決辦法 —— 分級路由 ? 對于大型網(wǎng)絡(luò)分而治之，每個路由器只知道自己所在子網(wǎng)的路由信息，而不去了解其他子網(wǎng)的內(nèi)部結(jié)構(gòu)。 ? 根據(jù)需要，可以分成區(qū)域 (regions)、聚類 (clusters)、區(qū) (zones)和組 (groups)… ? 圖例。 ? 分級路由帶來的問題 ? 路由表中的路由不一定是最優(yōu)路由。 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 分級路由圖例 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 小結(jié) — 路由算法 ? 最優(yōu)化原則 ? 路由算法的目的是找出并使用匯集樹。 ? 最短路徑路由算法 ? 目的是構(gòu)建兩個路由器間的路由，算法是在子網(wǎng)拓?fù)鋱D中找出最短路徑。 Dijkstra算法。 ? 洪泛算法 ? 把收到的每一個分組，向除了該分組到來的線路外的所有輸出線路發(fā)送。 ? 基于流量的路由算法 ? 根據(jù)網(wǎng)絡(luò)帶寬和平均流量，可得出平均延遲，因此路由問題歸結(jié)為找產(chǎn)生網(wǎng)絡(luò)最小延遲的路由算法。 ? 距離向量路由算法 ? 根據(jù)兩個結(jié)點間的隊列長度來完成路由選擇，但是最大的問題是無窮計算，而且水平分裂也不能完全解決所有的問題。 ? 鏈路狀態(tài)路由算法 ? 發(fā)現(xiàn)鄰居結(jié)點 ? 測量線路開銷 ? 將所有學(xué)習(xí)到的內(nèi)容封裝成一個分組 ? 發(fā)布鏈路狀態(tài)信息 ? 計算新路由 ? 分級路由 ? 對于大型網(wǎng)絡(luò)分而治之，每個路由器只知道自己所在子網(wǎng)的路由信息，而不去了解其他子網(wǎng)的內(nèi)部結(jié)構(gòu)。 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 擁塞的基本概念 ? 擁塞 (congestion)：網(wǎng)絡(luò)中存在過多分組的時候，網(wǎng)絡(luò)性能降低，這種情況被稱為擁塞。 圖例 ? 造成擁塞的原因 ? 多個輸入對應(yīng)一個輸出，只增加內(nèi)存，并不能解決問題。 ? 慢速處理器。 ? 低帶寬線路。 ? 針對某個因素的解決方案，只能對提高網(wǎng)絡(luò)性能起到一點點作用，甚至可能僅僅是轉(zhuǎn)移了影響性能的瓶頸。 ? 擁塞控制 (congestion control)與流量控制 (flow control) ? 擁塞控制需要確保通信子網(wǎng)能夠承載用戶提交的通信量，是一個全局性問題，涉及主機(jī)、路由器等很多因素。 ? 流量控制與點到點的通信量有關(guān)，主要解決快速發(fā)送方與慢速接收方的問題，是局部問題，一般都是基于反饋進(jìn)行控制的。 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 擁塞圖例 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 擁塞控制的分類 ? 根據(jù)控制論，擁塞控制可分為兩類。 ? 開環(huán)控制 (防患于未然 ) ? 通過良好的設(shè)計解決問題，以避免擁塞發(fā)生。一旦運行，就不再做中間階段的更正。 ? 進(jìn)行開環(huán)控制的工具需要決定何時接收新的分組、何時丟棄分組、丟棄哪些分組，制定網(wǎng)絡(luò)中不同地點的計劃表等。利用開環(huán)進(jìn)行擁塞控制時，所有這些操作都不會考慮網(wǎng)絡(luò)的當(dāng)前狀態(tài)。 ? 閉環(huán)控制 (因地制宜 ) ? 基于反饋機(jī)制。其工作過程為： ? 監(jiān)控系統(tǒng)，發(fā)現(xiàn)何時何地發(fā)生擁塞。 ? 把發(fā)生擁塞的消息傳給能采取動作的站點。 ? 調(diào)整系統(tǒng)操作，解決擁塞問題。 ? 閉環(huán)控制操作需要完成以下三個問題：何為擁塞、如何反饋和如何解決。 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 閉環(huán)控制 ? 何為擁塞 —— 衡量網(wǎng)絡(luò)擁塞的參數(shù) ? 缺乏緩沖區(qū)造成的丟包率 ? 平均隊列長度 ? 超時重傳的分組數(shù)目 ? 平均分組延遲 ? 分組延遲變化 (Jitter) ? 如何反饋 —— 反饋方法 ? 向負(fù)載的發(fā)生源發(fā)送一個報警分組，這同時加強(qiáng)了擁塞。 ? 在分組結(jié)構(gòu)中保留一個位或一個域來表示發(fā)生擁塞，一旦發(fā)生擁塞，路由器將所有輸出分組的擁塞位填充，報警。 ? 主機(jī)或路由器主動地、周期性地發(fā)送探報 (probe)， 查詢是否發(fā)生擁塞。 ? 如何解決 —— 利用擁塞控制算法 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 開環(huán)控制 — 擁塞預(yù)防策略 ? 影響擁塞的網(wǎng)絡(luò)設(shè)計策略 ? 數(shù)據(jù)鏈路層 ? 重傳、亂序緩存、確認(rèn)、流控 ? 網(wǎng)絡(luò)層 ? 子網(wǎng)中的虛電路和數(shù)據(jù)報、分組排隊和服務(wù)策略、分組丟棄策略、路由算法、分組的生存時間管理 ? 傳輸層 ? 重傳、亂序緩存、確認(rèn)、流控、超時中止 計 算 機(jī) 網(wǎng) 絡(luò) 原 理 —— 網(wǎng) 絡(luò) 層 開環(huán)控制 — 通信量整形 ? 通信量整形 (Traffic Shaping)的基本思想 ? 網(wǎng)絡(luò)上，突發(fā)的通信量是造成擁塞的主要原因。