[科普中國]-路由選擇語句

靜態(tài)路由選擇算法

靜態(tài)路由選擇算法是指采用某種路由選擇算法預(yù)先計算出每個路由器的路由表，在路由器加電啟動時加載到路由器中。在路由器工作過程中，路由表內(nèi)容保持不變。如果網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)或其他網(wǎng)絡(luò)參數(shù)發(fā)生變化，則需要重新預(yù)先計算出各個路由器的路由表，并重新加載到路由器中。這種路由選擇算法也稱固定路由選擇算法。

在靜態(tài)路由選擇算法中，有最短路徑(Shortest Path，SP)和基于流量的路由選擇(Flow—based Routing，F(xiàn)R)等。

最短路徑選擇在最短路徑選擇中，根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)將一個通信網(wǎng)絡(luò)表示成一個加權(quán)無向圖。

圖中每個節(jié)點代表網(wǎng)絡(luò)中的路由器，連線代表通信線路，連線上標(biāo)注的數(shù)字代表線路的權(quán)值。權(quán)值可以用線路長度、信道帶寬、平均通信量、通信費用、隊列長度、線路延時以及占用可用資源數(shù)量等加權(quán)函數(shù)計算出來。SP算法就是根據(jù)線路的加權(quán)值尋找出最短路徑。SP算法最初是由Dijkstra提出的，故也稱Dijkstra算法。

SP算法是一個逐步搜索過程，其搜索過程如下。

(1)假如在第m步已經(jīng)搜索到一個最短路徑，該路徑上有n個距離源節(jié)點最近的節(jié)點，它們構(gòu)成了一個節(jié)點集合N；

(2)在第m+1步，繼續(xù)搜索不屬于N的距離源節(jié)點最近的節(jié)點，并搜索到的節(jié)點加入到N中；

(3)繼續(xù)搜索，直至到達(dá)目的節(jié)點，N中的節(jié)點集合便是從源節(jié)點到目的節(jié)點的最短路徑。

在搜索過程中，每個節(jié)點用從源節(jié)點沿已知的最短路徑到本節(jié)點的距離來標(biāo)注，例如，在B(2，A)標(biāo)注中，B表示本節(jié)點名，2表示在最短路徑上源節(jié)點到本節(jié)點的距離(權(quán)值累加)，A表示最短路徑上的上游節(jié)點名。在初始時，由于最短路徑是未知的，故所有節(jié)點都標(biāo)注為無窮大()。隨著算法的進(jìn)展和不斷搜索到最短路徑，節(jié)點的標(biāo)注值也隨之改變，反映出一個較好的路徑。

每個路由器節(jié)點按照上述的SP算法計算出節(jié)點間的最短路徑，形成路由表，在路由器加電啟動時加載到路由器中。在路由器工作過程中，將根據(jù)數(shù)據(jù)分組中的目的地址查找路由表，找出最短的路徑來轉(zhuǎn)發(fā)數(shù)據(jù)分組。

基于流量的路由選擇SP算法只是根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)計算最短路徑，而沒有考慮通信流量或負(fù)載。FR算法則考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和通信流量兩方面因素進(jìn)行路由選擇。

在一些網(wǎng)絡(luò)中，節(jié)點之間的通信流量是相對穩(wěn)定和可預(yù)測的。如果預(yù)先知道節(jié)點之間平均通信流量的條件下，采用適當(dāng)?shù)乃惴▽νㄐ帕髁窟M(jìn)行數(shù)學(xué)分析，可以優(yōu)化路由選擇。FR算法的基本條件是：

(1)必須知道網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；

(2)必須知道節(jié)點之間平均通信流量；

(3)必須知道各條線路的容量；

FR算法的基本原理是：對于一個給定的線路，如果已知該線路的負(fù)荷量和平均流量，則可以用隊列理論計算出該線路的平均分組延遲。由所有的線路平均延遲可直接計算出流量加權(quán)平均值，從而得到整個網(wǎng)絡(luò)的平均分組延遲。于是，路由選擇問題就可歸結(jié)為如何找出產(chǎn)生網(wǎng)絡(luò)最小延遲的路由選擇算法。1

動態(tài)路由選擇算法網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和通信量是動態(tài)變化的，如路由器的加入或退出，網(wǎng)絡(luò)發(fā)生擁擠或阻塞等。如果路由器能夠及時獲得這些網(wǎng)絡(luò)動態(tài)變化情況，并以此作為路由選擇的依據(jù)，則會有助于路由器優(yōu)化路由選擇。動態(tài)路由選擇算法就是采用這一機理進(jìn)行路由選擇的．它也稱自適應(yīng)路由選擇算法。

