路由交換協定

路由系統將整個網際網路劃分為許多個自治系統的集合，每個自治系統由一個16bit的號碼來表示。自治系統在域邊界之內運行局部路由協定或內部網關協定(IGP，Interior Gateway Protocol)，例如RIP、IGRP、EIGRP、OSPF等，以維持一個一致的網路拓撲結構視圖；而在域邊界之間則通過執行一種稱為邊界網路協定(BGP，Border Gateway Protocol)的外部網關協定(EGP，Exterior Gateway Protocol)來構成一個全局的連通域，如圖1所示。

圖1網際網路路由結構

基本介紹

• 中文名：路由交換協定

路由算法

路由協定按路由算法一般劃分為距離向量協定和鏈路狀態協定兩類。距離向量協定，也稱為Bellman-Ford算法，是指使用中繼計數表示源節點到目的節點的距離，它基於下面的計算公式來計算兩個節點間距離：

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之間沒有中介節點。具體運算步驟如下：

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

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

③鄰居路由器接收處理更新分組。設更新分組來自G'，根據更新分組計算到目的地址N的路由開銷為D'，如果D'<D，則採用新的路由(N，G')。如果當前路由表中存放的相應的下一站地址為G'，即G'=G，則採用新的路由，不管D'是大還是小。

距離向量協定的優點是內部保存狀態少，網路負擔輕；缺點是用中繼計數表示距離不準確，不能反映鏈路的真實狀態；收斂速度緩慢，如一條鏈路中斷後，需要經過相當長時間才被發現。

鏈路狀態協定，也稱最短路徑算法，其計算原理可以分為以下4個過程來描述：

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

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

③通過flood(擴散)算法，向所有的其他路由器傳送該訊息。在鏈路狀態路由選擇算法中，如何可靠地發布鏈路狀態訊息包是相當重要的。鏈路狀態算法實現的好壞在一定程度上取決於flood算法的優劣。

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

鏈路狀態協定與距離向量協定相比，其優點是基於量度值(如鏈路頻寬和時延)，而不是由中繼計數來選擇最佳化路由，因此可使網路負載平衡；通過鏈路狀態更新，將鏈路和節點狀態的變化情況擴散到整個網路，使所有路由器馬上更新路由表，使網路具有更好的收斂特性。

內部網關協定

RIP

RIP(RoutingInformationProtocol)是一種距離向量協定，是當今套用最為廣泛的內部網關協定。在默認情況下，RIP使用一種非常簡單的度量制度：距離就是通往目的站點所需經過的鏈路數，取值為1～15，數值16表示無窮大。RIP進程使用UDP的520連線埠來傳送和接收RIP分組。RIP分組每隔30s以廣播的形式傳送一次，為了防止出現“廣播風暴”，其後續的分組將做隨機延遲後再傳送。在RIP中，如果一個路由在180s內未被刷新，則相應的距離就被設定成無窮大，並從路由表中刪除該表項。RIP分組分為兩種：請求分組和回響分組。

由於RIP1存在一些缺陷，因此RIP2試圖定義一套有效的RIP改進方案，例如子網路由選擇、支持無類型域間路由(CIDR，ClasslessInter-DomainRouting)、驗證機制和多點廣播等，並且還定義了過渡策略。但RIP2是一個兼容性的升級，也就繼承了RIP1的大部分缺點。

OSPF

為了解決RIP協定的缺陷，IETF於1998年4月在RFC2328中發布了OSPF協定的第二版(OSPFv2)。OSPF(OpenShortest-PathFirst)全稱為開放式最短路徑優先協定，OSPF中的O意味著OSPF標準是對公共開放的，而不是封閉的專有路由方案。

OSPF採用鏈路狀態協定算法，每個路由器維護一個相同的鏈路狀態資料庫，保存整個AS的拓撲結構(在自治系統不再劃分的情況下)。一旦每個路由器都有了完整的鏈路狀態資料庫之後，該路由器就可以自己為根構造最短路徑樹，然後再根據最短路徑構造路由表。對於大型的網路，為了進一步減少路由協定通信流量，利於管理和計算，OSPF將整個自治系統劃分為若干個區域，區域內的路由器維護一個相同的鏈路狀態資料庫，保存該區域的拓撲結構。OSPF路由器相互間交換信息，但它們交換的信息不是路由，而是鏈路狀態。OSPF定義了5種分組：Hello分組用於建立和維護連線；資料庫描述分組用於初始化路由器的網路拓撲資料庫，當發現資料庫中的某部分信息已經過時時，路由器傳送鏈路狀態請求分組，請求相鄰節點提供更新信息；路由器使用鏈路狀態更新分組來主動擴散自己的鏈路狀態資料庫或對鏈路狀態請求分組進行回響；由於OSPF直接運行在IP層，協定本身要提供確認機制，鏈路狀態應答分組是對鏈路狀態更新分組的確認。

