網海茫茫路何方

１．IP路由簡介

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

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

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

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

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

發送到該路由器的缺省網關地址。

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

２．路由表和路由協議

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

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

３．路由協議的“理想”

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

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

４．兩種路由算法

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

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

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

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

D（i，i） = 0

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

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

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

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

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

（2） 鏈路狀態算法（link state algorithm）

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

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

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

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

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

IV．根據收集到的鏈路狀態信息，通過Dijkstra算法，計算本路由器到全網其它路由器或網絡的最短距離。

［上一頁］ ［下一頁］