Ⅰ 路由演算法的類型有
路由演算法有很多種，如果從路由表對網路拓撲和通信量變化的自適應能力的角度劃分，可以分為靜態路由演算法和動態路由演算法兩大類，這兩大類又可細分為幾種小類型，比較典型常見的有以下幾種：
一、靜態路由演算法
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）計算到每個其它路由器的最短路徑。
Ⅱ BGP協議最佳路徑的選擇演算法有哪些
每個BGP路由器通過鄰居聲名與周邊的一個或多個路由器連接。一旦建立了鄰居關系，這些BGP路由器之間就會相互交換路由信息。據我最近一次統計，整個互聯網上有大約12.5萬個路由信息，因此要配備一個強大的路由器才能將所有BGP路由信息接收下來。
由於整個互聯網的BGP路由表有超過20萬個路由，同時一個BGP路由器可能從多個來源收到多份的路由表，因此肯定會有一種方法可以比較不同的BGP路由表，並從中選擇最佳的路由方案。這種方法就是BGP最佳路徑選擇演算法。
可能你會注意到，CiscoBGP路由器會將應用權重（weight）作為路由表的第一標准，而其它品牌的路由器則不是這樣。Cisco的官方BGP最佳路徑選擇演算法文檔中詳細列明了所參考的各項標准。接下來我會列出每種標准並給出解釋和範例。
默認情況下，BGP最佳路徑都是基於最短自治系統（AS）的原理得出的。不過很多時候，諸如weight，localpreference以及MED這樣的標准都是網路管理員自行設定的。
接下來我們就按照BGP選擇最佳路徑的參考順序將這幾項標准介紹一下：
#1 Weight —權重是Cisco為本地路由器設定的自定義參數，並不隨路由器更新而變化。如果指向某一IP地址的路徑有多條（這很常見），那麼BGP會尋找權重最高的路徑。設定權重的參考因素很多，包括鄰居命令，as-path訪問列表，或者路由鏡像等。
#2 Local Preference — 本地出口優先順序參數會告知AS哪條路徑具有本地優先，數值越高優先順序越高。默認為100。比如：
bgp default local-preference 150
#3 Network or Aggregate—這個參數會選擇本地發起的網路或聚合作為路徑。將特定的路徑加入路由中，會讓路由更有效率，同時也節省了網路空間。更多有關聚合的信息，可以參考Cisco的文章「UnderstandingRouteAggregation in BGP.」
#4 Shortest AS_PATH — BGP 只有在weight， localpreference和locallyoriginated相當接近的時候才使用這個參數。
#5 Lowest origin type — 這個參數處理Interior Gateway Protocol（IGP）協議的優先順序低於 Exterior Gateway Protocol （EGP）協議。
#6 Lowest multi-exit discriminator （MED） — 較低的MED值要優於較高的MED值。
#7 eBGP over iBGP — 類似於#5， BGP AS Path 更傾向 eBGP 而不是 iBGP。
#8 Lowest IGP metric — 這個參數傾向於採用最低IGP作為BGP下一跳。
#9 Multiple paths — 這個參數決定是否要在路由表中裝入多個路徑。可以參考 BGPMultipath獲取更多信息。
#10 External paths — 當所有路徑都為外部路徑時，選擇首先接收到的路徑（較老的路徑）。
#11 Lowest router ID — 選擇來自具有最低路由器ID的BGP路由器的路徑。
#12 Minimum cluster list — 如果多個路徑的originator或路由器ID相同，選擇cluster列表長度最短的路徑。