與其他協定相比，OSPF有許多優點。例如，OSPF支持各種不同鑑別機制(如簡單口令驗證、MD5加密驗證等)，並且允許各個系統或區域採用互不相同的鑑別機制；提供負載均衡功能，如果計算到某個目的站有若干條費用相同的路由，OSPF路由器則會把通信流量均勻地分配給這幾條路由，沿這幾條路由把該分組傳送出去；在一個自治系統內可劃分出若干個區域，每個區域根據自己的拓撲結構計算最短路徑，可以減少OSPF路由實現的工作量；OSPF屬動態的自適應協定，對於網路的拓撲結構變化可以迅速地做出反應，並進行相應調整，提供短的收斂期，使路由表儘快穩定，並且與其他路由協定相比，OSPF在對網路拓撲變化的處理過程中僅需要最少的通信流量；OSPF提供點到多點的接口，支持CIDR地址。

OSPF的不足之處就是協定本身龐大複雜，實現起來較RIP困難。

IS-IS協定

和OSPF一樣，IS-IS也包含一些子協定。其中，Hello協定用來發現鄰機，在廣播鏈路上選舉指派路由器；擴散協定用來在區域或主幹中傳播鏈路狀態記錄。

IGRP

由於RIP的局限性，Cisco公司在20世紀80年代中期開發了IGRP(InteriorGatewayRoutingProtocol)，它是一個距離向量家族的路由協定。IGRP使用組合度量制式，其路由更新的每一項都包含了一組4種度量制式：延遲(D)、頻寬(B)、可靠性(R)和負載(L)。此外，它還包括2個不參與路徑計算的變數：路由中的跳數(H)和路徑MTU的計算結果。

IGRP的更新傳送間隔更長(90s)，使用組合度量制式，可選擇多路徑路由、環路檢測和處理默認路由的新手段。IGRP最大的缺點是它為Cisco私有，故僅局限於Cisco產品，而RIP是任何平台上IP路由的一部分。

EIGRP

IGRP存在的缺點是它的環路檢測會持續較長時間，且路由更新的周期性傳送也會造成同樣效應。因此Cisco公司還開發了EIGRP(EnhancedlnteriorGatewayRoutingProtocol)。EIGRP仍是一個距離向量協定，使用了與IGRP相同的組合度量制式，除此之外就沒什麼相似之處了。EIGRP使用了擴散計算系統，保持快速收斂、避免環路產生。EIGRP比傳統的距離向量協定使用更少的頻寬。這使它適用於低頻寬、高費用WAN鏈路。最重要的是，EIGRP不僅可用於IP，而且還可用於IPX和AppleTalk。

外部網關協定

早期的網際網路最初採用一種外部網關協定(EGP，ExteriorGatewayProtocol)的。EGP是為一個簡單的樹形拓撲結構設計的。隨著網際網路的迅速擴大，EGP逐漸暴露出了很多的局限性，如不能處理環路和多個網路網狀連線等情況。為了克服EGP的局限性，IETF制定了實際上現已成為標準的邊界網關協定(BGP，BorderGatewayProtocol)。

BGP經歷了不同的階段，從最早的版本BGP1發展到了當前的版本BGP4。BGP4是第一個支持CIDR的版本。

BGP是一種用於在自治系統之間傳遞路由信息的路徑向量協定。路徑向量的含義是指BGP路由訊息中帶有一個自治域號碼的序列，它說明了一條路由所通過的路徑，這樣可有效地檢測並避免複雜拓撲結構中可能出現的環路問題。BGP支持CIDR定址方式，減少了路由表長度，從而加快了選路速度。另外，BGP使用TCP作為其傳輸協定(預設連線埠號為179)，這保證了傳輸的可靠性，由於差錯控制功能全部由TCP協定完成，因此BGP自身的實現就變得非常簡單。

BGP協定在TCP連線上傳送4種訊息類型，包括：Open分組用來建立對等體連線；Update訊息用來在BGP對等體之間傳輸路由信息；Keepalive訊息用於周期性刷新對等體連線，以確保連線的有效性；Notification訊息用於通知其他BGP對等體檢測到一個差錯。

BGP協定的運行分為建立對等體連線和路由更新處理兩個階段。BGP進程的對等體連線建立過程可用如圖2所示的有限狀態機模型來表示。

圖2BGP對話的有限狀態機模型

①空閒狀態：這是連線的第一階段。BGP進程等待一個通常由網路管理員發出的啟動事件，然後BGP初始化資源，復位連線重試計數器，打開一個TCP連線連線埠，並開始監聽可能由遠程對等體啟動的連線，若成功，就轉換到連線狀態，否則將回到空閒狀態。

