基本介紹
算法分類,靜態算法,動態算法,協定分類,距離矢量,鏈路狀態,選擇協定,自治系統,特點,分類,路由協定,IGP,RIP,EGP,域間策略,BGP,IDRP,比較,跳限制,子網掩碼,廣播更新,層次區別,路由表,目的IP,標準域,下一跳域,標誌域,計時器域,RIP實現,啟動運行,RIP限制,OSPF,特點,計算路由,EGP,
算法分類
路由選擇算法就是路由選擇的方法或策略。
靜態算法
靜態路由選擇算法就是非自適應路由選擇算法，這是一種不測量、不利用網路狀態信息，僅僅按照某種固定規律進行決策得簡單得路由選擇算法。靜態路由選擇算法得特點是簡單和開銷小，但是不能適應網路狀態的變化。靜態路由選擇算法主要包括擴散法和固定路由表法。靜態路由是依靠手工輸入的信息來配置路由表的方法。
靜態路由具有以下幾個優點：減小了路由器的日常開銷。在小型網際網路上很容易配置。可以控制路由選擇的更新。但是，靜態路由在網路變化頻繁出現的環境中並不會很好的工作。在大型的和經常變動的網際網路，配置靜態路由是不現實。
動態算法
動態路由選擇算法就是自適應路由選擇算法，是依靠當前網路的狀態信息進行決策，從而使路由選擇結果在一定程度上適應網路拓撲結構和通信量的變化。
動態路由選擇算法的特點是能較好的適應網路狀態的變化，但是實現起來較為複雜，開銷也比較大。動態路由選擇算法一般採用路由表法，主要包括分散式路由選擇算法和集中式路由選擇算法。分散式路由選擇算法是每一個節點通過定期得與相鄰節點交換路由選擇得狀態信息來修改各自的路由表，這樣使整個網路的路由選擇經常處於一種動態變化的狀況。集中式路由選擇算法是網路中設定一個節點，專門收集各個節點定期傳送得狀態信息，然後由該節點根據網路狀態信息，動態的計算出每一個節點的路由表，再將新的路由表傳送給各個節點。
協定分類
動態路由是指路由協定可以自動根據實際情況生成的路由表的方法。動態路由的主要優點是，如果存在到目的站點的多條路徑，運行了路由選擇協定（如RIP或IGRP）之後，而正在進行數據傳輸的一條路徑發生了中斷的情況下，路由器可以自動的選擇另外一條路徑傳輸數據。這對於建立一個大型的網路是一個優點。大多數路由選擇協定可分成兩種基本路由選擇協定：
距離矢量
計算網路中鏈路的距離矢量，然後根據計算結果進行路由選擇。典型的距離向量路由選擇協定有IGRP、RIP等。路由器定期向鄰居路由器傳送訊息，訊息的內容就是自己的整個路由表，如：1、到達目的網路所經過的距離、2、到達目的網路的下一跳地址運行距離矢量的路由器會根據相鄰路由器傳送過來的信息，更改自己的路由表。
鏈路狀態
選擇協定
自治系統
由於網際網路規模龐大，為了路由選擇的方便和簡化，一般將整個網際網路劃分為許多較小的區域，稱為自治系統。每個自治系統內部採用得路由選擇協定可以不同，自治系統根據自身得情況有權決定採用哪種路由選擇協定。
特點
網際網路的路由選擇協定的特點是：
分類
內部網關協定（IGP）：在一個自治系統內部使用得路由選擇協定。具體的協定有RIP和OSPF等。外部網關協定（EGP）：兩個自治系統之間使用得路由選擇協定。目前使用最多的是BGP（即BGP-4）此處的網關指的是路由器。
路由協定
IGP
Internet網被分成多個域或多個自治系統。一個域（domain）是一組主機和使用相同路由選擇協定的路由器集合，並由單一機構管理。換言之，一個域可能是由一所大學或其它機構管理的網際網路。內部網關協定（IGP）在一個域中選擇路由。外部網關協定（EGP）為兩個相鄰的位於各自域邊界上的路由器提供一種交換訊息和信息的方法。
OSPF(OpenShortestPathFirst）是一個內部網關協定(InteriorGatewayProtocol，簡稱IGP），用於在單一自治系統（autonomous system,AS）內決策路由。與RIP相對，OSPF是鏈路狀態路由協定，而RIP是距離向量路由協定。鏈路是路由器接口的另一種說法，因此OSPF也稱為接口狀態路由協定。OSPF通過路由器之間通告網路接口的狀態來建立鏈路狀態資料庫，生成最短路徑樹，每個OSPF路由器使用這些最短路徑構造路由內部網關協定用在一個域中交換路由選擇信息，如路由選擇信息協定（RIP）和優先開放最短路徑協定（OSPF）。OSPF是與OSI的IS-IS協定十分相似的內部路由選擇協定。在區域的邊界，周邊路由器將一個域與其它域相連。這些路由器使用外部路由選擇協定（ExteriorRoutingProto-cols）交換路由選擇。外部網關協定（[[ExteriorGatewayProtocol，EGP）為位於自治域邊界的兩個相鄰的周邊路由器提供一種交換訊息和信息的方法。對於EGP的替代是周邊網關協定（BorderGatewayProtocol，BGP），它被用於提供改進性能，如指定路由選擇策略的能力。
RIP
RIP使用距離向量算法（DVA）計算路由選擇路徑。在DVA中，路由選擇的確是基於到一個目的站中最少路由中繼（hop）數或到一個相鄰路由器路徑的費用計算出來的一個總的費用。RIP路由選擇表與其它路由器大約每30秒鐘交換一次，路由器就是基於新的訊息來重新生成它們的路由選擇信息表。如果一個路由器連到低吞吐量的WAN鏈路，那么它在重新生成路由選擇表時就會落後。另外，交換路由選擇信息表要增加網路額外開銷，它會引起許多擁塞，進一步推遲路由選擇表的更新。如果一條路由失敗了，重新建立路由選擇表所需的延遲將會推遲一條新的路由儘快地建立。
優先開放最短路徑（OSPF）：OSPF是一個鏈路狀態路由選擇算法，它是由開放系統互連（OSI）中間系統對中間系統（IS-IS）域內路由選擇協定所做的工作派生出來的。鏈路狀態路由選擇與距離向量路由選擇相比，需要更強的處理能力，但提供更多路由選擇處理控制和更快的變化回響，Dijkstra算法用於計算路由是基於分組必須跳躍（hop）過的路由器數、傳輸線路的速度、交通擁塞延遲和根據某種度量的路由器費用。OSPF路由選擇表只在必要時更新和僅更新有效（變化）的信息。
EGP
外部網關協定（EGP）提供一種方法，為兩個位於它們各自域邊界的相鄰路由器交換信息和訊息。外部網關協定還提供一種方法，為路由器相互交換路由選擇信息。每一個域有一個或多個路由器被選作EGP協定路由器。每一個EGP使用內部網關協定和同一域內部的網關交換路由選擇信息，以便它知道局域內端系統（主機）的地址。EGP與其它域內的EGP相連和交換有關各自域內端系統的路由選擇信息。有了這些信息，網關就知道傳送信息到域外其它系統的最佳路徑。
EGP的主要功能如下：執行相鄰網關連線過程使兩個外部網關相連和決定交換信息。通過傳送一條訊息周期性地核實相鄰的路由器和等待一個回響，這將確保一個外部網關仍可採用。周期性地交換路由選擇信息。路由器的EGP例行程式能夠輪詢相鄰的路由器以獲得更新的信息。通常要維持兩張表，用內部協定如RIP和OSPF獲得一張內部路由表，用EGP獲得一張外部路由表。然而，EGP有下述周邊網關協定（BGP）試圖解決的缺點。EGP是在Internet組成單個主幹網時設計的，它對於今天的多主幹網不是有效的。路由器是用顯式定義那些路由器能夠連線的靜態路由選擇表設定的，這避免環路和提供安全性，但不支持一個可擴展的網路。
域間策略
幾個新的域間路由選擇協定被推薦在Internet網上使用。隨著Internet網規模的擴大，現行的外部協定不能提供足夠的擴展能力。實現基於策略路由選擇的新協定比EGP更具有可擴展性（Internet的要求）。基於策略路由選擇給管理員更多的網路控制、允許最佳化交通流量和實現安全特性以及服務收費。
BGP
周邊網關協定（BorderGatewayProtocol，BGP）作為一種中間解決方法提供了一些有限的策略特性，但它沒有解決可擴展的需求。路由器屬性如一條路徑的費用和安全性也被加入BGP。由於BGP的路由選擇信息交換隻傳送增加的部分而不是整個資料庫，所以它所需的頻寬降低了。
IDRP
域間路由選擇協定（Inter Domain Routing Protocol，IDRP）是一個類似於In-ternet周邊網關協定（BGP）的基於策略路由選擇協定。策略路由選擇提供了以預定方式路由傳輸的方法，它是一種距離向量路由選擇協定，其中的每一種路由器為一個分組通過網路定義了一條路徑。注意，IDRP是一個基於OSI的協定。
域間策略路由選擇（IDPR）：域間策略路由選擇（Inter domain Policy Routing，IDPR）是一個在域間實現源路由選擇和基於策略的路由選擇的鏈路狀態路由選擇協定。源路由選擇由於分組本身保持路徑信息而提供一些有用的增強特性。這對於初始發現路徑是很必要的，但後繼的分組只是簡單地把路徑放入自己的頭部。
比較
RIP協定是一種傳統的路由協定，適合比較小型的網路，但是當前Internet網路的迅速發展和急劇膨脹使RIP協定無法適應今天的網路。OSPF協定則是在Internet網路急劇膨脹的時候制定出來的，它克服了RIP協定的許多缺陷。
跳限制
子網掩碼
OSPF協定支持可變長度子網掩碼（VLSM），RIP則不支持，這使得RIP協定對當前IP位址的缺乏和可變長度子網掩碼的靈活性缺少支持。
廣播更新
RIP協定不是針對網路的實際情況而是定期地廣播路由表，這對網路的頻寬資源是個極大的浪費，特別對大型的廣域網。OSPF協定的路由廣播更新只發生在路由狀態變化的時候，採用IP多路廣播來傳送鏈路狀態更新信息，這樣對頻寬是個節約。
層次區別
RIP網路是一個平面網路，對網路沒有分層。OSPF在網路中建立起層次概念，在自治域中可以劃分網路域，使路由的廣播限制在一定的範圍內，避免鏈路中繼資源的浪費。5、OSPF在路由廣播時採用了授權機制，保證了網路安全。上述兩者的差異顯示了OSPF協定後來居上的特點，其先進性和複雜性使它適應了今天日趨龐大的Internet網，並成為主要的網際網路路由協定。
路由表
使用RIP報文中列出的項，RIP主機可以彼此之間交流路由信息。這些信息存儲在路由表中，路由表為每一個知道的、可達的目的地保留一項。每個目的地表項是到達那個目的地的最低開銷路由。注意每個目的地的表項數可以隨路由生產商的不同而變化。生產商可能選擇遵守規範，也可以對標準進行他們認為合適的“強化”。所以，用戶很可能會發現某個特殊商標的路由器為每一個網路中的目的地存儲至多4條相同費用的路由。注意雖然RFC1058是一個開放式標準，能支持大量互連網路地址結構，然而它是由IETF設計用於INTERENT中自治系統內的協定。如此，使用這種形式RIP的自然是網路互聯協定。每個路由表項包括以下各域：目的IP位址域、距離-向量度量域、下一跳IP位址域、路由變化標誌域、路由計時器域。
目的IP
標準域
下一跳域
下一跳IP位址域包括至目的地的網路路徑上下一個路由器接口的IP位址。如果目的IP位址所在的網路與路由器不直接相連時，路由器表中才出現此項。
標誌域
路由變化標誌域用於指出至目的IP位址的路由是否發生了變化。這個域是重要的，因為RIP為每一個目的IP位址只記錄一條路由。
計時器域
RIP實現
RIP根據V-D算法的特點，將協定的參加者分為主動機和被動機兩種。主動機主動向外廣播路由刷新報文，被動機被動地接收路由刷新報文。一般情況下，主機作為被動機，路由器則既是主動機又是被動機，即在向外廣播路由刷新報文的同時，接受來自其它主動機的V-D報文，並進行路由刷新。RIP規定，路由器每30秒向外廣播一個V-D報文，報文信息來自本地路由表。RIP的V-D報文中，其距離以驛站計：與信宿網路直接相連的路由器規定為一個驛站，相隔一個路由器則為兩個驛站……以此類推。一條路由的距離為該路由（從信源機到信宿機）上的路由器數。為防止尋徑環長期存在，RIP規定，長度為16的路由為無限長路由，即不存在的路由。所以一條有效的路由長度不得超過15。正是這一規定限制了RIP的使用範圍，使RIP局限於中小型的網路網點中。為了保證路由的及時有效性，RIP採用觸發刷新技術和水平分割法。當本地路由表發生修改時，觸發廣播路由刷新報文，以迅速達到最新路由的廣播和全局路由的有效。水平分割法是指當路由器從某個網路接口傳送RIP路由刷新報文時，其中不包含從該接口獲取的路由信息。這是由於從某網路接口獲取的路由信息對於該接口來說是無用信息，同時也解決了兩路由器間的慢收斂問題。
對於區域網路的路由，RIP規定了路由的逾時處理。主要是考慮到這樣一個情況，如果完全根據V-D算法，一條路由被刷新是因為出現一條路由開銷更小的路由，否則路由會在路由表中一直保存下去，即使該路由崩潰。這勢必造成一定的錯誤路由信息。為此，RIP規定，所有機器對其尋徑表中的每一條路由都設定一個時鐘，每增加一條新路由，相應設定一個新時鐘。在收到的V-D報文中假如有關於此路由的表目，則將時鐘清零，重新計時。假如在180秒內一直未收到該路由的刷新信息，則認為該路由崩潰，將其距離設為16，廣播該路由信息。如果再過60秒後仍未收到該路由的刷新信息，則將它從路由表中刪除。如果某路由在距離被設為16後，在被刪除前路由被刷新，亦將時鐘清零，重新計時，同時廣播被刷新的路由信息。至於路由被刪除後是否有新的路由來代替被刪除路由，取決於去往原路由所指信宿有無其它路由。假如有，相應路由器會廣播之。機器一旦收到其它路由的信息，自然會利用V-D算法建立一條新路由。否則，去往原信宿的路由不再存在。
啟動運行
整個過程如下所描述：某路由器剛啟動RIP時，以廣播的形式向相鄰路由器傳送請求報文，相鄰路由器的RIP收到請求報文後，回響請求，回發包含本地路由表信息的回響報文。RIP收到回響報文後，修改本地路由表的信息，同時以觸發修改的形式向相鄰路由器廣播本地路由修改信息。相鄰路由器收到觸發修改報文後，又向其各自的相鄰路由器傳送觸發修改報文。在一連串的觸發修改廣播後，各路由器的路由都得到修改並保持最新信息。同時，RIP每30秒向相鄰路由器廣播本地路由表，各相鄰路由器的RIP在收到路由報文後，對本地路由進行的維護，在眾多路由中選擇一條最佳路由，並向各自的相鄰網廣播路由修改信息，使路由達到全局的有效。同時RIP採取一種逾時機制對過時的路由進行逾時處理，以保證路由的實時性和有效性。RIP作為內部路由器協定，正是通過這種報文交換的方式，提供路由器了解本自治系統內部個網路路由信息的機制。
RIP-2支持版本1和版本2兩種版本的報文格式。在版本2中，RIP還提供了對子網的支持和提供認證報文形式。版本2的報文提供子網掩碼域，來提供對子網的支持；另外，當報文中的路由項地址域值為0xFFFF時，默認該路由項的剩餘部分為認證。RIP2對撥號網的支持則是參考需求RIP和觸發RIP的形式經修改而加入的新功能。這時，我們只是要求在撥號網撥通之後對路由進行30秒一次的廣播，而在沒撥通時並不作如是要求，這是根據具體情況變通的結果。
RIP限制
雖然RIP有很長的歷史，但它還是有自身的限制。它非常適合於為早期的網路互聯計算路由；然而，技術進步已極大地改變了網際網路。建造和使用的方式。因此，RIP會很快被今天的網際網路所淘汰。RIP的一些最大限制是：
·不能支持長於15跳的路徑。
·依賴於固定的度量來計算路由。
·對路由更新反應強烈。
·相對慢的收斂。
·缺乏動態負均衡支持。
OSPF
特點
RouterID：一個32bit的無符號整數，是一台路由器的唯一標識，在整個自治系統內唯一。協定號：OSPF的協定號是89.OSPF協定報文不轉發：通常OSPF的協定報文是不被轉發的，只能傳遞一跳，即在IP報文頭中TTL值被設為1。（虛連線除外）OSPF協定OpenShortestPathFirst，目前IGP中套用最廣、性能能最優的一個協定具有如下特點：
1、可適應大規模網路
2、路由變化收斂速度快
3、無路由自環
4、支持變長子網掩碼VLSM
5、支持等值路由
6、支持區域劃分
7、提供路由分級管理
8、支持驗證
計算路由
OSPF雖然很複雜，卻使用下面兩種相當簡單的方法之一計算路由耗費：
OSPF是功能最強大、特點最豐富的開放式路由協定之一。它的複雜性也是其弱點來源，因為設計、建造和操作一個OSPF網際網路需要比使用幾乎每一種其他路由協定更多的專業知識和精力。採用路由耗費的預設值可以極大地簡化OSPF網路設計。隨著關於OSPF及網路操作特點知識的增加，用戶能夠慢慢地通過控制OSPF變數來最佳化網路性能。必須小心地設計區和網路拓撲。做得好，OSPF會使網路用戶得到優異的性能和快速的收斂速度。BGP用於特大型網路如INTERNET的核心。
EGP
兩個交換選路信息的路由器若分屬兩個自治系統，則被稱為外部鄰站（exteriorneighbors），但它們若同屬一個自治系統，則稱為內部鄰站（interiorneighbors）。外部鄰站使用的向其他自治系統通告可達信息的協定被稱為外部網關協定EGP（ExteriorGatewayProtocol），使用該協定的路由器被稱為外部路由器（exteriorrouter）。在Internet網中，EGP顯得尤為重要，因為與之相連的自治系統使用它向核心繫統通告可達信息。EGP有三大功能。第一個是它支持鄰居獲取（neighboracquisition）機制，即允許一個路由器請求另一個路由器同意交換可達信息。我們可以說，一個路由器獲得了（acquire）一個EGP對等路由器（EGPpeer）或一個EGP鄰站（EGPneighbor）。EGP對等路由器僅在交換選路信息的意義上來說是鄰站，而不論其地理位置是否鄰近。第二，路由器持續地測試其EGP鄰站是否能夠回響。第三，EGP鄰站周期性地傳送選路更新報文（routingupdatemessage）來交換網路可達信息。
外部網關協定用於在非核心的相鄰網關之間傳輸信息。非核心網關包含網際網路上所有與其直接相鄰的網關的路由信息及其所連機器信息，但是它們不包含Internet上其他網關的信息。對絕大多數EGP而言，只限制維護其服務的區域網路或廣域網信息。這樣可以防止過多的路由信息在區域網路或廣域網之間傳輸。EGP強制在非核心網關之間交流路由信息。
由於核心網關使用GGP，非核心網關使用EGP，而二者都套用在Internet上，所以必須有某些方法使二者彼此之間能夠通信。Internet使任何自治（非核心）網關給其他系統傳送“可達”信息，這些信息至少要送到一個核心網關。假如有一個更大的自治網路，經常認為有一個網關來處理這些可達信息。和GGP一樣，EGP使用一個查詢過程來讓網關清楚它的相鄰網關並不斷地與其相鄰者交換路由和狀態信息。EGP是狀態驅動的協定，意思是說它依靠於一個反映網關情況的狀態表和一組當狀態表項變化時必須執行的一組操作。
EGP報文首部：為了實現上述三個基本功能，EGP定義了下表所列的九種報文類型：
EGP報文類型 描述
AcquisitionRequest（獲取請求）請求路由器成為鄰站（對等路由器）
AcquisitionConfirm（獲取證實）對獲取請求的肯定回響
AcquisitionRefuse（獲取拒絕）對獲取請求的否定回響
CeaseRequest（中止請求）請求中止鄰站關係
CeaseConfirm（中止證實）對中止請求的證實回響
Hello（你好）請求鄰站回答是否活躍
IHeardYou（我聽見你）對Hello報文的回答
PollRequest（輪詢請求）請求更新網路的選路
RoutingUpdate（選路更新）網路可達信息
Error（差錯）對不正確報文的回響
所有的EGP報文都有固定的首都用於說明報文類型。
首部中的版本（VERSION）欄位取整數值，指出該報文使用的EGP的版本號。接收方檢測版本號以確認雙方使用相同版本的協定。類型（TYPE）欄位指出報文的類型，而代碼（CODE）欄位給出了子類型。狀態（STATUS）欄位包含了與本報文有關的狀態信息。EGP使用校驗和欄位來確認報文的正確到達。其算法與IP的校驗和算法相同。它把整個EGP報文當做16比特整數的序列，使用各個整數的二進制反碼和的二進制反碼作為校驗和。計算校驗和之前把校驗和（CHECKSUM）欄位初始化為零，通過填充0來把報文長度變為16比特的整數倍。自治系統號（AUTONOMOUSSYSTEMNUM）欄位給出了表示傳送該報文的路由器所在的自治系統的編號，而序號（SEQUENCENUMBER）用於收發雙方進行聯繫。路由器請求鄰站時賦一個初始序號，以後每次傳送報文時將序號增加。鄰站回送收到的序號值，傳送方便用這個回送值與傳送時的值作一比較來確保報文的正確性。
