動態選路協議

當相鄰路由器之間進行通信，以告知對方每個路由器當前所連接的網絡，這時就出現了動態選路。路由器之間必須採用選路協議進行通信，這樣的選路協議有很多種。路由器上有一個進程稱為路由守護程序（routing daemon），它運行選路協議，並與其相鄰的一些路由器進行通信。路由守護程序根據它從相鄰路由器接收到的信息，更新內核中的路由表。

動態選路並不改變內核在IP層的選路方式。這種選路方式稱為選路機制（routing mechanism）。內核搜索路由表，查找主機路由、網絡路由以及默認路由的方式並沒有改變。僅僅是放置到路由表中的信息改變了—當路由隨時間變化時，路由是由路由守護程序動態地增加或刪除，而不是來自於自引導程序文件中的route命令。

正如前面所描述的那樣，路由守護程序將選路策略（routing policy）加入到系統中，選擇路由並加入到內核的路由表中。如果守護程序發現前往同一信宿存在多條路由，那麼它（以某種方法）將選擇最佳路由並加入內核路由表中。如果路由守護程序發現一條鏈路已經斷開（可能是路由器崩潰或電話線路不好），它可以刪除受影響的路由或增加另一條路由以繞過該問題。

在像Internet這樣的系統中，目前採用了許多不同的選路協議。Internet是以一組自治系統(AS，Autonomous System)的方式組織的，每個自治系統通常由單個實體管理。常常將一個公司或大學校園定義為一個自治系統。NSFNET的Internet骨幹網形成一個自治系統，這是因為骨幹網中的所有路由器都在單個的管理控制之下。

每個自治系統可以選擇該自治系統中各個路由器之間的選路協議。這種協議我們稱之為內部網關協議IGP（Interior Gateway Protocol）或域內選路協議（intradomain routing protocol）。最常用的IGP是選路信息協議RIP。一種新的IGP是開放最短路徑優先OSPF（Open Shortest Path First）協議。它意在取代RIP。另一種1986年在原來NSFNET骨幹網上使用的較早的IGP協議—HELLO，現在已經不用了。

新的RFC[Almquist1993]規定，實現任何動態選路協議的路由器必須同時支持OSPF和RIP，還可以支持其他IGP協議。

外部網關協議EGP（ExterierGatewayProtocol）或域內選路協議的分隔選路協議用於不同自治系統之間的路由器。在歷史上，（令人容易混淆）改進的EGP有着一個與它名稱相同的協議：EGP。新EGP是當前在NSFNET骨幹網和一些連接到骨幹網的區域性網絡上使用的是邊界網關協議BGP（BorderGatewayProtocol）。BGP意在取代EGP ^[1]  。

動態路由協議可以按工作原理，工作範圍，是否攜帶掩碼來劃分 ^[2]  。

RIP協議比較簡單，容易實現，在網絡拓撲比較穩定時，其工作特性比較理想。其缺點是，網絡拓撲變化時，收斂較慢，可能出現路由不一致現象，從而引起數據包轉發混亂，另外鏈路度量方式比較簡單，不適宜在大規模的網絡中運行。

RIP只使用“跳數”來決定到達遠程網絡的最佳方式，並規定源站和目的站之間經過的路由器最多為15個，如果路由器收到了路由更新信息，且把距離加1後等於16（意為無窮大），就認為該目的網絡不可達。在小型網絡中，RIP會運行良好， 但是對於使用慢速 WAN 鏈接的大型網絡或者對於安裝有大量路由器的網絡來説，它的效率很低 ^[3]  。

RIP協議分為RIPv1和RIPv2兩個版本，二者具有很多相同的功能。它們的區別在於：RIPv1是有類路由協議，該網絡中的所有設備必須使用相同的子網掩碼，RIPv1不發送帶有子網掩碼信息的更新數據，而RIPv2是無類路由協議，RIPv2在路由更新時攜帶子網信息；RIPv1不支持VLSM（VariableLengthSubnetMask，可變長子網掩碼）和CIDR（ClasslessInter-DomainRouting，無類別域間路由），而RIPv2支持VLSM和CIDR；RIPv1採用廣播更新，而RIPv2採用組播更新；RIPv1不提供認證，而RIPv2提供認證。

RIP協議每30秒向相鄰路由器發送一次路由更新信息，同時監聽來自網絡中的相鄰路由器的路由更新信息，從而實現對本地路由表的動態維護，以確保IP層發送數據時選擇正確的路由。針對路由表中某一條路由信息，如果180秒內沒有接收到新的關於它的路由更新信息，則將其標記為失效，即跳數值標記為16；再經過120秒後，如果仍然沒有收到更新信息，則將該條失效信息刪除。

RIP協議中對“距離”的定義為：從一個路由器到直接連接的網絡的距離定義為1，從一個路由器到非直接連接的網絡的距離定義為所經過的路由器數目加1。因此，這裏的“距離”也稱為“跳數”，因為每經過一個路由器，跳數就加1。

依據距離向量算法，當網絡中的路由器收到相鄰路由器的一個RIP報文後，執行如下操作：

現在Internet已應用於軍事，科技，教育，工農業等各個領域，發揮着越來越重要的作用，它標誌着信息時代的興起。Internet的重要基礎是TCP/IP協議，該協議是計算機用於網絡通信的標準，它是一個協議族，包含控制，傳輸，標識等各方面的子協議 ^[4]  。

