路由算法分類(lèi)比較

1、路由算法是路由協(xié)議必須高效地提供其功能，盡量減少軟件和應(yīng)用的開(kāi)銷(xiāo)。路由器使用路由算法來(lái)找到到達(dá)目的地的最佳路由。關(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)）算法。收斂是在最佳路徑的判斷上所有路由器達(dá)到一致的過(guò)程。當(dāng)某個(gè)網(wǎng)絡(luò)事件引起路 由可用或不可用時(shí)，路由

2、器就發(fā)出更新信息。路由更新信息遍及整個(gè)網(wǎng)絡(luò)，引發(fā) 重新計(jì)算最佳路徑，最終達(dá)到所有路由器一致公認(rèn)的最佳路徑。收斂慢的路由算 法會(huì)造成路徑循環(huán)或網(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)路由。各路由算法的區(qū)別點(diǎn)包括：靜態(tài)與動(dòng)態(tài)、單路徑與多路徑、平坦與分層、主機(jī)智 能與路由器智能、域內(nèi)與域間、鏈接狀態(tài)與距離向量。鏈接狀態(tài)算法（也叫做短路徑優(yōu)先算法）把路由信息散

3、布到網(wǎng)絡(luò)的每個(gè)節(jié) 點(diǎn)，不過(guò)每個(gè)路由器只發(fā)送路由表中描述其自己鏈接狀態(tài)的部分。距離向量算法（也叫做Bellman-Ford算法）中每個(gè)路由器發(fā)送路由表的 全部或部分，但只發(fā)給其鄰居。也就是說(shuō)，鏈接狀態(tài)算法到處發(fā)送較少的更新信息，而距離向量算法只向 相鄰的路由器發(fā)送較多的更新信息。metric是路頃法用以確定到達(dá)目的地的最佳路徑的計(jì)量標(biāo)準(zhǔn)，如路徑長(zhǎng)度。路由選擇協(xié)議(Routing protocol)當(dāng)兩臺(tái)非直接連接的計(jì)算機(jī)需要經(jīng)過(guò)幾個(gè)網(wǎng)絡(luò)通信時(shí)，通常就需要路由器。路由 器提供一種方法來(lái)開(kāi)辟通過(guò)一個(gè)網(wǎng)狀聯(lián)結(jié)的路徑。路由選擇協(xié)議的任務(wù)是，為路 由器提供他們建立通過(guò)網(wǎng)狀網(wǎng)絡(luò)最佳路徑所需要的相互共享的路由

4、信息。當(dāng)一個(gè)計(jì)算機(jī)發(fā)送一個(gè)分組時(shí)，在網(wǎng)絡(luò)上網(wǎng)絡(luò)協(xié)議棧的每一層都附加一些信息給 它。在接收方的對(duì)等層協(xié)議可以讀出這些信息。這些信息類(lèi)似于通信會(huì)話的某些 部分。網(wǎng)絡(luò)層的協(xié)議附加路由選擇信息，這可能是通過(guò)一個(gè)網(wǎng)絡(luò)的完整的路徑或 是一些指示分組應(yīng)該采用那條路徑的優(yōu)先值。發(fā)送方添加的網(wǎng)絡(luò)層信息只能由路 由器或接收方的網(wǎng)絡(luò)層協(xié)議讀取。中繼器和橋接器不能識(shí)別網(wǎng)絡(luò)層信息，只能傳 送和轉(zhuǎn)發(fā)分組。Routing Algorithms路由選擇算法一個(gè)路由器設(shè)備可能有兩個(gè)或多個(gè)可以發(fā)送數(shù)據(jù)分組的端口。它必須有一張轉(zhuǎn)發(fā) 表(forwarding table)為每一個(gè)端口標(biāo)明一個(gè)特定地址。早期路由器不和其它 路由器交換網(wǎng)

