動態(tài)路由算法與擁塞控制.ppt

主要內(nèi)容（2）,7.1 網(wǎng)絡層概述 7.2 路由算法 7.2.1 最優(yōu)化原則 7.2.2 最短路徑路由算法 7.2.3 洪泛算法 7.2.4 基于流量的路由算法 7.2.5 距離向量路由算法 7.2.6 鏈路狀態(tài)路由算法 7.2.7 分層路由 7.2.8 移動主機的路由,7.2 路由算法（28）,7.2.5 距離向量路由算法（ DV： Distance Vector Routing） 屬于動態(tài)路由算法,也稱Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于ARPANET，被RIP(Routing Information Protocol)協(xié)議采用。 基本思想 每個路由器維護一張表，表中給出了到每個目的地的已知最佳距離和線路，并通過與相鄰路由器交換距離信息來更新表； 以子網(wǎng)中其它路由器為表的索引，表項包括兩部分：到達目的結(jié)點的最佳輸出線路，和到達目的結(jié)點所需時間或距離；,7.2 路由算法（29）,每隔一段時間，路由器向所有鄰居結(jié)點發(fā)送它到每個目的結(jié)點的距離表，同時它也接收每個鄰居結(jié)點發(fā)來的距離表； 鄰居結(jié)點X向路由器Y發(fā)來的表中，X到路由器Zi的距離為Li，路由器Y到X的距離為m，則路由器Y經(jīng)過X到Zi的距離為Li + m。根據(jù)不同鄰居發(fā)來的信息，計算Li + m，并取最小值，更新Y路由器的路由表； 注意：Y路由器中的老路由表在計算中不被使用,路由器,J從它的四個鄰居路由器上收到的向量,J的新路由表,A,8,20,A,28,I,20,H,17,I,30,I,18,H,12,H,10,I,0,6,K,15,K,7.2 路由算法（30）,無限計算問題 算法的缺陷： 對好消息反應迅速(好消息：網(wǎng)絡上加入一個路由器） 對壞消息反應遲鈍（壞消息：網(wǎng)絡上減少一個路由器）,對好消息反應迅速,對壞消息反應遲鈍：引起無窮計算問題,7.2 路由算法（31）,為什么會出現(xiàn)無窮計算問題： 因為路由器A通過路由器B才能到達路由器C，雖然路由器A已經(jīng)下線，C仍然向B報告了以前C到A的距離。 解決無窮計算問題的方法：水平分裂算法 工作過程與距離向量算法相同，區(qū)別在于到X的距離不向真正通向X的鄰居結(jié)點報告，使得壞消息傳播的也快。,7.2 路由算法（32）,7.2 路由算法（33）,雖然廣泛使用，但有時候會失敗。,主要內(nèi)容（2）,7.1 網(wǎng)絡層概述 7.2 路由算法 7.2.1 最優(yōu)化原則 7.2.2 最短路徑路由算法 7.2.3 洪泛算法 7.2.4 基于流量的路由算法 7.2.5 距離向量路由算法 7.2.6 鏈路狀態(tài)路由算法 7.2.7 分層路由 7.2.8 移動主機的路由,7.2 路由算法（34）,7.2.6 鏈路狀態(tài)路由算法（ LS：Link State Routing） 距離向量路由算法的主要問題 選擇路由時，沒有考慮線路帶寬； 路由收斂速度慢(無窮計算)。,7.2 路由算法（35）,鏈路狀態(tài)路由算法 發(fā)現(xiàn)鄰居結(jié)點，并學習它們的網(wǎng)絡地址； 測量到每個鄰居結(jié)點的延遲或開銷； 將所有學習到的內(nèi)容封裝成一個包； 將這個包發(fā)送給所有其它路由器； 每個路由器獨立計算到其它路由器的最短路徑。,返回,7.2 路由算法（36）,發(fā)現(xiàn)鄰居結(jié)點，并學習它們的網(wǎng)絡地址； 路由器啟動后，通過發(fā)送HELLO包發(fā)現(xiàn)鄰居結(jié)點； 兩個或多個路由器連在一個LAN時,引入人工結(jié)點；,7.2 路由算法（37）,7.2 路由算法（38）,測量到每個鄰居結(jié)點的延遲或開銷； 一種直接的方法是：發(fā)送一個要對方立即響應的ECHO包，來回時間除以2即為延遲。,7.2 路由算法（39）,將所有學習到的內(nèi)容封裝成一個包； 包以發(fā)送方的標識符開頭，后面是序號、年齡和一個鄰居結(jié)點列表； 列表中對應每個鄰居結(jié)點，都有發(fā)送方到它們的延遲或開銷； 鏈路狀態(tài)包定期創(chuàng)建或發(fā)生重大事件時創(chuàng)建。,7.2 路由算法（40）,7.2 路由算法（41）,將這個包發(fā)送給所有其它路由器； 基本思想： 洪泛鏈路狀態(tài)包，為控制洪泛，每個包包含一個序號，每次發(fā)送新包時加1。 路由器記錄信息對(源路由器，序號)，當一個鏈路狀態(tài)包到達時，若是新的，則分發(fā)； 若是重復的，則丟棄； 若序號比路由器記錄中的最大序號小，則認為過時而丟棄；,7.2 路由算法（42）,第4步中存在的問題 序號循環(huán)使用會混淆 路由器崩潰； 序號出錯；,7.2 路由算法（43）,解決這些問題的辦法 序號循環(huán)使用會混淆，解決辦法：使用32位序號； 路由器崩潰后，序號重置； 增加年齡（age）域，每秒鐘年齡減1，為零則丟棄。 鏈路狀態(tài)包到達后，延遲一段時間，并與其它已到達的來自同一路由器的鏈路狀態(tài)包比較序號，丟棄重復包，保留新包； 序號出錯 鏈路狀態(tài)包需要應答；,7.2 路由算法（44）,計算到每個其它路由器的最短路徑。 根據(jù)Dijkstra算法計算最短路徑； 實用協(xié)議 Internet網(wǎng)絡協(xié)議：內(nèi)部網(wǎng)關路由協(xié)議開放最短路徑優(yōu)先OSPF（Open Shortest Path First） IS-IS,7.2 路由算法（45）,距離向量算法（DV）和鏈路狀態(tài)算法（LS）的比較 路由信息的復雜性 DV 僅在鄰居節(jié)點之間交換 LS 路由信息向全網(wǎng)發(fā)送 N節(jié)點，E個連接的情況下，每個節(jié)點發(fā)送O(nE)的報文,7.2 路由算法（46）,收斂（Convergence）速度 DV 收斂時間不定：可能會出現(xiàn)路由循環(huán) LS 使用最短路徑優(yōu)先算法，算法復雜度為O(n2) （n個結(jié)點（不包括源結(jié)點），需要n*(n+1)/2 次比較），如果使用更有效的實現(xiàn)方法，算法復雜度可以達到O(nlogn) 可能存在路由振蕩（oscillations）,7.2 路由算法（47）,健壯性: 如果路由器不能正常工作會發(fā)生什么? DV 結(jié)點會廣播錯誤的路徑開銷 每個結(jié)點的路由表被別的結(jié)點使用，錯誤會傳播到全網(wǎng) LS 結(jié)點會廣播錯誤的鏈路開銷 每個結(jié)點只計算自己的路由表,主要內(nèi)容（2）,7.1 網(wǎng)絡層概述 7.2 路由算法 7.2.1 最優(yōu)化原則 7.2.2 最短路徑路由算法 7.2.3 洪泛算法 7.2.4 基于流量的路由算法 7.2.5 距離向量路由算法 7.2.6 鏈路狀態(tài)路由算法 7.2.7 分層路由 7.2.8 移動主機的路由,7.2 路由算法（48）,7.2.7 分層路由（Hierarchical Routing） 網(wǎng)絡規(guī)模增長帶來的問題 路由器中的路由表增大； 路由器為選擇路由而占用的內(nèi)存、CPU時間和網(wǎng)絡帶寬增大。,7.2 路由算法（49）,分層路由 分而治之的思想； 根據(jù)需要，將路由器分成區(qū)域（regions）、聚類（clusters）、區(qū)（zones）和組（groups） Fig. 5-17，路由表由17項減為7項。 分層路由帶來的問題 路由表中的路由不一定是最優(yōu)路由。,7.2 路由算法（50）,主要內(nèi)容（2）,7.1 網(wǎng)絡層概述 7.2 路由算法 7.2.1 最優(yōu)化原則 7.2.2 最短路徑路由算法 7.2.3 洪泛算法 7.2.4 基于流量的路由算法 7.2.5 距離向量路由算法 7.2.6 鏈路狀態(tài)路由算法 7.2.7 分層路由 7.2.8 移動主機的路由,7.2 路由算法（51）,7.2.8 移動主機的路由 需要解決的問題 為了能夠?qū)?shù)據(jù)包轉(zhuǎn)發(fā)給移動主機，網(wǎng)絡必須首先要找到移動的主機。 網(wǎng)絡結(jié)構(gòu)示意圖,7.2 路由算法（52）,一些基本概念,移動用戶（mobile users）：包括位置發(fā)生變化，通過固定方式或移動方式與網(wǎng)絡連接的兩類用戶,家鄉(xiāng)位置（home location）：所有用戶都有一個永久的家鄉(xiāng)位置，用一個地址來標識；,外部代理（foreign agent）：每個區(qū)域（一個LAN或一個wireless cell）有一個或多個外部代理，它們記錄正在訪問該區(qū)域的移動用戶；,家鄉(xiāng)代理（home agent）：每個區(qū)域有一個家鄉(xiāng)代理，負責記錄家鄉(xiāng)在該區(qū)域，但是目前正在訪問其它區(qū)域的用戶。,7.2 路由算法（53）,外部代理定期廣播聲明自己的存在和地址的包，新到達的移動主機接收該信息；若移動用戶未能收到該信息，則移動主機廣播包，詢問外部代理的地址,移動主機向外部代理注冊，告知其家鄉(xiāng)地址、目前的數(shù)據(jù)鏈路層地址和一些安全信息；,外部代理與移動主機的家鄉(xiāng)代理聯(lián)系，告知移動主機的目前位置、自己的網(wǎng)絡地址和一些安全信息；,家鄉(xiāng)代理檢查安全信息，通過，則給外部代理確認;,外部代理收到確認后，在登記表中加入一項，并通知移動主機注冊成功。,移動用戶進入一個新區(qū)域時，必須首先向外部代理注冊,7.2 路由算法（54）,移動用戶的路由轉(zhuǎn)發(fā)過程,當一個包發(fā)給移動用戶時，首先被轉(zhuǎn)發(fā)到用戶的家鄉(xiāng)局域網(wǎng)；,該包到達用戶的家鄉(xiāng)局域網(wǎng)后，被家鄉(xiāng)代理接收，家鄉(xiāng)代理查詢移動用戶的新位置和與其對應的外部代理的地址；,家鄉(xiāng)代理采用隧道技術(shù)，將收到的包作為凈荷封裝到一個新包中，發(fā)給外部代理；,家鄉(xiāng)代理告訴發(fā)送方，發(fā)給移動用戶的后續(xù)包作為凈荷封裝成包直接發(fā)給外部代理；,外部代理收到包后，將凈荷封裝成數(shù)據(jù)鏈路幀發(fā)給移動用戶。,主要內(nèi)容（2）小結(jié)（1）,7.1 網(wǎng)絡層概述 7.2 路由算法 7.2.1 最優(yōu)化原則 7.2.2 最短路徑路由算法 7.2.3 洪泛算法 7.2.4 基于流量的路由算法 7.2.5 距離向量路由算法 7.2.6 鏈路狀態(tài)路由算法 7.2.7 分層路由 7.2.8 移動主機的路由,主要內(nèi)容（2）小結(jié)（2）,最優(yōu)化原則 路由算法的目的是找出并使用匯集樹。 靜態(tài)路由算法 最短路徑路由算法 洪泛算法 基于流量的路由算法,主要內(nèi)容（2）小結(jié)（3）,動態(tài)路由算法 距離向量路由算法 將自己（路由結(jié)點）對全網(wǎng)拓撲結(jié)構(gòu)的認識告訴給鄰居 無窮計算問題，水平分裂算法 鏈路狀態(tài)路由算法 將自己（路由結(jié)點）對鄰居的認識洪泛給全網(wǎng) 分層路由 移動主機的路由,主要內(nèi)容（3）,7.3 擁塞控制算法 7.3.1 擁塞控制的基本原理 7.3.2 擁塞控制算法 7.4 網(wǎng)絡互連 7.4.1 級聯(lián)虛電路 7.4.2 無連接網(wǎng)絡互連 7.4.3 隧道技術(shù) 7.4.4 互聯(lián)網(wǎng)路由 7.4.5 分段 7.4.6 防火墻,主要內(nèi)容（3）,7.3 擁塞控制算法 7.3.1 擁塞控制的基本原理 7.3.2 擁塞控制算法,7.3 擁塞控制算法（1）,擁塞（congestion） 網(wǎng)絡上有太多的包時，性能會下降，這種情況稱為擁塞。 擁塞產(chǎn)生的原因 多個輸入對應一個輸出； 慢速處理器； 低帶寬線路。,7.3 擁塞控制算法（2）,解決辦法 針對某個因素的解決方案，只能對提高網(wǎng)絡性能起到一點點好處，甚至可能僅僅是轉(zhuǎn)移了影響性能的瓶頸； 需要全面考慮各個因素。,7.3 擁塞控制算法（3）,擁塞控制與流量控制的差別 擁塞控制（congestion control）需要確保通信子網(wǎng)能夠承載用戶提交的通信量，是一個全局性問題，涉及主機、路由器等很多因素； 流量控制（flow control）與點到點的通信量有關，主要解決快速發(fā)送方與慢速接收方的問題，是局部問題，一般都是基于反饋進行控制的。,發(fā)送的分組,轉(zhuǎn)發(fā)的分組,子網(wǎng)的最大傳輸容量,7.3 擁塞控制算法（4）,7.3.1 擁塞控制的基本原理 根據(jù)控制論，擁塞控制方法分為兩類 開環(huán)控制 通過好的設計來解決問題，避免擁塞發(fā)生； 擁塞控制時，不考慮網(wǎng)絡當前狀態(tài)。 閉環(huán)控制 基于反饋機制； 工作過程 監(jiān)控系統(tǒng)，發(fā)現(xiàn)何時何地發(fā)生擁塞； 把發(fā)生擁塞的消息傳給能采取動作的站點 調(diào)整系統(tǒng)操作，解決問題。,7.3 擁塞控制算法（5）,衡量網(wǎng)絡是否擁塞的參數(shù) 缺乏緩沖區(qū)造成的丟包率； 平均隊列長度； 超時重傳的包的數(shù)目； 平均包延遲； 包延遲變化（Jitter）。,7.3 擁塞控制算法（6）,反饋方法 向負載發(fā)生源發(fā)送一個告警包； 包結(jié)構(gòu)中保留一個位或域用來表示發(fā)生擁塞，一旦發(fā)生擁塞，路由器將所有的輸出包置位，向鄰居告警； 主機或路由器主動地、周期性地發(fā)送探報（probe），查詢是否發(fā)生擁塞。,主要內(nèi)容（3）,7.3 擁塞控制算法 7.3.1 擁塞控制的基本原理 7.3.2 擁塞控制算法,7.3 擁塞控制算法（7）,7.3.2 擁塞控制算法 擁塞預防策略 流量整形（Traffic Shaping） 流說明（Flow Specification） 虛電路子網(wǎng)中的擁塞控制 抑制包（Choke Packets） 加權(quán)公平隊列（Weighted Fair Queueing） 逐跳抑制包（Hop-by-Hop Choke Packets） 負載丟棄（Load Shedding）,7.3 擁塞控制算法（8）,擁塞預防策略 開環(huán)控制 影響擁塞的網(wǎng)絡設計策略,7.3 擁塞控制算法（9）,7.3 擁塞控制算法,7.3 擁塞控制算法（7）,7.3.2 擁塞控制算法 擁塞預防策略 流量整形（Traffic Shaping） 流說明（Flow Specification） 虛電路子網(wǎng)中的擁塞控制 抑制包（Choke Packets） 加權(quán)公平隊列（Weighted Fair Queueing） 逐跳抑制包（Hop-by-Hop Choke Packets） 負載丟棄（Load Shedding）,7.3 擁塞控制算法（10）,流量整形（Traffic Shaping） 開環(huán)控制 基本思想 造成擁塞的主要原因是網(wǎng)絡流量通常是突發(fā)性的； 強迫包以一種可預測的速率發(fā)送； 在ATM網(wǎng)中廣泛使用。,7.3 擁塞控制算法（11）,漏桶算法（The Leaky Bucket Algorithm） 將用戶發(fā)出的不平滑的數(shù)據(jù)包流轉(zhuǎn)變成網(wǎng)絡中平滑的數(shù)據(jù)包流； 可用于固定包長的協(xié)議，如ATM；也可用于可變包長的協(xié)議，如IP，使用字節(jié)計數(shù)； 無論負載突發(fā)性如何，漏桶算法強迫輸出按平均速率進行，不靈活。,7.3 擁塞控制算法（12）,令牌桶算法（The Token Bucket Algorithm） 漏桶算法不夠靈活，因此加入令牌機制； 基本思想：漏桶存放令牌，每T秒產(chǎn)生一個令牌，令牌累積到超過漏桶上界時就不再增加。包傳輸之前必須獲得一個令牌，傳輸之后刪除該令牌；,7.3 擁塞控制算法（13）,漏桶算法與令牌桶算法的區(qū)別 流量整形策略不同：漏桶算法不允許空閑主機積累發(fā)送權(quán)，以便以后發(fā)送大的突發(fā)數(shù)據(jù)；令牌桶算法允許，最大為桶的大小。 漏桶中存放的是數(shù)據(jù)包，桶滿了丟棄數(shù)據(jù)包；令牌桶中存放的是令牌，桶滿了丟棄令牌，不丟棄數(shù)據(jù)包。,漏桶算法/令牌桶算法比較,時間t,流量,漏桶輸入的流量,25MB/s 持續(xù)40ms,漏桶輸出的流量,25,漏桶算法,25MB/s 持續(xù)40ms,令牌桶輸出的流量,容量為250KB的令牌桶算法,25MB/s 持續(xù)40ms,令牌桶輸出的流量,容量為500KB的令牌桶算法,25MB/s 持續(xù)40ms,令牌桶輸出的流量,容量為750KB的令牌桶算法,7.3 擁塞控制算法（14）,漏桶/令牌桶組合方法：,一般設定為漏桶的速率比令牌桶的最低速率大，比網(wǎng)絡的最大速率小。,25MB/s 持續(xù)40ms,容量為500KB的令牌桶+10MB/s的漏桶,7.3 擁塞控制算法（15）,令牌桶輸出的流量,7.3 擁塞控制算法（16）,流說明（Flow Specification） 當發(fā)送者、接收者和子網(wǎng)都達到一致性后，通信量整形才能發(fā)揮最佳效果。 要達成一致，必須以一種精確的方式來通知各方，說明通信量模式，即采用流說明的方式。,7.3 擁塞控制算法（17）,一個數(shù)據(jù)流的發(fā)送方、接收方和通信子網(wǎng)三方認可的、描述發(fā)送數(shù)據(jù)流的模式和希望得到的服務質(zhì)量的數(shù)據(jù)結(jié)構(gòu)，稱為流說明。 對發(fā)送方的流說明，子網(wǎng)和接收方可以做出三種答復：同意、拒絕、其它建議。,7.3 擁塞控制算法（18）,一個流說明的例子,7.3 擁塞控制算法（19）,虛電路子網(wǎng)中的擁塞控制 許可控制（admission control），基本思想：一旦發(fā)生擁塞，在問題解決之前，不允許建立新的虛電路； 另一種方法是發(fā)生擁塞后可以建立新的虛電路，但要繞開發(fā)生擁塞的地區(qū)； 資源預留：建立虛電路時，主機與子網(wǎng)達成協(xié)議，子網(wǎng)根據(jù)協(xié)議在虛電路上為此連接預留資源。,7.3 擁塞控制算法（20）,7.3 擁塞控制算法（21）,抑制包（Choke Packets） 基本思想 路由器監(jiān)控輸出線路及其它資源的利用情況，超過某個閾值，則此資源進入警戒狀態(tài)； 每個新包到來，檢查它的輸出線路是否處于警戒狀態(tài)； 若是，則向源主機發(fā)送抑制包，包中指出發(fā)生擁塞的目的地址。同時將原包打上標記（為了以后不再產(chǎn)生抑制包），正常轉(zhuǎn)發(fā)；,7.3 擁塞控制算法（22）,源主機收到抑制包后，按一定比例減少發(fā)向特定目的地的流量，并在固定時間間隔內(nèi)忽略指示同一目的地的抑制包。然后開始監(jiān)聽，若此線路仍然擁塞，則主機在固定時間內(nèi)減輕負載、忽略抑制包；若在監(jiān)聽周期內(nèi)沒有收到抑制包，則增加負載； 通常采用的流量增減策略是：減少時，按一定比例減少，保證快速解除擁塞；增加時，以常量增加，防止很快導致?lián)砣?7.3 擁塞控制算法（23）,使用抑制包的方法的問題： 源端主機是否采取行動是自愿的，假設一個路由器由于被多個主機超量發(fā)送的流量而形成擁塞；路由器會向所有的源端主機都發(fā)送抑制包； 有些主機可能會減慢發(fā)送速度，但有些主機不一定會減慢發(fā)送速度；結(jié)果是遵守規(guī)則的主機反而得到了比以前少的帶寬。 解決這種問題的辦法是采用加權(quán)公平隊列,7.3 擁塞控制算法（24）,加權(quán)