路由算法典型種類(lèi)

路由算法LS算法

采用LS算法時(shí)，每個(gè)路由器必須遵循以下步驟：

1、確認(rèn)在物理上與之相連的路由器并獲得它們的IP地址。當(dāng)一個(gè)路由器開(kāi)始工作后，它首先向整個(gè)網(wǎng)絡(luò)發(fā)送一個(gè)“HELLO”分組數(shù)據(jù)包。每個(gè)接收到數(shù)據(jù)包的路由器都將返回一條消息，其中包含它自身的IP地址。

2、測(cè)量相鄰路由器的延時(shí)（或者其他重要的網(wǎng)絡(luò)參數(shù)，比如平均流量）。為做到這一點(diǎn)，路由器向整個(gè)網(wǎng)絡(luò)發(fā)送響應(yīng)分組數(shù)據(jù)包。每個(gè)接收到數(shù)據(jù)包的路由器返回一個(gè)應(yīng)答分組數(shù)據(jù)包。將路程往返時(shí)間除以2，路由器便可以計(jì)算出延時(shí)。（路程往返時(shí)間是網(wǎng)絡(luò)當(dāng)前延遲的量度，通過(guò)一個(gè)分組數(shù)據(jù)包從遠(yuǎn)程主機(jī)返回的時(shí)間來(lái)測(cè)量。）該時(shí)間包括了傳輸和處理兩部分的時(shí)間——也就是將分組數(shù)據(jù)包發(fā)送到目的地的時(shí)間以及接收方處理分組數(shù)據(jù)包和應(yīng)答的時(shí)間。

3、向網(wǎng)絡(luò)中的其他路由器廣播自己的信息，同時(shí)也接收其他路由器的信息。

在這一步中，所有的路由器共享它們的知識(shí)并且將自身的信息廣播給其他每一個(gè)路由器。這樣，每一個(gè)路由器都能夠知道網(wǎng)絡(luò)的結(jié)構(gòu)以及狀態(tài)。

4、使用一個(gè)合適的算法，確定網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間的最佳路由。

在這一步中，路由器選擇通往每一個(gè)節(jié)點(diǎn)的最佳路由。它們使用一個(gè)算法來(lái)實(shí)現(xiàn)這一點(diǎn)，如Dijkstra最短路徑算法。在這個(gè)算法中，一個(gè)路由器通過(guò)收集到的其他路由器的信息，建立一個(gè)網(wǎng)絡(luò)圖。這個(gè)圖描述網(wǎng)絡(luò)中的路由器的位置以及它們之間的鏈接關(guān)系。每個(gè)鏈接都有一個(gè)數(shù)字標(biāo)注，稱為權(quán)值或成本。這個(gè)數(shù)字是延時(shí)和平均流量的函數(shù)，有時(shí)它僅僅表示節(jié)點(diǎn)間的躍點(diǎn)數(shù)。例如，如果一個(gè)節(jié)點(diǎn)與目的地之間有兩條鏈路，路由器將選擇權(quán)值最低的鏈路。

路由算法Dijkstra算法

Dijkstra算法執(zhí)行下列步驟：1、路由器建立一張網(wǎng)絡(luò)圖，并且確定源節(jié)點(diǎn)和目的節(jié)點(diǎn)，在這個(gè)例子里我們?cè)O(shè)為V1和V2。然后路由器建立一個(gè)矩陣，稱為“鄰接矩陣”。在這個(gè)矩陣中，各矩陣元素表示權(quán)值。例如，[i, j]是節(jié)點(diǎn)Vi與Vj之間的鏈路權(quán)值。如果節(jié)點(diǎn)Vi與Vj之間沒(méi)有鏈路直接相連，它們的權(quán)值設(shè)為“無(wú)窮大”。

2、路由器為網(wǎng)路中的每一個(gè)節(jié)點(diǎn)建立一組狀態(tài)記錄。此記錄包括三個(gè)字段：

前序字段——表示當(dāng)前節(jié)點(diǎn)之前的節(jié)點(diǎn)。