5、絡(luò)上有關(guān)路由器的信息，因此，一個(gè)路由器通常沿著每條路徑發(fā)送 數(shù)據(jù)分組，分組 充滿網(wǎng)絡(luò)，并且發(fā)送的一些分組在網(wǎng)絡(luò)上無(wú)休止地循環(huán)。為了避免這些問(wèn)題，路由器可以依賴人工編程把選擇的路徑輸進(jìn)設(shè)備。這被 稱為靜態(tài)路由選擇。動(dòng)態(tài)路由選擇是一個(gè)更好的方式，它依靠路由器收集網(wǎng)絡(luò)信 息和建立自己的路由表。路由器相互交換路由表，并且歸并這些路由信息建立更 新的路由表。從其它路由器上獲得的信息，提供到網(wǎng)絡(luò)上目的站點(diǎn)的路由中繼 (hop)數(shù)或與路徑相關(guān)的費(fèi)用。同時(shí)，每個(gè)路由選擇設(shè)備上的路由表，應(yīng)該包 含大體上一致的路由選擇信息。路由選擇協(xié)議基本上有兩類(lèi)：距離向量和鏈路狀態(tài)，將在下面用兩段文字介 紹這兩類(lèi)協(xié)議。距離向量

6、路由選擇協(xié)議的分組傳送路由是根據(jù)到接收站的hop數(shù)或費(fèi)用決定的， 這些信息由各相鄰的路由器提供。技術(shù)上通常都遵循Bellman-Ford算法。一個(gè)路由器有幾個(gè)端口，每個(gè)端口都有指定的價(jià)值，這些價(jià)值是由網(wǎng)絡(luò)管理 員設(shè)定的。用使用一條線路實(shí)際費(fèi)用的多少，作為一種衡量手段表明一條線路比 另一條好或壞。此外，相鄰的那些路由器告訴它們把分組送往目的站要花費(fèi)的代 價(jià)。路由器將端口的價(jià)值加到相鄰路由器的價(jià)值上，如下面的例子：端口 1價(jià)值10 +相鄰路由器價(jià)值17 = 27。端口 2價(jià)值20 +相鄰路由器價(jià)值5 = 25。端口 3價(jià)值30 +相鄰路由器價(jià)值7 = 37。在這種情況下，路由器將通過(guò)端口2傳送分組

7、，因?yàn)樗砻鞯浇邮照镜拇鷥r(jià) 最少。假如有必要，用鄰接端口2的路由器再計(jì)算到下一個(gè)路由器的路徑價(jià)值。路由信息，如下一個(gè)hop的地址等都存在表中，并且路由器大約每隔30秒 互相交換表。初始時(shí)，每一個(gè)網(wǎng)絡(luò)只知道直接相連的路由器。當(dāng)一個(gè)路由器得到 一張表，它將表項(xiàng)與自己的表進(jìn)行比較。根據(jù)這些信息，它用新增路由或刪除路 由來(lái)修改表。表中信息包含：網(wǎng)絡(luò)號(hào)；端口號(hào)；價(jià)值度量；下一個(gè)hop的地址。價(jià)值度量是路由器向前傳送分組到網(wǎng)中下一個(gè)路由器時(shí)選擇路徑所用的量 值。通用距離向量路由選擇協(xié)議有：路由選擇信息協(xié)議（RIP）是一個(gè)首先在Xerox網(wǎng)絡(luò)系統(tǒng)（XNS）中實(shí)現(xiàn)，而 后又在Novell的NetWare中實(shí)現(xiàn)

8、的距離向量路由選擇協(xié)議。內(nèi)部網(wǎng)關(guān)路由選擇協(xié)議（IGRP）是由Cisco開(kāi)發(fā)的距離向量路由選擇協(xié)議。路由選擇表維護(hù)協(xié)議（RTMP）是一個(gè)在兩個(gè)AppleTalk區(qū)中選取最佳路徑的 Apple協(xié)議，大約每10秒廣播一次。距離向量路由選擇不適合于有幾百個(gè)路由器的大型網(wǎng)或經(jīng)常要更新的網(wǎng)。在 大型網(wǎng)中，表的更新過(guò)程可能過(guò)長(zhǎng)，以至于最遠(yuǎn)的路由器的選擇表不大可能與其 它表同步更新。在這種情況下，鏈路狀態(tài)路由選擇更可取些。另外，鏈路狀態(tài)協(xié) 議能夠?yàn)榘踩鹨?jiàn)把機(jī)密信息隔離在特殊區(qū)域，或避開(kāi)網(wǎng)上正在進(jìn)行計(jì)算機(jī)輔 助設(shè)計(jì)（CAD）、多媒體通訊等擁擠區(qū)域。并且，路由選擇信息表在必要時(shí)進(jìn)行 交換而不是規(guī)律性地交換，這樣

