距離矢量與鏈路狀態(tài)路由協(xié)議分析

1、第第1212章章 距離矢量與鏈路狀態(tài)路由協(xié)議分析距離矢量與鏈路狀態(tài)路由協(xié)議分析 周小云周小云客支新員崗前培訓(xùn)系列教材客支新員崗前培訓(xùn)系列教材前前 言言 通過對本章內(nèi)容的學(xué)習(xí)，你可以掌握距離矢量路通過對本章內(nèi)容的學(xué)習(xí)，你可以掌握距離矢量路由協(xié)議和鏈路狀態(tài)路由協(xié)議的基礎(chǔ)知識，并了解這些由協(xié)議和鏈路狀態(tài)路由協(xié)議的基礎(chǔ)知識，并了解這些協(xié)議的算法和原理。協(xié)議的算法和原理。 提提 綱綱q距離矢量路由協(xié)議簡介距離矢量路由協(xié)議簡介q距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析q鏈路狀態(tài)路由協(xié)議簡介鏈路狀態(tài)路由協(xié)議簡介q鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析距離矢量路由協(xié)議簡介距離矢量路由協(xié)議簡介距離矢量 (Di

2、stance-Vector)距離矢量路由選擇協(xié)議也稱為B e l l m a n - F o r d協(xié)議。距離矢量路由協(xié)議主要有： RIPV1 , RIPV2 , IGRP距離矢量路由器定期向相鄰的路由器發(fā)送它們的整個路由選擇表(routing table)。距離相鄰路由器在從相鄰路由器接收到的信息的基礎(chǔ)之上建立自己的路由選擇信息表。距離矢量路由協(xié)議簡介距離矢量路由協(xié)議簡介距離矢量路由選擇是一種路由選擇協(xié)議算法。距離矢量路由協(xié)議有一個嚴(yán)重的缺點(diǎn)，緩慢的收斂時間過程會造成路由回路（Routing Loop）。解決路由回環(huán)方法：水平分割，定義最大跳數(shù)，毒性逆轉(zhuǎn)，觸發(fā)更新 ，抑制時間。水平分割（sp

3、lithorizon）:水平分割保證路由器記住每一條路由信息的來源，并且不在收到這條信息的端口上再次發(fā)送它。這是保證不產(chǎn)生路由循環(huán)的最基本措施。距離矢量路由協(xié)議簡介距離矢量路由協(xié)議簡介水平分割（splithorizon）:水平分割保證路由器記住每一條路由信息的來源，并且不在收到這條信息的端口上再次發(fā)送它。這是保證不產(chǎn)生路由循環(huán)的最基本措施。定義最大跳數(shù):距離矢量路由協(xié)議定義了一個最大值，允許最大為15跳,16跳既為不可用。毒性逆轉(zhuǎn)（poisonreverse）:當(dāng)一條路徑信息變?yōu)闊o效之后，路由器并不立即將它從路由表中刪除，而是用16，即不可達(dá)的度量值將它廣播出去。這樣雖然增加了路由表的大小，但

4、對消除路由循環(huán)很有幫助，它可以立即清除相鄰路由器之間的任何環(huán)路。距離矢量路由協(xié)議簡介距離矢量路由協(xié)議簡介觸發(fā)更新（triggerupdate）: 當(dāng)路由表發(fā)生變化時，更新報文立即廣播給相鄰的所有路由器，而不是等待30秒的更新周期。同樣，當(dāng)一個路由器剛啟動RIP時，它廣播請求報文。收到此廣播的相鄰路由器立即應(yīng)答一個更新報文，而不必等到下一個更新周期。這樣，網(wǎng)絡(luò)拓?fù)涞淖兓瘯羁斓卦诰W(wǎng)絡(luò)上傳播開，減少了路由循環(huán)產(chǎn)生的可能性。抑制計(jì)時（holddowntimer）: 一條路由信息無效之后，一段時間內(nèi)這條路由都處于抑制狀態(tài)，即在一定時間內(nèi)不再接收關(guān)于同一目的地址的路由更新。如果，路由器從一個網(wǎng)段上得知一