長(zhǎng)度字段——表示從源節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的權(quán)值之和。

標(biāo)號(hào)字段——表示節(jié)點(diǎn)的狀態(tài)。每個(gè)節(jié)點(diǎn)都處于一個(gè)狀態(tài)模式：“永久”或“暫時(shí)”。

3、路由器初始化（所有節(jié)點(diǎn)的）狀態(tài)記錄集參數(shù)，將它們的長(zhǎng)度設(shè)為“無(wú)窮大”，標(biāo)號(hào)設(shè)為“暫時(shí)”。

4、路由器設(shè)置一個(gè)T節(jié)點(diǎn)。例如，如果設(shè)V1是源T節(jié)點(diǎn)，路由器將V1的標(biāo)號(hào)更改為“永久”。當(dāng)一個(gè)標(biāo)號(hào)更改為“永久”后，它將不再改變。一個(gè)T節(jié)點(diǎn)僅僅是一個(gè)代理而已。

5、路由器更新與源T節(jié)點(diǎn)直接相連的所有暫時(shí)性節(jié)點(diǎn)的狀態(tài)記錄集。

6、路由器在所有的暫時(shí)性節(jié)點(diǎn)中選擇距離V1的權(quán)值最低的節(jié)點(diǎn)。這個(gè)節(jié)點(diǎn)將是新的T節(jié)點(diǎn)。

7、如果這個(gè)節(jié)點(diǎn)不是V2（目的節(jié)點(diǎn)），路由器則返回到步驟5。

8、如果節(jié)點(diǎn)是V2，路由器則向前回溯，將它的前序節(jié)點(diǎn)從狀態(tài)記錄集中提取出來(lái)，如此循環(huán)，直到提取到V1為止。這個(gè)節(jié)點(diǎn)列表便是從V1到V2的最佳路由。

路由算法鏈路向量選路算法

鏈路狀態(tài)算法（也稱最短路徑算法）發(fā)送路由信息到互聯(lián)網(wǎng)上所有的結(jié)點(diǎn)，然而對(duì)于每個(gè)路由器，僅發(fā)送它的路由表中描述了其自身鏈路狀態(tài)的那一部分。

路由算法距離向量算法

距離向量算法（也稱為Bellman-Ford算法）則要求每個(gè)路由器發(fā)送其路由表全部或部分信息，但僅發(fā)送到鄰近結(jié)點(diǎn)上。從本質(zhì)上來(lái)說(shuō)，鏈路狀態(tài)算法將少量更新信息發(fā)送至網(wǎng)絡(luò)各處，而距離向量算法發(fā)送大量更新信息至鄰接路由器。 ——由于鏈路狀態(tài)算法收斂更快，因此它在一定程度上比距離向量算法更不易產(chǎn)生路由循環(huán)。但另一方面，鏈路狀態(tài)算法要求比距離向量算法有更強(qiáng)的CPU能力和更多的內(nèi)存空間，因此鏈路狀態(tài)算法將會(huì)在實(shí)現(xiàn)時(shí)顯得更昂貴一些。

路由算法使用了許多種不同的度量標(biāo)準(zhǔn)去決定最佳路徑。復(fù)雜的路由算法可能采用多種度量來(lái)選擇路由，通過(guò)一定的加權(quán)運(yùn)算，將它們合并為單個(gè)的復(fù)合度量、再填入路由表中，作為尋徑的標(biāo)準(zhǔn)。

通常所使用的度量有：路徑長(zhǎng)度、可靠性、時(shí)延、帶寬、負(fù)載、通信成本等。

路由算法路徑長(zhǎng)度

路徑長(zhǎng)度是最常用的路由metric。一些路由協(xié)議允許網(wǎng)管給每個(gè)網(wǎng)絡(luò)鏈接人工賦以代價(jià)值，這種情況下，路由長(zhǎng)度是所經(jīng)過(guò)各個(gè)鏈接的代價(jià)總和。其它路由協(xié)議定義了跳數(shù)，即分組在從源到目的的路途中必須經(jīng)過(guò)的網(wǎng)絡(luò)產(chǎn)品，如路由器的個(gè)數(shù)。