9、可以減少網(wǎng)絡(luò)上的信息流量。鏈路狀態(tài)路由選擇比距離向量路由選擇需要更強(qiáng)的處理能力，但它可以對(duì)路由選 擇過(guò)程提供更多的控制和對(duì)變化響應(yīng)更快。路由選擇可以基于避開(kāi)擁塞區(qū)、線路 的速度、線路的費(fèi)用或各種優(yōu)先級(jí)別。Dijkstra算法用于計(jì)算路由，根據(jù)如下：分組到達(dá)目的站經(jīng)過(guò)的路由器數(shù)量，這叫做路由中繼（hop），并且hop數(shù) 越少越好。局域網(wǎng)間傳輸線路的速度。有些路由使用低速異步連接，而另一些路由使用 高速數(shù)字鏈路。信息擁塞將造成延遲。如果一臺(tái)工作站傳送一個(gè)大文件，路由器可以通過(guò)不 同的路徑發(fā)送分組以避免交通阻塞。路由的費(fèi)用路由的費(fèi)用，網(wǎng)絡(luò)管理員定義的一個(gè)度量，通常是根據(jù)傳輸介質(zhì)確定的。最便宜 的路徑

10、可能不是最快的，但對(duì)某些類(lèi)型的傳輸卻更為可取。最常用的鏈路狀態(tài)路由選擇協(xié)議是優(yōu)先開(kāi)放最短路徑（OSPF），它和OSI的中間 系統(tǒng)到中間系統(tǒng)（IS IS）是類(lèi)似的。OSPF的原型是Proten開(kāi)發(fā)的，是從OSIIS -IS的一個(gè)早期版本中派生出來(lái)的。OSPF在Internet和TCP / IP網(wǎng)上IP通信 的路由選擇中使用。IS IS既可在IP通信中使用，也可在OSI通信中使用。OPSF路由選擇表OPSF路由選擇表僅當(dāng)在需要時(shí)更新，而不是定時(shí)更換。這有效地減少了通信 流量和節(jié)省了網(wǎng)絡(luò)帶寬。通過(guò)網(wǎng)絡(luò)的路徑由上述標(biāo)準(zhǔn)選定。一個(gè)網(wǎng)絡(luò)管理員可以 根據(jù)信息傳送的類(lèi)型編制通過(guò)網(wǎng)絡(luò)的路徑。例如，當(dāng)線路有較高數(shù)

11、據(jù)傳輸率時(shí)， 即使通過(guò)網(wǎng)絡(luò)的那條路徑有較多的hop數(shù)也是很可取的；另一方面，對(duì)于不大重 要的信息將安排在低速低值的線路上傳送。Autonomous Environments 自治環(huán)境Internet路由選擇（TCP/IP）和OSI路由選擇使用了一個(gè)自治系統(tǒng)（AS）或管 理區(qū)域（AD）的概念，可以簡(jiǎn)單地理解成區(qū)域（domains）。一個(gè)區(qū)域是一些使 用相同路由選擇協(xié)議的主機(jī)和路由器的集合，如圖R-11中所示，它們使用相同 的路由選擇協(xié)議和由單一機(jī)構(gòu)管理。換句話說(shuō)，一個(gè)區(qū)域可以是一所大學(xué)或其它 機(jī)構(gòu)管理的一個(gè)互聯(lián)網(wǎng)。例如Internet是一個(gè)由教育部門(mén)、政府機(jī)關(guān)和各個(gè)公 司管理的自治系統(tǒng)鏈接起來(lái)的

