鏈路狀態路由演算法

⑴ 鏈路狀態路由演算法的演算法工作原理

鏈路狀態選路演算法的工作原理如下
（1）在參與鏈路狀態選路的路由器集合中，每個路由器都需要通過某種機制來了解自己所連接的鏈路及其狀態。
（2）各路由器都能夠將其所連接的鏈路的狀態信息通知給網路中的所有其他路由器，這些鏈路信息包括鏈路狀態、費用以及鏈路兩端的路由器等。
（3）鏈路狀態信息的通過鏈路狀態分組（LSP）來向整個網路發布。一個LSP通常包含源路由器的標識符、相鄰路由器的標識符，以及而知之間鏈路的費用。每一個LSP都將被網路中的所有的路由器接收，並用於建立網路整體的統一拓撲資料庫。由於網路中所有的路由器都發送LSP，經過一段時間以後，每一個路由器都保持了一張完整的網路拓撲圖，再在這個拓撲圖上，利用最短通路演算法（例如Dijkstra演算法等），路由器就可以計算出從任何源點到任何目的地的最佳通路。
這樣，每一個路由器都能夠利用通路最短的原則建立一個以本路由器為根、分支到所有其他路由器的生成樹，依據這個生成樹就可以很容易地計算出本路由器的路由表。

⑵ 鏈路狀態路由協議運行什麼演算法來計算到達目的網路的最短路徑

一、RIP協議RIP(RoutinginformationProtocol)是應用較早、使用較普遍的內部網關協議(InteriorGatewayProtocol,簡稱IGP)，適用於小型同類網路，是典型的距離向量(distance-vector)協議。文檔見RFC1058、RFC1723。RIP通過廣播UDP報文來交換路由信息，每30秒發送一次路由信息更新。RIP提供跳躍計數(hopcount)作為尺度來衡量路由距離，跳躍計數是一個包到達目標所必須經過的路由器的數目。如果到相同目標有二個不等速或不同帶寬的路由器，但跳躍計數相同，則RIP認為兩個路由是等距離的。RIP最多支持的跳數為15，即在源和目的網間所要經過的最多路由器的數目為15，跳數16表示不可達。1.有關命令任務命令指定使用RIP協議routerrip指定RIP版本version{1|2}1指定與該路由器相連的網路networknetwork註：1.Cisco的RIP版本2支持驗證、密鑰管理、路由匯總、無類域間路由(CIDR)和變長子網掩碼(VLSMs)二、IGRP協議IGRP()是一種動態距離向量路由協議，它由Cisco公司八十年代中期設計。使用組合用戶配置尺度，包括延遲、帶寬、可靠性和負載。預設情況下，IGRP每90秒發送一次路由更新廣播，在3個更新周期內(即270秒)，沒有從路由中的第一個路由器接收到更新，則宣布路由不可訪問。在7個更新周期即630秒後，CiscoIOS軟體從路由表中清除路由。1.有關命令任務命令指定使用RIP協議routerigrpautonomous-system1指定與該路由器相連的網路networknetwork指定與該路由器相鄰的節點地址neighborip-address註：1、autonomous-system可以隨意建立，並非實際意義上的autonomous-system,但運行IGRP的路由器要想交換路由更新信息其autonomous-system需相同。三、OSPF協議OSPF(OpenShortestPathFirst)是一個內部網關協議(InteriorGatewayProtocol,簡稱IGP)，用於在單一自治系統(autonomoussystem,AS)內決策路由。與RIP相對，OSPF是鏈路狀態路有協議，而RIP是距離向量路由協議。鏈路是路由器介面的另一種說法，因此OSPF也稱為介面狀態路由協議。OSPF通過路由器之間通告網路介面的狀態來建立鏈路狀態資料庫，生成最短路徑樹，每個OSPF路由器使用這些最短路徑構造路由表。文檔見RFC2178。1．有關命令全局設置任務命令指定使用OSPF協議routerospfprocess-id1指定與該路由器相連的網路networkaddresswildcard-maskareaarea-id2指定與該路由器相鄰的節點地址neighborip-address註：1、OSPF路由進程process-id必須指定范圍在1-65535，多個OSPF進程可以在同一個路由器上配置，但最好不這樣做。多個OSPF進程需要多個OSPF資料庫的副本，必須運行多個最短路徑演算法的副本。process-id只在路由器內部起作用，不同路由器的process-id可以不同。2、wildcard-mask是子網掩碼的反碼,網路區域IDarea-id在0-4294967295內的十進制數，也可以是帶有IP地址格式的x.x.x.x。當網路區域ID為0或0.0.0.0時為主幹域。不同網路區域的路由器通過主幹域學習路由信息。

