我們知道網(wǎng)絡(luò)層的關(guān)鍵作用在于路由尋址，這主要依靠路由選擇協(xié)議來(lái)實(shí)現(xiàn)，而路由選擇協(xié)議的核心在于利用路由算法生成路由表。在正式介紹今天的路由算法以前，我們先來(lái)了解一下關(guān)于路由的幾個(gè)基本概念。

1. 理想的路由算法
   設(shè)計(jì)一個(gè)路由算法，如果要達(dá)到理想的作用，應(yīng)該具備以下幾個(gè)特點(diǎn)：
   -1. 正確性：這是最基本的，即通過(guò)路由表中的記錄保證數(shù)據(jù)分組一定可以最終到達(dá)目的主機(jī)；
   -2. 簡(jiǎn)單：路由算法的計(jì)算不應(yīng)使網(wǎng)絡(luò)增加太大的開(kāi)銷(xiāo)；
   -3. 自適應(yīng)性：路由算法應(yīng)當(dāng)能夠適應(yīng)網(wǎng)絡(luò)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓淳哂蟹€(wěn)健性；
   -4. 穩(wěn)定性：即在網(wǎng)絡(luò)通信量和網(wǎng)絡(luò)拓?fù)湎鄬?duì)穩(wěn)定的前提下，算法應(yīng)當(dāng)收斂于一個(gè)可接受的解；
   -5. 公平性；
   -6. 最佳的；

一般根據(jù)路由算法是否具有自適應(yīng)性，可以將其分為靜態(tài)路由選擇策略和動(dòng)態(tài)路由選擇策略。

2. 分層次的路由選擇協(xié)議 現(xiàn)實(shí)中的路由協(xié)議建立在分層管理實(shí)現(xiàn)的基礎(chǔ)之上，這主要是基于AS（Autonomous System）的劃分，所謂AS，經(jīng)典定義是在單一的技術(shù)管理下的一組路由器，因?yàn)楝F(xiàn)實(shí)中出現(xiàn)了內(nèi)部多種路由協(xié)議的AS，因此現(xiàn)在一般認(rèn)為AS盡管內(nèi)部有可能使用多種內(nèi)部路由選擇協(xié)議和度量，但是一個(gè)AS對(duì)其他AS表現(xiàn)出的是一個(gè)單一的和一致的路由選擇策略。
   之所以選擇將網(wǎng)絡(luò)拓?fù)涞穆酚煞謱庸芾?，一個(gè)原因是因特網(wǎng)的規(guī)模很大，因此如果保存所有目的網(wǎng)絡(luò)的地址，路由表會(huì)是一個(gè)相當(dāng)大的規(guī)模；另一個(gè)原因則是有些單位基于保密性的需要不希望外界看到自己內(nèi)部的網(wǎng)絡(luò)拓?fù)淝闆r。
   出現(xiàn)了AS概念之后，我們可以簡(jiǎn)單地理解為統(tǒng)一管理的一組路由器，內(nèi)部可以使用相同或不同的路由選擇協(xié)議，一般在AS內(nèi)部使用的路由選擇協(xié)議稱之為內(nèi)部網(wǎng)關(guān)協(xié)議IGP，比如RIP和OSPF；在AS間使用的路由選擇協(xié)議則稱之為外部網(wǎng)關(guān)協(xié)議EGP，比如BGP協(xié)議。關(guān)于AS、IGP、BGP的一個(gè)簡(jiǎn)單的示意圖如下：

一、內(nèi)部網(wǎng)關(guān)協(xié)議：RIP
路由信息協(xié)議RIP(Routing Information Protocol)是內(nèi)部網(wǎng)關(guān)協(xié)議IGP中最先得到廣泛使用的協(xié)議，RIP是一個(gè)分布式的基于距離向量的路由選擇協(xié)議，其最大優(yōu)點(diǎn)就是簡(jiǎn)單。下面不再羅嗦地細(xì)致介紹，而是簡(jiǎn)要列出RIP協(xié)議的一些要點(diǎn)和關(guān)鍵概念。

