楊航宇

（杭州師范大學(xué)錢江學(xué)院電器機(jī)械工程系 計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)，浙江 杭州 310012）

1 IP 路由算法

IP 路由算法可分為以下幾種：靜態(tài)和動態(tài)、單路和多路、平等和分級、源路由和透明路由、域內(nèi)和域間、鏈路狀態(tài)和距離向量。

鏈路狀態(tài)算法發(fā)送路由信息到互聯(lián)網(wǎng)上所有的結(jié)點(diǎn)，然而對于每個(gè)路由器，僅發(fā)送它的路由表中描述了其自身鏈路狀態(tài)的那一部分。距離向量算法則要求每個(gè)路由器發(fā)送其路由表全部或部分信息，但僅發(fā)送到鄰近結(jié)點(diǎn)上。從本質(zhì)上來說，鏈路狀態(tài)算法將少量更新信息發(fā)送至網(wǎng)絡(luò)各處，而距離向量算法發(fā)送大量更新信息至鄰接路由器。

由于鏈路狀態(tài)算法收斂更快，因此它在一定程度上比距離向量算法更不易產(chǎn)生路由循環(huán)。但另一方面，鏈路狀態(tài)算法要求比距離向量算法有更強(qiáng)的CPU 能力和更多的內(nèi)存空間，因此鏈路狀態(tài)算法將會在實(shí)現(xiàn)時(shí)顯得更昂貴一些。除了這些區(qū)別，兩種算法在大多數(shù)環(huán)境下都能很好地運(yùn)行。路由算法使用了許多種不同的度量標(biāo)準(zhǔn)去決定最佳路徑。復(fù)雜的路由算法可能采用多種度量來選擇路由，通過一定的加權(quán)運(yùn)算，將它們合并為單個(gè)的復(fù)合度量、再填入路由表中，作為尋徑的標(biāo)準(zhǔn)。

2 RIP 路由協(xié)議的原理分析

RIP 是基于距離矢量的路由協(xié)議。運(yùn)行RIP 的路由器維持一個(gè)到網(wǎng)絡(luò)中可能目的地的路由表，路由表包含目的地址和開銷等信息。具體的說，RIP 協(xié)議主要包括以下幾個(gè)方面的內(nèi)容。

2.1 計(jì)算距離矢量

距離矢量路由協(xié)議利用度量來跟蹤它和所有已知目的地間的距離。這種距離信息使路由器可以找出到位于非近鄰獨(dú)立系統(tǒng)中的目的地最有效的下一跳。在RFC-1058 中，有一個(gè)唯一的距離矢量單位，即跳數(shù)。在RIP 中默認(rèn)的跳數(shù)度量被置為1，這些距離度量用來構(gòu)造路由表。路由表識別出數(shù)據(jù)包，以最小開銷到達(dá)目的地所要采取的下一跳。

2.2 更新路由表

RIP只記錄每個(gè)目的地址的一條路由，這一事實(shí)要求RIP 經(jīng)常保持其路由表的完整性。它通過要求所有活躍的RIP 路由器周期性的向相鄰RIP 路由器廣播它們路由表的內(nèi)容。通常，RIP 依賴3 個(gè)計(jì)時(shí)器來維護(hù)路由表：即更新計(jì)時(shí)器、路由暫休計(jì)時(shí)器、路由清楚計(jì)時(shí)器。更新計(jì)時(shí)器用來激發(fā)節(jié)點(diǎn)路由表的更新。每個(gè)RIP節(jié)點(diǎn)只有一個(gè)更新計(jì)時(shí)器。然而，路由暫休和路由清除計(jì)時(shí)器則是每條路由都有一個(gè)。因此，每個(gè)路由表?xiàng)l目中都有一個(gè)不同的暫休和路由清除計(jì)時(shí)器?？傊@些計(jì)時(shí)器使RIP 節(jié)點(diǎn)能維護(hù)它們路由的完善性，并根據(jù)所用的時(shí)間進(jìn)行激活，從而恢復(fù)網(wǎng)絡(luò)故障。

2.3 激活路由更新