⑶ 鏈路狀態路由演算法的演算法思想

鏈路狀態演算法的思想是要求網路中所有參與鏈路狀態路由協議的路由器都掌握網路的全部拓撲結構信息，並記錄在路由資料庫中。鏈路狀態演算法中路由資料庫實質上是一個網路結構的拓撲圖，該拓撲圖由一個節點的集合和一個邊的集合構成。在網路拓撲圖中，結點代表網路中路由器，邊代表路由器之間的物理鏈路。在網路拓撲結構圖中，每一條鏈路上可以附加不同的屬性，例如鏈路的狀態、距離或費用等。如果沒一個路由器所保存的網路拓撲結構圖都是一致的，那麼個路由器生成的路由表也是最佳的，不存在錯誤路由或循環路由。

⑷ 路由演算法主要有哪幾種

靜態路由演算法主要有：
洪泛法（Flooding）
隨機走動法（Random Walk）
最短路徑法（Shortest Path，SP）
基於流量的路由演算法(Flow-based Routing，FR)</ol>動態路由演算法主要有：
距離矢量演算法（RIP）
鏈路狀態演算法（OSPF）
平衡混合演算法（EIGRP）</ol>

⑸ 6,路由選擇有哪些演算法

關於路由器如何收集網路的結構信息以及對之進行分析來確定最佳路由，有兩種主要的路由演算法：
總體式路由演算法和分散式路由演算法。採用分散式路由演算法時，每個路由器只有與它直接相連的路由器的信息——而沒有網路中的每個路由器的信息。這些演算法也被稱為dv（距離向量）演算法。採用總體式路由演算法時，每個路由器都擁有網路中所有其他路由器的全部信息以及網路的流量狀態。這些演算法也被稱為ls（鏈路狀態）演算法。

⑹ 兩種路由選擇演算法是什麼

鏈路狀態演算法（也稱最短路徑演算法）發送路由信息到互聯網上所有的結點，然而對於每個路由器，僅發送它的路由表中描述了其自身鏈路狀態的那一部分。距離向量演算法（也稱為Bellman-Ford演算法）則要求每個路由器發送其路由表全部或部分信息，但僅發送到鄰近結點上。從本質上來說，鏈路狀態演算法將少量更新信息發送至網路各處，而距離向量演算法發送大量更新信息至鄰接路由器。 ——由於鏈路狀態演算法收斂更快，因此它在一定程度上比距離向量演算法更不易產生路由循環。但另一方面，鏈路狀態演算法要求比距離向量演算法有更強的CPU能力和更多的內存空間，因此鏈路狀態演算法將會在實現時顯得更昂貴一些。除了這些區別，兩種演算法在大多數環境下都能很好地運行。

⑺ 路由協議中的鏈路狀態法的工作過程是什麼

鏈路狀態法工作過程：

1、了解直連網路。

2、向鄰居發送Hello數據包。

3、建立鏈路狀態數據包。

4、將鏈路狀態數據包泛洪給鄰居。

5、構建鏈路狀態資料庫。

運行鏈路狀態路由協議的路由器，只將它所直連的鏈路狀態與鄰居共享，這個鄰居是指一個域內（domain），或一個區域內（area）的所有路由器。

(7)鏈路狀態路由演算法擴展閱讀：

鏈路狀態路由協議，更新的是「拓撲」。每台路由器上都有完全相同的拓撲，他們各自分別進行SPF演算法，計算出路由條目。

