動態(tài)路由選擇協(xié)議.ppt

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

2、ount)分組在到達目的地前所必須經(jīng)過的路由器的數(shù)量。 帶寬(Bandwidth)固定的時間可傳輸?shù)臄?shù)據(jù)數(shù)量 。 負(fù)載(Load)網(wǎng)絡(luò)資源（如路由器或鏈路）上的活動量。 時延(Delay)從信號源到目的地所需要的時間長度。 可靠性(Reliability)通常指每個網(wǎng)絡(luò)鏈路的出錯率。 代價(Cost)一個任意的值，通常以帶寬、金錢的花銷或其他衡量標(biāo)準(zhǔn)為基礎(chǔ)。,收斂,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)的過程叫做收斂。,負(fù)載均衡,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、等代價 基于報文或基于目標(biāo)地址,距離矢量路由選擇協(xié)議,以矢量（距離，方向）的方式通告 定期更新(10s90s) 鄰居 廣播更新 包含整個路由表,距離矢量依照傳聞進行路徑選擇,路由器從收集到的源信息中選擇到達目標(biāo)地址的最佳路徑,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,距離矢量依照傳聞進行路徑選擇,路由器從收集到的源信息中選擇到達目標(biāo)地址的最佳路徑,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、中選擇到達目標(biāo)地址的最佳路徑,以時間驅(qū)動,更新路由表,更新路由表,B,A,路由失效計時器,更新路由表,B,A,X,每一個節(jié)點管理著與之相連的所有網(wǎng)絡(luò),路 由 環(huán) 路,緩慢的收斂容易造成路由信息的不一致 的更新計時器觸發(fā)之前的更新報文到了,X,路 由 環(huán) 路,路由器C 推斷到達10.4.0.0 網(wǎng)絡(luò)的最好路徑是通過路由器B,X,路 由 環(huán) 路,路由器 A 根據(jù)錯誤的信息升級它的路由表,X,路 由 環(huán) 路,無 限 計 數(shù),10.4.0.0 網(wǎng)絡(luò)的數(shù)據(jù)將在路由器 A, B, 和 C 之間循環(huán) 10.4.0.0 網(wǎng)絡(luò)的跳數(shù)將無限大,X,解決方法：水平分割,不發(fā)送從該接口接收到的路由信息 不能解決兩臺路

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

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

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

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

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

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

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