寫在前面：本文主要依據為《通信網絡基礎》李建東，盛敏編著,如有侵權，請聯系作者刪除。本文僅用于個人期末復習與知識結構的搭建。

文章目錄

• 第五章 路由算法
• • 5.1 路由算法概述
  • • 5.1.1路由選擇算法的分類
    • 5.1.2 對路由選擇算法的要求
    • 5.1.3路由算法的實現-路由表
    • 5.1.4 路由算法與流量控制的關系
  • 5.2 電路交換網中的路由
  • 5.3 分組交換網中的路由選擇
  • 5.4 最小代價算法
  • • 5.4.1 Dijkstra算法
    • 5.4.2 Bellman-Ford算法
    • 兩種最短路算法做題比較
  • 5.5 常用的路由算法
  • • 5.5.1廣域網中的路由算法
    • 5.5.2 互聯網中的路由算法
    • 5.5.3 Ad Hoc 網絡中的路由算法

第五章 路由算法

5.1 路由算法概述

現在，網絡設計者面臨的問題是：采用什么策略來選擇合適的路由？依據什么信息來進行這種選擇？應該如何執行這種選擇的策略？用什么標準來評判所選路徑的好壞？這些都是后面需要討論的問題。

一個路由算法應當在高的業務負荷的情況下，在保證相同的時延條件下，可以增加網絡的通過量；在輕負荷和中等負荷情況下，可以減少每
一個分組的平均時延。

5.1.1路由選擇算法的分類

一般是在每個節點設置一張路由表，用來決定該分組的輸出路徑。路由表應根據網絡的運行情況隨時加以修改、更新。每一個網絡都有反映自己特色要求和決定修改路由表的原則，這些原則體現為一種算法。網絡節點應根據所規定的算法，經過運算才能確定路由的選擇。

第一項功能通常包括一組在不同節點上運行的算法，這些算法相互之間交換必需的信息來互相支持，從而共同或單獨決定一條傳輸路徑。

路由算法的分類有多種方法，表5-1給出了路由選擇算法的基本要素，這些要素可以用來對路由選擇算法進行分類

（１）如果從路由選擇算法能否隨網絡的業務量或者拓撲變化自適應地進行調整來劃分，可分為兩大類：非自適應的和自適應的。非自適應算法不根據實測或估計的網絡當前業務量和拓撲結構來做路由選擇。例如，從某一節點ｉ到節點ｊ的路由對于節點ｉ和ｊ都是事先計算好的，在網絡啟動時就下載到網絡節點（路由器）中。這一過程也稱作靜態路由選擇。這種策略的最大優點是簡單和開銷小.

（２）如果按路由決策的方法來分，可分為：集中式和分布式。集中式路由算法是指網絡的路由是由路由控制中心計算的，該中心周期性收集各鏈路的狀態，經過路由計算后周期性地向各網絡節點提供路由表。分布式路由是指網絡中所有節點通過相互交換路由信息，獨立地計算到達各節點的路由。

（３）如果按應用場合來分，可分為：廣域網路由和互聯網路由。廣域網中的路由主要是用來解決一個子網內的路由，而互聯網中的路由主要解決不同子網之間的路由。

5.1.2 對路由選擇算法的要求

（１） 正確性：算法必須是正確的。即沿著各節點（交換機或路由器）中路由表所指引的路由，分組一定能夠最終到達目的節點（交換機或路由器）。并且，分組到達目的節點后不會再向其他節點（交換機或路由器）轉發該分組。
（２） 計算簡單：算法應使用節點上最少的運行資源，這樣可以節省開銷、減少時延，而且應該盡量少使用節點間鏈路的帶寬。如果為了計算合適的路由必須使用其他節點發來的大量狀態信息，額外開銷就會較大。
（３） 自適應性：又可稱為“穩健性”或“魯棒性”（robustness）。即算法能夠適應網絡業務量和拓撲的變化。當網絡總的業務量發生變化時，算法能自適應地改變路由。當節點、鏈路出現故障或修復后重新開始工作時，算法應能及時找到一條替換的路徑。
（４） 穩定性：算法必須收斂，當業務負載和拓撲變化時，沒有過多的振蕩。所謂振蕩，是指算法得出的整個或部分路徑是在多條可能路徑之間來回不停地變化，而不會穩定在一條可能的路徑上。
（５） 公平性：算法對所有的用戶必須是等同的。例如，僅考慮使某一對用戶的端到端時延為最小，它們就可能占用相對較多的網絡資源，這樣就明顯不符合公平性的要求。
（６） 最優性：路由選擇算法應該能提供最佳路由，從而使平均分組時延最小、吞吐量最大或可靠性最高。這里“最佳”可以是由多個因素決定的，如鏈路長度、數據率、鏈路容量、傳輸時延、節點緩沖區被占用的程度、鏈路的差錯率、分組的丟失率等。顯然不存在一種絕對最佳的路由算法，所謂“最佳”只能是相對于某一種特定準則要求下得出的較為合理的選擇而已。