12、互聯(lián)網(wǎng)絡(luò)。每個(gè)機(jī)構(gòu)都有自己的內(nèi)部網(wǎng)絡(luò)，通過(guò)外部網(wǎng)關(guān)與Internet網(wǎng)連接（Internet 網(wǎng)以前把路由器稱作網(wǎng)關(guān)，但現(xiàn)在已把它們叫做路由器了）。Internet有內(nèi)部 網(wǎng)關(guān)協(xié)議和外部網(wǎng)關(guān)協(xié)議。OSI協(xié)議也使用了自治系統(tǒng)的概念，但在一個(gè)區(qū)域內(nèi) 的路由選擇稱為域內(nèi)路由選擇，區(qū)域之間的路由選擇稱為域間路由選擇。內(nèi)部/域內(nèi)協(xié)議有許多種內(nèi)部網(wǎng)關(guān)協(xié)議，并有幾種在Internet網(wǎng)上常用，這些協(xié)議已在條目 “AppleTalk路由選擇”，“Internet路由選擇”和“OSI的路由選擇”中討論。地址解析協(xié)議（ARP）是一個(gè)Internet （TCP / IP）協(xié)議，它為內(nèi)部路由器傳遞 數(shù)據(jù)報(bào)提供了一種方

13、法。路由選擇信息協(xié)議（RIP）是一種距離向量路由選擇協(xié)議。優(yōu)先開(kāi)放最短路徑（OSPF）是一種鏈路狀態(tài)路由選擇協(xié)議，它優(yōu)于RIP。OSPF 是Internet網(wǎng)中最常用的內(nèi)部網(wǎng)關(guān)協(xié)議，但OSI IS-IS協(xié)議也用于Interneto 端系統(tǒng)到中間系統(tǒng)（ES-IS）是OSI公布的一種協(xié)議，它幫助端系統(tǒng)（如用戶的 計(jì)算機(jī)）尋找定位路由器，并提供一種方法使路由器告知端系統(tǒng)舊S）它們的存 在。中間系統(tǒng)到中間系統(tǒng)（IS-IS）也是OSI的一種路由選擇協(xié)議，它為一個(gè)域內(nèi)兩 個(gè)路由器之間傳送信息分組提供動(dòng)態(tài)路由。IS-IS是一種鏈接狀態(tài)協(xié)議。內(nèi)部網(wǎng)關(guān)路由選擇協(xié)議（IGRP）是Cisco開(kāi)發(fā)的一種距離向量路由選

14、擇協(xié)議。外部/域間協(xié)議在自治域的邊界是路由器（以前在Internet網(wǎng)上被稱為網(wǎng)關(guān)）。這些路由器和 其它路由器用外部協(xié)議或Internet術(shù)語(yǔ)的外部網(wǎng)關(guān)協(xié)議（EGP）交換信息。外部網(wǎng)關(guān)協(xié)議（EGP）是Internet上最初的域間路由選擇協(xié)議?，F(xiàn)在它已被周邊 網(wǎng)關(guān)協(xié)議（BGP）取代了。支持EGP的路由器也必須支持BGP。周邊網(wǎng)關(guān)協(xié)議（BGP）提供有關(guān)相鄰點(diǎn)可達(dá)性信息。BGP可以減低帶寬需求，這 是因?yàn)槁酚蛇x擇信息是增量交換的，而不是在路由器間發(fā)送路由選擇數(shù)據(jù)庫(kù)信 息。BGP也提供了基于策略的算法，使網(wǎng)絡(luò)管理者對(duì)路由選擇有較多的控制權(quán)， 例如對(duì)某些信息傳輸實(shí)行優(yōu)化的能力。域間路由選擇協(xié)議(IDRP

15、)是一種OSI無(wú)連接分組(CLNP)的OSI路由選擇協(xié)議。 IDRP包含路由選擇的策略，但它不大可能在Internet上代替BGP。IDRP可用一 種協(xié)議進(jìn)行IP和CLNP的域間路由選擇來(lái)增加對(duì)IP的支持。距離向量路由算法(Bellman-Ford Routing Algorithm)，也叫做最大流量演算法 (Ford-FulkersonAlgorithm)，其被距離向量協(xié)議作為一個(gè)算法，如RIP, BGP, ISO IDRP, NOVELL IPX。使用這個(gè)算法的路由器必須掌握這個(gè)距離表(它是一個(gè) 一維排列-“一個(gè)向量”)，它告訴在網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的最遠(yuǎn)和最近距離。在距離 表中的這個(gè)信息是根據(jù)

