第15次課路由選擇協(xié)議

1、第5章 網(wǎng)絡(luò)層廣域網(wǎng)技術(shù)5.2 因特網(wǎng)的路由選擇協(xié)議n路由算法理想的路由算法n算法必須是正確的和完整的算法必須是正確的和完整的。n算法在計(jì)算上應(yīng)簡(jiǎn)單算法在計(jì)算上應(yīng)簡(jiǎn)單。n算法應(yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓惴☉?yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓?。n算法應(yīng)具有穩(wěn)定性算法應(yīng)具有穩(wěn)定性。n算法應(yīng)是公平的算法應(yīng)是公平的。1.1.算法應(yīng)是最佳的算法應(yīng)是最佳的。5.2 因特網(wǎng)的路由選擇協(xié)議n路由算法理想的路由算法n算法必須是正確的和完整的算法必須是正確的和完整的。既沿著各路由表所指引的路由,分組一定能夠到達(dá)目的網(wǎng)絡(luò)或主機(jī)。n算法在計(jì)算上應(yīng)簡(jiǎn)單算法在計(jì)算上應(yīng)簡(jiǎn)單。n算法應(yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓惴☉?yīng)能適應(yīng)通

2、信量和網(wǎng)絡(luò)拓?fù)涞淖兓?。n算法應(yīng)具有穩(wěn)定性算法應(yīng)具有穩(wěn)定性。n算法應(yīng)是公平的算法應(yīng)是公平的。1.1.算法應(yīng)是最佳的算法應(yīng)是最佳的。5.2 因特網(wǎng)的路由選擇協(xié)議n路由算法理想的路由算法n算法必須是正確的和完整的算法必須是正確的和完整的。n算法在計(jì)算上應(yīng)簡(jiǎn)單算法在計(jì)算上應(yīng)簡(jiǎn)單。路由選擇的計(jì)算不應(yīng)使通信量增加太多額外的開銷。n算法應(yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓惴☉?yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓?。n算法應(yīng)具有穩(wěn)定性算法應(yīng)具有穩(wěn)定性。n算法應(yīng)是公平的算法應(yīng)是公平的。1.1.算法應(yīng)是最佳的算法應(yīng)是最佳的。5.2 因特網(wǎng)的路由選擇協(xié)議n路由算法理想的路由算法n算法必須是正確的和完整的算法必須是正確的和完整的。

3、n算法在計(jì)算上應(yīng)簡(jiǎn)單算法在計(jì)算上應(yīng)簡(jiǎn)單。n算法應(yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓惴☉?yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓＜础白赃m應(yīng)性”或“稱穩(wěn)健性”。n算法應(yīng)具有穩(wěn)定性算法應(yīng)具有穩(wěn)定性。n算法應(yīng)是公平的算法應(yīng)是公平的。1.1.算法應(yīng)是最佳的算法應(yīng)是最佳的。5.2 因特網(wǎng)的路由選擇協(xié)議n路由算法理想的路由算法n算法必須是正確的和完整的算法必須是正確的和完整的。n算法在計(jì)算上應(yīng)簡(jiǎn)單算法在計(jì)算上應(yīng)簡(jiǎn)單。n算法應(yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓惴☉?yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓算法應(yīng)具有穩(wěn)定性算法應(yīng)具有穩(wěn)定性。在通信量或網(wǎng)絡(luò)拓?fù)湎鄬?duì)穩(wěn)定的情況下，路由算法應(yīng)收斂于一個(gè)可接受的解。n算法應(yīng)是公平的算法應(yīng)是公平的。

4、1.1.算法應(yīng)是最佳的算法應(yīng)是最佳的。5.2 因特網(wǎng)的路由選擇協(xié)議n路由算法理想的路由算法n算法必須是正確的和完整的算法必須是正確的和完整的。n算法在計(jì)算上應(yīng)簡(jiǎn)單算法在計(jì)算上應(yīng)簡(jiǎn)單。n算法應(yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓惴☉?yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓?。n算法應(yīng)具有穩(wěn)定性算法應(yīng)具有穩(wěn)定性。n算法應(yīng)是公平的算法應(yīng)是公平的。即算法對(duì)所有用戶都平等。1.1.算法應(yīng)是最佳的算法應(yīng)是最佳的。5.2 因特網(wǎng)的路由選擇協(xié)議n路由算法理想的路由算法n算法必須是正確的和完整的算法必須是正確的和完整的。n算法在計(jì)算上應(yīng)簡(jiǎn)單算法在計(jì)算上應(yīng)簡(jiǎn)單。n算法應(yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓惴☉?yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓?/p>

5、n算法應(yīng)具有穩(wěn)定性算法應(yīng)具有穩(wěn)定性。n算法應(yīng)是公平的算法應(yīng)是公平的。n算法應(yīng)是最佳的算法應(yīng)是最佳的?！白罴选本褪且宰畹偷拇鷥r(jià)實(shí)現(xiàn)路由算法。而“代價(jià)”是由一個(gè)或多個(gè)因素綜合決定的一種度量，如鏈路長(zhǎng)度、數(shù)據(jù)率、鏈路容量、傳播時(shí)延、通信量、緩存等。5.2 因特網(wǎng)的路由選擇協(xié)議n路由算法n兩種類型的路由算法 按照“從路由算法能否隨網(wǎng)絡(luò)的通信量或拓?fù)渥赃m應(yīng)的進(jìn)行調(diào)整變化”來(lái)劃分，路由算法分為兩大類：靜態(tài)路由選擇策略靜態(tài)路由選擇策略（非自適應(yīng)的）和動(dòng)態(tài)路由選擇策略動(dòng)態(tài)路由選擇策略（自適應(yīng)的）。靜態(tài)路由選擇策略的特點(diǎn)是簡(jiǎn)單和開銷小簡(jiǎn)單和開銷小，但不能及時(shí)適應(yīng)網(wǎng)絡(luò)的變化不能及時(shí)適應(yīng)網(wǎng)絡(luò)的變化。如最短路徑路由。

6、2.動(dòng)態(tài)路由選擇策略的特點(diǎn)是能較好地適應(yīng)網(wǎng)絡(luò)能較好地適應(yīng)網(wǎng)絡(luò)狀態(tài)的變化狀態(tài)的變化，但實(shí)現(xiàn)起來(lái)較為復(fù)雜，開銷也實(shí)現(xiàn)起來(lái)較為復(fù)雜，開銷也比較大比較大。如距離矢量路由。5.2 因特網(wǎng)的路由選擇協(xié)議n路由算法n分層次的路由選擇協(xié)議因特網(wǎng)采用分層次的路由選擇協(xié)議，這是由于以下兩種原因：n因特網(wǎng)的規(guī)模巨大，不可能所有的路由器知道所有的網(wǎng)絡(luò)；n許多單位不希望外界了解自己網(wǎng)絡(luò)的內(nèi)部布局，但同時(shí)又希望連接到因特網(wǎng)上。為此，因特網(wǎng)將整個(gè)網(wǎng)絡(luò)劃分成許多小的自治系統(tǒng)（AS）。每個(gè)自治系統(tǒng)自治系統(tǒng)都有權(quán)自主決定在本有權(quán)自主決定在本系統(tǒng)內(nèi)采用何種路由協(xié)議系統(tǒng)內(nèi)采用何種路由協(xié)議。5.2 因特網(wǎng)的路由選擇協(xié)議n路由算法n分層

7、次的路由選擇協(xié)議因特網(wǎng)又將路由協(xié)議劃分為兩大類：n內(nèi)部網(wǎng)關(guān)協(xié)議內(nèi)部網(wǎng)關(guān)協(xié)議IGPIGP。3.3.外部網(wǎng)關(guān)協(xié)議外部網(wǎng)關(guān)協(xié)議EGPEGP。5.2 因特網(wǎng)的路由選擇協(xié)議n路由算法n分層次的路由選擇協(xié)議因特網(wǎng)又將路由協(xié)議劃分為兩大類：n內(nèi)部網(wǎng)關(guān)協(xié)議內(nèi)部網(wǎng)關(guān)協(xié)議IGPIGP。即在一個(gè)自治系統(tǒng)內(nèi)部使用的路由選擇協(xié)議。目前這類路由選擇協(xié)議使用得最多，如 RIP 和 OSPF 協(xié)議。如RIP和OSPF協(xié)議。3.3.外部網(wǎng)關(guān)協(xié)議外部網(wǎng)關(guān)協(xié)議EGPEGP。5.2 因特網(wǎng)的路由選擇協(xié)議n路由算法n分層次的路由選擇協(xié)議因特網(wǎng)又將路由協(xié)議劃分為兩大類：n內(nèi)部網(wǎng)關(guān)協(xié)議內(nèi)部網(wǎng)關(guān)協(xié)議IGPIGP。n外部網(wǎng)關(guān)協(xié)議外部網(wǎng)關(guān)協(xié)議E

8、GPEGP。若源站和目的站處在不同的自治系統(tǒng)中，當(dāng)數(shù)據(jù)報(bào)傳到一個(gè)自治系統(tǒng)的邊界時(shí)，就需要使用一種協(xié)議，將路由選擇信息傳遞到另一個(gè)自治系統(tǒng)中。這樣的協(xié)議就是外部網(wǎng)關(guān)協(xié)議EGP。如BGP-4。5.2 因特網(wǎng)的路由選擇協(xié)議n路由算法自治系統(tǒng)之間的路由選擇也稱為，而在自治系統(tǒng)內(nèi)部的路由選擇稱為。5.2 因特網(wǎng)的路由選擇協(xié)議n內(nèi)部網(wǎng)關(guān)協(xié)議RIPRIPRIP是內(nèi)部網(wǎng)關(guān)協(xié)議IGP中使用得最廣泛的一個(gè)，是因特網(wǎng)的標(biāo)準(zhǔn)協(xié)議，其最大優(yōu)點(diǎn)就是簡(jiǎn)單。RIP是一種分布式的。分布式路由選擇協(xié)議的特點(diǎn)是每個(gè)路由都要不斷的和其它路由器交換路由信息。用于維護(hù)從它自己到其他每一個(gè)目的網(wǎng)絡(luò)的距離記錄。 5.2 因特網(wǎng)的路由選擇協(xié)議

9、n內(nèi)部網(wǎng)關(guān)協(xié)議RIP分布式路由選擇協(xié)議的要點(diǎn)是：n僅和相鄰路由器交換信息僅和相鄰路由器交換信息。n交換的信息是當(dāng)前本路由器的路由表當(dāng)前本路由器的路由表。n按固定的時(shí)間間隔按固定的時(shí)間間隔交換路由表。路由表中最主要的信息是：到某網(wǎng)絡(luò)的距離，以及經(jīng)過(guò)的下一跳地址。路由表更新的原則是：找出每個(gè)目的網(wǎng)絡(luò)的最短距離。這種算法稱為距離向量算法。5.2 因特網(wǎng)的路由選擇協(xié)議n內(nèi)部網(wǎng)關(guān)協(xié)議RIPRIP協(xié)議中“距離”的定義：從一路由器到直接連接直接連接的網(wǎng)絡(luò)的距離定義為 1。從一個(gè)路由器到非直接連接的網(wǎng)絡(luò)的距離定義為所經(jīng)過(guò)的路由器數(shù)加 1。RIP協(xié)議中的“距離”也稱為“跳數(shù)跳數(shù)” 。RIP 認(rèn)為一個(gè)好的路由就是

10、它通過(guò)的路由器的數(shù)目少，即“距離短”。“距離”的最大值為16 時(shí)即相當(dāng)于不可達(dá)?？梢?RIP 只適用于小型互聯(lián)網(wǎng)。5.2 因特網(wǎng)的路由選擇協(xié)議n內(nèi)部網(wǎng)關(guān)協(xié)議RIPn最短路徑路由屬于非自適應(yīng)的算法。就是所有的路由選擇都是事先計(jì)算好了的，在網(wǎng)絡(luò)啟動(dòng)時(shí)被下載到路由器中，稱為靜態(tài)路由?；舅枷胧牵航⒁粋€(gè)子網(wǎng)的拓?fù)鋱D，找出各對(duì)節(jié)點(diǎn)之間的最短路徑。這里的最短路徑指的可能是地理距離、跳數(shù)或是時(shí)延。5.2 因特網(wǎng)的路由選擇協(xié)議n內(nèi)部網(wǎng)關(guān)協(xié)議RIPn最短路徑路由下圖是從A節(jié)點(diǎn)開始的路由算法右表是A節(jié)點(diǎn)的路由表ABGE2261FCHD3322724(2,A)(4,B)(5,E)(6,E)(8,F)(9,B)(1

11、0,H)A站的路由表5.2 因特網(wǎng)的路由選擇協(xié)議n內(nèi)部網(wǎng)關(guān)協(xié)議RIPn距離矢量路由屬于自適應(yīng)算法。就是每個(gè)路由器維護(hù)一張表每個(gè)路由器維護(hù)一張表，表中列出當(dāng)前已知的到每個(gè)目標(biāo)的最佳距離每個(gè)目標(biāo)的最佳距離，以及所使用的線路使用的線路。通過(guò)在鄰居之間互相交換信息，路由器不斷的更新這張表。5.2 因特網(wǎng)的路由選擇協(xié)議n內(nèi)部網(wǎng)關(guān)協(xié)議RIPn距離矢量路由更新路由表的基本思想是：每個(gè)路由器每隔T毫秒向它的鄰居發(fā)送一個(gè)列表其中包含它到每個(gè)目標(biāo)的”距離”；同時(shí)，每個(gè)路由器也收到鄰居發(fā)出的類似的列表。每個(gè)路由器根據(jù)各個(gè)鄰居發(fā)來(lái)的列表，重新計(jì)算到達(dá)各目標(biāo)節(jié)點(diǎn)的最短“距離”和最佳路徑，并依此修改自己的路由表。J 的新

12、表中新估距離 = Min（J 到鄰居的距離 + 鄰居到其它節(jié)點(diǎn)距離）ABCDEFGHIJKL810126J 到到4個(gè)鄰居的距離向量個(gè)鄰居的距離向量新估距離新估距離下一站下一站J 的新的新路由表路由表n內(nèi)部網(wǎng)關(guān)協(xié)議RIP RIP存在的一個(gè)問(wèn)題是這就是好消息傳播得快，而壞消息傳播得慢。好消息傳播得快，而壞消息傳播得慢。5.2 因特網(wǎng)的路由選擇協(xié)議R2R1網(wǎng) 1網(wǎng) 3網(wǎng) 2正常情況1 1 1 2 R1R1 說(shuō)：“我到網(wǎng) 1 的距離是 1，是直接交付?！盧2 說(shuō)：“我到網(wǎng) 1 的距離是 2，是經(jīng)過(guò) R1?！眓內(nèi)部網(wǎng)關(guān)協(xié)議RIP RIP存在的一個(gè)問(wèn)題是這就是好消息傳播得快，而壞消息傳播得慢。好消息傳播得

13、快，而壞消息傳播得慢。5.2 因特網(wǎng)的路由選擇協(xié)議R2R1網(wǎng) 1網(wǎng) 3網(wǎng) 2正常情況1 1 1 2 R1R1 說(shuō)：“我到網(wǎng) 1 的距離是 1，是直接交付。”R2 說(shuō)：“我到網(wǎng) 1 的距離是 2，是經(jīng)過(guò) R1。”網(wǎng) 1出了故障1 16 1 2 R1R1 說(shuō)：“我到網(wǎng) 1 的距離是 16 （表示無(wú)法到達(dá)）， 是直接交付?！盧2 在收到 R1 的更新報(bào)文之前，還發(fā)送原來(lái)的報(bào)文，因?yàn)檫@時(shí) R2 并不知道 R1 出了故障。1 3 R21 5 R21 16 R21 4 R11 16 R1n內(nèi)部網(wǎng)關(guān)協(xié)議OSPFOSPF又稱為，其最主要特征是使用分布式的鏈路狀態(tài)協(xié)議鏈路狀態(tài)協(xié)議。和RIP相比，不同的有三點(diǎn)：1