一條重要鏈路的變化，不必再發送所有被波及的路由條目，只需發送一條鏈路通告，告知其它路由器本鏈路發生故障即可。其它路由器會根據鏈路狀態，改變自已的拓撲資料庫，重新計算路由條目。

⑻ 鏈路狀態路由採用的演算法是：

b和c 例如ospf 區域內是最短路徑優先演算法，那麼區域間呢？區域間為距離矢量演算法。

⑼ 路由演算法的類型有

路由演算法有很多種，如果從路由表對網路拓撲和通信量變化的自適應能力的角度劃分，可以分為靜態路由演算法和動態路由演算法兩大類，這兩大類又可細分為幾種小類型，比較典型常見的有以下幾種：

一、靜態路由演算法

1.Dijkstra演算法（最短路徑演算法）

Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN,CLOSE表的方式，這里均採用永久和臨時標號的方式。注意該演算法要求圖中不存在負權迴路。

Dijkstra演算法執行步驟如下：

步驟一：路由器建立一張網路圖，並且確定源節點和目的節點，在這個例子里我們設為V1和V2。然後路由器建立一個矩陣，稱為「鄰接矩陣」。在這個矩陣中，各矩陣元素表示權值。例如，[i,j]是節點Vi與Vj之間的鏈路權值。如果節點Vi與Vj之間沒有鏈路直接相連，它們的權值設為「無窮大」。

步驟二：路由器為網路中的每一個節點建立一組狀態記錄。此記錄包括三個欄位：

前序欄位———表示當前節點之前的節點。

長度欄位———表示從源節點到當前節點的權值之和。

標號欄位———表示節點的狀態。每個節點都處於一個狀態模式：「永久」或「暫時」。

步驟三：路由器初始化（所有節點的）狀態記錄集參數，將它們的長度設為「無窮大」，標號設為「暫時」。

步驟四：路由器設置一個T節點。例如，如果設V1是源T節點，路由器將V1的標號更改為「永久」。當一個標號更改為「永久」後，它將不再改變。一個T節點僅僅是一個代理而已。

步驟五：路由器更新與源T節點直接相連的所有暫時性節點的狀態記錄集。

步驟六：路由器在所有的暫時性節點中選擇距離V1的權值最低的節點。這個節點將是新的T節點。

步驟七：如果這個節點不是V2（目的節點），路由器則返回到步驟5。

步驟八：如果節點是V2，路由器則向前回溯，將它的前序節點從狀態記錄集中提取出來，如此循環，直到提取到V1為止。這個節點列表便是從V1到V2的最佳路由。

2.擴散法
事先不需要任何網路信息；路由器把收到的每一個分組，向除了該分組到來的線路外的所有輸出線路發送。將來會有多個分組的副本到達目的地端，最先到達的，可能是走了「最優」的路徑常見的擴散法是選擇性擴散演算法。

3.LS演算法

採用LS演算法時，每個路由器必須遵循以下步驟：

步驟一：確認在物理上與之相連的路由器並獲得它們的IP地址。當一個路由器開始工作後，它首先向整個網路發送一個「HELLO」分組數據包。每個接收到數據包的路由器都將返回一條消息，其中包含它自身的IP地址。

步驟二：測量相鄰路由器的延時（或者其他重要的網路參數，比如平均流量）。為做到這一點，路由器向整個網路發送響應分組數據包。每個接收到數據包的路由器返回一個應答分組數據包。將路程往返時間除以2，路由器便可以計算出延時。（路程往返時間是網路當前延遲的量度，通過一個分組數據包從遠程主機返回的時間來測量。）該時間包括了傳輸和處理兩部分的時間——也就是將分組數據包發送到目的地的時間以及接收方處理分組數據包和應答的時間。

步驟三：向網路中的其他路由器廣播自己的信息，同時也接收其他路由器的信息。

在這一步中，所有的路由器共享它們的知識並且將自身的信息廣播給其他每一個路由器。這樣，每一個路由器都能夠知道網路的結構以及狀態。

步驟四：使用一個合適的演算法，確定網路中兩個節點之間的最佳路由。