實際上沒有一個算法能全部滿足上述要求，有的要求還可能是矛盾的。例如，要使吞吐量最大就可能會增加時延。然而，路由選擇的效能可能影響到時延隨吞吐量增加而增加的快慢程度，而且一個好的算法可能做到在一個較好的吞吐量門限以下，網絡的時延較小，而在這個門限值以上時延會過大，這時就必須進行流控，以保證網絡盡量工作在門限以下。

5.1.3路由算法的實現-路由表

節點上的路由表指明該節點如何選擇分組的傳送路徑，如圖５－２所示的網絡中，路由表的一個可能的例子如表５－２所示。

上述路徑選擇的原則是使到達目的節點的鏈路數（中轉的次數或跳數hops）最少。當存在２條以上具有相同鏈路數的最少鏈路數路徑時，可以選擇其中任意一條。路由表對每個目的節點指出分組應發向的下一個節點（輸出鏈路）。

在分布式路由計算過程中，各節點中關于某一對節點的路由信息可能不一致。不一致的路由表可能導致乒乓（Ｐｉｎｇ-Ｐｏｎｇ）效應，形成環路等現象。例如，節點ｉ上的路由表指出到目的節點ｍ 的最佳路徑是通過下一個節點ｊ，而節點ｊ上的路由表又指出下一個最佳節點是ｉ，則分組就會在節點ｉ和ｊ之間來回發送。當采用分布式算法時，特別是在適應網絡變化的過程中，很難消除暫時出現的路由環路。

當路由表建立起來之后，在進行路由選擇時只是簡單地查找路由表中的信息，無需再作計算。然而對自適應路由選擇來說，會要求相當數量的計算來維持這張路由表。

通常路由表中還會包含一些附加信息，例如基于最少鏈路數準則的算法可能包括到達目的節點的估計鏈路數，這樣表５－２所示的路由表要修改為表５－３所示的形式。

5.1.4 路由算法與流量控制的關系

路由選擇算法確定數據從源節點到目的節點傳送的路徑，而流量控制算法是限制允許到達某些數據鏈路或網絡某個部分的業務量，以防止這些鏈路或部分過分擁擠。這兩個算法往往要分別加以研究，但實際上它們是密切相關的，因為若路由算法把太多的業務量引導到同一區域內，則可能引發擁擠，從而需要采用流量控制算法。

路由選擇與流量控制（簡稱為流控）之間的一般關系可用圖５－３來說明。如圖所示，流控控制進入網絡的吞吐量，進入網絡的吞吐量影響到路由的選擇，路由選擇又影響到網絡分組傳輸的時延，而這一時延又影響流控所允許進入網絡的業務量，可能進一步影響到時延。路由選擇和流控總是處于這種動態的交互協調之中。**路由算法應當將網絡中分組時延維持在很低的水平上。**由于時延的存在，流控算法通過平衡通過量和時延的關系，采取必要措施來拒絕一些可能會引起網絡阻塞的業務，好的流控算法應當允許更多的業務流進入網絡。時延和通過量之間的嚴格平衡將由流控算法決定，而路由算法將決定不同的通過量對應的時延曲線。

5.2 電路交換網中的路由

從X到Y的交替路由舉例

5.3 分組交換網中的路由選擇

在分組交換網中，每個分組可以單獨選擇路由，也可以若干分組構成的序列選擇相同的路徑。

如果子網內部采用數據報的傳輸方式，則對每一個分組都要進行重新路由選擇。

如果子網內部采用虛電路的傳輸方式，則僅需在建立虛電路時，作一次路由選擇，以后數據就在這條建立起來的路由上進行數據傳送。

5.4 最小代價算法

