路由技術

路由選擇算法就是路由選擇的方法或策略。

按照路由選擇算法能否隨網絡的拓撲結構或者通信量自適應地進行調整變化進行分類，路由選擇算法可以分為靜態路由選擇算法和動態路由選擇算法。

靜態路由選擇算法就是非自適應路由選擇算法，這是一種不測量、不利用網絡狀態信息，僅僅按照某種固定規律進行決策得簡單得路由選擇算法。靜態路由選擇算法得特點是簡單和開銷小，但是不能適應網絡狀態的變化。靜態路由選擇算法主要包括擴散法和固定路由表法。靜態路由是依靠手工輸入的信息來配置路由表的方法。

靜態路由具有以下幾個優點：減小了路由器的日常開銷。在小型互聯網上很容易配置。可以控制路由選擇的更新。但是，靜態路由在網絡變化頻繁出現的環境中並不會很好的工作。在大型的和經常變動的互聯網，配置靜態路由是不現實。

動態路由選擇算法就是自適應路由選擇算法，是依靠當前網絡的狀態信息進行決策，從而使路由選擇結果在一定程度上適應網絡拓撲結構和通信量的變化。

動態路由選擇算法的特點是能較好的適應網絡狀態的變化，但是實現起來較為複雜，開銷也比較大。動態路由選擇算法一般採用路由表法，主要包括分佈式路由選擇算法和集中式路由選擇算法。分佈式路由選擇算法是每一個節點通過定期得與相鄰節點交換路由選擇得狀態信息來修改各自的路由表，這樣使整個網絡的路由選擇經常處於一種動態變化的狀況。集中式路由選擇算法是網絡中設置一個節點，專門收集各個節點定期發送得狀態信息，然後由該節點根據網絡狀態信息，動態的計算出每一個節點的路由表，再將新的路由表發送給各個節點。

動態路由是指路由協議可以自動根據實際情況生成的路由表的方法。動態路由的主要優點是，如果存在到目的站點的多條路徑，運行了路由選擇協議（如RIP或IGRP）之後，而正在進行數據傳輸的一條路徑發生了中斷的情況下，路由器可以自動的選擇另外一條路徑傳輸數據。這對於建立一個大型的網絡是一個優點。大多數路由選擇協議可分成兩種基本路由選擇協議：

計算網絡中鏈路的距離矢量，然後根據計算結果進行路由選擇。典型的距離向量路由選擇協議有IGRP、RIP等。路由器定期向鄰居路由器發送消息，消息的內容就是自己的整個路由表，如：1、到達目的網絡所經過的距離、2、到達目的網絡的下一跳地址運行距離矢量的路由器會根據相鄰路由器發送過來的信息，更改自己的路由表。

典型的鏈路狀態路由選擇協議有OSPF等。鏈路狀態路由選擇協議的目的是得到整個網絡的拓撲結構。運行鏈路狀態路由協議的每個路由器都要提供鏈路狀態的拓撲結構信息，信息的內容包括：1、路由器所連接的網段鏈路。2、以及該鏈路的物理狀態。根據返回的信息，路由器根據網絡拓撲結構的變化及時修改路由配置，以適應新的路由選擇。

由於因特網規模龐大，為了路由選擇的方便和簡化，一般將整個因特網劃分為許多較小的區域，稱為自治系統。每個自治系統內部採用得路由選擇協議可以不同，自治系統根據自身得情況有權決定採用哪種路由選擇協議。

因特網的路由選擇協議的特點是：

屬於自適應的選擇協議（即動態的）；是分佈式路由選擇協議；因特網採用分層次的路由選擇協議，即分自治系統內部和自治系統外部路由選擇協議。

內部網關協議（IGP）：在一個自治系統內部使用得路由選擇協議。具體的協議有RIP和OSPF等。外部網關協議（EGP）：兩個自治系統之間使用得路由選擇協議。使用最多的是BGP（即BGP-4）此處的網關指的是路由器。

IGP（內部網關協議）是在一個自治網絡內網關（主機和路由器）間交換路由信息的協議。路由信息能用於網間協議（IP）或者其它網絡協議來説明路由傳送是如何進行的。

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）交換路由選擇。外部網關協議（[Exterior Gateway Protocol]，EGP）為位於自治域邊界的兩個相鄰的周邊路由器提供一種交換消息和信息的方法。對於EGP的替代是周邊網關協議（BorderGatewayProtocol，BGP），它被用於提供改進性能，如指定路由選擇策略的能力。

內部網關協議用於域內交換路由選擇信息。常用的路由選擇協議：地址解析協議（ARP）：ARP用於Internet和TCP/IP網，是一種鄰居發現協議，它與OSI端系統對中間系統（ES-IS）協議相似。路由器和主機（用户計算機、服務器等）都使用ARP來相互通告。路由器把包含一個IP地址的分組廣播出去。網絡上有這個IP地址的計算機或設備回送自己的LAN地址。這些地址被存入路由選擇表中，以備將來使用。另一個與ARR相似的協議，稱為逆ARP（RARP），執行相反的任務，它根據已知的網絡地址獲得IP地址。