16、臨近接點(diǎn)信息的改變而時(shí)時(shí)更新的。表中數(shù)據(jù)的量和在網(wǎng) 絡(luò)中的所有的接點(diǎn)(除了它自己本身)是等同的。這個(gè)表中的列代表直接和它相連 的鄰居，行代表在網(wǎng)絡(luò)中的所有目的地。每個(gè)數(shù)據(jù)包括傳送數(shù)據(jù)包到每個(gè)在網(wǎng)上 的目的地的路徑和距離/或時(shí)間在那個(gè)路徑上來(lái)傳輸(我們叫這個(gè)為“成本”)。 這個(gè)在那個(gè)算法中的度量公式是跳躍的次數(shù)，等待時(shí)間，流出數(shù)據(jù)包的數(shù)量，等 等。在距離向量路由算法中，相鄰路由器之間周期性地相互交換各自的路由表備 份。當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)，路由器之間也將及時(shí)地相互通知有關(guān)變更信息。路由協(xié)議路曜提供了異構(gòu)網(wǎng)互聯(lián)的機(jī)制，實(shí)現(xiàn)將一個(gè)網(wǎng)絡(luò)的數(shù)據(jù)包發(fā)送到另一個(gè)網(wǎng) 絡(luò)。而路由就是指導(dǎo)IP數(shù)據(jù)包發(fā)送的路徑

17、信息。路由協(xié)議就是在路由指導(dǎo)IP 數(shù)據(jù)包發(fā)送過(guò)程中事先約定好的規(guī)定和標(biāo)準(zhǔn)。路由協(xié)議通過(guò)在路由器之間共享路 由信息來(lái)支持可路由協(xié)議。路由信息在相鄰路由器之間傳遞，確保所有路由器知 道到其它路由器的路徑?？傊?，路由協(xié)議創(chuàng)建了路由表，描述了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 路由協(xié)議與路由器協(xié)同工作，執(zhí)行路由選擇和數(shù)據(jù)包轉(zhuǎn)發(fā)功能。路由協(xié)議主要運(yùn)行于路由器上，路由協(xié)議是用來(lái)確定到達(dá)路徑的，它包括 RIP,IGRP,EIGRP,OSPF。起到一個(gè)地圖導(dǎo)航，負(fù)責(zé)找路的作用。它工作在網(wǎng)絡(luò)層 路由選擇協(xié)議主要是運(yùn)行在路由器上的協(xié)議，主要用來(lái)進(jìn)行路徑選擇。routed protocol (可被路由的協(xié)議)和routing proto