大約每30s 激活一次路由更新。更新路由器用來跟蹤這個(gè)時(shí)間量。當(dāng)這個(gè)時(shí)間量結(jié)束時(shí)，RIP 發(fā)送一系列幀來維護(hù)整個(gè)路由表。這些幀廣播到每個(gè)鄰節(jié)點(diǎn)。因此，每個(gè)RIP 路由器大約每30s 就要接收來自鄰RIP 節(jié)點(diǎn)的更新。

2.4 識別無效路由

路由變得無效的兩種情況：其一，路由到期；其二，路由器可能通知某個(gè)路由器某條路由是不可用的。在這兩種情況下，RIP 路由器都需要改變它的路由表，來反映給定路由的不可用性。假如路由器在給定的時(shí)間內(nèi)沒有接收到更新某路由的信息，該路由可能到期。路由暫休定時(shí)器常設(shè)成180s，當(dāng)路由激活或更新時(shí)，該定時(shí)器初始化。假如180s 過去了，路由器還沒有接到更新那條路由的信息，RIP 路由器就認(rèn)為目的IP 地址不再可達(dá)。因此路由器把表中那條路由項(xiàng)標(biāo)成無效。收到路由新近無效通知的鄰節(jié)點(diǎn)利用該信息來更新它們的路由表。這是路由表中路由變得無效的第2 種方法。無效路由表項(xiàng)不會自動的從路由表中清除;相反，那條無效項(xiàng)繼續(xù)在路由表中保留很短一段時(shí)間。下面將討論無效路由真正從路由表中清除的過程。

2.5 清除無效路由

當(dāng)路由器認(rèn)識到某條路由無效時(shí)，就初始化一個(gè)秒計(jì)時(shí)器，負(fù)責(zé)路由清除倒計(jì)時(shí)，這一計(jì)時(shí)稱為路由清除計(jì)時(shí)器。當(dāng)路由清除計(jì)時(shí)器結(jié)束時(shí)，路由仍未被收到，這一路由就從路由表中清除。這些計(jì)時(shí)器是RIP 恢復(fù)網(wǎng)絡(luò)故障能力中絕對重要的。

2.6 編址方案

IETF 保證RIP 能夠完全向后兼容所有已知的RIP 和ROUTED 異體。即使這些異體專用程度很高，開放標(biāo)準(zhǔn)RIP 仍有必要支持多種地址類型。

2.7 路由到網(wǎng)關(guān)

很多實(shí)際網(wǎng)絡(luò)中，并不要計(jì)算到每個(gè)單個(gè)主機(jī)的路由。特別是在大型網(wǎng)絡(luò)中，這會使路由表膨脹，從而使整個(gè)網(wǎng)絡(luò)的路由工作繁重。因此在實(shí)際網(wǎng)絡(luò)中，幾乎總是概括路由，而不是指出每個(gè)可能目的地。假如一個(gè)給定的網(wǎng)絡(luò)（或子網(wǎng)）上，每個(gè)主機(jī)都能通過網(wǎng)關(guān)到達(dá)的話，這時(shí)路由表只需定義那個(gè)網(wǎng)關(guān)為下一條IP 地址就可以了。所有發(fā)往那個(gè)網(wǎng)絡(luò)或子網(wǎng)上的數(shù)據(jù)包將發(fā)送給那個(gè)網(wǎng)關(guān)，這時(shí)網(wǎng)關(guān)就承擔(dān)了把它發(fā)送到最終目的地的任務(wù)。

總之，RIP 的特點(diǎn)是路由器間定時(shí)地交換網(wǎng)絡(luò)的整體知識，并且只和相鄰路由器交換這種知識。換句話說，路由器只和相鄰路由器共享網(wǎng)絡(luò)信息。路由器一旦從相鄰路由器獲取了新的知識，就將其追加到自己的數(shù)據(jù)庫中，并將該信息傳遞給所有的相鄰的路由器。相鄰路由器做同樣的操作，經(jīng)過若干次傳遞，使自治系統(tǒng)內(nèi)的所有路由器都能獲得完整的路由信息。

3 RIP 協(xié)議處理過程

RIP 協(xié)議的運(yùn)行過程就是路由器軟件對消息輸入和輸出處理過程，其輸入和輸出處理大致如下所描述。