5.4.1 Dijkstra算法

迪杰斯特拉算法舉例

以該圖為例，求結點1到其他各個結點的最短路

思路：
1初始化 ，T集合中只有源節點，其他相鄰的賦予邊權，不相鄰的邊權賦予∞
2 添加到源節點最短的邊 到T中
3.在T外選擇到源節點最短的邊 ，計算 min[L(n),L(x)+w(x,n)]最小值。

5.4.2 Bellman-Ford算法

以下圖為例，進行BF算法的過程進行模擬。

兩種最短路算法做題比較

1.Dijkstra算法：構造集合T，L(n)表示最小代價，相鄰的初始化，不相鄰的為無窮。不斷往T集合中添加，直到所有的結點添加完畢。

2.BF算法：h表示鏈路樹，初始化時全部為無窮。接著隨著h增大來迭代路徑，直到不再改變。

5.5 常用的路由算法

不同的應用場合對路由算法有不同的要求，正如前面討論的那樣，廣域網內的路由主要解決子網內分組的傳輸路徑問題，它主要包括三種路由算法：廣播、最短路由和最佳路由。而在互連網中則主要采用分層的網絡。目前還有一類網絡是Ad Hoc網絡，它是一種分布式的PRNET網絡，該網絡中使用了多種形式的路由算法。

5.5.1廣域網中的路由算法

1.廣播
廣播是通信網中最常用的方式，它用來傳播公共信息、拓撲變化信息（包括節點和鏈路工作變化和故障等信息）。廣播分組的接收節點通常是全網所有成員。如果接收節點僅為一個組或部分網絡節點，則稱為多播（multicast）。廣播時采用的路由算法可以有多種方法：如泛洪（flooding）路由、采用生成樹（spanning tree）的廣播方式等。當然也可以逐一地把要廣播的分組按照點對點的路由算法（unicast）發送給每一個目的節點，但這種方法可能會浪費大量的網絡資源，并且廣播節點需要知道全網所有節點的路由信息。

==泛洪路由的基本想法是源節點（發起廣播的節點）將消息以分組的形式發給其相鄰的節點，相鄰的節點再轉發給它們的相鄰節點，繼續下去，直至分組到達網絡中所有的節點。==為了限制分組的傳輸次數，需要兩個附加規則：
（１） 若節點Ｂ是從Ａ 收到一個廣播分組，則Ｂ不會將該廣播分組再轉發給Ａ；
（２） 每個節點僅將相同的廣播分組轉發給鄰節點最多一次。具體的實現方法是：源節點廣播的每一個分組都有一個標識符（ＩＤ）和序號，每發送一個新的分組，序號加１。每個節點在收到一個廣播分組后，要檢查該分組的標識符和序號，如果該分組的序號大于記錄中具有相同標識符分組的最大序號，則中轉該分組并記錄其標識符和序號，所有小于或等于記錄序號的分組都被丟棄，而不會被中轉，分組的廣播過程如圖５－４（ａ）所示。圖中箭頭上的標號表示該分組被中轉的次數。圖中Ａ 是廣播的發起節點。設Ｌ為網絡的鏈路數，該方法的分組傳輸次數在Ｌ～２Ｌ之間。為了減少廣播分組傳輸的次數，可以采用圖５－４（ｂ）的方法，首先構造一個生成樹，在該樹上分組僅需傳輸Ｎ－１次（Ｎ 為網絡的節點數）即可。

　
2.最短路由
許多實際的路由算法如ＲＩＰ（Routing Information Protocol），OSPF（Open Shortest Path First）等都是基于最短路徑這一概念。分組交換網絡的各種路由算法實質上都是建立在某種形式的最小費用準則的基礎上。譬如，把準則定為“最短路徑”，那就有所謂“最短路徑路由算法”；這里所說的“最短路徑”并不單純意味著一條物理長度最短的通路，它可以是從發送節點到達接收節點的中轉次數最少。

最短路由的一個關鍵是如何定義“費用”。如果最關心分組的時延，則可以把“費用”與時延相關聯。此時每條鏈路的“費用”明顯地與兩個參數有關：鏈路的物理長度和鏈路上的業務強度。前者決定信道的傳播時延，后者決定分組的發送等待時延。因此，如果能將上述兩個參數的值折算為該鏈路的費用或“長度”值（時延的大小），則最小費用算法也就等效為最小時延路由算法。所以，所謂“最短”取決于對鏈路長度的定義。長度通常是一個正數，它可以是物理距離長短、時延的大小、各個節點隊列長度等等。如果長度取１，則最短路由即為最小跳數（中轉次數）的路由。其次，鏈路的長度隨著時間可能是變化的，它取決于鏈路擁塞的情況。