現(xiàn)代計算機網(wǎng)絡(luò)系統(tǒng)通常采用動態(tài)路由選擇算法。在動態(tài)路由選擇算法中，最常用的有距離矢量路由選擇和鏈路狀態(tài)路由選擇兩種算法。

距離矢量路由選擇距離矢量路由選擇(Distance Vector Routing，DVR)算法的基本原理是每個路由器都維護(hù)一個路由表，表中記錄有通向目的節(jié)點的最佳距離和線路，每個路由器都要與相鄰的路由器交換路由信息來更新路由表，使路由表中的信息總是反映網(wǎng)絡(luò)最新的動態(tài)變化情況。

DVR算法最初應(yīng)用于ARPANET中，后被其他網(wǎng)絡(luò)所采用，如DECnet、Novell的IPX協(xié)議、Apple的AppleTalk協(xié)議以及Cisco路由器等。著名的路由選擇信息協(xié)議(Routing Information Protocol，RIP)也是基于該算法開發(fā)的。

在DVR算法中，每個路由器都維護(hù)一個路由表，表中的每個表項都對應(yīng)網(wǎng)絡(luò)中的一個路由器，每個表項包含兩部分內(nèi)容：一是通往目的節(jié)點的輸出線路；二是到達(dá)目的節(jié)點的距離或所需時間估算值，估算值的度量標(biāo)準(zhǔn)可以是節(jié)點數(shù)、時間延遲估算值、該路由的隊列長度等。路由器要選擇一種度量標(biāo)準(zhǔn)來估算本節(jié)點與目的節(jié)點之間的距離，如果選擇節(jié)點數(shù)，則一個距離長度為一個節(jié)點；如果選擇隊列長度，則路由器檢查每個隊列；如果選擇時間延遲，則路由器可以通過向相鄰路由器發(fā)送一個特殊的回應(yīng)(Echo)分組請求對方回送帶有時間標(biāo)記的分組來獲得時間延遲值。

在一個網(wǎng)絡(luò)系統(tǒng)中．每個路由器都按約定(或路由協(xié)議)采用某種度量標(biāo)準(zhǔn)來估算它到達(dá)目的節(jié)點的距離，并傳送給相鄰路由器；同時，它也會從相鄰路由器中得到類似的估算值，并以此更新路由表。這樣，路由器就可以從路由表上這些估算值中找出最佳值，該估算值對應(yīng)的輸出線路便是最佳路由，并選擇該路由轉(zhuǎn)發(fā)數(shù)據(jù)分組。

鏈路狀態(tài)路由選擇DVR算法存在兩個主要缺陷：一是在選擇路由時沒有考慮線路帶寬，而線路帶寬隨著網(wǎng)絡(luò)技術(shù)的發(fā)展在不斷地提高；二是算法在獲取路由信息時需要耗費很多的時間。因此，DVR算法后來被鏈路狀態(tài)路由選擇(Line State Routing，LSR)算法所取代?，F(xiàn)在，各種各樣的LSR算法廣泛應(yīng)用于現(xiàn)代網(wǎng)絡(luò)系統(tǒng)中，著名的開放最短路徑優(yōu)先(Open Shortest Path First，OSPF)協(xié)議采用的就是LSR算法，而OSPF協(xié)議廣泛應(yīng)用于Internet中。

每個路由器上的LSR算法都要執(zhí)行如下過程。

(1)發(fā)現(xiàn)相鄰路由器，獲取其網(wǎng)絡(luò)地址。當(dāng)一個路由器加入網(wǎng)絡(luò)后，首先向每個相鄰路由器發(fā)送一個特殊的Hello分組，目的是聲明它的存在，并希望得到相鄰路由器的響應(yīng)。各個相鄰路由器接收到Hello分組后，都回應(yīng)一個包含本路由器地址的響應(yīng)分組。每個路由器地址應(yīng)是一個全局唯一的地址。

(2)測量到各個相鄰路由器的時間延遲或線路開銷。一個路由器可通過發(fā)送Echo分組來測量到各個相鄰路由器的延遲，各個相鄰路由器接收到Echo分組后，都回應(yīng)一個包含時間標(biāo)記的響應(yīng)分組。從發(fā)送Echo分組開始到接收到響應(yīng)分組所經(jīng)歷時間除以2，便是該線路的延遲時間估算值。它反映了線路帶寬狀況，線路帶寬越大，延遲時間越??；反之，線路帶寬越小，延遲時間越大。