路由算法可靠性

可靠性，在路由算法中指網(wǎng)絡(luò)鏈接的可依賴性（通常以位誤率描述），有些網(wǎng)絡(luò)鏈接可能比其它的失效更多，網(wǎng)路失效后，一些網(wǎng)絡(luò)鏈接可能比其它的更易或更快修復(fù)。任何可靠性因素都可以在給可靠率賦值時(shí)計(jì)算在內(nèi)，通常是由網(wǎng)管給網(wǎng)絡(luò)鏈接賦以metric值。

路由算法路由延遲

路由延遲指分組從源通過(guò)網(wǎng)絡(luò)到達(dá)目的所花時(shí)間。很多因素影響到延遲，包括中間的網(wǎng)絡(luò)鏈接的帶寬、經(jīng)過(guò)的每個(gè)路由器的端口隊(duì)列、所有中間網(wǎng)絡(luò)鏈接的擁塞程度以及物理距離。因?yàn)檠舆t是多個(gè)重要變量的混合體，它是個(gè)比較常用且有效的metric。

路由算法帶寬

帶寬指鏈接可用的流通容量。在其它所有條件都相等時(shí)，10Mbps的以太網(wǎng)鏈接比64kbps的專(zhuān)線更可取。雖然帶寬是鏈接可獲得的最大吞吐量，但是通過(guò)具有較大帶寬的鏈接做路由不一定比經(jīng)過(guò)較慢鏈接路由更好。例如，如果一條快速鏈路很忙，分組到達(dá)目的所花時(shí)間可能要更長(zhǎng)。

路由算法負(fù)載

負(fù)載指網(wǎng)絡(luò)資源，如路由器的繁忙程度。負(fù)載可以用很多方面計(jì)算，包括CPU使用情況和每秒處理分組數(shù)。持續(xù)地監(jiān)視這些參數(shù)本身也是很耗費(fèi)資源的。

路由算法通信代價(jià)

通信代價(jià)是另一種重要的metric，尤其是有一些公司可能關(guān)心運(yùn)作費(fèi)用甚于關(guān)心性能。即使線路延遲可能較長(zhǎng)，他們也寧愿通過(guò)自己的線路發(fā)送數(shù)據(jù)而不采用昂貴的公用線路。

各路由算法的區(qū)別點(diǎn)包括：靜態(tài)與動(dòng)態(tài)、單路徑與多路徑、平坦與分層、主機(jī)智能與路由器智能、域內(nèi)與域間、鏈接狀態(tài)與距離向量。

路由算法靜態(tài)與動(dòng)態(tài)

靜態(tài)路由算法很難算得上是算法，只不過(guò)是開(kāi)始路由前由網(wǎng)管建立的表映射。這些映射自身并不改變，除非網(wǎng)管去改動(dòng)。使用靜態(tài)路由的算法較容易設(shè)計(jì)，在網(wǎng)絡(luò)通信可預(yù)測(cè)及簡(jiǎn)單的網(wǎng)絡(luò)中工作得很好。由于靜態(tài)路由系統(tǒng)不能對(duì)網(wǎng)絡(luò)改變做出反映，通常被認(rèn)為不適用于的大型、易變的網(wǎng)絡(luò)。九十年代主要的路由算法都是動(dòng)態(tài)路由算法，通過(guò)分析收到的路由更新信息來(lái)適應(yīng)網(wǎng)絡(luò)環(huán)境的改變。如果信息表示網(wǎng)絡(luò)發(fā)生了變化，路由軟件就重新計(jì)算路由并發(fā)出新的路由更新信息。這些信息滲入網(wǎng)絡(luò)，促使路由器重新計(jì)算并對(duì)路由表做相應(yīng)的改變。動(dòng)態(tài)路由算法可以在適當(dāng)?shù)牡胤揭造o態(tài)路由作為補(bǔ)充。例如，最后可選路由（router of last resort），作為所有不可路由分組的去路，保證了所有的數(shù)據(jù)至少有方法處理。

