TCP/IP協定族——單點傳播路由選擇協定RIP、OSPF、BGP

每個自治系統内部可以選擇一個或多個域内路由選擇協定來處理本自治系統内部的路由選擇，但是，處理自治系統之間的路由選擇隻能使用一種域間路由選擇協定。

一 距離向量路由選擇協定

該方法視AS及其所有路由器和網絡如同一張由結點連接配接結點的邊的集合構成的圖。

1.1 Bellman-Ford算法——任意兩個點之間的最短路徑

基本原理：結點i到結點j之間的最短Dij=min{di1+D1j，di2+D2j，di3+D3j，...，din+Dnj}，其中點1到n為點i的n個鄰點。

1.2 距離向量路由選擇算法

（1）路由器建立一個初始的路由表，隻能用于将分組轉發到與它的接口直接相連的網絡。如：

目的網絡   代價  下一跳

————————————

網絡1         1        ----

————————————

網絡2         1        ----

————————————

網絡6         1        ----

（2）對于每一個表項，向每一個鄰站發送記錄，該記錄包含兩個字段：目的位址和代價。

（3）每當路由器收到一個來自鄰站的記錄，就要更新自己的路由表，更新之後，路由器又将路由表的每一個表項發送給它的每一個鄰站，以便這些鄰站各自完成更新。

（4）當一個記錄到達時，路由器搜尋路由表以找到相應的目的位址。

（5）如果找到相應的表項，分兩種情況檢查并修改路由資訊。

a.如果這個記錄的代價加上1之後小于路由表中的相應代價，意味着該站發現了更好的路徑，更改下一條和代價。

b.如果下一條是相同的，則意味着某一部分網絡發生了變化，更新代價。

（6）如果路由表中沒有相應的表項，路由器就将其添加到路由表中，并根據目的位址對路由表進行排序。

問題：有關代價下降的消息（好消息）擴散的非常快，有關代價上升的消息（壞消息）擴散很慢。如：

二結點循環問題：

結點X--------------------結點A-----------------------結點B

開始時，結點A和B都知道怎樣到達X，但是在A和X之間的鍊路突然出來故障，結點A改變其路由表，如果A能夠立即把它的路由表發送給B，那麼一切問題都沒有了。但是，如果B在收到A的路由表之前，已經向A先發送了它自己的路由表，那麼這個系統就會變得不穩定：結點A收到這個更新，它認為B已經找到了到達X的路，于是立即對自己的路由表更新，然後A又将此次更新發給B，B認為A周圍網絡發生了一些變化，因而更新其路由表。到達X的代價逐漸增大，直到增加到無窮大，此時A和B才知道X是不可達的（壞消息傳的慢），在這個過程中，如果A收到了要發往X的分組，他就會被轉發到B，然後又被轉發到A，...，如此循環往複。

解決辦法：

（1）定義無窮大：把16定義為無窮大。優點：該系統會在較少的幾次更新内達到穩定。缺點：距離向量不能用于大系統中。

（2）分割範圍：不讓每個結點通過所有接口用洪範方法發送更新。而是隻發送它的路由表的一部分。如果結點B根據其路由表認為到達X的最佳路由要經過A，那麼它就不需要再把這個資訊通告給A了。缺點：距離向量協定使用一個計時器，若長時間沒有關于某個路由的消息，就要從路由表中删除該路由。

（3）分割範圍和毒性逆轉：為解決分割範圍的缺點，上述情況下，節點B可以仍然通知關于X的數值，但如果資訊源是A，就把代價換成為無窮大作為一種警告：不要使用該值，我的該值時根據你的消息計算出來的。

分割範圍和毒性逆轉可以解決二結點的不穩定性，但是三結點的不穩定性無法保證。

1.3 路由資訊協定RIP

1.3.1 RIP是基于距離向量路由選擇的簡單協定，并有以下考慮：

（1）路由器和網絡被表示為結點。

（2）終點是一個網絡，即路由表第一列目的位址為一個網絡位址。

（3）使用跳數作為度量。

（4）無窮大被定義為16。

（5）“下一個節點”是為了達到終點而要發往的下一個路由器的位址。

1.3.2 RIP封包格式

指令（8位）：指明封包類型，請求（1）、響應（2）。

版本（8位）：RIP協定版本，1或2。

系列（16位）：所使用協定系列，TCP/IP該值為2。

網絡位址：目的網絡位址，14個位元組，可用于包括IP（4位元組）在内的任何協定。

距離（32位）：從發出通告的路由器一直到目的網絡所經過的跳數。

1.3.3 請求和響應

當路由器剛剛接入到網絡上，或者路由器有一些表項逾時了，就發送請求封包。可以詢問某些特定的表項或者所有表項。

響應可以是詢問的或非詢問的，詢問的響應僅在回答請求時才發出，它包含了在對應的請求中指明的終點的資訊，而非詢問的響應則是定期發送的，如每隔30秒或當路由表中有變化時，這種響應也稱更新分組。

1.3.4 RIP的計時器

RIP使用三個定時器來支援它的操作：

（1）定期計時器：控制更新封包的定期發送，倒數計時，為0時發送更新封包。

（2）截止期計時器：管理路由的有效性，為每個路由項設定一個計時器（180s），若該時間内沒收到該路由項的任何更新封包，則将路由跳數設定為16。

（3）無用資訊收集計時器：通知某個路由出了故障，當某個路由資訊變成無效時，并不立即清除，而是設定無用資訊收集計時器120秒，當計數倒數為0時删除該表項。這個計時器使得鄰站在某個路由被清除之前能夠了解該路由是無效的。

