路由演算法有哪些

㈠ 路由演算法

路由演算法是網路層軟體的一部分。子網提供數據報服務，每個包都要做路由選擇；子網提供虛電路服務，只需在建立連接時做一次路由選擇

正確性，簡單性，健壯性（魯棒性，網路出現意外情況時候的解決問題的能力。例如突然某個路由器停電了，使得周邊的路由器都沒法正常工作，如果出現這樣的問題說明路由器的健壯性不夠），穩定性（常規使用是否穩定，數據量增多的時候能否正常工作），公平性（網路資源的使用是否公平，避免有些節點出現特別繁忙的狀態，而有些節點總是處於很閑的狀態），最優性

• 按轉發方式和數據副本數量劃分
1.全路路由（廣播路由）演算法：如洪泛演算法，按照所有路徑廣播轉發（中間轉發節點以及目標節點都會送到很多重復數據。不需要路由表和路由控制功能）
2.多路路由演算法：向所有接近目的節點的路徑轉發（中間轉發節點以及目標節點都會送到很多重復數據。）
3.單路路由演算法：如距離矢量演算法，向目的節點沿著唯一的路徑轉發（中間的轉發節點只轉發一份數據即可）

• 按健壯性和簡單性劃分
1.非自適應演算法（靜態路由演算法）：不能根據網路流量和拓撲結構的變化更新路由表，使用靜態路由表。需要人為的更改和設定。特點是簡單、開銷小、靈活性差。典型演算法為基於流量的路由演算法等
2.自適應演算法（動態路由演算法）：可根據網路流量（網路承載的數據量）和拓撲結構的變化更新路由表。特點是開銷大、健壯性和靈活性好。典型演算法為距離向量路由演算法、鏈路狀態路由演算法等

☆可以靜態路由和動態路由結合起來使用，此時靜態路由的優先順序別較高

測量（獲取）有關路由選擇的網路度量參數（選擇最優，比如是要求傳播距離最短，還是要求傳輸時延短等）。如何測量？選取哪些網路參數？
將路由信息傳送到適當的網路節點。傳送給誰？如何傳送？傳送什麼信息？
計算和更新路由表。更新路由表的演算法
根據新路由表執行分組的轉發

如果路由器J在路由器I到K的最優路由上，那麼從J到K的最優路由一定落在同一路由上

從所有的源節點到一個給定的目的節點的最優路由的集合形成了一個以目的節點為根的樹，稱為匯集樹；路由演算法的目的是找出並使用匯集樹

基本思想：構建子網的拓撲圖，圖中的每個節點代表一個路由器，每條弧代表一條通信線路。為了選擇兩個路由器間的路由，演算法需要在圖中找出節點間的最短路徑

節點數量；地理距離；傳輸延遲；距離、信道帶寬等參數的加權函數

網路規模增大帶來的問題：路由器中的路由表增大；路由器為選擇路由而佔用的內存、CPU時間和網路帶寬增大
分層路由：分而治之的思想；根據需要，將路由器分成區域、聚類、區和組；Fig.6-6，路由表由17項減為7項
分層路由帶來的問題：路由表中的路由不一定是最優路由

☆分層路由功能大部分時候性能是比較好的，可以選擇最優路徑，但是有時也會選擇到非最優路徑。比如上圖中如果想從1A到5C，應該是1A→1B→2A→2B→2D→5C是比較優的選擇，但是按照1A的分層路由表顯示，從區域1到區域5出口線路為1C，因此選擇的路線為1A→1C→3B→4A→5A→5B→5C，這時就相對繞遠了

DVR - Distance Vector Routing
動態路由演算法，也稱Bellman - Ford路由演算法或Ford - Fulkerson演算法，最初用於ARPANET（Internet的前身），被RIP協議所採用

每個路由器維護一張路由表，表中給出了到每個目的地的已知最佳距離和線路，並通過與相鄰路由器交換距離信息來更新表；每隔一段時間，路由器向所有鄰居節點發送它到每個目的節點的距離表，同時它也接收每個鄰居節點發來的距離表；鄰居節點X發來的表中，X到路由器I的距離為Xi，本路由器到X的距離為m，則路由器經過X到i的距離為Xi + m。根據不同鄰居發來的信息，計算Xi + m，並取最小值，更新本路由器的路由表

圖1：
此時路由A把它的路由表發給路由B，B會綜合從A得來的路由表來更新自己的矢量表↓
根據初始A矢量表和B矢量表得知B到A為6，B到C為1，B到D沒有；兩個表都有到E的距離，直接從B到E為8；如果B經由A再到E就要計算A到B的距離加上A到E的距離即可，即6+1=7

圖2：
B把路由表發給C之後↓
從C的初始矢量表可得知C到B為1，C到D為2，C無法直接到A，但是通過B的路由表得知B到A為6，再加上C到B的距離1，得出C到A距離為7，同理可得到E距離為7+1=8