5、條路徑失效，然后，立即在另一個網(wǎng)段上得知這個路由有效。這個有效的信息往往是不正確的，抑制計(jì)時避免了這個問題，而且，當(dāng)一條鏈路頻繁起停時，抑制計(jì)時減少了路由的浮動，增加了網(wǎng)絡(luò)的穩(wěn)定性。距離矢量路由協(xié)議簡介距離矢量路由協(xié)議簡介真正的距離矢量路由協(xié)議只有RIPV1和RIPV2，因?yàn)樗鼈冎挥玫搅薍OP跳數(shù)做為唯一的計(jì)算路由的方法。IGRP是CISCO公司專有的動態(tài)距離矢量路由協(xié)議，它使用到了跳數(shù)，但是主要決定路由因數(shù)是鏈路帶寬，延遲，負(fù)載，最大傳輸單元，設(shè)備可靠性，能力等。 提提 綱綱q距離矢量路由協(xié)議簡介距離矢量路由協(xié)議簡介q距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析q鏈路狀態(tài)路由協(xié)議簡介鏈路狀態(tài)路由

6、協(xié)議簡介q鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析距離矢量路由使用的是貝爾曼-福特路由算法：所有參加的路由器周期性地向外廣播路由刷新報文，主要是由很多路由項(xiàng)（entry）組成的路由刷新報文。對路由來說，最主要的內(nèi)容是目的地址和下一跳地址（next hop）。 距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析距離矢量路由在設(shè)計(jì)時，每個路由器管理了一個路由數(shù)據(jù)庫，該路由數(shù)據(jù)庫為系統(tǒng)中所有可能的信宿包含一個路由項(xiàng)，并為每個信宿保留如下信息：目的地址：在算法的IP實(shí)現(xiàn)中，這指的是主機(jī)或網(wǎng)絡(luò)的IP 地址。下一跳地址：到信宿的路由中的第一個路由器。距離矢量路由協(xié)議分析距離矢

7、量路由協(xié)議分析接口：用于到下一跳物理網(wǎng)絡(luò)。metric值：一個數(shù)，指明本路由器到信宿的開銷。定時器：路由項(xiàng)最后一次被修改的時間。路由標(biāo)記：區(qū)分路由為內(nèi)部路由協(xié)議的路由還是外部路由協(xié)議的路由的標(biāo)記。 距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析距離矢量路由協(xié)議中，數(shù)據(jù)庫由與系統(tǒng)直接相連的實(shí)體的描述初始化，通過從相鄰路由器受到的報文修改維護(hù)。路由器間交換的最重要的信息是修改報文，參加路由維護(hù)計(jì)劃的路由器發(fā)送當(dāng)前存在于實(shí)體的描述路由數(shù)據(jù)庫的路由修改報文。僅通過相鄰路由器間交換路由信息是可以維護(hù)整個系統(tǒng)的最佳路由的。 距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析距離矢量算法總是基于一個這樣的事實(shí)：路由數(shù)據(jù)庫中

8、的路由已是目前通過報文交換而得到的最佳路由。同時，報文交換僅限于相鄰的實(shí)體間，也就是說，實(shí)體共享同一個網(wǎng)絡(luò)。當(dāng)然，要定義路由是最佳的，就必須有衡量的辦法，這就用到前面所說的“metric”。 距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析在距離矢量路由協(xié)議中，通常用可行路由所經(jīng)的路由器數(shù)簡單地計(jì)算metric值。在復(fù)雜的網(wǎng)絡(luò)中，metric一般代表該路由傳輸數(shù)據(jù)報的延遲或其它發(fā)送開銷。具體地說，距離矢量算法如下所述： 距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析令D(i,j)代表從實(shí)體i到實(shí)體j的最佳路由的metric值，d（i，j）代表從i直接到j(luò)的開銷，因?yàn)殚_銷是可加的，算法中最佳路由如此獲取表示：