1. 距離向量：RIP協(xié)議中每個(gè)路由器都要維護(hù)自己到每一個(gè)目的網(wǎng)絡(luò)的距離記錄，由于是一組距離，因此稱之為距離向量，這將作為路由選擇的度量；一般直連網(wǎng)段定義為1，每通過(guò)一個(gè)路由器距離+1，當(dāng)然也可以定義直連網(wǎng)段為0，由于是統(tǒng)一的確定起始的基數(shù)，因此不會(huì)影響RIP協(xié)議的路由比較和選擇。
2. RIP協(xié)議的三個(gè)要點(diǎn)：-a. Who：與誰(shuí)交換信息？ RIP協(xié)議中的信息交換僅發(fā)生在相鄰的兩個(gè)路由器之間，不相鄰的路由器不交換信息；-b. What：交換什么信息？ 路由器交換的信息是當(dāng)前本路由器知道的全部信息，即自己的路由表【我到本AS中所有網(wǎng)絡(luò)的最短距離+到每個(gè)網(wǎng)路的NextHop】；-c. When：什么時(shí)候交換信息？ 路由器按規(guī)定的時(shí)間間隔交換路由信息，比如每隔30秒，然后路由器根據(jù)收到的信息更新路由表；當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)，路由器也會(huì)及時(shí)的告知相鄰路由器；
3. RIP協(xié)議的路由向量算法 RIP協(xié)議基于以下路由算法得出路由表，以路由器A為例：
   -1. A自動(dòng)獲取直連網(wǎng)段的路由；
   -2. 收到RIP更新包后，假設(shè)來(lái)自于相鄰路由器B，則對(duì)其中的記錄進(jìn)行修改- *將所有路由記錄項(xiàng)的距離+1； *將所有路由記錄的下一跳改為B；
   -3. 接下來(lái)針對(duì)修改過(guò)的B的路由表進(jìn)行以下判斷和處理： *若原來(lái)路由表中沒(méi)有的目的網(wǎng)絡(luò)記錄，則添加該項(xiàng)路由； *若原來(lái)路由表中有下一跳為B的記錄，直接更新； *若收到的項(xiàng)目中的距離小于原先路由表中的距離，則進(jìn)行更新； *否則什么也不做；
   -4. 若三分鐘還沒(méi)有收到相鄰路由器的更新路由表，則把此相鄰路由器記為不可達(dá)，即把距離記為16（最大15）；
   -5. 返回； 上面給出的距離向量算法的基礎(chǔ)就是Bellman-Ford算i法，其要點(diǎn)是設(shè)B是A到C的最短路徑上的一個(gè)節(jié)點(diǎn)，若把路徑A-C拆為兩段路徑A-B和B-C，則每一段路徑也分別是響應(yīng)端點(diǎn)之間的最短路徑。
   比如路由器6具有路由表1，相鄰路由器4發(fā)來(lái)路由表2，則RIP的運(yùn)行結(jié)果可以分析：
   首先我們對(duì)R4發(fā)來(lái)的路由表做一些處理，距離部分+1，然后下一跳均改為R4：
   然后我們分析比較原先的R6的路由表，發(fā)現(xiàn)第一條記錄Net1的記錄沒(méi)有，因此直接添加： 【Net1 4 R4】 第二條記錄Net2存在，且下一跳相同，因此用新的更新舊的： 【Net2 5 R4】 第三條記錄的下一跳不同，比較距離，新的更短，因此替換掉原先的路由： 【Net3 2 R4】 此時(shí)我們得到的新的路由表就是：
   4. RIP協(xié)議的缺點(diǎn) RIP實(shí)施簡(jiǎn)單，但是卻有自身的不足，比如最大跳數(shù)為16，只能適用于小規(guī)模網(wǎng)路；路由度量?jī)H僅是路由器跳數(shù)，比較單一，無(wú)法涵蓋跳數(shù)多、延遲小的高速鏈路情況；最為重要的一點(diǎn)是當(dāng)網(wǎng)絡(luò)出現(xiàn)故障時(shí)，要經(jīng)過(guò)較長(zhǎng)的時(shí)間才能將此信息傳送到所有的路由器。即：好消息傳得快，而壞消息傳得慢。 比如當(dāng)路由器R1到網(wǎng)1的鏈路出現(xiàn)了故障，R1無(wú)法到達(dá)網(wǎng)1了，那么R1就將到網(wǎng)1的距離改為了16；在R1向臨接的路由器R2發(fā)送自己的新路由項(xiàng)前，先收到了R2的路由項(xiàng)【Net1 2 R1】，于是按照規(guī)則R1修改后成為了【Net1 3 R2】，并且與16比較后更新了自己的路由表；然后R1再次發(fā)送該項(xiàng)給R2，R2接受到以后發(fā)現(xiàn)是【Net1 4 R1】，于是直接替換掉了自己的【Net1 2 R1】；然后R2再向R1發(fā)送路由表....循環(huán)交替，直到Net1的距離成為了16，R2才明白原來(lái)無(wú)法到達(dá)Net1了：
   解決這樣問(wèn)題的方法可以是對(duì)于某些特定端口發(fā)來(lái)的路由信息，不再回送回去。總之，RIP協(xié)議最大的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單、開(kāi)銷(xiāo)較小，但是對(duì)于較大的網(wǎng)絡(luò)，還是應(yīng)當(dāng)使用OSPF協(xié)議。