圖3：
C把路由表發給D之後↓

圖4：
D把路由表發給E之後↓

J的相鄰節點為4個，分別為A，I，H，K，因此可以選擇的路線也為4種
現在要求J的最新路由表。以J到E為例，J到A為8，A到E為14，和為22；J到I為10，I到E為7，和為17；J到H為12，H到E為30，和為42；J到K為6，K到E為22，和為28。從而得出，經由I的時候得到的和17最小，因此在新生成的J到E的位置記錄17

無限計算問題：對好消息反應迅速，對壞消息反應遲鈍

比如從E到A，E剛開始連通的時候是不知道如何才能到A的，只有通過B與A交互，C與B交互這樣最終E通過與D交互才知道如何能到A，這就是好消息。可能需要花些時間，但是結果都是無論目的節點是哪裡總會找到路徑

壞消息例子：A，B，C之間通信。B到A的距離為1（A，1），C到A的距離為2（B（經B），2）。各個節點都會有一個刷新周期，到了這個周期的時候每個節點會把自己的路由信息發給其相鄰節點。例如A路由斷開連接，這個時候B到A的線路斷開。也就是B到A的距離為無窮大了（A，∞）。如果在B把這個信息反饋給C之前，C先把路由信息告訴B了，那麼B收到的信息就為（C，3）。因為A已經不存在，而B從C處得知通過C有路徑可以到達A，這時B的路由表就變成（C，3），同樣的這時B再告訴C，C就會變成（B，4），就會這樣無窮計算下去。如果一開始是B先把信息發給C就不會發生這樣的問題

• 觸發式更新：節點不等到刷新周期的到來，只要有突發情況馬上就會把情況通知相鄰路由
• 水平分割：因為一開始C是從B得知經過B可以到達A的，所以用了這種方法之後，C就不會再向B發送如何到A，而只等著B給C發如何到A了。這樣就不會有無窮計算問題
• 定義一個最大值：壞消息例子當中，括弧里後面的數會一直循環增長下去，如果把這個數字設置一個最大值，那麼當循環到這個最大值的時候雙方就不會再就怎麼到A的信息進行交互了，就不會發生無窮計算的情況
• 掛起計數器：壞消息例子當中，B收到了C的路由最新信息（C，3）的時候這個不會馬上生效刷新，（A，∞）會保留兩個周期，在這兩個周期裡面，B肯定有機會給C發送（A，∞），
而因為C沒有通往A的路徑，所以當C到刷新周期的時候給B發的就為（B，∞）。B前後收到的信息不一致，但是第二次收到的信息和B發給C的信息是一致的，所以B就會認為第一次收到的（C，3）是無效的。但是如果C真的有了一條通往A的線路，這時兩次發的信息一定是一致的，那麼B就會相信C的信息，從而把（A，∞）刷新成C給B的信息

❉距離向量路由演算法只適用於小規模網路，每個節點不清楚整個網路的拓撲結構

發現鄰居節點，並學習它們的網路地址，測量到每個鄰居節點的延遲或開銷，將所有學習到的內容封裝成一個鏈路狀態包（包以發送方的標識符開頭，後面是序號、年齡和一個鄰居節點列表；鏈路狀態包定期創建或發生重大事件時創建）。將鏈路狀態包廣播發送給所有其他路由器【洪泛方式：狀態包包含一個序號，每次發送新包時加1。路由器記錄信息對（源路由器，序號），當一個鏈路狀態包到達時，若是新的則分發，若是重復的則丟棄，若序號比路由記錄中的最大序號小則認為過時而丟棄】。計算到每個其他路由器的最短路徑

☆鏈路狀態路由演算法適用於大規模網路。每個節點都會了解其他節點的局部拓撲，因此就會了解整個網路的拓撲結構，這時當前節點就能找到到目的節點的最優路由

• 使用32位序號。
因為序號是循環使用的，如果位數很少，比如只是1~7，那麼7不一定比1大，1有可能是下一輪的第一個數。而32位的時候因為數字特別龐大，不會出現這樣問題
• 增加年齡域，每秒鍾年齡減1，為零則丟棄
比如A發給B （C，4），由於差錯，本來是（C，5）的下一個包，變成了（C，1000）。這之後來的（C，6），（C，7）。。。都沒有（C，1000）大，因此包會被丟棄。但其實後面到的包都是新的。為了避免這樣的問題發生，（C，1000）里的1000就會在每一秒減1，直到年齡比新到的包小，接下來就可以正常接包了。不過這之前到的包都會被丟棄，這也是沒有辦法的事
• 鏈路狀態包到達後，延遲一段時間，並與其它已到達的來自同一路由器的鏈路狀態包比較序號，丟棄重復包，保留新包
• 鏈路狀態包需要應答
為了保證數據傳輸的可靠性

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

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

㈢ 路由演算法的類型有

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

一、靜態路由演算法

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）計算到每個其它路由器的最短路徑。