輸入處理：主要是指路由器協(xié)議軟件對在520 號UDP 端口收到的數(shù)據(jù)報(bào)進(jìn)行的處理。對于輸入處理，首先必須先作一定格式檢查，檢查通過后，再分別對幾種輸入消息做相應(yīng)的處理。

請求報(bào)文：路由器在開始運(yùn)行時(shí)，為了從鄰機(jī)處獲取路由表的初始值，通常會發(fā)一個(gè)請求。報(bào)文的Command 字段為。對所有或部分路由表的請求，一般以廣播形式從520 號UDP 端口發(fā)送。實(shí)際中，這種請求有兩種格式：請求獲取路由表的全部和請求獲取路由表的某些特定路由項(xiàng)。路由軟件先逐個(gè)路由項(xiàng)地處理請求，如果沒有任何路由項(xiàng)，也就沒有響應(yīng)；如果請求中恰好只有一個(gè)路由項(xiàng)，并且addressfamilyidentifier為0，metric 為16，則表示需要接收方發(fā)送所有路由表的請求；除此之外，則是要求部分路由，處理很簡單，沿著請求路由項(xiàng)表一個(gè)一個(gè)看，對于每個(gè)路由項(xiàng)，在主機(jī)路由數(shù)據(jù)庫中查找，如果找到，則將該路由的metric 值填入數(shù)據(jù)報(bào)的metric 字段，如果沒有，則向其中填16。一旦所有路由項(xiàng)均已處理，將command 字段設(shè)為響應(yīng)，并將該數(shù)據(jù)報(bào)發(fā)回其來自的端口。根據(jù)請求是否關(guān)于指定的一批目的地，還是關(guān)于整個(gè)路由表，處理有所不同。如果關(guān)于整個(gè)路由表，輸出作普通的處理即可，包括水平分割和子網(wǎng)隱藏，因此來自路由表的某些路由項(xiàng)將被隱藏；如果是指定路由項(xiàng)，則將查找結(jié)果返回，不作水平分割，如果需要還要返回子網(wǎng)信息。

響應(yīng)報(bào)文：因?yàn)橹付ú樵?、路由修改等原因而收到響?yīng)。不論收到什么樣的響應(yīng)，RIP 處理程序就開始更新它的路由表。

輸出處理：用于產(chǎn)生包含全部或部分路由表的響應(yīng)信息的處理，可能由于輸入進(jìn)程發(fā)現(xiàn)請求或路由修改而觸發(fā)。響應(yīng)請求產(chǎn)生的輸出可以直接按需工作，而觸發(fā)的修改因?yàn)閮蓚€(gè)方面需要處理。

首先，觸發(fā)的修改在容量有限或有許多路由器的網(wǎng)絡(luò)上可能導(dǎo)致格外大的負(fù)載，因此協(xié)議要求實(shí)現(xiàn)方在限制觸發(fā)式修改出現(xiàn)的頻率上采取一定的措施，觸發(fā)式修改發(fā)送后，需要隨機(jī)地將一個(gè)定時(shí)器設(shè)置成1 到5 秒，如果在定時(shí)器超時(shí)前發(fā)生其它修改，需要到定時(shí)器超時(shí)才觸發(fā)其中之一，然后定時(shí)器再隨機(jī)地設(shè)置成1到5 秒，觸發(fā)式修改可能被一般修改所禁止；另外，觸發(fā)式修改可能不必包括整個(gè)路由表，原則上說，只有改變過的路由才需要包括，作為觸發(fā)式修改一部分的信息至少包括設(shè)置了路由修改標(biāo)志的路由，也可以包括附加路由和全部路由。如果完整的修改需要多個(gè)數(shù)據(jù)報(bào)，則發(fā)送全部路由極有可能被打斷；而觸發(fā)式修改處理時(shí)，需要產(chǎn)生每個(gè)直連網(wǎng)絡(luò)的信息。產(chǎn)生觸發(fā)式修改或一般修改時(shí)，都需要進(jìn)行水平分割操作。

[1]蘇傳蓉.幾種常見路由協(xié)議的應(yīng)用.湖北郵電技術(shù),2002.

[2]張宏科,張思東,劉文紅.路由器原理與技術(shù).北京：國防工業(yè)出版社，2003.

[3]劉心松，李亞為，羅浩.RIP 路由器的開發(fā).電子學(xué)報(bào).2002.