二、內(nèi)部路由協(xié)議：OSPF OSPF協(xié)議的意思是“開(kāi)放最短路徑優(yōu)先”(Open Shortest Path First)，“開(kāi)放”指的是OSPF協(xié)議不受某一家廠商控制，是公開(kāi)發(fā)表的；“最短路徑優(yōu)先”則是指使用了Dijkstra算法的最短路徑算法SPF。OSPF與RIP協(xié)議不同，主要使用分布式的鏈路狀態(tài)協(xié)議，和RIP協(xié)議相比，OSPF具有自己的三個(gè)特點(diǎn)：
-1. Who 采用洪泛法（Flooding）向本AS系統(tǒng)內(nèi)的所有路由器發(fā)送信息，首先通過(guò)所有直連輸出接口向所有相鄰的路由器發(fā)送信息，每一個(gè)相鄰的路由器又將此信息發(fā)往其相鄰的所有路由器（不再重復(fù)回傳給信源路由器），這樣最終整個(gè)AS中所有的路由器都得到了這個(gè)信息的一個(gè)副本。RIP協(xié)議只是向自己相鄰的路由器發(fā)送信息；
-2. What 發(fā)送的信息就是本路由器相鄰的所有路由器的鏈路狀態(tài)，但這只是路由器所知道的部分信息。所謂鏈路狀態(tài)就是指【我的鄰居路由器有哪些？我到各個(gè)鄰居路由器的鏈路度量】，OSPF用這個(gè)度量表示費(fèi)用、距離、時(shí)延和帶寬等，而這些都由具體的網(wǎng)絡(luò)管理人員來(lái)規(guī)定，因此OSPF相對(duì)于RIP的距離向量來(lái)說(shuō)更為靈活。RIP則發(fā)送的是【到所有網(wǎng)絡(luò)的距離以及下一跳】；
-3. When 只有當(dāng)鏈路狀態(tài)發(fā)生變化時(shí)路由器才向所有路由器泛洪發(fā)送此消息，而不想RIP那樣，不管有無(wú)變化都發(fā)送路由信息。 除此之外，OSPF相對(duì)于RIP來(lái)說(shuō)具有以下不同：-1. OSPF對(duì)于不同類(lèi)型的業(yè)務(wù)可計(jì)算出不同的路由；-2. OSPF中到達(dá)一個(gè)目的網(wǎng)絡(luò)可以有多條相同代價(jià)的路徑，那么可以同時(shí)分配通信量，做到負(fù)載平衡； 經(jīng)過(guò)各路由器之間頻繁的交換鏈路狀態(tài)信息，最終一個(gè)路由器中都能建立一個(gè)鏈路狀態(tài)數(shù)據(jù)庫(kù)，這里面實(shí)際上就是全網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖。里面記錄著【全網(wǎng)絡(luò)中有哪些服務(wù)器、哪些服務(wù)器是直接相連的、鏈路代價(jià)是多少】，然后每一個(gè)路由器使用最小路徑算法得出自己的路由表。RIP協(xié)議永遠(yuǎn)只知道相鄰結(jié)點(diǎn)的情況，不曉得整體的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。
一般為了應(yīng)用到很大的網(wǎng)絡(luò)，OSPF又將一個(gè)AS分為了更小的范圍，稱為區(qū)域。每次劃分都有一個(gè)主區(qū)域，用于連接各個(gè)子區(qū)域；每個(gè)區(qū)域中的路由器最好不要超過(guò)200個(gè)；區(qū)域之間相連的是區(qū)域邊界路由器；主干區(qū)域內(nèi)的路由器都稱為主干路由器，且其中必須有一個(gè)用于和其他的AS相連，稱之為自治系統(tǒng)邊界路由器。