路由算法單路徑與多路徑

一些復(fù)雜的路由協(xié)議支持到同一目的的多條路徑。與單路徑算法不同，這些多路徑算法允許數(shù)據(jù)在多條線路上復(fù)用。多路徑算法的優(yōu)點(diǎn)很明顯：它們可以提供更好的吞吐量和可靠性。

路由算法平坦與分層

一些路由協(xié)議在平坦的空間里運(yùn)作，其它的則有路由的層次。在平坦的路由系統(tǒng)中，每個(gè)路由器與其它所有路由器是對(duì)等的；在分層次的路由系統(tǒng)中，一些路由器構(gòu)成了路由主干，數(shù)據(jù)從非主干路由器流向主干路由器，然后在主干上傳輸直到它們到達(dá)目標(biāo)所在區(qū)域，在這里，它們從最后的主干路由器通過(guò)一個(gè)或多個(gè)非主干路由器到達(dá)終點(diǎn)。路由系統(tǒng)通常設(shè)計(jì)有邏輯節(jié)點(diǎn)組，稱為域、自治系統(tǒng)或區(qū)間。

在分層的系統(tǒng)中，一些路由器可以與其它域中的路由器通信，其它的則只能與域內(nèi)的路由器通信。在很大的網(wǎng)絡(luò)中，可能還存在其它級(jí)別，最高級(jí)的路由器構(gòu)成了路由主干。

分層路由的主要優(yōu)點(diǎn)是它模擬了多數(shù)公司的結(jié)構(gòu)，從而能很好地支持其通信。多數(shù)的網(wǎng)絡(luò)通信發(fā)生在小組中（域）。因?yàn)橛騼?nèi)路由器只需要知道本域內(nèi)的其它路由器，它們的路由算法可以簡(jiǎn)化，根據(jù)所使用的路由算法，路由更新的通信量可以相應(yīng)地減少。

路由算法主機(jī)與路由器

一些路由算法假定源結(jié)點(diǎn)來(lái)決定整個(gè)路徑，這通常稱為源路由。在源路由系統(tǒng)中，路由器只作為存貯轉(zhuǎn)發(fā)設(shè)備，無(wú)意識(shí)地把分組發(fā)向下一跳。其它路由算法假定主機(jī)對(duì)路徑一無(wú)所知，在這些算法中，路由器基于自己的計(jì)算決定通過(guò)網(wǎng)絡(luò)的路徑。前一種系統(tǒng)中，主機(jī)具有決定路由的智能，后者則為路由器具有此能力。

主機(jī)智能和路由器智能的折衷實(shí)際是最佳路由與額外開(kāi)銷(xiāo)的平衡。主機(jī)智能系統(tǒng)通常能選擇更佳的路徑，因?yàn)樗鼈冊(cè)诎l(fā)送數(shù)據(jù)前探索了所有可能的路徑，然后基于特定系統(tǒng)對(duì)“優(yōu)化”的定義來(lái)選擇最佳路徑。然而確定所有路徑的行為通常需要很多的探索通信量和很長(zhǎng)的時(shí)間。

路由算法域內(nèi)與域間

一些路由算法只在域內(nèi)工作，其它的則既在域內(nèi)也在域間工作。這兩種算法的本質(zhì)是不同的。其遵循的理由是優(yōu)化的域內(nèi)路由算法沒(méi)有必要也成為優(yōu)化的域間路由算法。

路由算法鏈接與距離

鏈接狀態(tài)算法（也叫做短路徑優(yōu)先算法）把路由信息散布到網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)，不過(guò)每個(gè)路由器只發(fā)送路由表中描述其自己鏈接狀態(tài)的部分。距離向量算法（也叫做Bellman-Ford算法）中每個(gè)路由器發(fā)送路由表的全部或部分，但只發(fā)給其鄰居。也就是說(shuō)，鏈接狀態(tài)算法到處發(fā)送較少的更新信息，而距離向量算法只向相鄰的路由器發(fā)送較多的更新信息。

