鏈路狀態路由隨機選擇演算法

Ⅰ 路由演算法的類型有

靜態路由演算法

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，路由器便可以計算出延時。（路程往返時間是網路當前延遲的量度，通過一個分組數據包從遠程主機返回的時間來測量。）該時間包括了傳輸和處理兩部分的時間——也就是將分組數據包發送到目的地的時間以及接收方處理分組數據包和應答的時間。

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

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

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

Ⅱ 路由器選擇最佳的路徑策略即路由演算法是怎麼計算的

看你是選用什麼的路由協議
廣義上講分為鏈路狀態，距離矢量
鏈路狀態路由協議ospf 它根據cost值來選擇路徑，說白了就是根據鏈路帶寬，
距離矢量 rip eigrp bgp 它根據跳數來選擇路徑

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

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

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

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

Ⅳ 鏈路狀態路由協議的介紹

鏈路狀態路由選擇協議又稱為最短路徑優先協議，它基於Edsger Dijkstra的最短路徑優先（SPF）演算法。1它比距離矢量路由協議復雜得多，但基本功能和配置卻很簡單，甚至演算法也容易理解。路由器的鏈路狀態的信息稱為鏈路狀態，包括：介面的IP地址和子網掩碼、網路類型（如乙太網鏈路或串列點對點鏈路）、該鏈路的開銷、該鏈路上的所有的相鄰路由器。

Ⅵ 鏈路狀態路由演算法的演算法的優缺點

（1）與距離向量演算法相比，鏈路狀態演算法具有更快的收斂速度。由於LSP的發布是面向整個網路，使所有路由器都能夠利用LSP來迅速建立整個網路拓撲的一個准確視圖。這可以有效防止無限技術問題的出現。其次，鏈路狀態路由演算法還具有更小的網路開銷。LSP只有在網路拓撲發生變化時才發布，LSP的發布反應的是網路的變化，而不是對整個路由資料庫的發布和傳輸。LSP僅攜帶與本路由器直接相連的鏈路，報文長度都很小，且與互聯網中的網路數無關，可見鏈路狀態演算法更適於大規模互聯網。
（2）鏈路狀態演算法具有更好的功能擴展能力，很容易地在鏈路狀態中加入新的屬性和參數，而無需改變路由交換的規則，是路由計算中能夠引用不同的參數來實現新的功能。在鏈路狀態演算法中，各路由器使用相同的路由資料庫來獨立計算路由，而不依賴於其他的路由器，相比距離向量具有更好的防止錯誤傳播的能力。由於LSP在傳輸過程中不會被其他路由器修改，易於調試。路由器在本地計算路由，也確保了路由演算法的收斂性。
（3）路由狀態演算法還提供了更好的在規模上的可升級性，鏈路狀態演算法允許在一個大型網路中劃分選路層次。例如，可以將網路中的路由器劃分成若干組，在同一組中的路由器之間相互交換LSP，並建立一個該組統一的拓撲資料庫。為了在不同的組之間交換拓撲信息，組內的一個特殊路由器的子集首先總結出該組的拓撲資料庫，然後將這些總結性的拓撲資料庫在一個LSP鍾發送給鄰近組中的特定路由器。通過這種方式，減少網路中路由信息交換的開銷，同時也將組內拓撲結構的變化對其他族中的路由器隱藏起來。分級的概念是在鏈路狀態路由協議（如OSPF）實現過程中的一個十分重要的概念。 每個路由器需要有較大的存儲空間，用以存儲所收到的每一個節點的鏈路狀態分組；計算工作量大，每次都必須計算最短路徑。

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

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

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

鏈路狀態法工作過程：

1、了解直連網路。

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

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

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

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

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

(8)鏈路狀態路由隨機選擇演算法擴展閱讀：

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

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

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

一、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時為主幹域。不同網路區域的路由器通過主幹域學習路由信息。

Ⅹ 常見的路由選擇演算法有哪些

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