18、col (路由協(xié)議)經(jīng)常被 混淆?？杀宦酚傻膮f(xié)議(Routed Protocol)由路由協(xié)議(Routing Protocol)傳 輸，前者亦稱為網(wǎng)絡(luò)協(xié)議。這些網(wǎng)絡(luò)協(xié)議執(zhí)行在源與目的設(shè)備的用戶應(yīng)用間通信 所需的各種功能。網(wǎng)絡(luò)協(xié)議發(fā)生在OSI參考模型的上四層：傳輸層、會(huì)話層、表 示層和應(yī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、EIG

19、RP、OSPF、 EGP、BGP、IS-IS 及 RIP 等。路由協(xié)議作用是產(chǎn)生路由表，維護(hù)路由表。路由協(xié)議是指為可路由協(xié)議提供路由選擇服務(wù)的協(xié)議，路由協(xié)議的服務(wù)對(duì)象是可 路由協(xié)議，路由器節(jié)點(diǎn)通過(guò)路由協(xié)議實(shí)現(xiàn)路由表的自動(dòng)維護(hù)，目前主要的路由協(xié) 議包括 RIP,IGRP,OSPF,BGP 等?？陕酚蓞f(xié)議是指可以通過(guò)路由表來(lái)確定去向和路徑的協(xié)議，是受路由協(xié)議服務(wù)的 協(xié)議，是實(shí)現(xiàn)在網(wǎng)絡(luò)層設(shè)備之間進(jìn)行通信的協(xié)議，它們能夠完成不同網(wǎng)段間的通 信，可路由協(xié)議主要有IP/TCP協(xié)議棧中的IP協(xié)議，IPX/SPX協(xié)議棧中的IPX協(xié) 議，這些協(xié)議可以給網(wǎng)絡(luò)設(shè)備分配網(wǎng)絡(luò)號(hào)和主機(jī)號(hào)?？陕酚蓞f(xié)議是定義數(shù)據(jù)包內(nèi)各個(gè)字段

20、的格式和用途的網(wǎng)絡(luò)層封裝協(xié)議，該網(wǎng)絡(luò)層 協(xié)議允許將數(shù)據(jù)包從一個(gè)網(wǎng)絡(luò)設(shè)備轉(zhuǎn)發(fā)到另一個(gè)網(wǎng)絡(luò)設(shè)備。常見(jiàn)的可路由協(xié)議有 TCP/IP協(xié)議棧中的IP協(xié)議、Nover IPX/SPX協(xié)議棧的IPX協(xié)議?？陕酚蓞f(xié)議也 可稱為被路由協(xié)議，它是網(wǎng)絡(luò)層協(xié)議的支撐，象IP，IPX等，同時(shí)一個(gè)協(xié)議被成 為可路由協(xié)議必須能夠給每臺(tái)獨(dú)立的設(shè)備分配網(wǎng)絡(luò)號(hào)和主機(jī)號(hào)。如IPX只要求分 配網(wǎng)絡(luò)號(hào)，因?yàn)樗褂弥鳈C(jī)的MAC作為物理地址，而IP是要求你提供一個(gè)地址 和子網(wǎng)掩碼，通過(guò)它們的與運(yùn)算得到網(wǎng)絡(luò)號(hào)的，所以它們是可路由協(xié)議，NetBEUI 協(xié)議不是可路由協(xié)議，因?yàn)樗惶峁┑谌龑拥闹С?，它僅是一個(gè)小型的快速的高 效協(xié)議，僅限制在一個(gè)

21、網(wǎng)段中運(yùn)行。同時(shí)可路由協(xié)議是根據(jù)上層協(xié)議將數(shù)據(jù)封裝 到IP包里。路由協(xié)議是運(yùn)行終端系統(tǒng)上的協(xié)議，主要用來(lái)進(jìn)行相互通信。不可路由的傳輸協(xié)議，也就是傳輸協(xié)議可不可以路由（Routale or Nonroutable） 的意思，數(shù)據(jù)能不能使用這個(gè)傳輸協(xié)議，通過(guò)路由器將數(shù)據(jù)傳送到其他網(wǎng)絡(luò)網(wǎng)段。 換言之，可不可以路由，表示這個(gè)協(xié)議的信息包格式可否被路由器接受。TCP/IP、 IPX/SPX屬于可路由的協(xié)議，NetBUEI則屬于不可路由的協(xié)議。不可路由的協(xié)議通常通過(guò)網(wǎng)橋、集線器或中繼器傳送數(shù)據(jù)。路由可以靜態(tài)配置，也可以通過(guò)路由協(xié)議自動(dòng)生成。路由協(xié)議能夠自動(dòng)發(fā)現(xiàn) 和計(jì)算路由，并在拓?fù)渥兓瘯r(shí)自動(dòng)更新，無(wú)需人工

22、維護(hù)，適用于復(fù)雜的網(wǎng)絡(luò)。路由協(xié)議：路由器用來(lái)計(jì)算、維護(hù)網(wǎng)絡(luò)路由信息的協(xié)議，通常有一定的算法， 工作在傳輸層或應(yīng)用層。常見(jiàn)的路由協(xié)議：RIP、OSPF、BGP?？陕酚蓞f(xié)議：可被路由器轉(zhuǎn)發(fā)的協(xié)議，工作在網(wǎng)絡(luò)層。常見(jiàn)的可路由協(xié)議有 IP、IPX 等。路由協(xié)議和可路由協(xié)議之間的關(guān)系：routing protocol負(fù)責(zé)學(xué)習(xí)最佳路徑， 而routed protocol根據(jù)最佳路徑將來(lái)自上層的信息封裝在IP包里傳輸。動(dòng)態(tài)路由協(xié)議在協(xié)議棧中的位置BGP（基于TCP，端口 號(hào) 179）RIP （基于UDP，端口號(hào)520）OSPF（基于ip，協(xié)議 號(hào)89）TCPUDPIPRaw IP鏈路層物理層從所有的源結(jié)點(diǎn)到