RIP使用距離向量算法（DVA）計算路由選擇路徑。在DVA中，路由選擇的確是基於到一個目的站中最少路由中繼（hop）數或到一個相鄰路由器路徑的費用計算出來的一個總的費用。RIP路由選擇表與其它路由器大約每30秒鐘交換一次，路由器就是基於新的消息來重新生成它們的路由選擇信息表。如果一個路由器連到低吞吐量的WAN鏈路，那麼它在重新生成路由選擇表時就會落後。另外，交換路由選擇信息表要增加網絡額外開銷，它會引起許多擁塞，進一步推遲路由選擇表的更新。如果一條路由失敗了，重新建立路由選擇表所需的延遲將會推遲一條新的路由儘快地建立。

優先開放最短路徑（OSPF）：OSPF是一個鏈路狀態路由選擇算法，它是由開放系統互連（OSI）中間系統對中間系統（IS-IS）域內路由選擇協議所做的工作派生出來的。鏈路狀態路由選擇與距離向量路由選擇相比，需要更強的處理能力，但提供更多路由選擇處理控制和更快的變化響應，Dijkstra算法用於計算路由是基於分組必須跳躍（hop）過的路由器數、傳輸線路的速度、交通擁塞延遲和根據某種度量的路由器費用。OSPF路由選擇表只在必要時更新和僅更新有效（變化）的信息。

外部網關協議（EGP）提供一種方法，為兩個位於它們各自域邊界的相鄰路由器交換信息和消息。外部網關協議還提供一種方法，為路由器相互交換路由選擇信息。每一個域有一個或多個路由器被選作EGP協議路由器。每一個EGP使用內部網關協議和同一域內部的網關交換路由選擇信息，以便它知道局域內端系統（主機）的地址。EGP與其它域內的EGP相連和交換有關各自域內端系統的路由選擇信息。有了這些信息，網關就知道發送信息到域外其它系統的最佳路徑。

EGP的主要功能如下：執行相鄰網關連接過程使兩個外部網關相連和決定交換信息。通過發送一條消息週期性地核實相鄰的路由器和等待一個響應，這將確保一個外部網關仍可採用。週期性地交換路由選擇信息。路由器的EGP例行程序能夠輪詢相鄰的路由器以獲得更新的信息。通常要維持兩張表，用內部協議如RIP和OSPF獲得一張內部路由表，用EGP獲得一張外部路由表。然而，EGP有下述周邊網關協議（BGP）試圖解決的缺點。EGP是在Internet組成單個主幹網時設計的，它對於多主幹網不是有效的。路由器是用顯式定義那些路由器能夠連接的靜態路由選擇表設置的，這避免環路和提供安全性，但不支持一個可擴展的網絡。

幾個新的域間路由選擇協議被推薦在Internet網上使用。隨着Internet網規模的擴大，現行的外部協議不能提供足夠的擴展能力。實現基於策略路由選擇的新協議比EGP更具有可擴展性（Internet的要求）。基於策略路由選擇給管理員更多的網絡控制、允許優化交通流量和實現安全特性以及服務收費。

周邊網關協議（BorderGatewayProtocol，BGP）作為一種中間解決方法提供了一些有限的策略特性，但它沒有解決可擴展的需求。路由器屬性如一條路徑的費用和安全性也被加入BGP。由於BGP的路由選擇信息交換隻傳送增加的部分而不是整個數據庫，所以它所需的帶寬降低了。

域間路由選擇協議（Inter Domain Routing Protocol，IDRP）是一個類似於In-ternet周邊網關協議（BGP）的基於策略路由選擇協議。策略路由選擇提供了以預定方式路由傳輸的方法，它是一種距離向量路由選擇協議，其中的每一種路由器為一個分組通過網絡定義了一條路徑。注意，IDRP是一個基於OSI的協議。

域間策略路由選擇（IDPR）：域間策略路由選擇（Inter domain Policy Routing，IDPR）是一個在域間實現源路由選擇和基於策略的路由選擇的鏈路狀態路由選擇協議。源路由選擇由於分組本身保持路徑信息而提供一些有用的增強特性。這對於初始發現路徑是很必要的，但後繼的分組只是簡單地把路徑放入自己的頭部。

RIP協議是一種傳統的路由協議，適合比較小型的網絡，但是當前Internet網絡的迅速發展和急劇膨脹使RIP協議無法適應當今的網絡。OSPF協議則是在Internet網絡急劇膨脹的時候制定出來的，它克服了RIP協議的許多缺陷。

RIP協議一條路由有15跳（網關或路由器）的限制，如果一個RIP網絡路由跨越超過15跳（路由器），則它認為網絡不可到達，而OSPF對跨越路由器的個數沒有限制。