(3)將測量值通告給其他的路由器。路由器在獲得有關(guān)路由器和鏈路狀態(tài)信息后，構(gòu)造一個特殊的鏈路狀態(tài)(LS)分組來發(fā)布鏈路狀態(tài)信息，該分組包含發(fā)送者地址、序號、生存期以及各個相鄰路由器地址和對應(yīng)的延遲時間估算值等信息。該分組可以周期性地發(fā)送。也可以在網(wǎng)絡(luò)發(fā)生重大事件時發(fā)送，并采用如下的傳遞機制。

①路由器采用擴散法周期地向所有的線路廣播LS分組，每發(fā)送一個新的LS分組，分組的序號加1。

②相鄰路由器接收到LS分組后，通過核對發(fā)送者地址和序號來判斷LS分組是否是重復(fù)的或過時的。如果是新的LS分組，則在路由表中記錄新的鏈路狀態(tài)信息，并向除輸人線路之外的所有線路擴散，傳播給其他的路由器；如果是重復(fù)的LS分組．說明它已從其他的路徑接收到了該分組，則丟棄該分組；如果LS分組的序號小于以前曾收到的來自同一發(fā)送者的LS分組序號，說明該分組是一個過時的LS分組，則丟棄該分組。為了避免序號沖突問題。序號采用較長位數(shù)，如32位，序號以232為模，循環(huán)周期為232。

③鏈路狀態(tài)信息以軟狀態(tài)方式保存在路由器中，路由器定期地(如每隔ls)檢查它所記錄的LS分組的生存期，并減1。如果一個LS分組的生存期減至0，則刪除來自該LS分組的鏈路狀態(tài)信息。這樣就避免了無效的或出錯的鏈路狀態(tài)信息長期占據(jù)路由器的存儲空間。

這樣，一個路由器所測量的鏈路狀態(tài)信息通過上述的傳遞機制發(fā)布給網(wǎng)絡(luò)中所有的路由器。每個路由器用接收到的LS分組來建立和更新其路由表。

(4)最短路徑。各個路由器在建立路由表后，可采用Dijkstra算法計算到達(dá)目的節(jié)點的最短路徑，并按該路徑轉(zhuǎn)發(fā)數(shù)據(jù)分組。1

特點在路由器啟動之后，立刻與其相鄰路由設(shè)備建立路由關(guān)系。該初始通信的目的是為了識別相鄰設(shè)備，開始進(jìn)行通信并學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)。建立相鄰關(guān)系的方法和對拓?fù)浣Y(jié)構(gòu)的初始學(xué)習(xí)隨路由選擇協(xié)議選擇的不同而不同。

路由選擇協(xié)議會定期交換HELLO消息或路由更新數(shù)據(jù)包，以維持相鄰設(shè)備間的可達(dá)性。一個理想的路由選擇算法應(yīng)具有以下特點：

(1)路由算法必須具有正確性和完整性。一個數(shù)據(jù)包能根據(jù)路由算法所生成的路由表把該數(shù)據(jù)包指引到最終的目的網(wǎng)絡(luò)和目的主機。

(2)簡單性。路由選擇算法在生成路由表時在計算上應(yīng)該簡單，且不應(yīng)使網(wǎng)絡(luò)的通信流量增加太多的額外開銷。

(3)適應(yīng)性。路由選擇算法能根據(jù)目前網(wǎng)絡(luò)的狀態(tài)和網(wǎng)絡(luò)的流量動態(tài)地改變路由以均衡網(wǎng)絡(luò)各鏈路的負(fù)載。即當(dāng)網(wǎng)絡(luò)的某個節(jié)點、鏈路發(fā)生故障不能正常工作時，或者修理好了再投入運行時，算法也能及時地改變路由。

(4)穩(wěn)定性。在網(wǎng)絡(luò)通信量和網(wǎng)絡(luò)拓?fù)湎鄬Ψ€(wěn)定的情況下，路由算法應(yīng)收斂于一個可以接受的解，而不應(yīng)使路由不停地變化。

(5)公平性。路由選擇算法對所有用戶都是平等的。

(6)最佳性。最佳性是指以最低的代價來實現(xiàn)路由算法。這里的代價是指由一個或幾個綜合因素決定的度量(Metric)，如鏈路長度、數(shù)據(jù)率、鏈路容量、傳播時延等。所以這里的最佳性只能是相對于某一種特定要求下得出的較為合理的選擇而已。2