二 鍊路狀态路由選擇

2.1 原理

如果某個域的每一個結點都有這個域的完整拓撲，那個這個結點就能夠使用 Dijkstra算法構造一個路由表。通過以下四組動作來確定每一個結點的路由表能給出到達其他各結點的最小代價結點：

（1）每個結點先建立一個有關鍊路狀态的分組，稱為鍊路狀态分組或LSP。産生LSP的場合：

a.當這個域的拓撲發生變化時。

b.基于定期更新。周期較長（如60分鐘），目的是為了確定舊的資訊可以從該域删除。防止洪範不會再網絡上産生太大的通信量。

（2）以可靠和有效的方法向其它各結點（所有結點，并非相鄰結點）散發LSP，稱之為洪泛。

a.産生LSP的節點把LSP的副本從他的每一個接口發送出去。

b.節點把收到的LSP和可能已有的副本進行比較。如果新到達的LSP比原有的還舊（檢查序号可知），就丢棄該LSP。如果它比較新，這個結點丢棄舊的LSP，保留新的。并且将該LSP從除了接收該分組的接口以外的所有接口發送出去——保證了洪範會在某處（隻有一個接口的節點）處停止。

（3）為每個結點形成一個最短路徑樹——選擇作為樹的根節點，可以從這個跟經過僅一條路徑到達其他所有結點，從跟到其它每個結點的路徑都是最短的。

（4）基于這個最短路徑樹計算路由表——Dijkstra算法。

2.2 OSPF協定（開放最短路徑優先）

一種基于鍊路狀态路由選擇的域内路由選擇協定，它的域是一個自制系統。OSPF使用五種不同類型的分組： 問候分組、資料庫描述分組、鍊路狀态請求分組、鍊路狀态更新分組、鍊路狀态确認分組。

2.2.1 公共首部

所有的OSPF分組都有相同的公共首部，如下所示：

類型： 值1到5表示五種類型。 

封包長度：包括首部在内的總封包長度。

鑒别字段為64位（上圖有誤），公共首部總長度為24位元組。

2.2.2 鍊路狀态更新分組

OSPF運作的核心，路由器用它來通告自己的鍊路狀态，其通用格式如下：

每個更新分組可包含數個不同的LSA（鍊路狀态通告），所有五種LSA具有相同的通用首部，格式如下：

鍊路狀态類型：定義了五種LSA的類型之一。

2.2.3 其他分組

（1）問候封包：用于建立鄰站關系，并測試鄰站的可達性。

（2）資料庫描述封包： 鄰站收到新連接配接路由器發送的問候封包後，若是第一次收到該消息，他們就發送資料庫描述封包給新連接配接路由器，資料庫描述分組并不包含完整的資料庫資訊，它隻給出了概要，即資料庫中每一行的标題，新連接配接上的路由器檢查這些标題，并找出哪些行的資訊它還沒有，然後再發送一個或多個鍊路狀态請求封包，以便得到這個特定鍊路的完整資訊。

（3）鍊路狀态請求分組：對它的回答是鍊路狀态更新分組。

（4）鍊路狀态确認分組：對所收到的每一個鍊路狀态更新分組進行确認，使得路由選擇更加可靠。

2.2.4 封裝

OSPF分組被封裝成IP資料報，這些資料報包括确認機制，以實作流量控制和差錯控制。它們不需要通過運輸層協定來提供這些服務。

三 路徑向量路由選擇

3.1 原理和特點

距離向量路由選擇：運作區域跳數比較多時會變得不穩定。

鍊路狀态路由選擇：需要大量的資源用于計算路由表，洪泛法會産生很大的通信量。

——不适于自制系統之間的路由選擇

路徑向量路由選擇：路由器有一個網絡清單，列出了到達每個網絡的路徑，每個AS至少有一個收集了其内部所有網絡可達性資訊的路徑向量路由表，收集的資訊僅僅表示哪個網絡是存在的，不同AS之間共享可達性清單，特點如下：

（1）防止環路

收到可達性資訊後，檢查自己的自制系統是否在到達終點的路徑上，如果是就說明會出現環路，丢棄該封包。

（2）聚合

CIDR記法和地質聚合使得路由表簡短，路由器之間資訊交換更快。

（3）政策路由選擇

收到封包就檢查其路徑，如果路徑中列出的一個自治系統與政策相違背，就忽略這條路徑和這個終點。

3.2 邊界網關協定BGP

一個使用路徑向量路由選擇的域間路由選擇協定。

分組類型：打開、更新、保活和通知。所有BGP分組共享相同的公共首部，如下所示：

長度：包括首部在内的封包總長度。

類型：1到4定義的四種類型。

3.2.1 分組類型

（1）打開封包：為了建立鄰站關系，運作BGP的路由器需要打開與鄰站的TCP連接配接，因而要發送打開封包，若對方接受這種關系就用保活封包來響應，表示在這兩個路由器之間已經建立了關系。

（2）更新封包：用來撤銷以前曾通告過的終點，或宣布到一個新終點的路由。

（3）保活封包：定期互相交換保活封包，用來告訴對方自己是工作的。

（4）通知封包：當檢測出差錯狀态或路由器打算關閉連接配接時，路由器就發送通知封包。

3.2.2 封裝

BGP封包封裝成TCP封包段，并使用熟知端口179，這表示不需要使用差錯控制和流量控制，在TCP連接配接被打開後，就不停的交換着更新封包，直到發出停止類型的通知為止。