路由是把信息從源穿過(guò)網(wǎng)絡(luò)傳遞到目的的行為，在路上，至少遇到一個(gè)中間節(jié)點(diǎn)。路由通常與橋接來(lái)對(duì)比，在粗心的人看來(lái)，它們似乎完成的是同樣的事。它們的主要區(qū)別在于橋接發(fā)生在OSI參考協(xié)議的第二層（鏈接層），而路由發(fā)生在第三層（網(wǎng)絡(luò)層）。這一區(qū)別使二者在傳遞信息的過(guò)程中使用不同的信息，從而以不同的方式來(lái)完 成其任務(wù)。
路由的話題早已在計(jì)算機(jī)界出現(xiàn)，但直到八十年代中期才獲得商業(yè)成功，這一時(shí)間延遲的主要原因是七十年代的網(wǎng)絡(luò)很簡(jiǎn)單，后來(lái)大型的網(wǎng)絡(luò)才較為普遍。
二、路由的組成
??路由包含兩個(gè)基本的動(dòng)作：確定最佳路徑和通過(guò)網(wǎng)絡(luò)傳輸信息。在路由的過(guò)程中，后者也稱(chēng)為（數(shù)據(jù)）交換。交換相對(duì)來(lái)說(shuō)比較簡(jiǎn)單，而選擇路徑很復(fù)雜。
1、路徑選擇
metric是路由算法用以確定到達(dá)目的地的最佳路徑的計(jì)量標(biāo)準(zhǔn)，如路徑長(zhǎng)度。為了幫助選路，路由算法初始化并維護(hù)包含路徑信息的路由表，路徑信息根據(jù)使用的路由算法不同而不同。
??路由算法根據(jù)許多信息來(lái)填充路由表。目的/下一跳地址對(duì)告知路由器到達(dá)該目的最佳方式是把分組發(fā)送給代表“下一跳”的路由器，當(dāng)路由器收到一個(gè)分組，它就檢查其目標(biāo)地址，嘗試將此地址與其“下一跳”相聯(lián)系。
??路由表還可以包括其它信息。路由表比較metric以確定最佳路徑，這些metric根據(jù)所用的路由算法而不同，下面將介紹常見(jiàn)的metric。路由器彼此通信，通過(guò)交換路由信息維護(hù)其路由表，路由更新信息通常包含全部或部分路由表，通過(guò)分析來(lái)自其它路由器的路由更新信息，該路由器可以建立網(wǎng)絡(luò)拓?fù)浼?xì)圖。路由器間發(fā)送的另一個(gè)信息例子是鏈接狀態(tài)廣播信息，它通知其它路由器發(fā)送者的鏈接狀態(tài)，鏈接信息用于建立完整的拓?fù)鋱D，使路由器可以確定最佳路徑。
2、交換
??交換算法相對(duì)而言較簡(jiǎn)單，對(duì)大多數(shù)路由協(xié)議而言是相同的，多數(shù)情況下，某主機(jī)決定向另一個(gè)主機(jī)發(fā)送數(shù)據(jù)，通過(guò)某些方法獲得路由器的地址后，源主機(jī)發(fā)送指向該路由器的物理（MAC）地址的數(shù)據(jù)包，其協(xié)議地址是指向目的主機(jī)的。
??路由器查看了數(shù)據(jù)包的目的協(xié)議地址后，確定是否知道如何轉(zhuǎn)發(fā)該包，如果路由器不知道如何轉(zhuǎn)發(fā)，通常就將之丟棄。如果路由器知道如何轉(zhuǎn)發(fā)，就把目的物理地址變成下一跳的物理地址并向之發(fā)送。下一跳可能就是最終的目的主機(jī)，如果不是，通常為另一個(gè)路由器，它將執(zhí)行同樣的步驟。當(dāng)分組在網(wǎng)絡(luò)中流動(dòng)時(shí)，它的物理地址在改變，但其協(xié)議地址始終不變。
??上面描述了源系統(tǒng)與目的系統(tǒng)間的交換，ISO定義了用于描述此過(guò)程的分層的術(shù)語(yǔ)。在該術(shù)語(yǔ)中，沒(méi)有轉(zhuǎn)發(fā)分組能力的網(wǎng)絡(luò)設(shè)備稱(chēng)為端系統(tǒng)（ES--end system），有此能力的稱(chēng)為中介系統(tǒng)（IS--intermediate system）。IS又進(jìn)一步分成可在路由域內(nèi)通信的域內(nèi)IS（intradomain IS）和既可在路由域內(nèi)有可在域間通信的域間IS（interdomain IS）。路由域通常被認(rèn)為是統(tǒng)一管理下的一部分網(wǎng)絡(luò)，遵守特定的一組管理規(guī)則，也稱(chēng)為自治系統(tǒng)utonomous system）。在某些協(xié)議中，路由域可以分為路由區(qū)間，但是域內(nèi)路由協(xié)議仍可用于在區(qū)間內(nèi)和區(qū)間之間交換數(shù)據(jù)。
三、路由算法
??路由算法可以根據(jù)多個(gè)特性來(lái)加以區(qū)分。首先，算法設(shè)計(jì)者的特定目標(biāo)影響了該路由協(xié)議的操作；其次，存在著多種路由算法，每種算法對(duì)網(wǎng)絡(luò)和路由器資源的影響都不同；最后，路由算法使用多種metric，影響到最佳路徑的計(jì)算。下面的章節(jié)分析了這些路由算法的特性。
1、設(shè)計(jì)目標(biāo)
??路由算法通常具有下列設(shè)計(jì)目標(biāo)的一個(gè)或多個(gè)：
優(yōu)化
簡(jiǎn)單、低耗
健壯、穩(wěn)定
快速聚合
靈活性
??優(yōu)化指路由算法選擇最佳路徑的能力，根據(jù)metric的值和權(quán)值來(lái)計(jì)算。例如有一種路由算法可能使用跳數(shù)和延遲，但可能延遲的權(quán)值要大些。當(dāng)然，路由協(xié)議必須嚴(yán)格定義計(jì)算metric的算法。
??路由算法也可以設(shè)計(jì)得盡量簡(jiǎn)單。換句話說(shuō)，路由協(xié)議必須高效地提供其功能，盡量減少軟件和應(yīng)用的開(kāi)銷(xiāo)。當(dāng)實(shí)現(xiàn)路由算法的軟件必須運(yùn)行在物理資源有限的計(jì)算機(jī)上時(shí)高效尤其重要。
??路由算法必須健壯，即在出現(xiàn)不正常或不可預(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)路中斷。
??路由算法還應(yīng)該是靈活的，即它們應(yīng)該迅速、準(zhǔn)確地適應(yīng)各種網(wǎng)絡(luò)環(huán)境。例如，假定某網(wǎng)段斷掉了，當(dāng)知道問(wèn)題后，很多路由算法對(duì)通常使用該網(wǎng)段的路徑將迅速選擇次佳的路徑。路由算法可以設(shè)計(jì)得可適應(yīng)網(wǎng)絡(luò)帶寬、路由器隊(duì)列大小和網(wǎng)絡(luò)延遲。
2、算法類(lèi)型
??各路由算法的區(qū)別點(diǎn)包括：
靜態(tài)與動(dòng)態(tài)
單路徑與多路徑
平坦與分層
主機(jī)智能與路由器智能
域內(nèi)與域間
鏈接狀態(tài)與距離向量
(1)靜態(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)為不適用于現(xià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ù)至少有方法處理。
(2)單路徑與多路徑
??一些復(fù)雜的路由協(xié)議支持到同一目的的多條路徑。與單路徑算法不同，這些多路徑算法允許數(shù)據(jù)在多條線路上復(fù)用。多路徑算法的優(yōu)點(diǎn)很明顯：它們可以提供更好的吞吐量和可靠性。
(3)平坦與分層
??一些路由協(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)組，稱(chēng)為域、自治系統(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)地減少。
(4)主機(jī)智能與路由器智能
??一些路由算法假定源結(jié)點(diǎn)來(lái)決定整個(gè)路徑，這通常稱(chēng)為源路由。在源路由系統(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í)間。
(5)域內(nèi)與域間
??一些路由算法只在域內(nèi)工作，其它的則既在域內(nèi)也在域間工作。這兩種算法的本質(zhì)是不同的。其遵循的理由是優(yōu)化的域內(nèi)路由算法沒(méi)有必要也成為優(yōu)化的域間路由算法。
(6)鏈接狀態(tài)與距離向量
??鏈接狀態(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)境中都可以工作得很好。
3、路由的metric
??路由表中含有由交換軟件用以選擇最佳路徑的信息。但是路由表是怎樣建立的呢？它們包含信息的本質(zhì)是什么？路由算法怎樣根據(jù)這些信息決定哪條路徑更好呢？
??路由算法使用了許多不同的metric以確定最佳路徑。復(fù)雜的路由算法可以基于多個(gè)metric選擇路由，并把它們結(jié)合成一個(gè)復(fù)合的metric。常用的metric如下：
路徑長(zhǎng)度
可靠性
延遲
帶寬
負(fù)載
通信代價(jià)
??路徑長(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ò)鏈接的可依賴(lài)性（通常以位誤率描述），有些網(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ù)載指網(wǎng)絡(luò)資源，如路由器的繁忙程度。負(fù)載可以用很多方面計(jì)算，包括CPU使用情況和每秒處理分組數(shù)。持續(xù)地監(jiān)視這些參數(shù)本身也是很耗費(fèi)資源的。
??通信代價(jià)是另一種重要的metric，尤其是有一些公司可能關(guān)系運(yùn)作費(fèi)用甚于性能。即使線路延遲可能較長(zhǎng)，他們也寧愿通過(guò)自己的線路發(fā)送數(shù)據(jù)而不采用昂貴的公用線路。
四、網(wǎng)絡(luò)協(xié)議
??可被路由的協(xié)議（Routed Protocol）由路由協(xié)議(Routing Protocol）傳輸，前者亦稱(chēng)為網(wǎng)絡(luò)協(xié)議。
這些網(wǎng)絡(luò)協(xié)議執(zhí)行在源與目的設(shè)備的用戶(hù)應(yīng)用間通信所需的各種功能，不同的協(xié)議中這些功能可能差異很大。網(wǎng)絡(luò)協(xié)議發(fā)生在OSI參考模型的上四層：傳輸層、會(huì)話層、表示層和應(yīng)用層。
??術(shù)語(yǔ)routed protocol（可被路由的協(xié)議）和routing protocol（路由協(xié)議）經(jīng)常被混淆。routed protocol在網(wǎng)絡(luò)中被路由，例如IP、DECnet、AppleTalk、Novell NetWare、OSI、Banyan VINES和Xerox Network System(XNS)。而路由協(xié)議是實(shí)現(xiàn)路由算法的協(xié)議，簡(jiǎn)單地說(shuō)，它給網(wǎng)絡(luò)協(xié)議做導(dǎo)向。路由協(xié)議如：IGRP、EIGRP、OSPF、EGP、BGP、IS-IS及RIP等。
