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

1、1動(dòng)態(tài)路由選擇協(xié)議動(dòng)態(tài)路由選擇協(xié)議2上一節(jié)課堂作業(yè)回顧上一節(jié)課堂作業(yè)回顧l什么是子網(wǎng)？在IP環(huán)境下為什么使用子網(wǎng)？l請(qǐng)問(wèn)接口上配置IP地址192.168.13.175,掩碼255.255.255.240會(huì)有問(wèn)題嗎？若有，有何問(wèn)題？lIPv4和IPv6的分段有哪些不同之處？l什么是匯總路由和浮動(dòng)靜態(tài)路由？子網(wǎng)化是對(duì)A、B、C類(lèi)地址進(jìn)行子劃分。如果沒(méi)有使用子網(wǎng)，A、B、C類(lèi)的主IP地址的網(wǎng)絡(luò)部分只能表示一個(gè)數(shù)據(jù)鏈路。子網(wǎng)化使用主IP地址中的一些主機(jī)位作為網(wǎng)絡(luò)位，允許一個(gè)單獨(dú)的主地址被劃分為多個(gè)網(wǎng)絡(luò)地址。掩碼255.255.255.240可知網(wǎng)絡(luò)位是28位，而192.168.13.175/28的主機(jī)

2、號(hào)是1111，因此這是該子網(wǎng)192.168.13.160/28的廣播地址。除了分段擴(kuò)展頭標(biāo)外，IPv6和IPv4的分段的重要不同是，IPv6路由器不對(duì)數(shù)據(jù)包進(jìn)行分段。它會(huì)告訴始發(fā)主機(jī)要么對(duì)數(shù)據(jù)包進(jìn)行分段，要么確保不發(fā)起太大的數(shù)據(jù)包。匯總路由是一個(gè)單獨(dú)的路由表項(xiàng)，指向多個(gè)子網(wǎng)或IP地址。對(duì)于靜態(tài)路由，匯總路由等減少需要配置的靜態(tài)路由表項(xiàng)。浮動(dòng)靜態(tài)路由是達(dá)到目的地址的備用路由，它的管理距離被設(shè)得很高，這樣只有當(dāng)點(diǎn)優(yōu)先級(jí)高的路由均不可用時(shí)，它才能利用。3outlinel路由選擇協(xié)議基礎(chǔ)l距離矢量路由選擇協(xié)議l鏈路狀態(tài)路由選擇協(xié)議l內(nèi)部和外部網(wǎng)關(guān)協(xié)議l靜態(tài)或動(dòng)態(tài)路由選擇動(dòng)態(tài)路由選擇協(xié)議目的：n執(zhí)行路徑

3、決策和路由表更新功能；n在最優(yōu)路徑不可用時(shí)決策下一條最優(yōu)路徑。與靜態(tài)路由選擇協(xié)議相比的優(yōu)勢(shì)：n能夠緩解網(wǎng)絡(luò)拓?fù)渥兓瘞?lái)的影響。4路由選擇協(xié)議基礎(chǔ)路由選擇協(xié)議基礎(chǔ)l所有路由選擇協(xié)議都是圍繞一種算法而構(gòu)建的，一個(gè)路由算法至少指明以下內(nèi)容：l向其他路由器傳送網(wǎng)絡(luò)可達(dá)性信息的過(guò)程；l從其他路由器接收可達(dá)性信息的過(guò)程；l基于現(xiàn)有可達(dá)性信息決策最優(yōu)路由的過(guò)程以及在路由表中記錄這些信息的過(guò)程；l響應(yīng)、修正和通告網(wǎng)絡(luò)中拓?fù)渥兓倪^(guò)程。l所有路由選擇協(xié)議共同存在的問(wèn)題：l路徑?jīng)Q策l度量（指標(biāo)）l收斂l負(fù)載均衡5路徑?jīng)Q策路徑?jīng)Q策路由器A、B、C所做工作：n檢測(cè)并將直連網(wǎng)絡(luò)相關(guān)信息保存到路由表中；n封裝并發(fā)送路由選