由于鏈接狀態(tài)算法聚合得較快，它們相對(duì)于距離算法產(chǎn)生路由環(huán)的傾向較小。在另一方面，鏈接狀態(tài)算法需要更多的CPU和內(nèi)存資源，因此鏈接狀態(tài)算法的實(shí)現(xiàn)和支持較昂貴。雖然有差異，這兩種算法類(lèi)型在多數(shù)環(huán)境中都可以工作得很好。

路由算法還應(yīng)該是靈活的，即它們應(yīng)該迅速、準(zhǔn)確地適應(yīng)各種網(wǎng)絡(luò)環(huán)境。路由算法可以設(shè)計(jì)得可適應(yīng)網(wǎng)絡(luò)帶寬、路由器隊(duì)列大小和網(wǎng)絡(luò)延遲。

路由算法的核心是路由選擇算法，設(shè)計(jì)路由算法時(shí)要考慮的技術(shù)要素有：

1、選擇最短路由還是最佳路由；

2、通信子網(wǎng)是采用虛電路操作方式還是采用數(shù)據(jù)報(bào)的操作方式；

3、采用分布式路由算法還是采用集中式路由算法；

4、考慮關(guān)于網(wǎng)絡(luò)拓?fù)?、流量和延遲等網(wǎng)絡(luò)信息的來(lái)源；

5、確定采用靜態(tài)路由還是動(dòng)態(tài)路由。

優(yōu)化指路由算法選擇最佳路徑的能力，根據(jù)metric的值和權(quán)值來(lái)計(jì)算。例如有一種路由算法可能使用跳數(shù)和延遲，但可能延遲的權(quán)值要大些。當(dāng)然，路由協(xié)議必須嚴(yán)格定義計(jì)算metric的算法。

路由算法通常具有下列設(shè)計(jì)目標(biāo)的一個(gè)或多個(gè)：優(yōu)化、簡(jiǎn)單、低耗、健壯、穩(wěn)定、快速聚合、靈活性。

（1）最優(yōu)化：指路由算法選擇最佳路徑的能力。根據(jù)metric的值和權(quán)值來(lái)計(jì)算。

（2）簡(jiǎn)潔性：算法設(shè)計(jì)必須簡(jiǎn)潔。路由協(xié)議在網(wǎng)絡(luò)中必須高效地提供其功能，盡量減少軟件和應(yīng)用的開(kāi)銷(xiāo)。這在當(dāng)實(shí)現(xiàn)路由算法的軟件必須運(yùn)行在物理資源有限的計(jì)算機(jī)上時(shí)尤其重要。

（3）堅(jiān)固性：路由算法處于非正?；虿豢深A(yù)料的環(huán)境時(shí)，如硬件故障、負(fù)載過(guò)高或操作失誤時(shí)，都能正確運(yùn)行。由于路由器分布在網(wǎng)絡(luò)聯(lián)接點(diǎn)上，所以在它們出故障時(shí)會(huì)產(chǎn)生嚴(yán)重后果。最好的路由器算法通常能經(jīng)受時(shí)間的考驗(yàn)，并在各種網(wǎng)絡(luò)環(huán)境下被證實(shí)是可靠的。

（4）快速收斂：收斂是在最佳路徑的判斷上所有路由器達(dá)到一致的過(guò)程。當(dāng)某個(gè)網(wǎng)絡(luò)事件引起路由可用或不可用時(shí)，路由器就發(fā)出更新信息。路由更新信息遍及整個(gè)網(wǎng)絡(luò)，引發(fā)重新計(jì)算最佳路徑，最終達(dá)到所有路由器一致公認(rèn)的最佳路徑。收斂慢的路由算法會(huì)造成路徑循環(huán)或網(wǎng)絡(luò)中斷。