14、.使用洪泛法洪泛法向本自治系統(tǒng)中所有的路由器發(fā)送信息所有的路由器發(fā)送信息。5.2 因特網(wǎng)的路由選擇協(xié)議R發(fā)送更新報(bào)文ACK報(bào)文n內(nèi)部網(wǎng)關(guān)協(xié)議OSPFOSPF的三個(gè)要點(diǎn)：n使用洪泛法洪泛法向本自治系統(tǒng)中所有的路由器發(fā)送信息所有的路由器發(fā)送信息。n發(fā)送信息是與本路由器相鄰的所有路由器的鏈路狀態(tài)所有路由器的鏈路狀態(tài)。n只有當(dāng)鏈路狀態(tài)發(fā)生變化發(fā)生變化時(shí)，路由器才發(fā)此信息。由于各路由器之間頻繁的交換鏈路狀態(tài)信息，因此所有的路由器最終都能建立一個(gè)鏈路狀態(tài)數(shù)據(jù)庫(kù)鏈路狀態(tài)數(shù)據(jù)庫(kù)，即全網(wǎng)全網(wǎng)的拓?fù)浣Y(jié)構(gòu)圖的拓?fù)浣Y(jié)構(gòu)圖。每個(gè)路由器使用該數(shù)據(jù)庫(kù)的數(shù)據(jù)，構(gòu)造自己的路由表。因而能查出到每個(gè)目的網(wǎng)絡(luò)應(yīng)該走哪條查出到每個(gè)目的