4、擇更新信息；n保存或更新接收到的關(guān)于其他路由器的路由表信息。路由器處理信息時(shí)所存在的問(wèn)題：n是否將接收到的更新信息轉(zhuǎn)發(fā)給其他路由器？A(B) Cn若不轉(zhuǎn)發(fā)，則無(wú)法實(shí)現(xiàn)信息共享，如下若B、C不存在鏈路，因此A必須轉(zhuǎn)發(fā)；n對(duì)于路由器B和C的子網(wǎng)192.168.4.0中的分組，A應(yīng)該轉(zhuǎn)發(fā)給誰(shuí)？（最優(yōu)路徑）n什么機(jī)制可以保證所有路由器都能接收到所有路由信息且避免這些更新信息無(wú)休止循環(huán)下去？n如果路由器共享某個(gè)直連網(wǎng)絡(luò)，那么路由器是否仍告知這些網(wǎng)絡(luò)？這些簡(jiǎn)單的問(wèn)題導(dǎo)致了協(xié)議設(shè)計(jì)的復(fù)雜性；每種路由選擇協(xié)議都必須解決這些問(wèn)題。6度量（指標(biāo)）度量（指標(biāo)）l什么是度量（指標(biāo)）？為什么需要度量？l當(dāng)有多條路徑到達(dá)

5、相同目標(biāo)網(wǎng)絡(luò)時(shí)，路由器需要一種機(jī)制來(lái)計(jì)算最優(yōu)路徑。度量(metric)是指派給路由的一種變量。l作為一種手段，度量可以按最好到最壞，或按最先選擇到最后選擇的順序?qū)β酚蛇M(jìn)行劃分。RIPEIGRPn跳數(shù)：簡(jiǎn)單記錄路由器跳數(shù)。n帶寬：BwMin(Bwi)。n負(fù)載：反應(yīng)流量占用沿途鏈路帶寬的數(shù)量。n時(shí)延：分組經(jīng)過(guò)一條路徑所花費(fèi)的時(shí)間（Ddi）。n可靠性：測(cè)量鏈路在某種情況下發(fā)生故障的概率（Ppi）n代價(jià)：由管理員設(shè)置的代價(jià)cost可以反應(yīng)更優(yōu)或更差的路由7收斂收斂l動(dòng)態(tài)路由選擇協(xié)議的工作過(guò)程：l用于路由器向其他路由器通告本地的直連網(wǎng)絡(luò)；l接收并處理來(lái)自其他路由器的同類(lèi)信息；l傳遞從其他路由器接收到的信

6、息；l定義已確定的最優(yōu)路徑的度量。l路由選擇環(huán)路l在兩個(gè)或多個(gè)目標(biāo)網(wǎng)絡(luò)之間流量的持續(xù)循環(huán)過(guò)程。n所有路由器的路由表中的可達(dá)信息不一致導(dǎo)致了出現(xiàn)環(huán)路。n為了使得避免這種問(wèn)題，必須使得各路由表中的可達(dá)信息保持一致；n使得所有路由表都到達(dá)一致?tīng)顟B(tài)的過(guò)程叫做收斂。n全網(wǎng)實(shí)現(xiàn)信息共享以及所有路由器計(jì)算最優(yōu)路徑所花費(fèi)的時(shí)間總和就是收斂時(shí)間。未收斂狀態(tài)未收斂狀態(tài)8負(fù)載均衡負(fù)載均衡l目標(biāo)l有效的使用帶寬l降低網(wǎng)絡(luò)中某些鏈路的負(fù)載l手段l將流量分配到相同目標(biāo)網(wǎng)絡(luò)的多條路徑上。l方式l等代價(jià)/不等代價(jià)l基于數(shù)據(jù)包/基于目標(biāo)地址9outlinel路由選擇協(xié)議基礎(chǔ)l距離矢量路由選擇協(xié)議l鏈路狀態(tài)路由選擇協(xié)議l內(nèi)部和外

7、部網(wǎng)關(guān)協(xié)議l靜態(tài)或動(dòng)態(tài)路由選擇10距離矢量路由選擇協(xié)議距離矢量路由選擇協(xié)議l距離矢量：路由是以矢量(距離，方向距離，方向)的方式被通告出去的，其中距離是根據(jù)度量定義的，方向是根據(jù)下一跳路由器定義的。l距離矢量路由選擇協(xié)議：lIP路由選擇信息協(xié)議(RIP)lXerox網(wǎng)絡(luò)系統(tǒng)的XNS RIPlNovell的IPX RIPlCisco的IGRP和EICRP（增強(qiáng)型Internet網(wǎng)關(guān)路由協(xié)議）lDEC的DNA階段4lApple Talk的路由選擇表維護(hù)協(xié)議(RTMP)n(5,Router X)：目標(biāo)A在下一跳路由器X的方向，距本機(jī)5跳之遠(yuǎn)。n每臺(tái)路由器向鄰接路由器學(xué)習(xí)他們所觀察到的路由信息，然后再