（5）靈活性：路由算法要求可以快速、準(zhǔn)確地適應(yīng)各種網(wǎng)絡(luò)環(huán)境。例如，某個(gè)網(wǎng)段發(fā)生故障，路由算法要能很快發(fā)現(xiàn)故障，并為使用該網(wǎng)段的所有路由選擇另一條最佳路徑。

路由器使用路由算法來(lái)找到到達(dá)目的地的最佳路由。當(dāng)說(shuō)“最佳路由”時(shí)，考慮的參數(shù)包括諸如跳躍數(shù)（分組數(shù)據(jù)包在網(wǎng)絡(luò)中從一個(gè)路由器或中間節(jié)點(diǎn)到另外的節(jié)點(diǎn)的行程）、延時(shí)以及分組數(shù)據(jù)包傳輸通信耗時(shí)。關(guān)于路由器如何收集網(wǎng)絡(luò)的結(jié)構(gòu)信息以及對(duì)之進(jìn)行分析來(lái)確定最佳路由，有兩種主要的路由算法：

總體式路由算法和分散式路由算法。采用分散式路由算法時(shí)，每個(gè)路由器只有與它直接相連的路由器的信息——而沒(méi)有網(wǎng)絡(luò)中的每個(gè)路由器的信息。這些算法也被稱為DV（距離向量）算法。采用總體式路由算法時(shí)，每個(gè)路由器都擁有網(wǎng)絡(luò)中所有其他路由器的全部信息以及網(wǎng)絡(luò)的流量狀態(tài)。這些算法也被稱為L(zhǎng)S（鏈路狀態(tài)）算法。

路由算法是提高路由協(xié)議功能，盡量減少路由時(shí)所帶來(lái)開(kāi)銷(xiāo)的算法。當(dāng)實(shí)現(xiàn)路由算法的軟件必須運(yùn)行在物理資源有限的計(jì)算機(jī)上時(shí)高效尤其重要。路由算法必須健壯，即在出現(xiàn)不正?；虿豢深A(yù)見(jiàn)事件的情況下必須仍能正常處理，例如硬件故障、高負(fù)載和不正確的實(shí)現(xiàn)。因?yàn)槁酚善魑挥诰W(wǎng)絡(luò)的連接點(diǎn)，當(dāng)它們失效時(shí)會(huì)產(chǎn)生重大的問(wèn)題。最好的路由算法通常是那些經(jīng)過(guò)了時(shí)間考驗(yàn)，證實(shí)在各種網(wǎng)絡(luò)條件下都很穩(wěn)定的算法。

此外路由算法必須能快速聚合，聚合是所有路由器對(duì)最佳路徑達(dá)成一致的過(guò)程。當(dāng)某網(wǎng)絡(luò)事件使路徑斷掉或不可用時(shí)，路由器通過(guò)網(wǎng)絡(luò)分發(fā)路由更新信息，促使最佳路徑的重新計(jì)算，最終使所有路由器達(dá)成一致。聚合很慢的路由算法可能會(huì)產(chǎn)生路由環(huán)或網(wǎng)路中斷。

可以看到，在LS和DV算法中，每個(gè)路由器都需要保存其他路由器的一些信息。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，網(wǎng)絡(luò)中的路由器也將增加。因此，路由表的規(guī)模也將增大，從而使路由器不能有效地處理網(wǎng)絡(luò)流量。使用分級(jí)路由可以解決這個(gè)問(wèn)題。讓使用DV算法來(lái)查找節(jié)點(diǎn)間的最佳路由。

在下述情形中，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)保存了一個(gè)有17個(gè)記錄的路由表。在分級(jí)路由中，路由器被分成很多組，稱為區(qū)域。每個(gè)路由器都只有自己所在區(qū)域路由器的信息，而沒(méi)有其他區(qū)域路由器的信息。所以在其路由表中，路由器只需要存儲(chǔ)其他每個(gè)區(qū)域的一條記錄。在這個(gè)例子中，我們將網(wǎng)絡(luò)分為5個(gè)區(qū)域。

