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

１．IP路由簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

４．兩種路由算法

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

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

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

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

D（i，i） = 0

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

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

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

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

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

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

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

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

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

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

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

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

［上一頁］ ［下一頁］