23、一個(gè)給定的目的結(jié)點(diǎn)的最優(yōu)路由的集合形成了一個(gè)以目 的結(jié)點(diǎn)為根的樹(shù)，稱為匯集樹(shù)；路由算法的目的是找出并使用匯集樹(shù)。常見(jiàn)的路由選擇算法靜態(tài)路由算法最短路徑法構(gòu)建子網(wǎng)的拓?fù)鋱D，圖中的每個(gè) 結(jié)點(diǎn)代表一個(gè)路由器，每條弧代 表一條通信線路，為了選擇兩個(gè) 路由器間的路由，算法在圖中找 出最短路徑。Dijkstra 算法擴(kuò)散法事先不需要任何網(wǎng)絡(luò)信息；路由 器把收到的每一個(gè)分組，向除了 該分組到來(lái)的線路外的所有輸出 線路發(fā)送。將來(lái)會(huì)有多個(gè)分組的 副本到達(dá)目的地端，最先到達(dá)的， 可能是走了“最優(yōu)”的路徑擴(kuò)散法選擇性擴(kuò)散算法（能夠消除多余的 分組）基于流量的路 由算法既考慮拓?fù)浣Y(jié)構(gòu)，又兼顧網(wǎng)絡(luò)負(fù)荷；前 提：每對(duì)結(jié)點(diǎn)

24、間平均數(shù)據(jù)流是相對(duì)穩(wěn)定 和可預(yù)測(cè)的；根據(jù)網(wǎng)絡(luò)帶寬和平均流 量，可得出平均包延遲，因此路由選擇 問(wèn)題歸結(jié)為找產(chǎn)生網(wǎng)絡(luò)最小延遲的路 由選擇算法。提前離線（off-line）計(jì) 算動(dòng)態(tài)路由算法距離向量路由算法（也稱BellmanFord路由算法和FordFulkerson算法）每個(gè)結(jié)點(diǎn)通過(guò)測(cè)取與相鄰結(jié)點(diǎn)的 距離，再依據(jù)與其相鄰結(jié)點(diǎn)交換 的距離信息，間接地求出路由表； 各結(jié)點(diǎn)周期性地測(cè)取相鄰結(jié)點(diǎn)的 距離；向相鄰結(jié)點(diǎn)發(fā)送它到每個(gè) 目的結(jié)點(diǎn)的距離表，同時(shí)，它也 接收每個(gè)鄰居結(jié)點(diǎn)發(fā)來(lái)的距離 表；結(jié)點(diǎn)中的老路由表在計(jì)算中 不被使用。算法的缺陷：對(duì)好消息反應(yīng)迅速， 對(duì)壞消息反應(yīng)遲鈍。被RIP協(xié)議米 用距離向量路

25、由算法水平分裂算法（在發(fā) 送路由更新消息時(shí) 進(jìn)行限制，結(jié)點(diǎn)不向 相鄰結(jié)點(diǎn)報(bào)告那些 從該相鄰結(jié)點(diǎn)學(xué)習(xí) 到的路由信息）鏈路狀態(tài)路由 算法/鏈路狀 態(tài)最短路由優(yōu) 先算法SPF1.發(fā)現(xiàn)鄰居結(jié)點(diǎn)，并學(xué)習(xí)它們 的網(wǎng)絡(luò)地址；2 .測(cè)量到各鄰居 節(jié)點(diǎn)的延遲或者開(kāi)銷(xiāo)；3 .創(chuàng)建 鏈路狀態(tài)分組；4.使用擴(kuò)散 法發(fā)布鏈路狀態(tài)分組；5.計(jì)算 到每個(gè)其它路由器的最短路 徑實(shí)用協(xié)議：OSPF、IS-IS使用Dijkstra算 法處理鏈路信息分級(jí)路由選擇分而治之的思想；根據(jù)需要，將路由器分成區(qū)域（regions）、聚 類(lèi)（clusters）、區(qū)（zones）和 組（group）移動(dòng)主機(jī)的路 由選擇廣播路由選擇完全發(fā)送法、擴(kuò)