如果A想發(fā)送分組數(shù)據(jù)包到在區(qū)域2中的一個(gè)路由器（D、E、F或G），它就將分組數(shù)據(jù)包先發(fā)送到B，依此類(lèi)推?？梢钥吹剑谶@種類(lèi)型的路由中，可以對(duì)路由表進(jìn)行概括，因此網(wǎng)絡(luò)效率提高了。上面的例子描述了一個(gè)兩級(jí)的分級(jí)路由。同樣我們也可以采用三級(jí)或者四級(jí)的分級(jí)路由。

在一個(gè)三級(jí)的分級(jí)路由中，網(wǎng)絡(luò)被分為很多簇。每個(gè)簇由很多個(gè)區(qū)域組成，每個(gè)區(qū)域包含很多個(gè)路由器。分級(jí)路由廣泛應(yīng)用于互聯(lián)網(wǎng)路由中，并且使用了多種路由協(xié)議。

路由算法，又名選路算法，可以根據(jù)多個(gè)特性來(lái)加以區(qū)分。算法的目的是找到一條從源路由器到目的路由器的“好”路徑（即具有最低費(fèi)用的路徑） 。算法設(shè)計(jì)者的特定目標(biāo)影響了該路由協(xié)議的操作；具體來(lái)說(shuō)存在著多種路由算法，每種算法對(duì)網(wǎng)絡(luò)和路由器資源的影響都不同；由于路由算法使用多種度量標(biāo)準(zhǔn)（metric），從而影響到最佳路徑的計(jì)算。路由算法通常具有下列設(shè)計(jì)目標(biāo)的一個(gè)或多個(gè)：優(yōu)化、簡(jiǎn)單、低耗、健壯、穩(wěn)定、快速聚合、靈活性。（1）最優(yōu)化：指路由算法選擇最佳路徑的能力。根據(jù)metric的值和權(quán)值來(lái)計(jì)算。（2）簡(jiǎn)潔性：算法設(shè)計(jì)必須簡(jiǎn)潔。路由協(xié)議在網(wǎng)絡(luò)中必須高效地提供其功能，盡量減少軟件和應(yīng)用的開(kāi)銷(xiāo)。這在當(dāng)實(shí)現(xiàn)路由算法的軟件必須運(yùn)行在物理資源有限的計(jì)算機(jī)上時(shí)尤其重要。（3）堅(jiān)固性：路由算法處于非正常或不可預(yù)料的環(huán)境時(shí)，如硬件故障、負(fù)載過(guò)高或操作失誤時(shí)，都能正確運(yùn)行。由于路由器分布在網(wǎng)絡(luò)聯(lián)接點(diǎn)上，所以在它們出故障時(shí)會(huì)產(chǎn)生嚴(yán)重后果。最好的路由器算法通常能經(jīng)受時(shí)間的考驗(yàn)，并在各種網(wǎng)絡(luò)環(huán)境下被證實(shí)是可靠的。（4）快速收斂：收斂是在最佳路徑的判斷上所有路由器達(dá)到一致的過(guò)程。當(dāng)某個(gè)網(wǎng)絡(luò)事件引起路由可用或不可用時(shí)，路由器就發(fā)出更新信息。路由更新信息遍及整個(gè)網(wǎng)絡(luò)，引發(fā)重新計(jì)算最佳路徑，最終達(dá)到所有路由器一致公認(rèn)的最佳路徑。收斂慢的路由算法會(huì)造成路徑循環(huán)或網(wǎng)絡(luò)中斷。（5）靈活性：路由算法要求可以快速、準(zhǔn)確地適應(yīng)各種網(wǎng)絡(luò)環(huán)境。例如，某個(gè)網(wǎng)段發(fā)生故障，路由算法要能很快發(fā)現(xiàn)故障，并為使用該網(wǎng)段的所有路由選擇另一條最佳路徑。2100433B