9、D（i，i）=0，對所有的iD（i，j）=MINd（i，j）+D（k，j），當(dāng)i不等于k時實(shí)體i從相鄰路由器k收到k到j(luò)的開銷的估計(jì)D(i，j)，i將D（i，j）加上i到k的開銷估計(jì)d（i，j），i比較從所有相鄰路由器得到的數(shù)值，取得最小數(shù)，就得到了它到j(luò)的最佳路由。距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析首先，路由器剛啟動時，對距離矢量路由表（V-D路由表）進(jìn)行初始化，該初始化路由表包含所有去往與本路由器直接相連的網(wǎng)絡(luò)的路徑。由于去往直接相連的網(wǎng)絡(luò)不經(jīng)過中間路由器，所以初始化的V-D路由表中的各路由的距離均為0。圖2.1初始V-D路由表的一個示例。 距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析距

10、離矢量路由協(xié)議分析距離矢量路由協(xié)議分析各路由器周期性地向外廣播其V-D路由表內(nèi)容。與某路由器直接相連的（位于同一物理網(wǎng)絡(luò)）的路由器收到該路由表報文后，根據(jù)此報文對本地路由表進(jìn)行刷新。刷新時，路由器逐項(xiàng)檢查來自相鄰路由器的V-D報文，遇到下述情況之一，須修改本地路由表（假設(shè)路由器Gi收到路由器Gj的V-D報文）： 距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析1)Gj列出的某表目Gi路由表中沒有。則Gi路由表中須增加相應(yīng)表目，其“信宿”是Gj表目中的信宿，其“路徑”為“Gj”（即下一路由器為Gj）。2)Gj去往某信宿的距離值比Gi去往該信宿的距離減1還小。這種情況說明，Gi去往某信宿若經(jīng)過Gj，距離會

11、更短。則Gi修改本表目，其中“信宿”域不變，“距離”為Gj表目中距離加1，“路徑”為“Gj”。距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析3)Gi去往某信宿的路由經(jīng)過Gj，而Gj去往該信宿的路由發(fā)生變化。這里分兩種情況：Gj的V-D表不再包含去往某信宿的路由，則GI中相應(yīng)路由須刪除。Gj的V-D表中去往某信宿的路由距離發(fā)生變化，則Gi中相應(yīng)表目“距離”須修改，以Gj中的“距離”加1取代原來的距離。距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析這里要特別強(qiáng)調(diào)的是，V-D算法的路由刷新發(fā)生在相鄰路由器之間，所以V-D報文不一定以廣播方式發(fā)送出去，我們可以對V-D報文進(jìn)行優(yōu)化，讓路由器直接向相鄰路由器發(fā)送V-

12、D報文，不必采用廣播方式。距離矢量路由選擇協(xié)議在IANA網(wǎng)絡(luò)中(主網(wǎng)絡(luò))邊界進(jìn)行匯總,這是根據(jù)首字節(jié)規(guī)則實(shí)現(xiàn)的 。 提提 綱綱q距離矢量路由協(xié)議簡介距離矢量路由協(xié)議簡介q距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析q鏈路狀態(tài)路由協(xié)議簡介鏈路狀態(tài)路由協(xié)議簡介q鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議簡介鏈路狀態(tài)路由協(xié)議簡介鏈路狀態(tài)協(xié)議也叫最短路徑優(yōu)先協(xié)議或分布式數(shù)據(jù)庫協(xié)議。鏈路狀態(tài)協(xié)議有一下一些：1、 IP開放式最短路徑優(yōu)先OSPF2、 CLNS或IP ISO的中介系統(tǒng)IS-IS3、 DEC的DNA階段54、 Novell的netware鏈路服務(wù)協(xié)議NLSP鏈路狀態(tài)路由協(xié)議簡介鏈路狀