15、網(wǎng)絡(luò)應(yīng)該走哪條路徑路徑。5.2 因特網(wǎng)的路由選擇協(xié)議自治系統(tǒng) AS5.2 因特網(wǎng)的路由選擇協(xié)議n內(nèi)部網(wǎng)關(guān)協(xié)議OSPF為了使OSPF能夠用于規(guī)模很大的網(wǎng)絡(luò)，OSPF將一個(gè)自治系統(tǒng)再劃分為若干個(gè)更小的范圍，叫做區(qū)域。區(qū)域 0.0.0.1區(qū)域 0.0.0.3主干區(qū)域 0.0.0.0至其他自治系統(tǒng)R9R7R6R5R4R3R2R1網(wǎng) 8網(wǎng) 6網(wǎng) 3網(wǎng) 2網(wǎng) 1網(wǎng) 7區(qū)域 0.0.0.2網(wǎng) 4網(wǎng) 5R8 劃分區(qū)域的好處是將利用洪泛法交換鏈路狀態(tài)信息的范圍局限于每個(gè)區(qū)域而不是整個(gè)自治系統(tǒng)，這就減少了整個(gè)網(wǎng)絡(luò)的通信量。 在一個(gè)區(qū)域內(nèi)部的路由器只知道本區(qū)域的完整網(wǎng)絡(luò)拓?fù)?，而不知道其他區(qū)域的網(wǎng)絡(luò)拓?fù)涞那闆r。 OS