各種路由算法不盡相同，主要是由于：首先，算法設(shè)計(jì)者的設(shè)計(jì)目標(biāo)會(huì)影響路由選擇協(xié)議的運(yùn)行結(jié)果；其次，現(xiàn)有的各種路由選擇算法對(duì)網(wǎng)絡(luò)和路由器資源的影響不同；最后，不同的計(jì)量標(biāo)準(zhǔn)也會(huì)影響最佳路徑的計(jì)算結(jié)果。

路由協(xié)議按路由算法一般劃分為距離向量協(xié)議和鏈路狀態(tài)協(xié)議兩類(lèi)。距離向量協(xié)議，也稱為Bellman-Ford算法，是指使用中繼計(jì)數(shù)表示源節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離，它基于下面的計(jì)算公式來(lái)計(jì)算兩個(gè)節(jié)點(diǎn)間距離：

D(i，i)=0

D(i，j)=min[d(i，k) D(k，j)]

其中，D(i，j)表示從節(jié)點(diǎn)(節(jié)點(diǎn)為網(wǎng)絡(luò)或路由器)i到節(jié)點(diǎn)j的最短路徑，d(i，k)表示從節(jié)點(diǎn)i到k的直接路徑，也就是說(shuō)，節(jié)點(diǎn)i和k之間沒(méi)有中介節(jié)點(diǎn)。具體運(yùn)算步驟如下：

①所有的路由器都建有一個(gè)路由表，使系統(tǒng)中的所有目的地址都出現(xiàn)在表中，每一個(gè)表項(xiàng)內(nèi)容均包括目的地址和下一站地址，記為元組(N，G)。

②路由器周期性地向鄰居發(fā)送更新分組，更新分組的內(nèi)容為路由表中的所有信息。

③鄰居路由器接收處理更新分組。設(shè)更新分組來(lái)自G'，根據(jù)更新分組計(jì)算到目的地址N的路由開(kāi)銷(xiāo)為D'，如果D'

鏈路狀態(tài)協(xié)議，也稱最短路徑算法，其計(jì)算原理可以分為以下4個(gè)過(guò)程來(lái)描述：

①發(fā)現(xiàn)該路由器的鄰居，獲取它們的網(wǎng)絡(luò)地址，建立相鄰關(guān)系，并測(cè)量到每個(gè)相鄰路由器的開(kāi)銷(xiāo)或延遲。建立相鄰關(guān)系是通過(guò)發(fā)送Hello分組來(lái)實(shí)現(xiàn)的。

②將用于交換的信息收集起來(lái)，構(gòu)造包含這些信息的鏈路狀態(tài)消息。創(chuàng)建鏈路狀態(tài)消息的時(shí)機(jī)分兩種，一種為定期創(chuàng)建，另一種就是當(dāng)有事件發(fā)生時(shí)創(chuàng)建。

③通過(guò)flood(擴(kuò)散)算法，向所有的其他路由器發(fā)送該消息。在鏈路狀態(tài)路由選擇算法中，如何可靠地發(fā)布鏈路狀態(tài)消息包是相當(dāng)重要的。鏈路狀態(tài)算法實(shí)現(xiàn)的好壞在一定程度上取決于flood算法的優(yōu)劣。

④根據(jù)收集到的鏈路狀態(tài)信息，通過(guò)Dijkstra算法計(jì)算本路由器到全網(wǎng)其他路由器或網(wǎng)絡(luò)的最短距離。

鏈路狀態(tài)協(xié)議與距離向量協(xié)議相比，其優(yōu)點(diǎn)是基于量度值(如鏈路帶寬和時(shí)延)，而不是由中繼計(jì)數(shù)來(lái)選擇優(yōu)化路由，因此可使網(wǎng)絡(luò)負(fù)載平衡；通過(guò)鏈路狀態(tài)更新，將鏈路和節(jié)點(diǎn)狀態(tài)的變化情況擴(kuò)散到整個(gè)網(wǎng)絡(luò)，使所有路由器馬上更新路由表，使網(wǎng)絡(luò)具有更好的收斂特性。