13、態(tài)路由協(xié)議簡介鏈路狀態(tài)協(xié)議的步驟：步驟1：每臺路由與他的鄰居間建立聯(lián)系，這種聯(lián)系叫做鄰接關(guān)系。步驟2：每臺路由向每個鄰居發(fā)送鏈路狀態(tài)通告(LSA)，有時也叫鏈路狀態(tài)報文(LSP)。每臺鏈路都會生成一個LSA，LSA用于標(biāo)識這條鏈路、鏈路狀態(tài)、路由器接口到鏈路的代價度量值以及鏈路所連接的所有鄰居。每個鄰居收到公告后要依次向他的鄰居轉(zhuǎn)發(fā)這些通告（泛洪）步驟3：每臺路由要在數(shù)據(jù)庫中保存一份所收到的LSA，如所有工作正常所有路由的數(shù)據(jù)庫應(yīng)該是相同的。步驟4：完整的拓?fù)鋽?shù)據(jù)庫也叫做鏈路狀態(tài)庫。鏈路狀態(tài)路由協(xié)議簡介鏈路狀態(tài)路由協(xié)議簡介鏈路狀態(tài)路由選擇協(xié)議的目的是映射互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，它是一種比距離矢量更

14、復(fù)雜的路由選擇協(xié)議，目前最流行的動態(tài)路由協(xié)議就是一種鏈路狀態(tài)協(xié)議：OSPF 。OSPF的普及因?yàn)槎鄥f(xié)議標(biāo)簽交換（MPLS）的出現(xiàn)而更流行。鏈路狀態(tài)路由協(xié)議主要有： OSPF , IS-IS鏈路狀態(tài)路由協(xié)議簡介鏈路狀態(tài)路由協(xié)議簡介鏈路狀態(tài)路由協(xié)議是目前使用最廣的一類域內(nèi)路由協(xié)議。它采用一種“拼圖”的設(shè)計(jì)策略，即每個路由器將它到其周圍鄰居的鏈路狀態(tài)向全網(wǎng)的其他路由器進(jìn)行廣播。這樣，一個路由器收到從網(wǎng)絡(luò)中其他路由器發(fā)送過來的路由信息后，它對這些鏈路狀態(tài)進(jìn)行拼裝，最終生成一個全網(wǎng)的拓?fù)湟晥D，近而可以通過最短路徑算法來計(jì)算它到別的路由器的最短路徑。 提提 綱綱q距離矢量路由協(xié)議簡介距離矢量路由協(xié)議簡介q

15、距離矢量路由協(xié)議分析距離矢量路由協(xié)議分析q鏈路狀態(tài)路由協(xié)議簡介鏈路狀態(tài)路由協(xié)議簡介q鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議(link-state routing protocol)的特征:1.對網(wǎng)絡(luò)發(fā)生的變化能夠快速響應(yīng)2.當(dāng)網(wǎng)絡(luò)發(fā)生變化的時候發(fā)送觸發(fā)式更新(triggered update)3.發(fā)送周期性更新(鏈路狀態(tài)刷新),間隔時間為30分鐘鏈路狀態(tài)路由協(xié)議只在網(wǎng)絡(luò)拓?fù)浒l(fā)生變化以后產(chǎn)生路由更新.當(dāng)鏈路狀態(tài)發(fā)生變化以后,檢測到變化的設(shè)備創(chuàng)建。鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)含義鏈路（Link）指的是路由之間的連接，即路

16、由器之間的物理連接（介質(zhì)），邏輯鏈路是通過這種連接建立的。鏈路狀態(tài)路由選擇協(xié)議在鏈路狀態(tài)發(fā)生變化時，在路由器之間發(fā)送有關(guān)鏈路的信息。因此，當(dāng)路由器A和路由器B之間的連接發(fā)生故障后，路由器A和路由器B將發(fā)送一條更新，以告訴整個網(wǎng)絡(luò)：路由器A和路由器B之間出現(xiàn)了故障。鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析LSA(link state advertisement),通過使用組播地址傳送給所有的鄰居設(shè)備,然后每個設(shè)備拷貝一份LSA,更新它自己的鏈路狀態(tài)數(shù)據(jù)庫(link state database,LSDB),接著再轉(zhuǎn)發(fā)LSA給其他的鄰居設(shè)備.這種LSA的洪泛(flooding)保證了所有的路由設(shè)備