②連線狀態：BGP進程等待TCP連線的建立。如果TCP連線已建立，就轉換到OPEN傳送狀態，同時傳送OPEN訊息。如果TCP連線沒有建立，那么將轉換到行動(active)狀態。如果連線重試計時器溢出，狀態就停留在連線階段，計時器將被復位，一個TCP連線請求被啟動。

③行動狀態：BGP進程建立一個TCP連線，獲得一個對等體。若成功，則轉換為Open傳送狀態，同時傳送Open訊息。如果TCP連線計時器溢出，那么BGP進程將重新設定計時器，並回到連線狀態。一般地，如果BGP進程的狀態在連線與行動之間來回變化，則表明存在故障，不能建立TCP連線。這可能是因為對等體的IP位址不可達。

④Open傳送狀態：BGP進程等待接收來自對等體的Open訊息。若收到Open訊息，就對Open訊息進行正確性檢查：如果沒有錯誤，就轉換為Open確認狀態，同時開始傳送Keepalive訊息，並且復位Keepalive時鐘；否則，傳送Notification訊息，轉換到空閒狀態。在這個階段，BGP進程比較對等體的自治域號碼，以確認對等體是內部對等體還是外部對等體。

⑤Open確認狀態：BGP進程等待一個Keepalive或Notification報文。如果收到Keepalive報文，就進入對等已建立狀態，表示對等體連線已建立；如果收到Notification報文，則回到空閒狀態。

⑥已建立狀態：BGP進程與對等體交換Update或Keepalive數據包，假設Keepalive計時器的值不是零，那么當收到Update或Keepalive數據包時，計時器將復位。如果收到任何Notification報文，則說明系統出現錯誤，將就回到空閒狀態。

路由更新處理是BGP協定的核心。當BGP收到一個Update訊息時，首先驗證Update數據包的有效性，若Update訊息內沒有錯誤信息，那么就調用圖3所示的路由更新處理過程。

一個Update訊息或者通告一條可達路由，或者撤銷多條不再可達路由。對於不可達路由，BGP將從BGP路由表或路由信息庫的輸入路由表中刪除這些不可達路由，然後再調用決策過程處理。對於收到的可達路由信息，BGP將根據輸入路由策略進行路由過濾及屬性控制。例如，BGP要過濾從一個對等體收到的一條路徑的某個自治域號碼，為了防止流量通過該對等體到達該自治網路，輸出的路由將存儲到BGP路由表或路由信息庫的輸入路由表中。

BGP決策過程基於路徑屬性值，在多條可達路由中選擇一條到達某個目的地的最佳路由。BGP協定使用的一些重要的路徑屬性包括：

①起源(Origins)：表示一條路由的起源，如由外部BGP獲取，或者由內部路由協定輸入等。

圖3BGP路由更新處理過程

②自治系統路徑(AS_Path)：一條路由到達一個目的地址所經過的一系列自治系統號碼。

③下一段地址(Next-hop)：到達一個網路的下一跳地址。

④多出口判別(MULTI_EXIT_DISC)：用於提示進入一個多入口自治系統的入口優先權。

⑤本地優先(LOCAL_PREF)：用於自治系統內部到達某一地址出口點的優先權。

BGP決策過程分為以下幾個步驟：

①如果下一段地址是不可達的，這路由就要被忽略；

②優先選擇最大本地優先的路由；

③如果本地優先相同，優先選擇本地始發的路由；

④如果本地始發相同，優先選擇具有最短自治系統路徑的路由；

⑤如果自治系統路徑相同，優先選擇具有低起源屬性的路由；

⑥如果起源屬性相同，優先選擇具有最低多出口判別屬性值的路由；

⑦如果以上情況都相同，優先選擇可通過最近對等體到達的路由。

由以上決策過程產生的最佳路由是路由器本身使用的，將被存儲到BGP路由表的內部使用路由表中，同時輸入到路由轉發表。

BGP路由表中內部使用路由表的路由以及路由器在本地產生的路由需要通告給其他的對等體。在送出更新訊息以前，要套用輸出策略進行路由過濾及屬性控制。例如，自治系統記憶體在多個入口，給各個入口設定不同的多出口判別屬性來調整各個入境流量的大小。另外，還需區別內部和外部對等體，例如從內部對等體得知的路由不應傳送到內部對等體。

總之，BGP協定是一種基於策略的路由協定，雖然協定本身相對簡單，但配置相當複雜，若使用不當，則有可能影響其他網路。更詳細的BGP協定內容及套用指導參見IETFRFC1771、RFC1773等。