16、PF 使用層次結(jié)構(gòu)的區(qū)域劃分。在上層的區(qū)域叫作主干區(qū)域主干區(qū)域(backbone area)。主干區(qū)域的標(biāo)識(shí)符規(guī)定為0.0.0.0。主干區(qū)域的作用是用來(lái)連通其他在下層的區(qū)域。 自治系統(tǒng) AS5.2 因特網(wǎng)的路由選擇協(xié)議n內(nèi)部網(wǎng)關(guān)協(xié)議OSPF主干區(qū)域中的路由器稱為主干路由器主干路由器，其中區(qū)域相連接的又稱為區(qū)域邊界路由器區(qū)域邊界路由器。區(qū)域 0.0.0.1區(qū)域 0.0.0.3主干區(qū)域 0.0.0.0至其他自治系統(tǒng)R9R7R6R5R4R3R2R1網(wǎng) 8網(wǎng) 6網(wǎng) 3網(wǎng) 2網(wǎng) 1網(wǎng) 7區(qū)域 0.0.0.2網(wǎng) 4網(wǎng) 5R8R7R6R5R4R35.2 因特網(wǎng)的路由選擇協(xié)議n外部網(wǎng)關(guān)協(xié)議BGPBGP使用的環(huán)

17、境與內(nèi)部網(wǎng)關(guān)協(xié)議不同。因?yàn)椋?。由于各自治系統(tǒng)是運(yùn)行自己選定的內(nèi)部路由選擇協(xié)議，使用自己指明的路徑度量，因此，當(dāng)一條路徑通過(guò)幾個(gè)不同的自治系統(tǒng)時(shí)，要想對(duì)這樣的路徑計(jì)算出有意義的費(fèi)用是不可能的。因此，邊界網(wǎng)關(guān)協(xié)議 BGP 只能是力求尋找一條能夠到達(dá)目的網(wǎng)絡(luò)且（不能兜圈子），而。5.2 因特網(wǎng)的路由選擇協(xié)議n外部網(wǎng)關(guān)協(xié)議BGP在配置BGP時(shí)，每個(gè)自治系統(tǒng)的管理員要選擇至少一個(gè)路由器作為該自治系統(tǒng)的“BGPBGP發(fā)言人發(fā)言人”，它往往又是BGP的邊界路由器邊界路由器。自治系統(tǒng)連通圖 BGP 所交換的網(wǎng)絡(luò)可達(dá)性的信息就是要到達(dá)某個(gè)網(wǎng)絡(luò)所要經(jīng)過(guò)的一系列 AS。 當(dāng) BGP 發(fā)言人互相交換了網(wǎng)絡(luò)可達(dá)性的信息

