1、對(duì)路由算法的討論電氣學(xué)院 自動(dòng)化1313 金莉萍 5摘要：路由算法是提高路由協(xié)議功能，盡量減少路由時(shí)所帶來(lái)開(kāi)銷(xiāo)的算法。路由算法在路由協(xié)議中起著至關(guān)重要的作用，采用何種算法往往決定了最終尋徑結(jié)果。本文就對(duì)各路由算法在不同模型下，綜合對(duì)比它們路徑選擇的差異以展開(kāi)研究討論。關(guān)鍵詞：路由算法 差異 不同模式 研究討論隨著科學(xué)技術(shù)的飛速發(fā)展，不僅傳統(tǒng)業(yè)務(wù)流量大大增加，而且出現(xiàn)了許多新業(yè)務(wù)，如語(yǔ)音、數(shù)據(jù)和多媒體應(yīng)用等對(duì)網(wǎng)絡(luò)傳輸質(zhì)量的要求差別很大，關(guān)于IP網(wǎng)絡(luò)相關(guān)問(wèn)題變得日益尖銳，特別是寬帶業(yè)務(wù)，對(duì)網(wǎng)絡(luò)性能加轉(zhuǎn)發(fā)速度、流量控制以及網(wǎng)絡(luò)的可擴(kuò)展性等提出了較高的要求、隨著主干網(wǎng)鏈路傳輸速度的不斷提高，IP網(wǎng)絡(luò)中

2、節(jié)點(diǎn)上的包轉(zhuǎn)發(fā)成了網(wǎng)絡(luò)的瓶頸，在不斷地需求下，人們提出了新的高效的路由算法，這種算法是通過(guò)提高網(wǎng)絡(luò)的調(diào)節(jié)和控制功能使流量分布更加合理，以達(dá)到盡可能減少網(wǎng)絡(luò)阻塞、最小的網(wǎng)絡(luò)代價(jià)、分布的網(wǎng)絡(luò)負(fù)載等目標(biāo)。路由算法，又名選路算法，可以根據(jù)多個(gè)特性來(lái)加以區(qū)分。實(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)定的算法。就我看來(lái)，一個(gè)理想的路由算法應(yīng)該在計(jì)算上應(yīng)

3、簡(jiǎn)單。路由選擇的計(jì)算不應(yīng)使網(wǎng)絡(luò)通信量增加太多的額外開(kāi)銷(xiāo)。算法應(yīng)具有穩(wěn)定性。在網(wǎng)絡(luò)通信量和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相對(duì)穩(wěn)定的情況下，路由算法應(yīng)收斂于一個(gè)可以接受的解，而不應(yīng)使得出的路由不停的變化。算法必須是正確的和完整的。這里，“正確”的含義是指沿著各路由表所指引的路由，分組一定能夠最終到達(dá)目的網(wǎng)絡(luò)和目的主機(jī)。算法應(yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓?，這就是說(shuō)要有自適應(yīng)性。當(dāng)網(wǎng)絡(luò)中的通信量發(fā)生變化時(shí)，算法能自適應(yīng)的改變路由以均衡個(gè)鏈路的負(fù)載。等某個(gè)或某些節(jié)點(diǎn)、鏈路發(fā)生故障不能工作，或者修理好了再投入運(yùn)行時(shí)，算法也能及時(shí)的改變路由。有時(shí)稱這種自適應(yīng)性為“穩(wěn)健性”。算法應(yīng)是最佳的。路由選擇算法應(yīng)當(dāng)能夠找出最好的路由，

4、使得分組平均延時(shí)最小而網(wǎng)絡(luò)的吞吐量最大。我們希望得到“最佳”的算法，但這并不是最重要的。對(duì)于某些網(wǎng)絡(luò)，網(wǎng)絡(luò)的可靠性有時(shí)要比最小的分組平均延時(shí)或最大吞吐量更加重要。因此，所謂“最佳”只能是相對(duì)于某一種特定要求下得出的較為合理的選擇而已。一個(gè)實(shí)際的路由選擇算法，應(yīng)盡可能接近于理想算法。在不同的應(yīng)用條件下對(duì)以上提出的六個(gè)方面也可有不同的側(cè)重。所以，路由是個(gè)非常復(fù)雜的問(wèn)題，因?yàn)樗蔷W(wǎng)絡(luò)中的所有結(jié)點(diǎn)共同協(xié)調(diào)工作的結(jié)果。路由算法應(yīng)是公平的。路由選擇算法應(yīng)對(duì)所有用戶（除了少數(shù)優(yōu)先級(jí)高的用戶）都是平等的。例如，若僅僅使某一對(duì)用戶的端到端時(shí)延為最小，但卻不考慮其他的廣大用戶，這就明顯的不符合公平性的要求。 路由

5、算法的核心是路由選擇算法，常見(jiàn)的路由選擇算法有最短路徑法、擴(kuò)散法、基于流量的路由選擇、距離向量路由選擇 、鏈路狀態(tài)路由選擇、分級(jí)路由選擇、移動(dòng)主機(jī)的路由選擇、組播路由選擇、廣播路由選擇。這種算法是個(gè)非常復(fù)雜的問(wèn)題，因?yàn)樗蔷W(wǎng)絡(luò)中的所有節(jié)點(diǎn)共同協(xié)調(diào)工作的結(jié)果。其次，路由選擇的環(huán)境往往是不斷變化的，而這種變化有時(shí)無(wú)法事先知道，例如，網(wǎng)絡(luò)中出現(xiàn)了某些故障。此外，當(dāng)網(wǎng)絡(luò)發(fā)生擁塞時(shí)，就特別需要有能緩解這種擁塞的路由選擇策略，但恰好在這種條件下，很難從網(wǎng)絡(luò)中的各結(jié)點(diǎn)獲得所需的路由選擇信息。然而，倘若從路由算法能否隨網(wǎng)絡(luò)的通信量或拓?fù)渥赃m應(yīng)的進(jìn)行調(diào)整變化來(lái)劃分，則只有兩大類(lèi)，即靜態(tài)路由選擇策略與動(dòng)態(tài)路由選擇

