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

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

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

4、對消除路由循環很有幫助，它可以立即清除相鄰路由器之間的任何環路。距離矢量路由協議簡介距離矢量路由協議簡介觸發更新（triggerupdate）: 當路由表發生變化時，更新報文立即廣播給相鄰的所有路由器，而不是等待30秒的更新周期。同樣，當一個路由器剛啟動RIP時，它廣播請求報文。收到此廣播的相鄰路由器立即應答一個更新報文，而不必等到下一個更新周期。這樣，網絡拓撲的變化會最快地在網絡上傳播開，減少了路由循環產生的可能性。抑制計時（holddowntimer）: 一條路由信息無效之后，一段時間內這條路由都處于抑制狀態，即在一定時間內不再接收關于同一目的地址的路由更新。如果，路由器從一個網段上得知一

5、條路徑失效，然后，立即在另一個網段上得知這個路由有效。這個有效的信息往往是不正確的，抑制計時避免了這個問題，而且，當一條鏈路頻繁起停時，抑制計時減少了路由的浮動，增加了網絡的穩定性。距離矢量路由協議簡介距離矢量路由協議簡介真正的距離矢量路由協議只有RIPV1和RIPV2，因為它們只用到了HOP跳數做為唯一的計算路由的方法。IGRP是CISCO公司專有的動態距離矢量路由協議，它使用到了跳數，但是主要決定路由因數是鏈路帶寬，延遲，負載，最大傳輸單元，設備可靠性，能力等。 提提 綱綱q距離矢量路由協議簡介距離矢量路由協議簡介q距離矢量路由協議分析距離矢量路由協議分析q鏈路狀態路由協議簡介鏈路狀態路由

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

7、量路由協議分析接口：用于到下一跳物理網絡。metric值：一個數，指明本路由器到信宿的開銷。定時器：路由項最后一次被修改的時間。路由標記：區分路由為內部路由協議的路由還是外部路由協議的路由的標記。 距離矢量路由協議分析距離矢量路由協議分析距離矢量路由協議中，數據庫由與系統直接相連的實體的描述初始化，通過從相鄰路由器受到的報文修改維護。路由器間交換的最重要的信息是修改報文，參加路由維護計劃的路由器發送當前存在于實體的描述路由數據庫的路由修改報文。僅通過相鄰路由器間交換路由信息是可以維護整個系統的最佳路由的。 距離矢量路由協議分析距離矢量路由協議分析距離矢量算法總是基于一個這樣的事實：路由數據庫中

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

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

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

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

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

13、態路由協議簡介鏈路狀態協議的步驟：步驟1：每臺路由與他的鄰居間建立聯系，這種聯系叫做鄰接關系。步驟2：每臺路由向每個鄰居發送鏈路狀態通告(LSA)，有時也叫鏈路狀態報文(LSP)。每臺鏈路都會生成一個LSA，LSA用于標識這條鏈路、鏈路狀態、路由器接口到鏈路的代價度量值以及鏈路所連接的所有鄰居。每個鄰居收到公告后要依次向他的鄰居轉發這些通告（泛洪）步驟3：每臺路由要在數據庫中保存一份所收到的LSA，如所有工作正常所有路由的數據庫應該是相同的。步驟4：完整的拓撲數據庫也叫做鏈路狀態庫。鏈路狀態路由協議簡介鏈路狀態路由協議簡介鏈路狀態路由選擇協議的目的是映射互連網絡的拓撲結構，它是一種比距離矢量更

14、復雜的路由選擇協議，目前最流行的動態路由協議就是一種鏈路狀態協議：OSPF 。OSPF的普及因為多協議標簽交換（MPLS）的出現而更流行。鏈路狀態路由協議主要有： OSPF , IS-IS鏈路狀態路由協議簡介鏈路狀態路由協議簡介鏈路狀態路由協議是目前使用最廣的一類域內路由協議。它采用一種“拼圖”的設計策略，即每個路由器將它到其周圍鄰居的鏈路狀態向全網的其他路由器進行廣播。這樣，一個路由器收到從網絡中其他路由器發送過來的路由信息后，它對這些鏈路狀態進行拼裝，最終生成一個全網的拓撲視圖，近而可以通過最短路徑算法來計算它到別的路由器的最短路徑。 提提 綱綱q距離矢量路由協議簡介距離矢量路由協議簡介q

15、距離矢量路由協議分析距離矢量路由協議分析q鏈路狀態路由協議簡介鏈路狀態路由協議簡介q鏈路狀態路由協議分析鏈路狀態路由協議分析鏈路狀態路由協議分析鏈路狀態路由協議分析鏈路狀態路由協議(link-state routing protocol)的特征:1.對網絡發生的變化能夠快速響應2.當網絡發生變化的時候發送觸發式更新(triggered update)3.發送周期性更新(鏈路狀態刷新),間隔時間為30分鐘鏈路狀態路由協議只在網絡拓撲發生變化以后產生路由更新.當鏈路狀態發生變化以后,檢測到變化的設備創建。鏈路狀態路由協議分析鏈路狀態路由協議分析鏈路狀態含義鏈路（Link）指的是路由之間的連接，即路

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

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

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

19、由器彼此之間能夠收到對方的Hello分組，這種鄰接關系便保持不變。要建立鄰接關系，兩臺路由器的子網掩碼和Hello定時器值必須相同。鏈路狀態路由協議分析鏈路狀態路由協議分析鏈路狀態協議中，由于鄰居的關系是持續的，因此路由選擇進程之間能夠快速、高效地交換信息。所以，網絡中的鏈路發生變化后，將很快被知道。路由器能迅速知道鄰居（同時可能也是下一跳）是否失效，因為如果鄰居失效，路由器將收不到Hello消息。鏈路狀態路由協議分析鏈路狀態路由協議分析路由選擇協議發現問題后，立刻發送一條消息，而無需等待定時器到期。這也被稱為觸發更新，這是一條增量更新，因為它只包含網絡變化的信息。通過使用增量更新，提高了網絡

20、的會聚速度，同時減少了需要通過網絡發送的信息量。這減輕了物理介質上的網絡開銷，將更多的帶寬留給了用戶數據。鏈路狀態路由協議分析鏈路狀態路由協議分析hello報文結構如下： 路由器ID *區域ID *接口的子網掩碼 *認證類型 *HELLO間隔 鏈路狀態路由協議分析鏈路狀態路由協議分析*無效時間 優先級 DR和BDR 鄰居列表 只有在同一物理網絡上的路由器對以上所有標記為“*”的項目匹配，兩個路由器才可能建立鄰接關系 鏈路狀態路由協議分析鏈路狀態路由協議分析鏈路狀態路由協議用于大型網絡中，因為它們更新路由選擇表的方法占用的網絡資源較少。鏈路狀態路由協議通過以下方法來降低網絡開銷：1.使用多播地址；2.發送觸發更新；3.偶爾發送有關網絡的摘要；4.每臺路由器都使用小型分組來描述其本地連接性，而不是發送整個路由表。鏈路狀態路由協議分析鏈路狀態路由協議分析距離矢量路由選擇協議和鏈路狀態路由選擇協議