8、向外通告自己觀察到的路由信息。n每臺(tái)路由器在信息上都依賴于鄰接路由器，而鄰接路由器又從它們的鄰接路由器學(xué)習(xí)路由。n距離矢量路由選擇有時(shí)也稱(chēng)為“依照傳聞進(jìn)行路由選擇”。11通用屬性通用屬性l路由選擇算法：路由器通過(guò)廣播整個(gè)路由表，定期向所有鄰居發(fā)送路由更新信息。l路由表相關(guān)信息包括：l定期更新l鄰居l廣播更新l全路由選擇表更新n每經(jīng)過(guò)特定時(shí)間周期就發(fā)送更新信息。n10s90sn頻率高擁塞；頻率低收斂時(shí)間n共享相同數(shù)據(jù)鏈路的路由器或者某種更高層的邏輯鄰接關(guān)系n本機(jī)鄰接路由器鄰接路由器鄰接路由器鄰接路由器n使用逐跳更新方式n路由器首次在網(wǎng)絡(luò)上被激活，如何查找其他路由器？n向廣播地址發(fā)送更新信息n廣播

9、整個(gè)路由表；n收到更新信息后，收集自己需要的信息，丟棄其他信息。12依照傳聞進(jìn)行路由選擇依照傳聞進(jìn)行路由選擇13路由失效計(jì)時(shí)器路由失效計(jì)時(shí)器n網(wǎng)絡(luò)拓?fù)渥兓?0.1.5.0子網(wǎng)發(fā)生故障路由器D將在下一個(gè)更新周期將這個(gè)網(wǎng)絡(luò)標(biāo)記為不可達(dá)并發(fā)送出去。n網(wǎng)絡(luò)拓?fù)渥兓郝酚善鱀而不是子網(wǎng)5.0發(fā)生故障呢？導(dǎo)致路由器A、B和C路由表中該項(xiàng)還在，但實(shí)際上所有通往5.0網(wǎng)絡(luò)的分組已經(jīng)不可達(dá)。n解決辦法：為路由表中的每項(xiàng)設(shè)置路由失效計(jì)時(shí)器輸入表項(xiàng)時(shí)為該表項(xiàng)設(shè)置計(jì)時(shí)器，每次收到該表項(xiàng)的更新信息時(shí)復(fù)位該計(jì)時(shí)器，否則計(jì)時(shí)器超時(shí)并標(biāo)記該表項(xiàng)為不可達(dá)，并將在下一個(gè)更新周期傳遞該信息。n計(jì)時(shí)器的周期范圍：36個(gè)更新周期n防

10、止由于網(wǎng)絡(luò)原因丟失某個(gè)更新信息n周期過(guò)長(zhǎng)網(wǎng)絡(luò)收斂速度14水平分隔水平分隔n每臺(tái)路由器在每個(gè)更新周期都要向每個(gè)鄰居發(fā)送它的整個(gè)路由表必要性? 造成資源（帶寬）的浪費(fèi)。n逆向路由：路由的指向與數(shù)據(jù)包流動(dòng)方向相反的路由。n水平分隔：一種在兩臺(tái)路由器之間阻止逆向路由的技術(shù)。n另一個(gè)優(yōu)點(diǎn)：不會(huì)把從路由器學(xué)習(xí)到的可達(dá)性信息再返回給該路由器。否則會(huì)導(dǎo)致環(huán)路的發(fā)生。n水平分隔的兩個(gè)分類(lèi)n簡(jiǎn)單水平分隔法n毒性逆轉(zhuǎn)水平分隔法n簡(jiǎn)單水平分隔法：從某接口發(fā)送的更新信息不能包含從該接口收到的更新所包含的網(wǎng)絡(luò)。n采用的是抑制信息的工作方式。n毒性逆轉(zhuǎn)水平分隔法：當(dāng)更新信息被發(fā)送出某個(gè)接口時(shí)，信息中將指定從該接口收到的更新