6、策略。靜態(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)路由也叫做非自適應(yīng)路由選擇，其特點(diǎn)是簡(jiǎn)單和開(kāi)銷(xiāo)較小，但不能及時(shí)適應(yīng)網(wǎng)絡(luò)狀態(tài)的變化。對(duì)于很簡(jiǎn)單的小網(wǎng)絡(luò)，完全可以采用靜態(tài)路由選擇，用人工配置每一條路由。由于靜態(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ò)，促使

7、路由器重新計(jì)算并對(duì)路由表做相應(yīng)的改變。動(dòng)態(tài)路由選擇也叫做自適應(yīng)路由選擇，其特點(diǎn)是能較好的適應(yīng)網(wǎng)絡(luò)狀態(tài)的變化，但實(shí)現(xiàn)起來(lái)較為復(fù)雜，開(kāi)銷(xiāo)也比較大。因此，動(dòng)態(tài)路由選擇適用于較復(fù)雜的大網(wǎng)絡(luò)。 動(dòng)態(tài)路由算法可以在適當(dāng)?shù)牡胤揭造o態(tài)路由作為補(bǔ)充。例如，最后可選路由，作為所有不可路由分組的去路，保證了所有的數(shù)據(jù)至少有方法處理。關(guān)于路由器如何收集網(wǎng)絡(luò)的結(jié)構(gòu)信息以及對(duì)之進(jìn)行分析來(lái)確定最佳路由，有兩種主要的路由算法：總體式路由算法和分散式路由算法。采用分散式路由算法時(shí)，每個(gè)路由器只有與它直接相連的路由器的信息，而沒(méi)有網(wǎng)絡(luò)中的每個(gè)路由器的信息，這些算法被稱為DV算法。DV算法也稱為Bellman-Ford算法，是要求

8、每個(gè)路由器發(fā)送其路由表全部或部分信息，但僅發(fā)送到鄰近結(jié)點(diǎn)上。而采用總體式路由算法時(shí)，每個(gè)路由器都擁有網(wǎng)絡(luò)中所有其他路由器的全部信息以及網(wǎng)絡(luò)的流量狀態(tài)，這些算法被稱為L(zhǎng)S算法。LS算法也稱為最短路徑算法，其發(fā)送路由信息到互聯(lián)網(wǎng)上所有的結(jié)點(diǎn)，然而對(duì)于每個(gè)路由器，僅發(fā)送它的路由表中描述了其自身鏈路狀態(tài)的那一部分，因此，從本質(zhì)上來(lái)說(shuō)IS算法到處發(fā)送較少的更新信息，而DV算法只向相鄰的路由器發(fā)送較多的更新信息。由于LS算法收斂更快，因此它在一定程度上比DV算法更不易產(chǎn)生路由循環(huán)。但另一方面，LS算法要求比距離向量算法有更強(qiáng)的CPU能力和更多的內(nèi)存空間，因此LS算法將會(huì)在實(shí)現(xiàn)時(shí)顯得更昂貴一些。另外，路由算

9、法使用了許多種不同的度量標(biāo)準(zhǔn)去決定最佳路徑。復(fù)雜的路由算法可能采用多種度量來(lái)選擇路由，通過(guò)一定的加權(quán)運(yùn)算，將它們合并為單個(gè)的復(fù)合度量、再填入路由表中，作為尋徑的標(biāo)準(zhǔn)。通常所使用的度量有：路徑長(zhǎng)度、可靠性、時(shí)延、帶寬、負(fù)載、通信成本等。路徑長(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(wǎng)絡(luò)鏈接的可依賴性，有些網(wǎng)絡(luò)鏈接可能比其它的失效更多，網(wǎng)路失效后，一些網(wǎng)絡(luò)鏈接可能比其它的更易或更快修復(fù)。任何可靠性因素都可

10、以在給可靠率賦值時(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的專線更可取。雖然帶寬是鏈接可獲得的最大吞吐量，但是通過(guò)具有較大帶寬的鏈接做路由不一定比經(jīng)過(guò)較慢鏈接路由更好。例如，如果一條快速鏈路很忙，分組到達(dá)目的所花時(shí)間可能要更長(zhǎng)。負(fù)載指網(wǎng)絡(luò)資源，如路由器的繁忙程度。負(fù)載可以用很多方面計(jì)算，包括CPU使用情況和每秒處理分組數(shù)。持續(xù)地監(jiān)視這些參數(shù)本身也是很耗費(fèi)資源的。最后通信代價(jià)是另一種重要的metric，尤其是有一些公司可能關(guān)心運(yùn)作費(fèi)用甚于關(guān)心性能。即使線路延遲可能較長(zhǎng)，他們也寧愿通過(guò)自己的線路發(fā)送數(shù)據(jù)而不采用昂貴的公用線路。隨著網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，路由算法的使用率越來(lái)越高，可擴(kuò)展性越來(lái)越大，也越發(fā)受人關(guān)注，是人們今后網(wǎng)