26、散 法、多目的地路由 選擇、生成樹(shù)法、 逆向路徑轉(zhuǎn)發(fā)組播路由選擇（一）有類(lèi)路由協(xié)議1、有類(lèi)路由協(xié)議的特點(diǎn)是發(fā)送路由更新包的時(shí)候不攜帶路由條目的子網(wǎng)掩碼2、有類(lèi)路由協(xié)議在路由傳遞過(guò)程中使用路由發(fā)送和接收規(guī)則。有類(lèi)路由協(xié)議更新發(fā)送規(guī)則：檢查路由更新網(wǎng)絡(luò)是否與發(fā)送端口同一主網(wǎng)1）.若否，路由更新自動(dòng)匯總成主類(lèi)網(wǎng)絡(luò)2）.若是，繼續(xù)檢查更新的路由是否與發(fā)送接口的掩碼一致是，發(fā)送更新否，忽略更新有類(lèi)路由協(xié)議更新接收規(guī)則：將網(wǎng)絡(luò)地址和接收接口的網(wǎng)絡(luò)地址進(jìn)行比較，判斷是否處于同一主網(wǎng)絡(luò)1）.處于同一主網(wǎng)絡(luò)，直接賦予該網(wǎng)絡(luò)地址接收接口的掩碼并寫(xiě)入路由表2）.不處于同一主網(wǎng)絡(luò),首先查看路由表中是否存在該主網(wǎng)絡(luò)的任

27、一子網(wǎng)a.不存在，接收該網(wǎng)絡(luò)地址，并賦予該網(wǎng)絡(luò)地址一個(gè)有類(lèi)掩碼，同時(shí)寫(xiě)入路由表b.存在，忽略該路由更新并丟棄3、有類(lèi)路由協(xié)議的特性：1）同一個(gè)主網(wǎng)絡(luò)下的子網(wǎng)若掩碼不一致，則會(huì)出現(xiàn)子網(wǎng)丟失，即不支持VLSM2）在邊界路由器上面會(huì)產(chǎn)生自動(dòng)匯總，并且這個(gè)自動(dòng)匯總是無(wú)法關(guān)閉的。對(duì)于不連續(xù)子網(wǎng)，必然導(dǎo)致多個(gè)路由器通告相同的路由更新（匯總后的），這樣將導(dǎo)致網(wǎng)絡(luò)不 正常，所以不支持不連續(xù)子網(wǎng)。對(duì)于連續(xù)子網(wǎng)，則是支持的。3）那么有類(lèi)路由協(xié)議包括：RIPV1 IGRP（二）無(wú)類(lèi)路由協(xié)議1、無(wú)類(lèi)路由協(xié)議的特點(diǎn)是發(fā)送路由更新包的時(shí)候攜帶自己的子網(wǎng)掩碼2、無(wú)類(lèi)路由協(xié)的特性：1）因?yàn)榘l(fā)送子網(wǎng)掩碼，可以支持VLSM，2）在邊界路由器上面的自動(dòng)匯總可以關(guān)閉，可以支持不連續(xù)子網(wǎng)。3）無(wú)類(lèi)路由協(xié)議包括:RIPV2 EIGRP OSPF ISIS BGPV44）基于現(xiàn)在我們所使用的網(wǎng)段一般都是VLSM，所以，我們現(xiàn)在都會(huì)使用無(wú)類(lèi)的路由協(xié)議?？偨Y(jié)：有類(lèi)路由協(xié)議和無(wú)類(lèi)路由協(xié)議的本質(zhì)區(qū)別就是在發(fā)送路由更新時(shí)是否發(fā)送子網(wǎng)掩碼。所以有 類(lèi)無(wú)類(lèi)協(xié)議的不同就在于是否支持VLSM（可變長(zhǎng)子網(wǎng)mask）。有類(lèi)的不發(fā)送mask，不支持 VLSM，無(wú)類(lèi)的反之。