11、信息中獲取的網(wǎng)絡(luò)是不可達(dá)的。n改進(jìn)版本，提供更為積極的信息。n缺點(diǎn)：使更新數(shù)據(jù)包變大，可能加劇網(wǎng)絡(luò)鏈路的擁塞問(wèn)題。15其他問(wèn)題其他問(wèn)題l計(jì)數(shù)到無(wú)窮大l水平分割不能割斷網(wǎng)絡(luò)中的環(huán)路，從而會(huì)可能導(dǎo)致計(jì)數(shù)變得無(wú)窮大將跳數(shù)定義16跳為無(wú)窮大。l依然導(dǎo)致收斂速度慢。l觸發(fā)更新（快速更新）l及時(shí)發(fā)送度量的好壞信息l減少了處理時(shí)間和對(duì)網(wǎng)絡(luò)帶寬的影響l抑制計(jì)時(shí)器l目的：降低接受錯(cuò)誤路由選擇信息的可能性引入某種程度的懷疑量。l異步更新l避免同步產(chǎn)生的碰撞問(wèn)題。16outlinel路由選擇協(xié)議基礎(chǔ)l距離矢量路由選擇協(xié)議l鏈路狀態(tài)路由選擇協(xié)議l內(nèi)部和外部網(wǎng)關(guān)協(xié)議l靜態(tài)或動(dòng)態(tài)路由選擇17鏈路狀態(tài)路由選擇協(xié)議鏈路狀態(tài)路

12、由選擇協(xié)議l也稱(chēng)最短路徑優(yōu)先協(xié)議或分布式數(shù)據(jù)庫(kù)協(xié)議l基本功能l每臺(tái)路由器與它的鄰居建立聯(lián)系鄰接關(guān)系l每臺(tái)路由器向鄰居發(fā)送鏈路狀態(tài)通告LSA，LSA用來(lái)標(biāo)識(shí)該鏈路、鏈路狀態(tài)、路由器接口到鏈路的代價(jià)度量值以及鏈路所鏈接的所有鄰居，每個(gè)鄰居收到LSA后將依次向它的鄰居轉(zhuǎn)發(fā)（泛洪）l每臺(tái)路由器在數(shù)據(jù)庫(kù)中備份LSA所有節(jié)點(diǎn)的數(shù)據(jù)庫(kù)相同l完整的拓?fù)鋽?shù)據(jù)庫(kù)（鏈路狀態(tài)庫(kù)），Dijkstra算法計(jì)算最短路徑并修改路由表。n鏈路狀態(tài)協(xié)議：nOSPFnCLNS或IP ISO的中間系統(tǒng)到中間系統(tǒng)IS-ISnDEC的DNA階段5nNovell的Netware鏈路服務(wù)協(xié)議NLSP18鄰居鄰居l鄰居發(fā)現(xiàn)是建立鏈路狀態(tài)環(huán)境并

13、運(yùn)轉(zhuǎn)的第一步。l使用Hello協(xié)議發(fā)現(xiàn)鄰居l路由器IDlHello間隔：路由器宣布鄰居死亡前等待的最大周期l典型的Hello分組交換間隔10sl典型的死亡周期是分組交換間隔的4倍19鏈路狀態(tài)泛洪擴(kuò)散鏈路狀態(tài)泛洪擴(kuò)散l建立鄰接關(guān)系后，路由器開(kāi)始發(fā)送LSA。l路由器保存并同時(shí)轉(zhuǎn)發(fā)LSA加快響應(yīng)時(shí)間l泛洪擴(kuò)散：當(dāng)所有路由器收到所有LSA后，泛洪擴(kuò)散應(yīng)該停止。l泛洪擴(kuò)散的兩個(gè)重要過(guò)程l序列號(hào)l老化n路由器A鏈接的子網(wǎng)172.22.4.0發(fā)生故障，A發(fā)送LSA而在C的處理過(guò)程（發(fā)現(xiàn)相同的LSA序列號(hào)）n子網(wǎng)4.0先發(fā)生故障，ALSA(166)；馬上又好了， ALSA(167)；C的處理過(guò)程（LSA(16

14、6) LSA(167) LSA(166)）20序列號(hào)到達(dá)上限的處理辦法序列號(hào)到達(dá)上限的處理辦法l序列號(hào)放在LSA的一個(gè)固定字段內(nèi)，因此有上限。l線性序列號(hào)空間l循環(huán)序列號(hào)空間l棒棒糖形序列號(hào)空間n使用一個(gè)非常大的線性序列號(hào)空間以至于根本無(wú)法到達(dá)上限n如32位長(zhǎng)字段，可用序列號(hào)0,232，LSA/10s1361年n偶然性時(shí)間的發(fā)生（用完了）停止路由器，并等待它發(fā)出的LSA在所有數(shù)據(jù)庫(kù)中不再使用。n另一種常見(jiàn)困難：重啟序列號(hào)歸1LSA被其他路由器忽略掉n增加規(guī)則：重啟后向鄰居發(fā)送的LSA的序列號(hào)比鄰居保存的低，則鄰居返回自己保存的LSA和序列號(hào)。n序列號(hào)a和b若滿足以下任一條件，則認(rèn)為a更新（數(shù)量

