網(wǎng)海茫茫路何方

１．IP路由簡介

　　路由就是選擇一條數(shù)據(jù)包傳輸路徑的過程。當(dāng)TCP/IP主機(jī)發(fā)送IP數(shù)據(jù)包時，便出現(xiàn)了路由。路由器是從一個物理網(wǎng)向另一個物理網(wǎng)發(fā)送數(shù)據(jù)包的裝置，路由器通常被稱為網(wǎng)關(guān)。對于發(fā)送的主機(jī)和路由器而言，必須決定向哪里轉(zhuǎn)發(fā)數(shù)據(jù)包。在決定路由時，IP層查詢位于內(nèi)存中的路由表。

（1）當(dāng)一個主機(jī)試圖與另一個主機(jī)通信時，IP首先決定目的主機(jī)是一個本地網(wǎng)還是遠(yuǎn)程網(wǎng)。

（2）如果目的主機(jī)是遠(yuǎn)程網(wǎng)，IP將查詢路由表來為遠(yuǎn)程主機(jī)或遠(yuǎn)程網(wǎng)選擇一個路由。

（3）若未找到明確的路由，IP用缺省的網(wǎng)關(guān)地址將一個數(shù)據(jù)傳送給另一個路由器。

（4）在該路由器中，路由表再次為遠(yuǎn)程主機(jī)或網(wǎng)絡(luò)查詢路由，若還未找到路由，該數(shù)據(jù)包將

發(fā)送到該路由器的缺省網(wǎng)關(guān)地址。

　　每發(fā)現(xiàn)一條路由，數(shù)據(jù)包被轉(zhuǎn)送下一級路由器，稱為一次“跳步”（hop），并最終發(fā)送至目的主機(jī)。若未發(fā)現(xiàn)任何一個路由，源主機(jī)將收到一個出錯信息。　

２．路由表和路由協(xié)議

　　交換路由信息的協(xié)議聯(lián)接世界上的許多路由器，盡管這些路由器并不同類，通過路由表還是可以提供它們共同的網(wǎng)絡(luò)視圖。路由表為路由器存儲了到達(dá)網(wǎng)絡(luò)上任一目的地所需要的一切必要的信息。

　　各種各樣的路由協(xié)議被用來填寫網(wǎng)絡(luò)中的路由表。象BGP，OSPF，RIP和ISIS這樣的協(xié)議可以傳輸給所有的路由器一個正確和一致的網(wǎng)絡(luò)視圖。

３．路由協(xié)議的“理想”

　　你能夠想象如果每個路由器都存儲從它的節(jié)點(diǎn)所能到達(dá)的每個目標(biāo)點(diǎn)所需的信息，很可能該路由器會積累一張龐大的路由表。由于物理上（CPU、內(nèi)存等）的限制路由器很難有時就根本不可能處理一個龐大的路由表。因此在不影響到達(dá)每個目的地的能力的情況下，我們要使路由表最小化。例如，一個路由器通過連接到另一個路由器的一個鏈路連接到Internet，那么這個路由器可以將Internet上所有節(jié)點(diǎn)的信息都存儲，或者它也可以將所有鏈路外的非本地的信息都不存儲。也就是說路由器沒有在它的路由表中存儲任何有關(guān)數(shù)據(jù)“包”要尋找的非本地網(wǎng)絡(luò)目的地的信息，而是將這些“包”發(fā)送到鏈路另一端的路由器，由這個路由器來提供必要的信息。這種簡單的小把戲可以替路由表節(jié)省30個數(shù)量級的條目。路由信息沒有必要被過于頻繁地在路由器之間交換。通常路由表中的攪拌器給任何路由器所能提供的貧乏的內(nèi)存和CPU施加了許多不必要的壓力。信息的復(fù)制不應(yīng)該影響路由器的轉(zhuǎn)發(fā)操作。盡管沒有必要每毫秒都刷新路由表，當(dāng)然也不能每隔一個星期才刷新一次路由表。路由的一重要的目標(biāo)就是為主機(jī)提供能夠準(zhǔn)確反映當(dāng)前網(wǎng)絡(luò)狀態(tài)的一張路由表。

　　路由器最重要的操作是將接收的包發(fā)送到正確的路徑。未經(jīng)路由的包可能會導(dǎo)致數(shù)據(jù)丟失。而路由表的不一致將會導(dǎo)致路由環(huán)路并使某個數(shù)據(jù)包在兩個相鄰的界面之間被循環(huán)發(fā)送。

４．兩種路由算法