3.最佳路由
上述最短路由僅關心的是一個節點對之間的一條路徑的選擇和求解，因而有兩個方面的缺陷：一是為每對節點之間僅提供一條路由，因而限制了網絡的通過量；二是適應業務變化的能力受到防止路由振蕩的限制。而最佳路由是從全網的范圍尋找所有可能的傳輸路徑，從而使得發送節點到達接收節點的信息流的時延最小、流量最大，而不是局限于一條所謂的最短路徑。因此，采用最佳路由（基于平均時延最佳化）可以克服最短路徑的上述缺陷，它可以將節點對之間的流量分配在多條路徑上，從而可使網絡的通過量最大，時延最小。

5.5.2 互聯網中的路由算法

為了實現網絡之間的互連，通常采用三種設備：網關、網橋和路由器。實現廣域網（ＷＡＮ）至廣域網（ＷＡＮ）之間的互連設備稱為網關（ｇａｔｅｗａｙ）。它完成相當復雜的網絡層的任務，包括協議轉換、路由功能等。它通常在網際子層。實現局域網（ＬＡＮ）與局域網（ＬＡＮ）之間在ＭＡＣ 層互連的設備稱為網橋（ｂｒｉｄｇｅ）。實現ＬＡＮ與ＷＡＮ或ＬＡＮ 與ＬＡＮ 之間互連的設備稱為路由器（Ｒｏｕｔｅｒ），它提供高級的路由功能。一個典型的互連網絡如圖５－５（ａ）所示。

可以以兩種觀點來看待一個互連的網絡，一是將互連的設備看成是一個附加的網絡節點，它與網絡中其他節點的地位等同，所有的節點組成一個更大的網絡。網絡中的每一個節點都維持一個到達各個節點的路由表（這個表通常會很大）。第二種觀點是把每個子網看成是一個節點，如圖５－５（ｂ）所示。這樣將網絡分為兩層，高層是由互連設備和子網組成的網絡，低層是各子網的內部網絡。在這種分層的方式中，Ｇａｔｅｗａｖ或Ｒｏｕｔｅｒ只維持到達各個子網的路由表，各個子網僅維持子網內的路由表。這樣路由表的維持和修正的負荷相對較小和易于操作。分層的缺點是所形成的路由對整個網絡而言不一定是最佳的。

從上面的討論中可以看到，隨著網絡的增大，路由表中存儲的內容也將不斷的增大。增大的路由表不僅占用路由器的內存，而且需要更多的ＣＰＵ 時間掃描表格，以及需要更大的鏈路容量來傳送關于路由表的狀態報告。因此，為了實現充分利用有限資源的同時，還可以實現網絡擴展，必須進行分級路由選擇。

所謂分級路由選擇是指：將路由器劃分為區域，每個路由器僅知道怎樣在其所屬區域內選擇路由和知道分組在該區域要到達的目的端的全部細節，但并不知道其他區域的內部結構。當不同的網絡相連時，很自然地將每個網絡看作為獨立的區域，以便讓一個網絡中的路由器免于知道其他網絡的拓撲結構，從而有效地減少了每個路由表的存儲內容。

對于大型的網絡而言，通常需要分成多級。圖５－６給出了在有五個區域的兩級結構中作路由選擇的一個例子。路由器１Ａ的整個路由表共有１７個表項，如圖５－６（ｂ）所示。在圖５－６（ｃ）中，所有其他區域都被抽象為一個單獨的路由器，大大節省了存儲空間。因此，到區域２ 的所有業務都經過１Ｂ－２Ａ 這條路徑，其余的業務量都經過１Ｃ－３Ｂ這條路徑。分級路由選擇將路由器１Ａ 的路由表從１７個表項減少到７個。如果區域數和區域內的路由器的比例增大時，節省的存儲空間也會按比例增大。

5.5.3 Ad Hoc 網絡中的路由算法

總結

以上是生活随笔為你收集整理的通信网络基础期末复习-第五章-路由算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。