壹 臺主機通常直接與壹臺路由器相連接，該路由器即為該主機的默認路由器，又稱為該主機的默認網關。 每當某主機向外部網絡發送壹個分組時，該分組都被傳送給它的默認網關。
如果將源主機的默認網關稱為源路由器,把目的主機的默認網關稱為目的路由器。為壹個分組從源主機到目的主機選路的問題於 是可歸結為從源路由器到目的路由器的選路問題。
選路算法的目標很簡單:給定壹組路由器以及連接路由器的鏈路，選路算法要找到壹條從源路由器到目的路由器的最好路徑，通常壹條好路徑是指具有最低費用的路徑。
圖 G=(N，E)是壹個 N 個節點和 E 條邊的集合，其中每條邊是來自 N 的壹對節點。在網 絡選路的環境中，節點表示路由器，這是做出分組轉發決定的節點，連接節點的邊表示路由 器之間的物理鏈路。
壹條邊有壹個值表示它的費用。通常壹條邊的費用可反映出對應鏈路的物理長度、鏈路速度或與該鏈路相關的費用。
對於 E 中的任壹條邊(xy)可以用 c(xy )表示節點 x 和 y 間邊的費用。壹般考慮的都是無向 圖，因此邊(xy)與邊(y x)是相同的並且開銷相等。節點 y 也被稱為節點 x 的鄰居。
在圖中為各條邊指派了費用後，選路算法的目標自然是找出從源到目的間的最低費用路徑。圖 G=(N，E)中的壹條路徑(Path)是壹個節點的序列，使得每壹對以(x1,x2)， (x2,x3)，…，是 E 中的邊。路徑的費用是沿著路徑所有邊費用的總和。
從廣義上來說，我們對 選路算法分類的壹種方法就是根據該算法是全局性還是分布式來區分的。
.全局選路算法： 用完整的、全局性的網絡信息來計算從源到目的之間的最低費用路徑。
實際上， 具有全局狀態信息的算法常被稱作鏈路狀態 LS 算法， 因為該算法必須知道網絡中每條鏈路的費用。
.分布式選路算法： 以叠代的、分布式的方式計算出最低費用路徑。通過叠代計算並與相鄰節點交換信息，逐漸計算出到達某目的節點或壹組目的節點的最低費用路徑。
DV 算法是分布式選路算法， 因為每個節點維護到網絡中的所有其他節點的費用(距離)估計的矢量。
選路算法的第二種廣義分類方法是根據算法是靜態的還是動態的來分類。
壹： 鏈路狀態選路算法 LS
在鏈路狀態算法中，通過讓每個節點向所有其他路由器廣播鏈路狀態分組， 每個鏈路狀態分組包含它所連接的鏈路的特征和費用， 從而網絡中每個節點都建立了關於整個網絡的拓撲。
Dijkstra 算法計算從源節點到網絡中所有其他節點的最低費用路徑.
Dijkstra 算法是叠代算法，經算法的第 k 次叠代後，可知道到 k 個目的節點的最低費用路徑。
定義下列記號:
D(V)隨著算法進行本次叠代，從源節點到目的節點的最低費用路徑的費用。
P(v)從源節點到目的節點 v 沿著當前最低費用路徑的前壹節點(，的鄰居)。
N`節點子集；如果從源節點到目的節點 v 的最低費用路徑已找到，那麽 v 在 N`中。
Dijkstra 全局選路算法由壹個初始化步驟和循環組成。循環執行的次數與網絡中的節點個數相同。在結束時，算法會計算出從源節點 u 到網絡中每個其他節點的最短路徑。
考慮圖中的網絡，計算從 u 到所有可能目的地的最低費用路徑。
.在初始化階段 ，從 u 到與其直接相連的鄰居 v、x、w 的當前已知最低費用路徑分別初始化為 2，1 和 5。到 y 與 z 的費用被設為無窮大，因為它們不直接與 u 連接。
.在第壹次叠代時， 需要檢查那些還未加到集合 N`中的節點，找出在前壹次叠代結束時具有最低費用的節點。那個節點是 x 其費用是 1，因此 x 被加到集合 N`中。然後更新所有節點的 D(v)，產生下表中第 2 行(步驟)所示的結果。到 v 的路徑費用未變。經過節點 x 到 w 的 路徑的費用被確定為 4。因此沿從 u 開始的最短路徑到 w 的前壹個節點被設為 x。類似地， 到 y 經過 x 的費用被計算為 2，且該表項也被更新。
.在第二次叠代時 ，節點 v 與 y 被發現具有最低費用路徑 2。任意選擇將 y 加到集合 N` 中，使得 N’中含有 u、x 和 y。通過更新，產生如表中第 3 行所示的結果。
.以此類推…
當 LS 算法結束時，對於每個節點都得到從源節點沿著它的最低費用路徑的前繼節點， 對於每個前繼節點，又有它的前繼節點，按照此方式可以構建從源節點到所有目的節點的完 整路徑。
根據從 u 出發的最短路徑，可以構建壹個節點(如節點 u)的轉發表。
二 距離矢量選路算法 DV
LS 算法是壹種使用全局信息的算法，而距離矢量算法是壹種叠代的、異步的和分布式的算法。
Bellman-Ford 方程：
設 dx(y)是從節點 x 到節點 y 的最低費用路徑的費用，則有? dx(y) = min {c(x,v) + dv(y) }
PS： 方程中的 min，是指取遍 x 的所有鄰居。
Bellman-Ford 方程含義相當直觀，意思是從 x 節點出發到 y 的最低費用路徑肯定經過 x 的某個鄰居，而且 x 到這個鄰居的費用加上這個鄰居到達目的節點 y 費用之和在所有路徑 中其總費用是最小的。 實際上，從 x 到 v 遍歷之後，如果取從 v 到 y 的最低費用路徑，該路 徑費用將是 c(x,v)+ dv(y)。因此必須從遍歷某些鄰居 v 開始，從 x 到 y 的最低費用是對所有鄰 居的 c(x,v)+dv(y)的最小值。
在該 DV 算法中，當節點 x 看到它的直接相連的鏈路費用變化，或從某個鄰居接收到壹 個距離矢量的更新時，就根據 Bellman-Ford 方程更新其距離矢量表。
三 LS 與 DV 選路算法的比較
DV 和 LS 算法采用不同的方法來解決計算選路問題。
在 DV 算法中，每個節點僅與它的直接相連鄰居交換信息，但它為它的鄰居提供了從其 自己到網絡中(它所知道的)所有其他節點的最低費用估計。
在 LS 算法中，每個節點(經廣播)與所有其他節點交換信息，但它僅告訴它們與它直接 相連鏈路的費用。
·報文復雜性：
LS 算法要求每個節點都知道網絡中每條鏈路的費用，需要發送 O(nE)個消息。
DV 算法要求在每次叠代時，在兩個直接相連鄰居之間交換報文，算法收斂所需的時間 依賴於許多因素。當鏈路費用改變時，DV 算法僅當在會導致該節點的最低費用路徑發生改 變時，才傳播已改變的鏈路費用。
·收效速度：
DV算法收斂較慢，且在收斂時會遇到選路環路。DV算法還會遭受到計數到無窮的問題。
?健壯性：? 在 LS 算法中，如果壹臺路由器發生故障、或受到破壞，路由器會向其連接的鏈路廣播 不正確費用，導致整個網絡的錯誤。
在 Dv 算法下， 每次叠代時，其中壹個節點的計算結果會傳遞給它的鄰居，然後在下次叠代時再間接地傳遞給鄰居的鄰居。在這種情況下，DV 算法中壹個不正確的計算結果也會擴散到整個網絡。
四.層次選路
兩個原因導致層次的選路策略：
?規模： 隨著路由器數目增長，選路信息的計算、存儲及通信的開銷逐漸增高。
?管理自治： 壹般來說，壹個單位都會要求按自己的意願運行路由器(如運行其選擇的某 種選路算法)，或對外部隱藏其內部網絡的細節。
層次的選路策略是通過將路由器劃分成自治系統 AS 來實施的。
每個 AS 由壹組通常在相同管理控制下的路由器組成(例如由相同的 ISP 運營或屬於相同 的公司網絡)。在相同的 AS 內的路由器都全部運行同樣的選路算法。
在壹個自治系統內運行的選路算法叫做自治系統內部選路協議。 在壹個 AS 邊緣的壹臺 或多臺路由器，來負責向本 AS 之外的目的地轉發分組，這些路由器被稱為網關路由器
在各 AS 之間，AS 運行相同的自治系統間選路協議。