網(wǎng)絡層必須確定從發(fā)送方到接收方分組所經(jīng)過的路徑盾戴。選路就是在網(wǎng)絡中的路由器里的給某個數(shù)據(jù)報確定好路徑(即路由)。
一臺主機通常直接與一臺路由器相連接茧妒，該路由器即為該主機的默認路由器姿骏，又稱為該主機的默認網(wǎng)關身笤。每當某主機向外部網(wǎng)絡發(fā)送一個分組時豹悬，該分組都被傳送給它的默認網(wǎng)關。
如果將源主機的默認網(wǎng)關稱為源路由器,把目的主機的默認網(wǎng)關稱為目的路由器液荸。為一個分組從源主機到目的主機選路的問題于是可歸結為從源路由器到目的路由器的選路問題瞻佛。
選路算法的目標很簡單:給定一組路由器以及連接路由器的鏈路，選路算法要找到一條從源路由器到目的路由器的最好路徑娇钱，通常一條好路徑是指具有最低費用的路徑伤柄。
圖 G=(N，E)是一個 N 個節(jié)點和 E 條邊的集合文搂，其中每條邊是來自 N 的一對節(jié)點适刀。在網(wǎng) 絡選路的環(huán)境中，節(jié)點表示路由器煤蹭，這是做出分組轉發(fā)決定的節(jié)點笔喉，連接節(jié)點的邊表示路由 器之間的物理鏈路。
一條邊有一個值表示它的費用硝皂。通常一條邊的費用可反映出對應鏈路的物理長度常挚、鏈路速度或與該鏈路相關的費用。
對于 E 中的任一條邊(xy)可以用 c(xy )表示節(jié)點 x 和 y 間邊的費用稽物。一般考慮的都是無向 圖奄毡，因此邊(xy)與邊(y x)是相同的并且開銷相等。節(jié)點 y 也被稱為節(jié)點 x 的鄰居贝或。
在圖中為各條邊指派了費用后秧倾，選路算法的目標自然是找出從源到目的間的最低費用路徑。圖 G=(N傀缩，E)中的一條路徑(Path)是一個節(jié)點的序列那先，使得每一對以(x1,x2)， (x2,x3)赡艰，…售淡，是 E 中的邊。路徑的費用是沿著路徑所有邊費用的總和慷垮。
從廣義上來說揖闸，我們對選路算法分類的一種方法就是根據(jù)該算法是全局性還是分布式來區(qū)分的。
.全局選路算法：用完整的料身、全局性的網(wǎng)絡信息來計算從源到目的之間的最低費用路徑汤纸。
實際上，具有全局狀態(tài)信息的算法常被稱作鏈路狀態(tài) LS 算法芹血，因為該算法必須知道網(wǎng)絡中每條鏈路的費用贮泞。
.分布式選路算法：以迭代的楞慈、分布式的方式計算出最低費用路徑。通過迭代計算并與相鄰節(jié)點交換信息啃擦，逐漸計算出到達某目的節(jié)點或一組目的節(jié)點的最低費用路徑囊蓝。
DV 算法是分布式選路算法，因為每個節(jié)點維護到網(wǎng)絡中的所有其他節(jié)點的費用(距離)估計的矢量令蛉。
選路算法的第二種廣義分類方法是根據(jù)算法是靜態(tài)的還是動態(tài)的來分類聚霜。
一： 鏈路狀態(tài)選路算法 LS
在鏈路狀態(tài)算法中，通過讓每個節(jié)點向所有其他路由器廣播鏈路狀態(tài)分組珠叔，每個鏈路狀態(tài)分組包含它所連接的鏈路的特征和費用蝎宇，從而網(wǎng)絡中每個節(jié)點都建立了關于整個網(wǎng)絡的拓撲。
Dijkstra 算法計算從源節(jié)點到網(wǎng)絡中所有其他節(jié)點的最低費用路徑.
Dijkstra 算法是迭代算法祷安，經(jīng)算法的第 k 次迭代后姥芥，可知道到 k 個目的節(jié)點的最低費用路徑。
定義下列記號:
D(V)隨著算法進行本次迭代辆憔，從源節(jié)點到目的節(jié)點的最低費用路徑的費用撇眯。
P(v)從源節(jié)點到目的節(jié)點 v 沿著當前最低費用路徑的前一節(jié)點(，的鄰居)虱咧。
N`節(jié)點子集熊榛；如果從源節(jié)點到目的節(jié)點 v 的最低費用路徑已找到，那么 v 在 N`中腕巡。
Dijkstra 全局選路算法由一個初始化步驟和循環(huán)組成玄坦。循環(huán)執(zhí)行的次數(shù)與網(wǎng)絡中的節(jié)點個數(shù)相同。在結束時绘沉，算法會計算出從源節(jié)點 u 到網(wǎng)絡中每個其他節(jié)點的最短路徑煎楣。
考慮圖中的網(wǎng)絡，計算從 u 到所有可能目的地的最低費用路徑车伞。
.在初始化階段择懂，從 u 到與其直接相連的鄰居 v、x另玖、w 的當前已知最低費用路徑分別初始化為 2困曙，1 和 5。到 y 與 z 的費用被設為無窮大谦去，因為它們不直接與 u 連接慷丽。
.在第一次迭代時，需要檢查那些還未加到集合 N`中的節(jié)點鳄哭，找出在前一次迭代結束時具有最低費用的節(jié)點要糊。那個節(jié)點是 x 其費用是 1，因此 x 被加到集合 N`中妆丘。然后更新所有節(jié)點的 D(v)锄俄，產(chǎn)生下表中第 2 行(步驟)所示的結果局劲。到 v 的路徑費用未變。經(jīng)過節(jié)點 x 到 w 的 路徑的費用被確定為 4珊膜。因此沿從 u 開始的最短路徑到 w 的前一個節(jié)點被設為 x容握。類似地宣脉， 到 y 經(jīng)過 x 的費用被計算為 2车柠，且該表項也被更新。
.在第二次迭代時塑猖，節(jié)點 v 與 y 被發(fā)現(xiàn)具有最低費用路徑 2竹祷。任意選擇將 y 加到集合 N` 中，使得 N’中含有 u羊苟、x 和 y塑陵。通過更新，產(chǎn)生如表中第 3 行所示的結果焚虱。
.以此類推…
當 LS 算法結束時粟按，對于每個節(jié)點都得到從源節(jié)點沿著它的最低費用路徑的前繼節(jié)點镀岛， 對于每個前繼節(jié)點，又有它的前繼節(jié)點兼都，按照此方式可以構建從源節(jié)點到所有目的節(jié)點的完 整路徑。
根據(jù)從 u 出發(fā)的最短路徑稽寒，可以構建一個節(jié)點(如節(jié)點 u)的轉發(fā)表扮碧。
二 距離矢量選路算法 DV
LS 算法是一種使用全局信息的算法，而距離矢量算法是一種迭代的杏糙、異步的和分布式的算法慎王。
Bellman-Ford 方程：
設 dx(y)是從節(jié)點 x 到節(jié)點 y 的最低費用路徑的費用，則有?dx(y) = min {c(x,v) + dv(y) }
PS：方程中的 min宏侍，是指取遍 x 的所有鄰居赖淤。
Bellman-Ford 方程含義相當直觀，意思是從 x 節(jié)點出發(fā)到 y 的最低費用路徑肯定經(jīng)過 x 的某個鄰居谅河，而且 x 到這個鄰居的費用加上這個鄰居到達目的節(jié)點 y 費用之和在所有路徑 中其總費用是最小的咱旱。實際上，從 x 到 v 遍歷之后旧蛾，如果取從 v 到 y 的最低費用路徑莽龟，該路 徑費用將是 c(x,v)+ dv(y)。因此必須從遍歷某些鄰居 v 開始锨天，從 x 到 y 的最低費用是對所有鄰 居的 c(x,v)+dv(y)的最小值毯盈。
在該 DV 算法中，當節(jié)點 x 看到它的直接相連的鏈路費用變化病袄，或從某個鄰居接收到一 個距離矢量的更新時搂赋，就根據(jù) Bellman-Ford 方程更新其距離矢量表赘阀。
三 LS 與 DV 選路算法的比較
DV 和 LS 算法采用不同的方法來解決計算選路問題。
在 DV 算法中脑奠，每個節(jié)點僅與它的直接相連鄰居交換信息基公，但它為它的鄰居提供了從其 自己到網(wǎng)絡中(它所知道的)所有其他節(jié)點的最低費用估計。
在 LS 算法中宋欺，每個節(jié)點(經(jīng)廣播)與所有其他節(jié)點交換信息轰豆，但它僅告訴它們與它直接 相連鏈路的費用。
·報文復雜性：
LS 算法要求每個節(jié)點都知道網(wǎng)絡中每條鏈路的費用齿诞，需要發(fā)送 O(nE)個消息酸休。
DV 算法要求在每次迭代時，在兩個直接相連鄰居之間交換報文祷杈，算法收斂所需的時間 依賴于許多因素斑司。當鏈路費用改變時，DV 算法僅當在會導致該節(jié)點的最低費用路徑發(fā)生改 變時但汞，才傳播已改變的鏈路費用宿刮。
·收效速度：
DV算法收斂較慢，且在收斂時會遇到選路環(huán)路私蕾。DV算法還會遭受到計數(shù)到無窮的問題僵缺。
?健壯性：?在 LS 算法中，如果一臺路由器發(fā)生故障是目、或受到破壞谤饭，路由器會向其連接的鏈路廣播 不正確費用，導致整個網(wǎng)絡的錯誤懊纳。
在 Dv 算法下揉抵， 每次迭代時，其中一個節(jié)點的計算結果會傳遞給它的鄰居嗤疯，然后在下次迭代時再間接地傳遞給鄰居的鄰居冤今。在這種情況下，DV 算法中一個不正確的計算結果也會擴散到整個網(wǎng)絡茂缚。
四.層次選路
兩個原因?qū)е聦哟蔚倪x路策略：
?規(guī)模：隨著路由器數(shù)目增長戏罢，選路信息的計算、存儲及通信的開銷逐漸增高脚囊。
?管理自治：一般來說龟糕，一個單位都會要求按自己的意愿運行路由器(如運行其選擇的某 種選路算法)，或?qū)ν獠侩[藏其內(nèi)部網(wǎng)絡的細節(jié)悔耘。
層次的選路策略是通過將路由器劃分成自治系統(tǒng) AS 來實施的讲岁。
每個 AS 由一組通常在相同管理控制下的路由器組成(例如由相同的 ISP 運營或?qū)儆谙嗤?的公司網(wǎng)絡)。在相同的 AS 內(nèi)的路由器都全部運行同樣的選路算法。
在一個自治系統(tǒng)內(nèi)運行的選路算法叫做自治系統(tǒng)內(nèi)部選路協(xié)議缓艳。在一個 AS 邊緣的一臺 或多臺路由器校摩，來負責向本 AS 之外的目的地轉發(fā)分組，這些路由器被稱為網(wǎng)關路由器
在各 AS 之間阶淘，AS 運行相同的自治系統(tǒng)間選路協(xié)議衙吩。
