1、第五章 動態(tài)路由選擇協(xié)議,課程內容,路由選擇協(xié)議基礎 距離矢量路由選擇協(xié)議 鏈路狀態(tài)路由選擇協(xié)議 內部和外部網(wǎng)關協(xié)議,路由選擇協(xié)議基礎,發(fā)送網(wǎng)絡可達信息 接收可達信息 記錄信息及決策最優(yōu)路由 響應、修正和通告拓撲變化 對所有路由選擇協(xié)議來說，共有的幾個問題是路徑決策、度量、收斂和負載均衡。,路徑決策,1,確認直接網(wǎng)絡,加入路由表,3,加入報文,1.將的信息傳遞給嗎？ 2.應走哪條路徑到達網(wǎng)絡 192.168.4.0？ 3.如何確保所有路由器收到所 有路由信息？如何確保不會無 休止循環(huán)？ ,度量,最優(yōu)路徑的選擇 不同協(xié)議有不同的度量標準 RIP跳數(shù) IGRB帶寬和時延,度量標準,跳數(shù)(Hop c

2、ount)分組在到達目的地前所必須經過的路由器的數(shù)量。 帶寬(Bandwidth)固定的時間可傳輸?shù)臄?shù)據(jù)數(shù)量 。 負載(Load)網(wǎng)絡資源（如路由器或鏈路）上的活動量。 時延(Delay)從信號源到目的地所需要的時間長度。 可靠性(Reliability)通常指每個網(wǎng)絡鏈路的出錯率。 代價(Cost)一個任意的值，通常以帶寬、金錢的花銷或其他衡量標準為基礎。,收斂,Router A,Router B,Router C,192.168.2.1/24,192.168.7.1/24,192.168.1.1/24,192.168.1.2/24,192.168.3.1/24,192.168.3.2/24

3、,192.168.6.1/24,192.168.6.2/24,192.168.4.1/24,192.168.5.1/24,1,2,3,1,2,3,路由環(huán)路,所有路由選擇表都達到一致狀態(tài)的過程叫做收斂。,負載均衡,Router A,Router B,Router C,192.168.2.1/24,192.168.7.1/24,192.168.1.1/24,192.168.1.2/24,192.168.3.1/24,192.168.3.2/24,192.168.6.1/24,192.168.6.2/24,192.168.4.1/24,192.168.5.1/24,1,2,2,3,1,3,等代價或不

4、等代價 基于報文或基于目標地址,距離矢量路由選擇協(xié)議,以矢量（距離，方向）的方式通告 定期更新(10s90s) 鄰居 廣播更新 包含整個路由表,距離矢量依照傳聞進行路徑選擇,路由器從收集到的源信息中選擇到達目標地址的最佳路徑,A,B,C,10.1.0.0,10.2.0.0,10.3.0.0,10.4.0.0,E0,S0,S0,S1,S0,E0,距離矢量依照傳聞進行路徑選擇,路由器從收集到的源信息中選擇到達目標地址的最佳路徑,A,B,C,10.1.0.0,10.2.0.0,10.3.0.0,10.4.0.0,E0,S0,S0,S1,S0,E0,距離矢量依照傳聞進行路徑選擇,路由器從收集到的源信息

5、中選擇到達目標地址的最佳路徑,以時間驅動,更新路由表,更新路由表,B,A,路由失效計時器,更新路由表,B,A,X,每一個節(jié)點管理著與之相連的所有網(wǎng)絡,路 由 環(huán) 路,緩慢的收斂容易造成路由信息的不一致 的更新計時器觸發(fā)之前的更新報文到了,X,路 由 環(huán) 路,路由器C 推斷到達10.4.0.0 網(wǎng)絡的最好路徑是通過路由器B,X,路 由 環(huán) 路,路由器 A 根據(jù)錯誤的信息升級它的路由表,X,路 由 環(huán) 路,無 限 計 數(shù),10.4.0.0 網(wǎng)絡的數(shù)據(jù)將在路由器 A, B, 和 C 之間循環(huán) 10.4.0.0 網(wǎng)絡的跳數(shù)將無限大,X,解決方法：水平分割,不發(fā)送從該接口接收到的路由信息 不能解決兩臺路

6、由器以上的情況 減少資源浪費,X,X,X,解決方法：路由毒化,路由器將該路由信息的跳數(shù)標記為無限大并且廣播出去，顯式地告知相鄰路由器某項路由已經無效了。,X,解決方法：毒性逆轉,接受路由毒化消息的路由器并不遵從水平分割的原則，而是將這條消息轉發(fā)給所有相鄰路由器，以實現(xiàn)最快的收斂。,X,PoisonReverse,解決方法：定義最大跳數(shù),指定最大跳數(shù)來防止路由回環(huán),X,解決方法：觸發(fā)更新,當路由表發(fā)生變化時路由器不等待更新計時器超時，立即發(fā)送更新信息 觸發(fā)更新減少了處理時間和對網(wǎng)絡帶寬的占用,解決方法：抑制計時器,路由器在Hold-Down時間內將該條記錄標記為possibly down以使其它

