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

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

2、ount)分組在到達(dá)目的地前所必須經(jīng)過的路由器的數(shù)量。 帶寬(Bandwidth)固定的時(shí)間可傳輸?shù)臄?shù)據(jù)數(shù)量 。 負(fù)載(Load)網(wǎng)絡(luò)資源（如路由器或鏈路）上的活動(dòng)量。 時(shí)延(Delay)從信號(hào)源到目的地所需要的時(shí)間長(zhǎng)度。 可靠性(Reliability)通常指每個(gè)網(wǎng)絡(luò)鏈路的出錯(cuò)率。 代價(jià)(Cost)一個(gè)任意的值，通常以帶寬、金錢的花銷或其他衡量標(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)路,所有路由選擇表都達(dá)到一致狀態(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,等代價(jià)或不

4、等代價(jià) 基于報(bào)文或基于目標(biāo)地址,距離矢量路由選擇協(xié)議,以矢量（距離，方向）的方式通告 定期更新(10s90s) 鄰居 廣播更新 包含整個(gè)路由表,距離矢量依照傳聞進(jìn)行路徑選擇,路由器從收集到的源信息中選擇到達(dá)目標(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,距離矢量依照傳聞進(jìn)行路徑選擇,路由器從收集到的源信息中選擇到達(dá)目標(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,距離矢量依照傳聞進(jìn)行路徑選擇,路由器從收集到的源信息

5、中選擇到達(dá)目標(biāo)地址的最佳路徑,以時(shí)間驅(qū)動(dòng),更新路由表,更新路由表,B,A,路由失效計(jì)時(shí)器,更新路由表,B,A,X,每一個(gè)節(jié)點(diǎn)管理著與之相連的所有網(wǎng)絡(luò),路 由 環(huán) 路,緩慢的收斂容易造成路由信息的不一致 的更新計(jì)時(shí)器觸發(fā)之前的更新報(bào)文到了,X,路 由 環(huán) 路,路由器C 推斷到達(dá)10.4.0.0 網(wǎng)絡(luò)的最好路徑是通過路由器B,X,路 由 環(huán) 路,路由器 A 根據(jù)錯(cuò)誤的信息升級(jí)它的路由表,X,路 由 環(huán) 路,無 限 計(jì) 數(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ā)送從該接口接收到的路由信息 不能解決兩臺(tái)路

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

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

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

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

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

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

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