『壹』 常見的路由選擇演算法有哪些
常見的路由選擇演算法主要分為靜態路由演算法和動態路由演算法兩大類,具體如下:
靜態路由演算法: 泛射路由演算法:該演算法將數據包向所有可能的路徑發送,直到數據包到達目的地。這種方法簡單但效率較低,因為會產生大量冗餘數據。 固定路由演算法:數據包按照預先設定的固定路徑進行傳輸。這種方法適用於網路結構穩定、變化不大的場景。 隨機走動法:數據包在網路中隨機選擇路徑進行傳輸,直到到達目的地。這種方法適用於網路拓撲復雜且難以預測的場景,但效率同樣較低。 最短路徑法:根據網路中的鏈路代價,選擇從源節點到目的節點代價最小的路徑。這種方法能夠優化網路性能,但需要預先知道網路拓撲和鏈路代價。
動態路由演算法: 分布式路由選擇: 距離向量演算法:每個路由器維護一張到網路中所有其他路由器的距離表,並根據鄰居路由器的信息更新自己的距離表。這種方法適用於中小型網路。 鏈路狀態演算法:每個路由器收集並廣播其鄰居路由器的鏈路狀態信息,所有路由器根據這些信息構建全局網路拓撲圖,並選擇最短路徑。這種方法適用於大型網路,因為它能夠提供更准確和全局的網路視圖。 集中式路由選擇:所有路由決策都由一個中心節點做出。這種方法能夠全局優化網路性能,但中心節點的故障可能導致整個網路癱瘓。 混合式動態路由選擇:結合分布式和集中式路由選擇的優點,根據網路實際情況靈活選擇路由策略。
特別說明:鏈路狀態路由演算法雖然歸類於動態路由選擇演算法中的分布式路由選擇,但由於其重要性和特殊性,常常單獨列出。它通過收集並廣播鏈路狀態信息來構建全局網路拓撲圖,從而選擇最優路徑。這種方法在大型、復雜網路中表現出色。
『貳』 路由演算法的類型有
靜態路由演算法
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,路由器便可以計算出延時。(路程往返時間是網路當前延遲的量度,通過一個分組數據包從遠程主機返回的時間來測量。)該時間包括了傳輸和處理兩部分的時間——也就是將分組數據包發送到目的地的時間以及接收方處理分組數據包和應答的時間。
步驟三:向網路中的其他路由器廣播自己的信息,同時也接收其他路由器的信息。
在這一步中,所有的路由器共享它們的知識並且將自身的信息廣播給其他每一個路由器。這樣,每一個路由器都能夠知道網路的結構以及狀態。
步驟四:使用一個合適的演算法,確定網路中兩個節點之間的最佳路由。