7、路由器能夠重新計算網(wǎng)絡結構的變化 例如路由器不再接收關于同一目的網(wǎng)絡的更遠路由更新。即如果路由器從一個網(wǎng)絡得知一條路徑失效，然后，立即在另一個網(wǎng)段上得知這個路由有效，這條有效的信息往往是不正確的，是沒有及時更新的結果。,鏈路狀態(tài)協(xié)議,傳遞最佳的路徑信息給其它的路由器,LSA數(shù)據(jù)包,SPF 運算,拓補結構數(shù)據(jù),最佳路由信息,路由表,C,A,D,B,1,建立鄰接關系,2,2,2,2,泛洪,3,4,5,鄰居,路由器每隔一定的時間發(fā)送一次Hello報文，用以建立、保持鄰接（Neighbors）關系； 如果在選定時間內沒有從鄰居收到Hello報文，那么認為鄰居不可達，解除鄰接關系； 典型的Hello報文

8、交換間隔為10s，典型的死亡周期是報文交換間隔的4倍,鏈路狀態(tài)泛洪擴散,距離矢量是先運行算法更新路由表再發(fā)送 鏈路狀態(tài)是立刻轉發(fā)LSA 排序和老化,序列號,D,F,E,C,A,B,172.22.4.0,X,t0,t0,t1,t3,t2,t1,數(shù)據(jù)庫中已經存在些LSA且序列號相同時丟棄 如果信息相同但序列號更大，更新數(shù)據(jù)庫并泛洪擴散些SLA,線性序列號空間,使用一個大的序列號空間232 如果路由器無法記得上次使用的序列號，它必須重新使用1。 最新的LSA被認為更老而被忽略，一直等待。 鄰居向該路由器發(fā)送自己保存的LSA和序列號。 最近使用的序列號不能接近上界。,循環(huán)序列號空間,認為a比b更新(a

9、更大) ab且a-bn/2 an/2,可能出現(xiàn)的故障,假設一臺路由器發(fā)送了3個相同且序列號為44(101100)的LSA然后離線，一個鄰居也發(fā)生了故障，丟失了第2個和第3個LSA的幾個比特。 假設路由器重啟后之前用到的序列號是48,棒棒糖形序列號空間,包括一個線性組件和一個圓形組件； 路由器重啟時將從小于其它所有數(shù)的a開始； 鄰居若保留了以前的序列號b，它將b發(fā)送給；將跳至該序列號。 保證在收到之前的序列號前不會用光序列號。 用完了棒部分就進入糖部分。,N=231,-N+1,0,N-2,老化,年齡字段LSA被創(chuàng)建時被置為0，擴散時每經過一臺路由器都會增加年齡。 MaxAgeDiff當路由器收到

10、一個序列號重復的LSA時會比對兩個年齡的差值，如果差值超過MaxAgeDiff定義的數(shù)值，則認為網(wǎng)絡發(fā)生異常。典型的數(shù)值為15min。 MaxAge 當LSA駐留在路由器數(shù)據(jù)庫時時，年齡值會不停的增加，當達到MaxAge的時候，路由器從數(shù)據(jù)庫中刪除相關記錄，并泛洪該lsa。ospf定義的MaxAge為1hour。 LSRefreshTime 用來復位MaxAge的值。ospf定義的lsfrfreshtime為30min,鏈路狀態(tài)數(shù)據(jù)庫,路由器鏈路信息使用路由器ID、鄰居ID和代價通告路由器的鄰居路由器，這里的代價是發(fā)送LSA路由器到其鄰居的代價； 末梢網(wǎng)絡信息使用路由器ID、網(wǎng)絡ID和代價通告

11、路由器直接連接的末梢網(wǎng)絡(沒有鄰居的網(wǎng)絡)；,鏈路狀態(tài)路由協(xié)議算法,(一）網(wǎng)絡的拓樸結構,（四）每臺路由器分別以自己為根節(jié)點計算最小生成樹,（三）由鏈路狀態(tài)數(shù)據(jù)庫得 到的帶權有向圖,C,A,B,D,1,2,3,5,RTC,RTD,3,2,1,5,RTB,RTA,區(qū)域,1、數(shù)據(jù)庫會消耗大量的內存 2、復雜的算法需要更多的cpu資源 3、消耗大量的帶寬 當一個網(wǎng)絡被劃分為多個區(qū)域時，在一個區(qū)域內的路由器僅需要在本區(qū)域擴散LSA，因而只需要維護本區(qū)域的鏈路狀態(tài)數(shù)據(jù)庫。數(shù)據(jù)庫越小，意味著需要內存越少，運行SPF算法需要的CPU周期也越少。如果拓撲改變頻繁發(fā)生，引起的擴散將被限制在不穩(wěn)定的區(qū)域！ 區(qū)域邊

12、界路由器是連接兩個區(qū)域的路由器，它屬于所連接的兩個區(qū)域，而且必須為每個區(qū)域維護各自的拓撲數(shù)據(jù)庫！,內部和外部網(wǎng)關協(xié)議,路由協(xié)議有兩大類： 內部網(wǎng)關協(xié)議（Interior Gateway Protocol，IGP），內部網(wǎng)關協(xié)議運行在一個自治系統(tǒng)（Autonomous System，AS）中 ，一個ISP或一個公司的廣域網(wǎng)就是一個自治系統(tǒng) 。 外部網(wǎng)關協(xié)議（Exterior Gateway Protocol，EGP），EGP運行在各個自治系統(tǒng)之間,Autonomous System 100,Autonomous System 200,IGPs: RIP, IGRP,EGPs: BGP,自治系統(tǒng)：內部與外部路由協(xié)議,自治系統(tǒng)指一個具有統(tǒng)一管理機構、統(tǒng)一路由策略的網(wǎng)絡 IGPs 操作在自治系統(tǒng)