18、后，各 BGP 發(fā)言人就根據(jù)所采用的策略從收到的路由信息中找出到達(dá)各 AS 的較好路由。 BGP構(gòu)造出的自治區(qū)與連通圖是樹形的，沒(méi)有回路。BGP 發(fā)言人交換路徑向量 主干網(wǎng)（AS1）地區(qū) ISP（AS2）地區(qū) ISP（AS3）本地 ISP（AS4）N1， N2本地 ISP（AS5）N3， N4本地 ISP（AS6）N5本地 ISP（AS7）N6， N7自治系統(tǒng) AS2 的 BGP 發(fā)言人通知主干網(wǎng)的 BGP 發(fā)言人：“要到達(dá)網(wǎng)絡(luò) N1, N2, N3 和 N4 可經(jīng)過(guò) AS2?！?BGP 發(fā)言人交換路徑向量 主干網(wǎng)（AS1）地區(qū) ISP（AS2）地區(qū) ISP（AS3）本地 ISP（AS4）N1， N2本地 ISP（AS5）N3， N4本地 ISP（AS6）N5本地 ISP（AS7）N6， N7主干網(wǎng)還可發(fā)出通知：“要到達(dá)網(wǎng)絡(luò) N5, N6 和 N7 可沿路徑（AS1, AS3）?！?5.2 因特網(wǎng)的路由選擇協(xié)