OSPF協議支持可變長度子網掩碼（VLSM），RIP則不支持，這使得RIP協議對當前IP地址的缺乏和可變長度子網掩碼的靈活性缺少支持。

RIP協議不是針對網絡的實際情況而是定期地廣播路由表，這對網絡的帶寬資源是個極大的浪費，特別對大型的廣域網。OSPF協議的路由廣播更新只發生在路由狀態變化的時候，採用IP多路廣播來發送鏈路狀態更新信息，這樣對帶寬是個節約。

RIP網絡是一個平面網絡，對網絡沒有分層。OSPF在網絡中建立起層次概念，在自治域中可以劃分網絡域，使路由的廣播限制在一定的範圍內，避免鏈路中繼資源的浪費。5、OSPF在路由廣播時採用了授權機制，保證了網絡安全。上述兩者的差異顯示了OSPF協議後來居上的特點，其先進性和複雜性使它適應了日趨龐大的Internet網，併成為主要的互聯網路由協議。

使用RIP報文中列出的項，RIP主機可以彼此之間交流路由信息。這些信息存儲在路由表中，路由表為每一個知道的、可達的目的地保留一項。每個目的地表項是到達那個目的地的最低開銷路由。注意每個目的地的表項數可以隨路由生產商的不同而變化。生產商可能選擇遵守規範，也可以對標準進行他們認為合適的“強化”。所以，用户很可能會發現某個特殊商標的路由器為每一個網絡中的目的地存儲至多4條相同費用的路由。注意雖然RFC1058是一個開放式標準，能支持大量互連網絡地址結構，然而它是由IETF設計用於INTERENT中自治系統內的協議。如此，使用這種形式RIP的自然是網絡互聯協議。每個路由表項包括以下各域：目的IP地址域、距離-向量度量域、下一跳IP地址域、路由變化標誌域、路由計時器域。

任何路由表中所包含的最重要信息是到所知目的地的IP地址。一旦一台RIP路由器收到一個數據報文，就會查找路由表中的目的IP地址以決定從哪裏轉發那個報文。

路由表中的度量域指出報文從起始點到特定目的地的總耗費。路由表中的度量是從路由器到特定目的地之間網絡鏈路的耗費總和。

下一跳IP地址域包括至目的地的網絡路徑上下一個路由器接口的IP地址。如果目的IP地址所在的網絡與路由器不直接相連時，路由器表中才出現此項。

路由變化標誌域用於指出至目的IP地址的路由是否發生了變化。這個域是重要的，因為RIP為每一個目的IP地址只記錄一條路由。

有兩個計時器與每條路由相聯繫，一個是超時計時器，一個是路由刷新計時器。這些計時器一同工作來維護路由表中存儲的每條路由的有效性。

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的一些最大限制是：

·不能支持長於15跳的路徑。

·依賴於固定的度量來計算路由。

·對路由更新反應強烈。

·相對慢的收斂。

·缺乏動態負均衡支持。

RouterID：一個32bit的無符號整數，是一台路由器的唯一標識，在整個自治系統內唯一。協議號：OSPF的協議號是89.OSPF協議報文不轉發：通常OSPF的協議報文是不被轉發的，只能傳遞一跳，即在IP報文頭中TTL值被設為1。（虛連接除外）OSPF協議OpenShortestPathFirst，IGP中應用最廣、性能能最優的一個協議具有如下特點：

1、可適應大規模網絡

2、路由變化收斂速度快

3、無路由自環

4、支持變長子網掩碼VLSM

5、支持等值路由

6、支持區域劃分

7、提供路由分級管理

8、支持驗證

9、支持以組播地址發送協議報文。

OSPF雖然很複雜，卻使用下面兩種相當簡單的方法之一計算路由耗費：

1、非帶寬敏感的缺省值可以用於每一個OSPF接口。

2、OSPF能自動計算使用每個路由接口的耗費。不管使用哪種方法，任何一條路由的耗費可以通過把路由上遇到的每個路由器接口耗費加起來得到。在OSPF的最短路徑樹中記錄了每一個已知目的地的和耗費。

OSPF是功能最強大、特點最豐富的開放式路由協議之一。它的複雜性也是其弱點來源，因為設計、建造和操作一個OSPF互聯網絡需要比使用幾乎每一種其他路由協議更多的專業知識和精力。採用路由耗費的缺省值可以極大地簡化OSPF網絡設計。隨着關於OSPF及網絡操作特點知識的增加，用户能夠慢慢地通過控制OSPF變量來優化網絡性能。必須小心地設計區和網絡拓撲。做得好，OSPF會使網絡用户得到優異的性能和快速的收斂速度。BGP用於特大型網絡如INTERNET的核心。

兩個交換選路信息的路由器若分屬兩個自治系統，則被稱為外部鄰站（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）用於收發雙方進行聯繫。路由器請求鄰站時賦一個初始序號，以後每次發送報文時將序號增加。鄰站回送收到的序號值，發送方便用這個回送值與發送時的值作一比較來確保報文的正確性。