15、更大）：n(1) ab且(a-b) n/2n(2) ab且(b-a) n/2n假定使用一個(gè)六位序列號(hào)空間n=64n假定兩個(gè)序列號(hào)48和18，由規(guī)則(1)可得48較新;n假定兩個(gè)序列號(hào)3和48，由規(guī)則(2)可得3較新 n在不正常網(wǎng)絡(luò)環(huán)境下，其中一臺(tái)路由器決定離線，突然發(fā)送3個(gè)相同且序列號(hào)為44(101100)的LSA，一個(gè)鄰居也發(fā)生故障，導(dǎo)致出現(xiàn)3個(gè)序列號(hào)不同的LSA并泛洪死循環(huán)網(wǎng)絡(luò)CPU超載網(wǎng)絡(luò)崩潰(44比40更新，40比8更新，8比44更新)21老化老化lLSA中包括一個(gè)用于通告年齡的字段。當(dāng)LSA被創(chuàng)建時(shí)，路由器將該字段設(shè)為0，隨著數(shù)據(jù)包的擴(kuò)散，每臺(tái)路由器都會(huì)增加通告中的年齡。l收到的LS

16、A的年齡值和最大年齡差距MaxAgeDiff比較l如尋列號(hào)相同，年齡值 MaxAgeDiff，則網(wǎng)絡(luò)異常，LSA被記錄并擴(kuò)散lLSA駐留在數(shù)據(jù)庫(kù)中，年齡也會(huì)不斷增長(zhǎng)，超過(guò)MaxAge則刪除22鏈路狀態(tài)數(shù)據(jù)庫(kù)鏈路狀態(tài)數(shù)據(jù)庫(kù)lLSA還包括兩類(lèi)通用信息l路由器鏈路信息：三元組(路由器ID,鄰居ID,代價(jià))l末梢網(wǎng)絡(luò)信息：三元組(路由器ID,網(wǎng)絡(luò)ID,代價(jià))，通告路由器直接連接的末梢（沒(méi)有鄰居網(wǎng)絡(luò)）l最短路徑優(yōu)先(SPF)算法對(duì)路由器鏈路信息進(jìn)行一次計(jì)算以建立到每臺(tái)路由器的最短路徑，然后使用末梢網(wǎng)絡(luò)信息向路由器添加網(wǎng)絡(luò)。23區(qū)域區(qū)域l一個(gè)區(qū)域是構(gòu)成一個(gè)網(wǎng)絡(luò)的路由器的一個(gè)子集l原因l必要的數(shù)據(jù)庫(kù)要求內(nèi)存的數(shù)量比距離矢量協(xié)議更多l(xiāng)復(fù)雜的算法要求CPU時(shí)間比距離矢量協(xié)議更多l(xiāng)鏈路狀態(tài)泛洪擴(kuò)散數(shù)據(jù)包對(duì)可用帶寬帶來(lái)不利的影響，特別是不穩(wěn)定的網(wǎng)絡(luò)。n區(qū)域邊界路由器：連接兩個(gè)區(qū)域的路由器，它屬于所連接的兩個(gè)區(qū)域，而且必須為每個(gè)區(qū)域維護(hù)各自的數(shù)據(jù)庫(kù)。24outlinel路由選擇協(xié)議基礎(chǔ)l距離矢量路由選擇協(xié)議l鏈路狀態(tài)路由選擇協(xié)議l內(nèi)部和外部網(wǎng)關(guān)協(xié)議l靜態(tài)或動(dòng)態(tài)路由選擇25內(nèi)部和外部網(wǎng)關(guān)協(xié)議內(nèi)部和外部網(wǎng)關(guān)協(xié)議l自主系統(tǒng)：在共同管理域下的一組運(yùn)行相同路由選擇協(xié)議的路由器。l當(dāng)前定義：在共同管理下的網(wǎng)絡(luò)。l內(nèi)部網(wǎng)關(guān)協(xié)議（IGP）：在一個(gè)自主系統(tǒng)內(nèi)運(yùn)行的路由選擇協(xié)議。l距離矢量/鏈路狀態(tài)協(xié)議l外部