　　路由算法形式多樣，得到廣泛應(yīng)用的有兩種：距離向量算法和鏈路狀態(tài)算法。目前大多數(shù)路由協(xié)議都是基于這兩種路由算法之一。

（1） 距離向量算法（distance vector algorithm）

　　距離矢量路由協(xié)議向路由器的所有鄰居分發(fā)一張記錄形式為<目標(biāo)，開銷>的列表。這些記錄為網(wǎng)絡(luò)中的每個非本節(jié)點(diǎn)的其他節(jié)點(diǎn)賦上了開銷這個值。值得注意的是這些信息只分發(fā)給源路由器的鄰路由器。開銷的意思是從源路由器到目標(biāo)節(jié)點(diǎn)的鏈路開銷的總和。源路由器定期地刷新它的距離矢量記錄并把記錄分發(fā)給它的鄰路由器。鄰路由器將過去接收到的記錄與現(xiàn)在的比較，如果過去的開銷較小路由器將沿過去接收的距離矢量記錄所指的路徑發(fā)送輸出。

　　距離向量算法是基于下面的計算公式：

D（i，i） = 0

D（i，j） = min [d（i，k） + D（k，j）]　

　　其中，D（i，j）表示從節(jié)點(diǎn)（節(jié)點(diǎn)為網(wǎng)絡(luò)或路由器）i到節(jié)點(diǎn)j的最短路徑，d（i，k）表示從節(jié)點(diǎn)i到k的直接路徑，也就是說節(jié)點(diǎn)i和k之間沒有中介節(jié)點(diǎn)。具體運(yùn)算步驟如下：

I　所有的路由器建有一個路由表，使系統(tǒng)中的所有目的地址都出現(xiàn)在表中。每一表項內(nèi)容包括目的地址和下一站地址，記為元組（N，G）。

II　路由器周期性地向鄰居發(fā)送更新分組，更新分組的內(nèi)容為路由表中的所有信息。

III　鄰居路由器接收處理更新分組。設(shè)更新分組來自G'，根據(jù)更新分組計算到目的地址N的路由開銷為D'，如果D'應(yīng)下一站地址為G'，也就是G' =G，采用新的路由，不管D'是大或小。

（2） 鏈路狀態(tài)算法（link state algorithm）

　　一個路由器在使用鏈路狀態(tài)路由時，它將會向網(wǎng)絡(luò)上所有其它的路由器分發(fā)它到它鄰路由器的距離。這就使每個路由器不用知道從某一源節(jié)點(diǎn)到目的節(jié)點(diǎn)的開銷，該路由器就可以產(chǎn)生一張路由表。環(huán)路的問題不會出現(xiàn)，因為每個路由器都擁有整個網(wǎng)絡(luò)的拓?fù)�。主要思想是一個路由器產(chǎn)生有3個部分的記錄：源路由器（它自己）、鄰路由器和到鄰路由器的開銷。因此，如果路由器A通過一條開銷為3的鏈路連接到路由器B，并且路由器A通過一條開銷為5的鏈路連接到路由器C，那么路由器將會向網(wǎng)絡(luò)上所有的路由器廣播鏈路狀態(tài)包（LSPs）和。每個路由器將可以從接收到的LSPs中推算出一條通向目的節(jié)點(diǎn)的最短路徑。

　　鏈路狀態(tài)算法，或者稱為SPF（Shortest-Path First）算法，其思路可以分為以下4個部分來描述：

I．發(fā)現(xiàn)該路由器的鄰居，獲取它們的網(wǎng)絡(luò)地址，建立相鄰關(guān)系，并測量到每個相鄰路由器的開銷或延遲。建立相鄰關(guān)系是通過發(fā)送Hello分組來實現(xiàn)的。

II．將用于交換的信息收集起來，構(gòu)造包含這些信息的鏈路狀態(tài)分組。創(chuàng)建鏈路狀態(tài)分組的時機(jī)分兩種，一種為定期創(chuàng)建，另一種就是當(dāng)有事件發(fā)生時創(chuàng)建。

III．通過flood（洪泛擴(kuò)散）算法，向所有的其它路由器發(fā)送該分組。如何可靠地發(fā)布鏈路狀態(tài)分組在鏈路狀態(tài)路由選擇算法中占相當(dāng)大的比重，鏈路狀態(tài)算法實現(xiàn)的好壞在一定程度上取決于flood算法的優(yōu)劣。

IV．根據(jù)收集到的鏈路狀態(tài)信息，通過Dijkstra算法，計算本路由器到全網(wǎng)其它路由器或網(wǎng)絡(luò)的最短距離。

［上一頁］ ［下一頁］