17、在更新自己的路由表之前更新它自己的LSDB。鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析LSDB通過使用Dijkstra算法(該算法累積路徑長度,以建立最短路徑優(yōu)先數(shù),常在鏈路狀態(tài)路由選擇協(xié)議中用來決定使用哪條路由 )來計(jì)算到達(dá)目標(biāo)網(wǎng)絡(luò)的最佳路徑,建立一條SPF樹(tree),然后最佳路徑從SPF樹里選出來,被放進(jìn)路由表里.過程如下圖: 鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析OSPF和IS-IS協(xié)議被歸類到鏈路狀態(tài)路由協(xié)議中.鏈路狀態(tài)路由協(xié)議在一個特定的區(qū)域(area)里從鄰居處收集網(wǎng)絡(luò)信息,一旦路由信息都被收集齊以后,每個路由器開始通過使用Dijkstr

18、a算法(SPF)獨(dú)立計(jì)算到達(dá)目標(biāo)網(wǎng)絡(luò)的最佳路徑。鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)協(xié)議的工作方式鏈路狀態(tài)協(xié)議的工作方式 工作方式： 1.發(fā)送HELLO包，建立鄰接關(guān)系 2.同步鏈路狀態(tài)數(shù)據(jù)庫 3.使用SPF算法生成最短路徑優(yōu)先樹 4.將計(jì)算結(jié)果寫入路由表 在鏈路狀態(tài)路由協(xié)議中，所有路由器所記錄的鏈路數(shù)據(jù)庫都是一致的 鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)協(xié)議使用hello協(xié)議，來與同一鏈路上的其他路由器建立鄰接關(guān)系，并維護(hù)這種關(guān)系。這是一種面向連接的交換。路由器之間通過交換路由選擇更新使其路由選擇表同步后，他們便成了鄰接鄰居（adjacent neighbor)。只要路

19、由器彼此之間能夠收到對方的Hello分組，這種鄰接關(guān)系便保持不變。要建立鄰接關(guān)系，兩臺路由器的子網(wǎng)掩碼和Hello定時器值必須相同。鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)協(xié)議中，由于鄰居的關(guān)系是持續(xù)的，因此路由選擇進(jìn)程之間能夠快速、高效地交換信息。所以，網(wǎng)絡(luò)中的鏈路發(fā)生變化后，將很快被知道。路由器能迅速知道鄰居（同時可能也是下一跳）是否失效，因?yàn)槿绻従邮?，路由器將收不到Hello消息。鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析路由選擇協(xié)議發(fā)現(xiàn)問題后，立刻發(fā)送一條消息，而無需等待定時器到期。這也被稱為觸發(fā)更新，這是一條增量更新，因?yàn)樗话W(wǎng)絡(luò)變化的信息。通過使用增量更新，提高了網(wǎng)絡(luò)

20、的會聚速度，同時減少了需要通過網(wǎng)絡(luò)發(fā)送的信息量。這減輕了物理介質(zhì)上的網(wǎng)絡(luò)開銷，將更多的帶寬留給了用戶數(shù)據(jù)。鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析hello報文結(jié)構(gòu)如下： 路由器ID *區(qū)域ID *接口的子網(wǎng)掩碼 *認(rèn)證類型 *HELLO間隔 鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析*無效時間 優(yōu)先級 DR和BDR 鄰居列表 只有在同一物理網(wǎng)絡(luò)上的路由器對以上所有標(biāo)記為“*”的項(xiàng)目匹配，兩個路由器才可能建立鄰接關(guān)系 鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議用于大型網(wǎng)絡(luò)中，因?yàn)樗鼈兏侣酚蛇x擇表的方法占用的網(wǎng)絡(luò)資源較少。鏈路狀態(tài)路由協(xié)議通過以下方法來降低網(wǎng)絡(luò)開銷：1.使用多播地址；2.發(fā)送觸發(fā)更新；3.偶爾發(fā)送有關(guān)網(wǎng)絡(luò)的摘要；4.每臺路由器都使用小型分組來描述其本地連接性，而不是發(fā)送整個路由表。鏈路狀態(tài)路由協(xié)議分析鏈路狀態(tài)路由協(xié)議分析距離矢量路由選擇協(xié)議和鏈路狀態(tài)路由選擇協(xié)議