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