TCP/IP協議中，尋找一台計算機到另一台計算機的路由是很重要的，一方面，要判斷是否能找到路，～方面，找到路後找一條短的路(花費時間最小)，再一方面，不能循環。最好還應該能動態處理路由變化，如：接口的uP和DOWN，時間花費的變網絡結構的改變等。網絡上的節點通常通過路由器與整個網絡連續，需要知道到達網絡的另一個節點的路由。當IP包要在網絡上傳送時，需要進行IP選路。

IP選路(路由)：IP可以從上層的TCP、UDP、ICMP和IGMP協議中接收數據報(即在本地生成的數據報)進行發送，或者從一個網絡接口接收數據報(待轉發的數據報)進行發送。在發送之前，IP層都要查詢在內存中的路由表來確定往那個網絡接口發送數據報文。每當數據報來自某個網絡接口時，IP首先檢查目的IP地址是否為本機的IP地址之一或者IP廣播地址。如果確實是，數據報就被送到由IP首部協議字段所指定的協議模塊進行處理。如果數據報的目的不是這些地址，那麼如果IP層被設置為路由器的功能，那麼就對數據報進行轉發；否則數據報被丟棄。然後發送ICMP報文給源主機通知目的地不可達，並且給出原因。

OSPF協議的基本思路如下：在自治系統中每一台運行OSPF的路由器收集各自的接口、鄰接信息稱為鏈路狀態，通過Flooding算法在整個系統廣播自己的鏈路狀態，使得在整個系統內部維護一個同步的鏈路狀態數據庫，根據這一數據庫，路由器計算出以自己為根，其它網絡節點為葉的一根最短的路徑樹，從而計算出自己到達系統內部各可達的最佳路由。它處理在一個自治系統中，路由器的網絡的路由表信息 ^[5]  。

OSPF路由協議是一種典型的鏈路狀態(Link—state)的路由協議，一般用於同一個路由域內。在這裏，路由域是指一個自治系統(Autonomous System)，即AS，它是指一組通過統一的路由政策或路由協議互相交換路由信息的網絡。在這個As中，所有的OSPF路由器都維護一個相同的描述這個As結構的數據庫，該數據庫中存放的是路由域中相應鏈路的狀態信息，OSPF路由器正是通過這個數據庫計算出其OSPF路由表的。

作為一種鏈路狀態的路由協議，OSPF將鏈路狀態廣播數據包LSA(LinkStateAdvertisement)傳送給在某一區域內的所有路由器，這一點與距離矢量路由協議不同。運行距離矢量路由協議的路由器是將部分或全部的路由表傳遞給與其相鄰的路由器。

BGP(Border Gateway Protoc01)邊界網關協議是一種路由協議，用於交換因特網自治域系統間的路由信息，其主要功能是在系統之間交換網絡可達信息(NetworkLayerReachableInformation，簡稱NLRI)。隨着網絡拓撲的日益複雜，多個自治域系統之間通信的要求越來越高，需要配置的策略越來越複雜，BGP協議已經成為因特網路由體系的重要組成部分。國際和國內許多的網絡和電信設備供應商已經實現和配置BGP協議，用於支撐因特網運行，減少交換和路由設備的運行負荷 ^[6]  。

BGP協議是一種路徑向量協議，在一定程度上綜合了距離向量和鏈路狀態算法的優點。BGP認為自治域內的路由選擇由IGP完成，並不對自治域內的路由作任何假設。BGP不需要所有自治域都運行同樣的內部路由協議，對底層的網絡拓撲沒有任何限制，通過BGP的Update消息交換的信息已經足夠建立一個自治域連接圖。有了自治域連接圖，就能夠消除路由環路，並在自治系統內應用路由策略。

BGP是一種不同自治系統的路由器之間進行通信的外部網關協議。BGP是ARPANET所使用的老EGP的取代品。RFC1267[Lougheed and Rekhter1991]對第3版的BGP進行了描述。RFC1268[Rekhter and Gross1991]描述瞭如何在Internet中使用BGP。下面對於BGP的大部分描述都來自於這兩個RFC文檔。同時，1993年開發第4版的BGP（見RFC1467[Topolcic1993]） ^[1]  。

BGP協議運行在TCP之上，使用TCP端口179作為它的傳輸端口。通過TCP建立可靠的傳輸機制，在BGP鄰居(對等體)之間交換信息。在BGP的對等體交換信息之前，BGP首先建立鄰居關係。BGP的對等體使用一個特殊的IP地址來配置，而不是動態發現BGP的鄰居。建立鄰居關係後，BGP使用週期的KeepAlive消息來確認BGP鄰居的可訪問性。BGP消息包括OPEN、UPDATE、NOTIFICATION和KEEPALIVE四種 ^[6]  。

BGP鄰居關係建立後開始交換完整的BGP由表，之後當路由有變化時發送路由更新操作即UPDATE消息。BGP不要求週期性地刷新路由，只有週期性的KEEPALIE信息在形成BGP鄰關係的路由器之間發送，以保證BGP鄰居關係維持。如果在。路由信息交換的過程中發生錯誤，其中的一台路由器向鄰居發送NOTIFICATION消息指出錯誤的類型並關閉BGP連接。