路由演算法有哪些類型？路由演算法與路由協議的區別

在這一步中，路由器選擇通往每一個節點的最佳路由。它們使用一個演算法來實現這一點，如Dijkstra最短路徑演算法。在這個演算法中，一個路由器通過收集到的其他路由器的信息，建立一個網路圖。這個圖描述網路中的路由器的位置以及它們之間的鏈接關系。每個鏈接都有一個數字標注，稱為權值或成本。這個數字是延時和平均流量的函數，有時它僅僅表示節點間的躍點數。例如，如果一個節點與目的地之間有兩條鏈路，路由器將選擇權值最低的鏈路。

二、動態路由演算法

1.距離向量路由演算法

距離向量路由演算法，也叫做最大流量演演算法，其被距離向量協議作為一個演算法，如RIP、BGP、ISO IDRP、NOVELL IPX。使用這個演算法的路由器必須掌握這個距離表(它是一個一維排列-「一個向量」)，它告訴在網路中每個節點的最遠和最近距離。在距離表中的這個信息是根據臨近接點信息的改變而時時更新的。表中數據的量和在網路中的所有的接點(除了它自己本身)是等同的。這個表中的列代表直接和它相連的鄰居，行代表在網路中的所有目的地。每個數據包括傳送數據包到每個在網上的目的地的路徑和距離/或時間在那個路徑上來傳輸(我們叫這個為「成本」)。這個在那個演算法中的度量公式是跳躍的次數，等待時間，流出數據包的數量，等等。在距離向量路由演算法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當網路拓撲結構發生變化時，路由器之間也將及時地相互通知有關變更信息。其優點是演算法簡單容易實現。缺點是慢收斂問題，路由器的路徑變化需要像波浪一樣從相鄰路由器傳播出去，過程緩慢。

每一個相鄰路由器發送過來的路由表都要經過以下步驟：

步驟一：對地址為X的路由器發過來的路由表，先修改此路由表中的所有項目：把」下一跳」欄位中的地址改為X，並把所有」距離」欄位都加1。

步驟二：對修改後的路由表中的每一個項目，進行以下步驟：

（1）將X的路由表(修改過的)，與S的路由表的目的網路進行對比。若在X中出現，在S中沒出現，則將X路由表中的這一條項目添加到S的路由表中。

（2）對於目的網路在S和X路由表中都有的項目進行下面步驟：

1）在S的路由表中，若下一跳地址是x，則直接用X路由表中這條項目替換S路由表中的項目。

2）在S的路由表中，若下一跳地址不是x，若X路由表項目中的距離d小於S路由表中的距離，則進行更新。

步驟三：若3分鍾還沒有收到相鄰路由器的更新表，則把此相鄰路由器記為不可到達路由器，即把距離設置為16。

2.鏈路狀態最短路由優先演算法SPF

1）發現鄰居結點，並學習它們的網路地址；

2）測量到各鄰居節點的延遲或者開銷；

3）創建鏈路狀態分組；

4）使用擴散法發布鏈路狀態分組；

5）計算到每個其它路由器的最短路徑。

⑽ 什麼是鏈路狀態路由演算法,和DV演算法

鏈路狀態演算法（也稱最短路徑演算法）發送路由信息到互聯網上所有的結點，然而對於每個路由器，僅發送它的路由表中描述了其自身鏈路狀態的那一部分。距離向量演算法（也稱為Bellman-Ford演算法）則要求每個路由器發送其路由表全部或部分信息，但僅發送到鄰近結點上。從本質上來說，鏈路狀態演算法將少量更新信息發送至網路各處，而距離向量演算法發送大量更新信息至鄰接路由器。 ——由於鏈路狀態演算法收斂更快，因此它在一定程度上比距離向量演算法更不易產生路由循環。但另一方面，鏈路狀態演算法要求比距離向量演算法有更強的CPU能力和更多的內存空間，因此鏈路狀態演算法將會在實現時顯得更昂貴一些。除了這些區別，兩種演算法在大多數環境下都能很好地運行。