備份路由演算法

① 路由協議分類、比較

分類：：對於路由器協議這個名詞，可能很多人都已經耳熟能詳，特別目前網路發展的很快，Internet路由器協議也在不斷的完善，同時也出現了很多新功能。信息技術在各個領域的廣泛應用促使信息交換網路的迅猛發展，其中Internet是最大的受益者。

Internet網路的主要節點設備是路由器，路由器技術通過路由決定數據的轉發。轉發策略稱為路由選擇（routing），這也是路由器名稱的由來（router，轉發者）。決定轉發的辦法可以是人為指定，但人為指定工作量大，而且不能採取靈活的策略，於是動態路由器協議應運而生，通過傳播、分析、計算、挑選路由，來實現路由發現、路由選擇、路由切換和負載分擔等功能。

RIP、OSPF和BGP協議

Internet上現在大量運行的路由器協議有RIP、OSPF和BGP。RIP、OSPF是內部網關協議，適用於單個ISP的統一路由器協議的運行，由一個ISP運營的網路稱為一個自治系統（AS）。BGP是自治系統間的路由器協議，是一種外部網關協議。

RIP是推出時間最長的路由器協議，也是最簡單的路由器協議。它是「路由信息協議」的縮寫，主要傳遞路由信息（路由表）來廣播路由：每隔30秒，廣播一次路由表，維護相鄰路由器的關系，同時根據收到的路由表計算自己的路由表。RIP運行簡單，適用於小型網路，Internet上還在部分使用著RIP。

OSPF協議是「開放式最短路優先」的縮寫。「開放」是針對當時某些廠家的「私有」路由器協議而言，而正是因為協議開放性，才造成OSPF今天強大的生命力和廣泛的用途。它通過傳遞鏈路狀態（連接信息）來得到網路信息，維護一張網路有向拓撲圖，利用最小生成樹演算法（SPF演算法）得到路由表。OSPF是一種相對復雜的路由器協議。

總的來說，OSPF、RIP都是自治系統內部的路由器協議，適合於單一的ISP（自治系統）使用。一般說來，整個Internet並不適合跑單一的路由器協議，因為各ISP有自己的利益，不願意提供自身網路詳細的路由信息。為了保證各ISP利益，標准化組織制定了ISP間的路由器協議BGP。

BGP是「邊界網關協議」的縮寫，處理各ISP之間的路由傳遞。其特點是有豐富的路由策略，這是RIP、OSPF等協議無法做到的，因為它們需要全局的信息計算路由表。BGP通過ISP邊界的路由器加上一定的策略，選擇過濾路由，把RIP、OSPF、BGP等的路由發送到對方。全局范圍的、廣泛的Internet是BGP處理多個ISP間的路由的實例。BGP的出現，引起了Internet的重大變革，它把多個ISP有機的連接起來，真正成為全球范圍內的網路。帶來的副作用是Internet的路由爆炸，現在Internet網的路由大概是60000條，這還是經過「聚合」後的數字。配置BGP需要對用戶需求、網路現狀和BGP協議非常了解，還有——需要非常小心，BGP運行在相對核心的地位，一旦出錯，其造成的損失可能會很大！

為適應Internet網路一對多的多點傳送應用如天氣預報、網路會議等，出現了一種新的傳輸模式——多播（multicast）。多播適合於一到多的傳輸環境，同時也可適用多到多、多到一的情況。多播轉發主要由路由器決定，路由器通過兩種方式決定所謂的下游：決定是否有主機（用戶）的下游，通過Multicastclient（IGMP）協議；決定是否有間接用戶，即通過「下游」路由器帶的組員，由下游路由器通過多播路由器協議的報文通告，路由器決定是否往該下游轉發數據。 可以看到，第二種方式中多播路由器協議的應用是大規模網路多播轉發的關鍵。多播路由器協議應該至少能正確通告組員信息，並能形成全局統一的路由拓撲。

密集模式適用於小型網路，其假設是全網有非常「密集」的組員存在，採用廣播＋剪枝的工作策略。其默認假設是向所有的下游轉發數據，當收到某下游發來的明確的剪枝信息後，才把該介面從下游列表中除去。一般說來，轉發路徑應該是以「源」為根、組員為枝葉的一棵樹。密集模式的路由器協議包括DVMRP、MOSPF和PIMDM。

稀疏模式是Internet上應用廣泛的一種情形。畢竟，針對Internet網，現在任何一次多播應用都不會有1％以上的機器需要接收。稀疏模式默認所有機器都不需要收多播包，只有明確指定需要的才予以轉發，這確實能適用於「稀疏」的考慮。現在所有稀疏模式協議的主要轉發思路是所有同類報文按相同的路徑轉發，即先發送到一個匯聚點（或稱為核），再沿以匯聚點為根的組員為枝葉的共享樹轉發。稀疏方式的路由器協議包括PIMSM和CBT。

可以毫不誇張的說，路由器協議支持著IP，支持著Internet。沒有路由器協議，Internet將是一個混亂的世界，不可能有今天這樣的方便快捷。而多播則開創了一個新的發展前景，將成為引導Internet未來的主力。
比較：：路由分為靜態路由和動態路由，其相應的路由表稱為靜態路由表和動態路由表。靜態路由表由網路管理員在系統安裝時根據網路的配置情況預先設定，網路結構發生變化後由網路管理員手工修改路由表。動態路由隨網路運行情況的變化而變化，路由器根據路由協議提供的功能自動計算數據傳輸的最佳路徑，由此得到動態路由表。 根據路由演算法，動態路由協議可分為距離向量路由協議（Distance Vector Routing Protocol）和鏈路狀態路由協議（Link State Routing Protocol）。距離向量路由協議基於Bellman-Ford演算法，主要有RIP、IGRP（IGRP為Cisco公司的私有協議）；鏈路狀態路由協議基於圖論中非常著名的Dijkstra演算法，即最短優先路徑（Shortest Path First，SPF）演算法，如OSPF。在距離向量路由協議中，路由器將部分或全部的路由表傳遞給與其相鄰的路由器；而在鏈路狀態路由協議中，路由器將鏈路狀態信息傳遞給在同一區域內的所有路由器。 根據路由器在自治系統（AS）中的位置，可將路由協議分為內部網關協議（Interior Gateway Protocol，IGP）和外部網關協議（External Gateway Protocol，EGP，也叫域間路由協議）。域間路由協議有兩種：外部網關協議（EGP）和邊界網關協議（BGP）。EGP是為一個簡單的樹型拓撲結構而設計的，在處理選路循環和設置選路策略時，具有明顯的缺點，目前已被BGP代替。 EIGRP是Cisco公司的私有協議，是一種混合協議，它既有距離向量路由協議的特點，同時又繼承了鏈路狀態路由協議的優點。各種路由協議各有特點，適合不同類型的網路。下面分別加以闡述。2 靜態路由 靜態路由表在開始選擇路由之前就被網路管理員建立，並且只能由網路管理員更改，所以只適於網路傳輸狀態比較簡單的環境。靜態路由具有以下特點： · 靜態路由無需進行路由交換，因此節省網路的帶寬、CPU的利用率和路由器的內存。 · 靜態路由具有更高的安全性。在使用靜態路由的網路中，所有要連到網路上的路由器都需在鄰接路由器上設置其相應的路由。因此，在某種程度上提高了網路的安全性。 · 有的情況下必須使用靜態路由，如DDR、使用NAT技術的網路環境。 靜態路由具有以下缺點： · 管理者必須真正理解網路的拓撲並正確配置路由。 · 網路的擴展性能差。如果要在網路上增加一個網路，管理者必須在所有路由器上加一條路由。 · 配置煩瑣，特別是當需要跨越幾台路由器通信時，其路由配置更為復雜。3 動態路由 動態路由協議分為距離向量路由協議和鏈路狀態路由協議，兩種協議各有特點，分述如下。 1. 距離向量（DV）協議 距離向量指協議使用跳數或向量來確定從一個設備到另一個設備的距離。不考慮每跳鏈路的速率。 距離向量路由協議不使用正常的鄰居關系，用兩種方法獲知拓撲的改變和路由的超時： · 當路由器不能直接從連接的路由器收到路由更新時； · 當路由器從鄰居收到一個更新，通知它網路的某個地方拓撲發生了變化。 在小型網路中（少於100個路由器，或需要更少的路由更新和計算環境），距離向量路由協議運行得相當好。當小型網路擴展到大型網路時，該演算法計算新路由的收斂速度極慢，而且在它計算的過程中，網路處於一種過渡狀態，極可能發生循環並造成暫時的擁塞。再者，當網路底層鏈路技術多種多樣，帶寬各不相同時，距離向量演算法對此視而不見。 距離向量路由協議的這種特性不僅造成了網路收斂的延時，而且消耗了帶寬。隨著路由表的增大，需要消耗更多的CPU資源，並消耗了內存。 2. 鏈路狀態（LS）路由協議 鏈路狀態路由協議沒有跳數的限制，使用「圖形理論」演算法或最短路徑優先演算法。 鏈路狀態路由協議有更短的收斂時間、支持VLSM（可變長子網掩碼）和CIDR。 鏈路狀態路由協議在直接相連的路由之間維護正常的鄰居關系。這允許路由更快收斂。鏈路狀態路由協議在會話期間通過交換Hello包（也叫鏈路狀態信息）創建對等關系，這種關系加速了路由的收斂。 不像距離向量路由協議那樣，更新時發送整個路由表。鏈路狀態路由協議只廣播更新的或改變的網路拓撲，這使得更新信息更小，節省了帶寬和CPU利用率。另外，如果網路不發生變化，更新包只在特定的時間內發出（通常為30min到2h）。 3. 鏈路狀態路由協議和距離向量路由協議的比較4 常用動態路由協議的分析4.1 RIP RIP（路由信息協議）是路由器生產商之間使用的第一個開放標准，是最廣泛的路由協議，在所有IP路由平台上都可以得到。當使用RIP時，一台Cisco路由器可以與其他廠商的路由器連接。RIP有兩個版本：RIPv1和RIPv2，它們均基於經典的距離向量路由演算法，最大跳數為15跳。 RIPv1是族類路由（Classful Routing）協議，因路由上不包括掩碼信息，所以網路上的所有設備必須使用相同的子網掩碼，不支持VLSM。RIPv2可發送子網掩碼信息，是非族類路由（Classless Routing）協議，支持VLSM。 RIP使用UDP數據包更新路由信息。路由器每隔30s更新一次路由信息，如果在180s內沒有收到相鄰路由器的回應，則認為去往該路由器的路由不可用，該路由器不可到達。如果在240s後仍未收到該路由器的應答，則把有關該路由器的路由信息從路由表中刪除。 RIP具有以下特點：· 不同廠商的路由器可以通過RIP互聯；· 配置簡單； · 適用於小型網路（小於15跳）；· RIPv1不支持VLSM；· 需消耗廣域網帶寬；· 需消耗CPU、內存資源。 RIP的演算法簡單，但在路徑較多時收斂速度慢，廣播路由信息時佔用的帶寬資源較多，它適用於網路拓撲結構相對簡單且數據鏈路故障率極低的小型網路中，在大型網路中，一般不使用RIP。4.2 IGRP 內部網關路由協議（Interior Gateway Routing Protocol，IGRP）是Cisco公司20世紀80年代開發的，是一種動態的、長跨度（最大可支持255跳）的路由協議，使用度量（向量）來確定到達一個網路的最佳路由，由延時、帶寬、可靠性和負載等來計算最優路由，它在同個自治系統內具有高跨度，適合復雜的網路。Cisco IOS允許路由器管理員對IGRP的網路帶寬、延時、可靠性和負載進行權重設置，以影響度量的計算。 像RIP一樣，IGRP使用UDP發送路由表項。每個路由器每隔90s更新一次路由信息，如果270s內沒有收到某路由器的回應，則認為該路由器不可到達；如果630s內仍未收到應答，則IGRP進程將從路由表中刪除該路由。 與RIP相比，IGRP的收斂時間更長，但傳輸路由信息所需的帶寬減少，此外，IGRP的分組格式中無空白位元組，從而提高了IGRP的報文效率。但IGRP為Cisco公司專有，僅限於Cisco產品。4.3 EIGRP 隨著網路規模的擴大和用戶需求的增長，原來的IGRP已顯得力不從心，於是，Cisco公司又開發了增強的IGRP，即EIGRP。EIGRP使用與IGRP相同的路由演算法，但它集成了鏈路狀態路由協議和距離向量路由協議的長處，同時加入散播更新演算法（DUAL）。 EIGRP具有如下特點： · 快速收斂。快速收斂是因為使用了散播更新演算法，通過在路由表中備份路由而實現，也就是到達目的網路的最小開銷和次最小開銷（也叫適宜後繼，feasible successor）路由都被保存在路由表中，當最小開銷的路由不可用時，快速切換到次最小開銷路由上，從而達到快速收斂的目的。 · 減少了帶寬的消耗。EIGRP不像RIP和IGRP那樣，每隔一段時間就交換一次路由信息，它僅當某個目的網路的路由狀態改變或路由的度量發生變化時，才向鄰接的EIGRP路由器發送路由更新，因此，其更新路由所需的帶寬比RIP和EIGRP小得多——這種方式叫觸發式（triggered）。 · 增大網路規模。對於RIP，其網路最大隻能是15跳（hop），而EIGRP最大可支持255跳（hop）。 · 減少路由器CPU的利用。路由更新僅被發送到需要知道狀態改變的鄰接路由器，由於使用了增量更新，EIGRP比IGRP使用更少的CPU。 · 支持可變長子網掩碼。 · IGRP和EIGRP可自動移植。IGRP路由可自動重新分發到EIGRP中，EIGRP也可將路由自動重新分發到IGRP中。如果願意，也可以關掉路由的重分發。 · EIGRP支持三種可路由的協議（IP、IPX、AppleTalk）。 · 支持非等值路徑的負載均衡。 · 因EIGIP是Cisco公司開發的專用協議，因此，當Cisco設備和其他廠商的設備互聯時，不能使用EIGRP4.4 OSPF 開放式最短路徑優先（Open Shortest Path First，OSPF）協議是一種為IP網路開發的內部網關路由選擇協議，由IETF開發並推薦使用。OSPF協議由三個子協議組成：Hello協議、交換協議和擴散協議。其中Hello協議負責檢查鏈路是否可用，並完成指定路由器及備份指定路由器；交換協議完成「主」、「從」路由器的指定並交換各自的路由資料庫信息；擴散協議完成各路由器中路由資料庫的同步維護。 OSPF協議具有以下優點： · OSPF能夠在自己的鏈路狀態資料庫內表示整個網路，這極大地減少了收斂時間，並且支持大型異構網路的互聯，提供了一個異構網路間通過同一種協議交換網路信息的途徑，並且不容易出現錯誤的路由信息。 · OSPF支持通往相同目的的多重路徑。 · OSPF使用路由標簽區分不同的外部路由。 · OSPF支持路由驗證，只有互相通過路由驗證的路由器之間才能交換路由信息；並且可以對不同的區域定義不同的驗證方式，從而提高了網路的安全性。 · OSPF支持費用相同的多條鏈路上的負載均衡。 · OSPF是一個非族類路由協議，路由信息不受跳數的限制，減少了因分級路由帶來的子網分離問題。 · OSPF支持VLSM和非族類路由查表，有利於網路地址的有效管理。 · OSPF使用AREA對網路進行分層，減少了協議對CPU處理時間和內存的需求。4.5 BGP BGP用於連接Internet。BGPv4是一種外部的路由協議。可認為是一種高級的距離向量路由協議。 在BGP網路中，可以將一個網路分成多個自治系統。自治系統間使用eBGP廣播路由，自治系統內使用iBGP在自己的網路內廣播路由。 Internet由多個互相連接的商業網路組成。每個企業網路或ISP必須定義一個自治系統號（ASN）。這些自治系統號由IANA（Internet Assigned Numbers Authority）分配。共有65535個可用的自治系統號，其中65512~65535為私用保留。當共享路由信息時，這個號碼也允許以層的方式進行維護。 BGP使用可靠的會話管理，TCP中的179埠用於觸發Update和Keepalive信息到它的鄰居，以傳播和更新BGP路由表。 在BGP網路中，自治系統有： 1. Stub AS只有一個入口和一個出口的網路。2. 轉接AS（Transit AS）當數據從一個AS到另一個AS時，必須經過Transit AS。 如果企業網路有多個AS，則在企業網路中可設置Transit AS。 IGP和BGP最大的不同之處在於運行協議的設備之間通過的附加信息的總數不同。IGP使用的路由更新包比BGP使用的路由更新包更小（因此BGP承載更多的路由屬性）。BGP可在給定的路由上附上很多屬性。 當運行BGP的兩個路由器開始通信以交換動態路由信息時，使用TCP埠179，他們依賴於面向連接的通信（會話）。 BGP必須依靠面向連接的TCP會話以提供連接狀態。因為BGP不能使用Keepalive信息（但在普通頭上存放有Keepalive信息，以允許路由器校驗會話是否Active）。標準的Keepalive是在電路上從一個路由器送往另一個路由器的信息，而不使用TCP會話。路由器使用電路上的這些信號來校驗電路沒有錯誤或沒有發現電路。 某些情況下，需要使用BGP：· 當你需要從一個AS發送流量到另一個AS時；· 當流出網路的數據流必須手工維護時；· 當你連接兩個或多個ISP、NAP（網路訪問點）和交換點時。以下三種情況不能使用BGP· 如果你的路由器不支持BGP所需的大型路由表時；· 當Internet只有一個連接時，使用默認路由；· 當你的網路沒有足夠的帶寬來傳送所需的數據時（包括BGP路由表）。

② 路由演算法的要求是什麼。

距離向量路由演算法(Bellman-Ford Routing Algorithm)，也叫做最大流量演演算法(Ford-Fulkerson Algorithm)，其被距離向量協議作為一個演算法，如RIP, BGP, ISO IDRP, NOVELL IPX。使用這個演算法的路由器必須掌握這個距離表(它是一個一維排列-「一個向量」)，它告訴在網路中每個節點的最遠和最近距離。在距離表中的這個信息是根據臨近接點信息的改變而時時更新的。表中數據的量和在網路中的所有的接點(除了它自己本身)是等同的。這個表中的列代表直接和它相連的鄰居，行代表在網路中的所有目的地。每個數據包括傳送數據包到每個在網上的目的地的路徑和距離/或時間在那個路徑上來傳輸(我們叫這個為「成本」)。這個在那個演算法中的度量公式是跳躍的次數， 等待時間，流出數據包的數量，等等。
在距離向量路由演算法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當網路拓撲結構發生變化時，路由器之間也將及時地相互通知有關變更信息。

③ 路由工作原理是什麼

路由器原理及路由協議
來源：中國電信網站

本文通過闡述TCP／IP網路中路由器的基本工作原理，介紹了IP路由器的幾大功能，給出了靜態路由協議和動態路由協議，以及內部網關協議和外部網關協議的概念，同時簡要介紹了目前最常見的RIP、OSPF、BGP和BGP-4這幾種路由協議，然後描述了路由演算法的設計目標和種類，著重介紹了鏈路狀態法和距離向量法。在文章的最後，扼要講述了新一代路由器的特徵。

——近十年來，隨著計算機網路規模的不斷擴大，大型互聯網路（如Internet）的迅猛發展，路由技術在網路技術中已逐漸成為關鍵部分，路由器也隨之成為最重要的網路設備。用戶的需求推動著路由技術的發展和路由器的普及，人們已經不滿足於僅在本地網路上共享信息，而希望最大限度地利用全球各個地區、各種類型的網路資源。而在目前的情況下，任何一個有一定規模的計算機網路（如企業網、校園網、智能大廈等），無論採用的是快速以大網技術、FDDI技術，還是ATM技術，都離不開路由器，否則就無法正常運作和管理。

1 網路互連

——把自己的網路同其它的網路互連起來，從網路中獲取更多的信息和向網路發布自己的消息，是網路互連的最主要的動力。網路的互連有多種方式，其中使用最多的是網橋互連和路由器互連。

1.1 網橋互連的網路

——網橋工作在OSI模型中的第二層，即鏈路層。完成數據幀（frame）的轉發，主要目的是在連接的網路間提供透明的通信。網橋的轉發是依據數據幀中的源地址和目的地址來判斷一個幀是否應轉發和轉發到哪個埠。幀中的地址稱為「MAC」地址或「硬體」地址，一般就是網卡所帶的地址。

——網橋的作用是把兩個或多個網路互連起來，提供透明的通信。網路上的設備看不到網橋的存在，設備之間的通信就如同在一個網上一樣方便。由於網橋是在數據幀上進行轉發的，因此只能連接相同或相似的網路（相同或相似結構的數據幀），如乙太網之間、乙太網與令牌環（token ring）之間的互連，對於不同類型的網路（數據幀結構不同），如乙太網與X.25之間，網橋就無能為力了。

——網橋擴大了網路的規模，提高了網路的性能，給網路應用帶來了方便，在以前的網路中，網橋的應用較為廣泛。但網橋互連也帶來了不少問題：一個是廣播風暴，網橋不阻擋網路中廣播消息，當網路的規模較大時（幾個網橋，多個乙太網段），有可能引起廣播風暴（broadcasting storm），導致整個網路全被廣播信息充滿，直至完全癱瘓。第二個問題是，當與外部網路互連時，網橋會把內部和外部網路合二為一，成為一個網，雙方都自動向對方完全開放自己的網路資源。這種互連方式在與外部網路互連時顯然是難以接受的。問題的主要根源是網橋只是最大限度地把網路溝通，而不管傳送的信息是什麼。

1.2 路由器互連網路

——路由器互連與網路的協議有關，我們討論限於TCP／IP網路的情況。

——路由器工作在OSI模型中的第三層，即網路層。路由器利用網路層定義的「邏輯」上的網路地址（即IP地址）來區別不同的網路，實現網路的互連和隔離，保持各個網路的獨立性。路由器不轉發廣播消息，而把廣播消息限制在各自的網路內部。發送到其他網路的數據茵先被送到路由器，再由路由器轉發出去。

——IP路由器只轉發IP分組，把其餘的部分擋在網內（包括廣播），從而保持各個網路具有相對的獨立性，這樣可以組成具有許多網路（子網）互連的大型的網路。由於是在網路層的互連，路由器可方便地連接不同類型的網路，只要網路層運行的是IP協議，通過路由器就可互連起來。

——網路中的設備用它們的網路地址（TCP／IP網路中為IP地址）互相通信。IP地址是與硬體地址無關的「邏輯」地址。路由器只根據IP地址來轉發數據。IP地址的結構有兩部分，一部分定義網路號，另一部分定義網路內的主機號。目前，在Internet網路中採用子網掩碼來確定IP地址中網路地址和主機地址。子網掩碼與IP地址一樣也是32bit，並且兩者是一一對應的，並規定，子網掩碼中數字為「1」所對應的IP地址中的部分為網路號，為「0」所對應的則為主機號。網路號和主機號合起來，才構成一個完整的IP地址。同一個網路中的主機IP地址，其網路號必須是相同的，這個網路稱為IP子網。

——通信只能在具有相同網路號的IP地址之間進行，要與其它IP子網的主機進行通信，則必須經過同一網路上的某個路由器或網關（gateway）出去。不同網路號的IP地址不能直接通信，即使它們接在一起，也不能通信。

——路由器有多個埠，用於連接多個IP子網。每個埠的IP地址的網路號要求與所連接的IP子網的網路號相同。不同的埠為不同的網路號，對應不同的IP子網，這樣才能使各子網中的主機通過自己子網的IP地址把要求出去的IP分組送到路由器上。

2 路由原理

——當IP子網中的一台主機發送IP分組給同一IP子網的另一台主機時，它將直接把IP分組送到網路上，對方就能收到。而要送給不同IP於網上的主機時，它要選擇一個能到達目的子網上的路由器，把IP分組送給該路由器，由路由器負責把IP分組送到目的地。如果沒有找到這樣的路由器，主機就把IP分組送給一個稱為「預設網關（default gateway）」的路由器上。「預設網關」是每台主機上的一個配置參數，它是接在同一個網路上的某個路由器埠的IP地址。

——路由器轉發IP分組時，只根據IP分組目的IP地址的網路號部分，選擇合適的埠，把IP分組送出去。同主機一樣，路由器也要判定埠所接的是否是目的子網，如果是，就直接把分組通過埠送到網路上，否則，也要選擇下一個路由器來傳送分組。路由器也有它的預設網關，用來傳送不知道往哪兒送的IP分組。這樣，通過路由器把知道如何傳送的IP分組正確轉發出去，不知道的IP分組送給「預設網關」路由器，這樣一級級地傳送，IP分組最終將送到目的地，送不到目的地的IP分組則被網路丟棄了。

——目前TCP／IP網路，全部是通過路由器互連起來的，Internet就是成千上萬個IP子網通過路由器互連起來的國際性網路。這種網路稱為以路由器為基礎的網路（router based network），形成了以路由器為節點的「網間網」。在「網間網」中，路由器不僅負責對IP分組的轉發，還要負責與別的路由器進行聯絡，共同確定「網間網」的路由選擇和維護路由表。

——路由動作包括兩項基本內容：尋徑和轉發。尋徑即判定到達目的地的最佳路徑，由路由選擇演算法來實現。由於涉及到不同的路由選擇協議和路由選擇演算法，要相對復雜一些。為了判定最佳路徑，路由選擇演算法必須啟動並維護包含路由信息的路由表，其中路由信息依賴於所用的路由選擇演算法而不盡相同。路由選擇演算法將收集到的不同信息填入路由表中，根據路由表可將目的網路與下一站（nexthop）的關系告訴路由器。路由器間互通信息進行路由更新，更新維護路由表使之正確反映網路的拓撲變化，並由路由器根據量度來決定最佳路徑。這就是路由選擇協議（routing protocol），例如路由信息協議（RIP）、開放式最短路徑優先協議（OSPF）和邊界網關協議（BGP）等。

——轉發即沿尋徑好的最佳路徑傳送信息分組。路由器首先在路由表中查找，判明是否知道如何將分組發送到下一個站點（路由器或主機），如果路由器不知道如何發送分組，通常將該分組丟棄；否則就根據路由表的相應表項將分組發送到下一個站點，如果目的網路直接與路由器相連，路由器就把分組直接送到相應的埠上。這就是路由轉發協議（routed protocol）。

——路由轉發協議和路由選擇協議是相互配合又相互獨立的概念，前者使用後者維護的路由表，同時後者要利用前者提供的功能來發布路由協議數據分組。下文中提到的路由協議，除非特別說明，都是指路由選擇協議，這也是普遍的習慣。

3 路由協議

——典型的路由選擇方式有兩種：靜態路由和動態路由。

——靜態路由是在路由器中設置的固定的路由表。除非網路管理員干預，否則靜態路由不會發生變化。由於靜態路由不能對網路的改變作出反映，一般用於網路規模不大、拓撲結構固定的網路中。靜態路由的優點是簡單、高效、可靠。在所有的路由中，靜態路由優先順序最高。當動態路由與靜態路由發生沖突時，以靜態路由為准。

——動態路由是網路中的路由器之間相互通信，傳遞路由信息，利用收到的路由信息更新路由器表的過程。它能實時地適應網路結構的變化。如果路由更新信息表明發生了網路變化，路由選擇軟體就會重新計算路由，並發出新的路由更新信息。這些信息通過各個網路，引起各路由器重新啟動其路由演算法，並更新各自的路由表以動態地反映網路拓撲變化。動態路由適用於網路規模大、網路拓撲復雜的網路。當然，各種動態路由協議會不同程度地佔用網路帶寬和CPU資源。

——靜態路由和動態路由有各自的特點和適用范圍，因此在網路中動態路由通常作為靜態路由的補充。當一個分組在路由器中進行尋徑時，路由器首先查找靜態路由，如果查到則根據相應的靜態路由轉發分組；否則再查找動態路由。

——根據是否在一個自治域內部使用，動態路由協議分為內部網關協議（IGP）和外部網關協議（EGP）。這里的自治域指一個具有統一管理機構、統一路由策略的網路。自治域內部採用的路由選擇協議稱為內部網關協議，常用的有RIP、OSPF；外部網關協議主要用於多個自治域之間的路由選擇，常用的是BGP和BGP-4。下面分別進行簡要介紹。

3.1 RIP路由協議

——RIP協議最初是為Xerox網路系統的Xerox parc通用協議而設計的，是Internet中常用的路由協議。RIP採用距離向量演算法，即路由器根據距離選擇路由，所以也稱為距離向量協議。路由器收集所有可到達目的地的不同路徑，並且保存有關到達每個目的地的最少站點數的路徑信息，除到達目的地的最佳路徑外，任何其它信息均予以丟棄。同時路由器也把所收集的路由信息用RIP協議通知相鄰的其它路由器。這樣，正確的路由信息逐漸擴散到了全網。

——RIP使用非常廣泛，它簡單、可靠，便於配置。但是RIP只適用於小型的同構網路，因為它允許的最大站點數為15，任何超過15個站點的目的地均被標記為不可達。而且RIP每隔30s一次的路由信息廣播也是造成網路的廣播風暴的重要原因之一。

3.2 OSPF路由協議

——80年代中期，RIP已不能適應大規模異構網路的互連，0SPF隨之產生。它是網間工程任務組織（1ETF）的內部網關協議工作組為IP網路而開發的一種路由協議。

——0SPF是一種基於鏈路狀態的路由協議，需要每個路由器向其同一管理域的所有其它路由器發送鏈路狀態廣播信息。在OSPF的鏈路狀態廣播中包括所有介面信息、所有的量度和其它一些變數。利用0SPF的路由器首先必須收集有關的鏈路狀態信息，並根據一定的演算法計算出到每個節點的最短路徑。而基於距離向量的路由協議僅向其鄰接路由器發送有關路由更新信息。

——與RIP不同，OSPF將一個自治域再劃分為區，相應地即有兩種類型的路由選擇方式：當源和目的地在同一區時，採用區內路由選擇；當源和目的地在不同區時，則採用區間路由選擇。這就大大減少了網路開銷，並增加了網路的穩定性。當一個區內的路由器出了故障時並不影響自治域內其它區路由器的正常工作，這也給網路的管理、維護帶來方便。

3.3 BGP和BGP-4路由協議

——BGP是為TCP／IP互聯網設計的外部網關協議，用於多個自治域之間。它既不是基於純粹的鏈路狀態演算法，也不是基於純粹的距離向量演算法。它的主要功能是與其它自治域的BGP交換網路可達信息。各個自治域可以運行不同的內部網關協議。BGP更新信息包括網路號／自治域路徑的成對信息。自治域路徑包括到達某個特定網路須經過的自治域串，這些更新信息通過TCP傳送出去，以保證傳輸的可靠性。

——為了滿足Internet日益擴大的需要，BGP還在不斷地發展。在最新的BGp4中，還可以將相似路由合並為一條路由。

3.4 路由表項的優先問題

——在一個路由器中，可同時配置靜態路由和一種或多種動態路由。它們各自維護的路由表都提供給轉發程序，但這些路由表的表項間可能會發生沖突。這種沖突可通過配置各路由表的優先順序來解決。通常靜態路由具有默認的最高優先順序，當其它路由表表項與它矛盾時，均按靜態路由轉發。

4 路由演算法

——路由演算法在路由協議中起著至關重要的作用，採用何種演算法往往決定了最終的尋徑結果，因此選擇路由演算法一定要仔細。通常需要綜合考慮以下幾個設計目標：

——（1）最優化：指路由演算法選擇最佳路徑的能力。

——（2）簡潔性：演算法設計簡潔，利用最少的軟體和開銷，提供最有效的功能。

——（3）堅固性：路由演算法處於非正常或不可預料的環境時，如硬體故障、負載過高或操作失誤時，都能正確運行。由於路由器分布在網路聯接點上，所以在它們出故障時會產生嚴重後果。最好的路由器演算法通常能經受時間的考驗，並在各種網路環境下被證實是可靠的。

——（4）快速收斂：收斂是在最佳路徑的判斷上所有路由器達到一致的過程。當某個網路事件引起路由可用或不可用時，路由器就發出更新信息。路由更新信息遍及整個網路，引發重新計算最佳路徑，最終達到所有路由器一致公認的最佳路徑。收斂慢的路由演算法會造成路徑循環或網路中斷。

——（5）靈活性：路由演算法可以快速、准確地適應各種網路環境。例如，某個網段發生故障，路由演算法要能很快發現故障，並為使用該網段的所有路由選擇另一條最佳路徑。

——路由演算法按照種類可分為以下幾種：靜態和動態、單路和多路、平等和分級、源路由和透明路由、域內和域間、鏈路狀態和距離向量。前面幾種的特點與字面意思基本一致，下面著重介紹鏈路狀態和距離向量演算法。

——鏈路狀態演算法（也稱最短路徑演算法）發送路由信息到互聯網上所有的結點，然而對於每個路由器，僅發送它的路由表中描述了其自身鏈路狀態的那一部分。距離向量演算法（也稱為Bellman-Ford演算法）則要求每個路由器發送其路由表全部或部分信息，但僅發送到鄰近結點上。從本質上來說，鏈路狀態演算法將少量更新信息發送至網路各處，而距離向量演算法發送大量更新信息至鄰接路由器。

——由於鏈路狀態演算法收斂更快，因此它在一定程度上比距離向量演算法更不易產生路由循環。但另一方面，鏈路狀態演算法要求比距離向量演算法有更強的CPU能力和更多的內存空間，因此鏈路狀態演算法將會在實現時顯得更昂貴一些。除了這些區別，兩種演算法在大多數環境下都能很好地運行。

——最後需要指出的是，路由演算法使用了許多種不同的度量標准去決定最佳路徑。復雜的路由演算法可能採用多種度量來選擇路由，通過一定的加權運算，將它們合並為單個的復合度量、再填入路由表中，作為尋徑的標准。通常所使用的度量有：路徑長度、可靠性、時延、帶寬、負載、通信成本等。

5 新一代路由器

——由於多媒體等應用在網路中的發展，以及ATM、快速乙太網等新技術的不斷採用，網路的帶寬與速率飛速提高，傳統的路由器已不能滿足人們對路由器的性能要求。因為傳統路由器的分組轉發的設計與實現均基於軟體，在轉發過程中對分組的處理要經過許多環節，轉發過程復雜，使得分組轉發的速率較慢。另外，由於路由器是網路互連的關鍵設備，是網路與其它網路進行通信的一個「關口」，對其安全性有很高的要求，因此路由器中各種附加的安全措施增加了CPU的負擔，這樣就使得路由器成為整個互聯網上的「瓶頸」。

——傳統的路由器在轉發每一個分組時，都要進行一系列的復雜操作，包括路由查找、訪問控製表匹配、地址解析、優先順序管理以及其它的附加操作。這一系列的操作大大影響了路由器的性能與效率，降低了分組轉發速率和轉發的吞吐量，增加了CPU的負擔。而經過路由器的前後分組間的相關性很大，具有相同目的地址和源地址的分組往往連續到達，這為分組的快速轉發提供了實現的可能與依據。新一代路由器，如IP Switch、Tag Switch等，就是採用這一設計思想用硬體來實現快速轉發，大大提高了路由器的性能與效率。

——新一代路由器使用轉發緩存來簡化分組的轉發操作。在快速轉發過程中，只需對一組具有相同目的地址和源地址的分組的前幾個分組進行傳統的路由轉發處理，並把成功轉發的分組的目的地址、源地址和下一網關地址（下一路由器地址）放人轉發緩存中。當其後的分組要進行轉發時，茵先查看轉發緩存，如果該分組的目的地址和源地址與轉發緩存中的匹配，則直接根據轉發緩存中的下一網關地址進行轉發，而無須經過傳統的復雜操作，大大減輕了路由器的負擔，達到了提高路由器吞吐量的目標。

④ 路由演算法的類型有

路由演算法有很多種，如果從路由表對網路拓撲和通信量變化的自適應能力的角度劃分，可以分為靜態路由演算法和動態路由演算法兩大類，這兩大類又可細分為幾種小類型，比較典型常見的有以下幾種：

一、靜態路由演算法

1.Dijkstra演算法（最短路徑演算法）

Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN,CLOSE表的方式，這里均採用永久和臨時標號的方式。注意該演算法要求圖中不存在負權迴路。

Dijkstra演算法執行步驟如下：

步驟一：路由器建立一張網路圖，並且確定源節點和目的節點，在這個例子里我們設為V1和V2。然後路由器建立一個矩陣，稱為「鄰接矩陣」。在這個矩陣中，各矩陣元素表示權值。例如，[i,j]是節點Vi與Vj之間的鏈路權值。如果節點Vi與Vj之間沒有鏈路直接相連，它們的權值設為「無窮大」。

步驟二：路由器為網路中的每一個節點建立一組狀態記錄。此記錄包括三個欄位：

前序欄位———表示當前節點之前的節點。

長度欄位———表示從源節點到當前節點的權值之和。

標號欄位———表示節點的狀態。每個節點都處於一個狀態模式：「永久」或「暫時」。

步驟三：路由器初始化（所有節點的）狀態記錄集參數，將它們的長度設為「無窮大」，標號設為「暫時」。

步驟四：路由器設置一個T節點。例如，如果設V1是源T節點，路由器將V1的標號更改為「永久」。當一個標號更改為「永久」後，它將不再改變。一個T節點僅僅是一個代理而已。

步驟五：路由器更新與源T節點直接相連的所有暫時性節點的狀態記錄集。

步驟六：路由器在所有的暫時性節點中選擇距離V1的權值最低的節點。這個節點將是新的T節點。

步驟七：如果這個節點不是V2（目的節點），路由器則返回到步驟5。

步驟八：如果節點是V2，路由器則向前回溯，將它的前序節點從狀態記錄集中提取出來，如此循環，直到提取到V1為止。這個節點列表便是從V1到V2的最佳路由。

2.擴散法
事先不需要任何網路信息；路由器把收到的每一個分組，向除了該分組到來的線路外的所有輸出線路發送。將來會有多個分組的副本到達目的地端，最先到達的，可能是走了「最優」的路徑常見的擴散法是選擇性擴散演算法。

3.LS演算法

採用LS演算法時，每個路由器必須遵循以下步驟：

步驟一：確認在物理上與之相連的路由器並獲得它們的IP地址。當一個路由器開始工作後，它首先向整個網路發送一個「HELLO」分組數據包。每個接收到數據包的路由器都將返回一條消息，其中包含它自身的IP地址。

步驟二：測量相鄰路由器的延時（或者其他重要的網路參數，比如平均流量）。為做到這一點，路由器向整個網路發送響應分組數據包。每個接收到數據包的路由器返回一個應答分組數據包。將路程往返時間除以2，路由器便可以計算出延時。（路程往返時間是網路當前延遲的量度，通過一個分組數據包從遠程主機返回的時間來測量。）該時間包括了傳輸和處理兩部分的時間——也就是將分組數據包發送到目的地的時間以及接收方處理分組數據包和應答的時間。

步驟三：向網路中的其他路由器廣播自己的信息，同時也接收其他路由器的信息。

在這一步中，所有的路由器共享它們的知識並且將自身的信息廣播給其他每一個路由器。這樣，每一個路由器都能夠知道網路的結構以及狀態。

步驟四：使用一個合適的演算法，確定網路中兩個節點之間的最佳路由。

路由演算法有哪些類型？路由演算法與路由協議的區別

在這一步中，路由器選擇通往每一個節點的最佳路由。它們使用一個演算法來實現這一點，如Dijkstra最短路徑演算法。在這個演算法中，一個路由器通過收集到的其他路由器的信息，建立一個網路圖。這個圖描述網路中的路由器的位置以及它們之間的鏈接關系。每個鏈接都有一個數字標注，稱為權值或成本。這個數字是延時和平均流量的函數，有時它僅僅表示節點間的躍點數。例如，如果一個節點與目的地之間有兩條鏈路，路由器將選擇權值最低的鏈路。

二、動態路由演算法

1.距離向量路由演算法

距離向量路由演算法，也叫做最大流量演演算法，其被距離向量協議作為一個演算法，如RIP、BGP、ISO IDRP、NOVELL IPX。使用這個演算法的路由器必須掌握這個距離表(它是一個一維排列-「一個向量」)，它告訴在網路中每個節點的最遠和最近距離。在距離表中的這個信息是根據臨近接點信息的改變而時時更新的。表中數據的量和在網路中的所有的接點(除了它自己本身)是等同的。這個表中的列代表直接和它相連的鄰居，行代表在網路中的所有目的地。每個數據包括傳送數據包到每個在網上的目的地的路徑和距離/或時間在那個路徑上來傳輸(我們叫這個為「成本」)。這個在那個演算法中的度量公式是跳躍的次數，等待時間，流出數據包的數量，等等。在距離向量路由演算法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當網路拓撲結構發生變化時，路由器之間也將及時地相互通知有關變更信息。其優點是演算法簡單容易實現。缺點是慢收斂問題，路由器的路徑變化需要像波浪一樣從相鄰路由器傳播出去，過程緩慢。

每一個相鄰路由器發送過來的路由表都要經過以下步驟：

步驟一：對地址為X的路由器發過來的路由表，先修改此路由表中的所有項目：把」下一跳」欄位中的地址改為X，並把所有」距離」欄位都加1。

步驟二：對修改後的路由表中的每一個項目，進行以下步驟：

（1）將X的路由表(修改過的)，與S的路由表的目的網路進行對比。若在X中出現，在S中沒出現，則將X路由表中的這一條項目添加到S的路由表中。

（2）對於目的網路在S和X路由表中都有的項目進行下面步驟：

1）在S的路由表中，若下一跳地址是x，則直接用X路由表中這條項目替換S路由表中的項目。

2）在S的路由表中，若下一跳地址不是x，若X路由表項目中的距離d小於S路由表中的距離，則進行更新。

步驟三：若3分鍾還沒有收到相鄰路由器的更新表，則把此相鄰路由器記為不可到達路由器，即把距離設置為16。

2.鏈路狀態最短路由優先演算法SPF

1）發現鄰居結點，並學習它們的網路地址；

2）測量到各鄰居節點的延遲或者開銷；

3）創建鏈路狀態分組；

4）使用擴散法發布鏈路狀態分組；

5）計算到每個其它路由器的最短路徑。

⑤ 距離向量路由演算法

距離向量路由演算法(Bellman-Ford Routing Algorithm)，也叫做最大流量演演算法(Ford-Fulkerson Algorithm)， 相應的圖片
其被距離向量協議作為一個演算法，如RIP, BGP, ISO IDRP, NOVELL IPX。使用這個演算法的路由器必須掌握這個距離表(它是一個一維排列-「一個向量」)，它告訴在網路中每個節點的最遠和最近距離。在距離表中的這個信息是根據臨近接點信息的改變而時時更新的。表中數據的量和在網路中的所有的接點(除了它自己本身)是等同的。這個表中的列代表直接和它相連的鄰居，行代表在網路中的所有目的地。每個數據包括傳送數據包到每個在網上的目的地的路徑和距離/或時間在那個路徑上來傳輸(我們叫這個為「成本」)。這個在那個演算法中的度量公式是跳躍的次數， 等待時間，流出數據包的數量，等等。 在距離向量路由演算法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當網路拓撲結構發生變化時，路由器之間也將及時地相互通知有關變更信息。

路由表的建立和更新
如上圖，有三個路由器，A，B和C。路由器A的兩個網路介面E0和S0 分別連接在 10.1.0.0和10.2.0.0網段上；路由器B的兩個網路介面S0和S1 分別連接在 10.2.0.0和10.3.0.0網段上；路由器C的兩個網路介面S0和E0 分別連接在 10.3.0.0和10.4.0.0網段上； 如上圖中各路由表的前兩行所示，通過路由表的網路介面到與之直接相連的網 絡的網路連接，其向量距離設置為0。這即是最初的路由表。 當路由器B和A以及B和C之間相互交換路由信息後，它們會更新各自的路由表。 例如，路由器B通過網路埠S1收到路由器C的路由信息（10.3.0.0,S0,0）和(10.4.0.0,E0,0) 靜態路由的具體配置
後，在自己的路由表中增加一條(10.4.0.0,S1,1)路由信息。該信息表示：通過路由器B的網路接 口S1可以訪問到10.4.0.0網段，其向量距離為1,該向量距離是在路由器C的基礎上加1獲得的。 同樣道理，路由器B還會產生一條(10.1.0.0,S0,1)路由，這條路由是通過網路埠S0從路由器A 獲得的。如此反復，直到最終收斂，形成圖中所示的路由表。 概括地說，距離向量演算法要求每一個路由器把它的整個路由表發送給與它直接連接的其它路由 器。路由表中的每一條記錄都包括目標邏輯地址、相應的網路介面和該條路由的向量距離。當一個路 由器從它的相鄰處收到更新信息時，它會將更新信息與本身的路由表相比較。如果該路由器比較出一條 新路由或是找到一條比當前路由更好的路由時，它會對路由表進行更新：將從該路由器到鄰居之間的 向量距離與更新信息中的向量距離相加作為新路由的向量距離。
參與運算信息
目的地址：在演算法的IP實現中，這指的是主機或的IP 地址。 下一跳地址：到信宿的路由中的第一個路由器。 介面：用於到下一跳物理。 metric值：一個數，指明本路由器到信宿的開銷。 定時器：路由項最後一次被修改的時間。 路由標記：區分路由為內部路由協議的路由還是外部路由協議的路由的標記。
運算
路由器間交換的最重要的信息是修改報文，參加路由維護計劃的路由器發送當前存在於實體的描述路由庫的路由修改報文。僅通過相鄰路由器間交換路由信息是可以維護整個系統的最佳路由的，這在接下來的討論中會逐步得到證明。 距離向量演算法總是基於一個這樣的事實：路由庫中的路由已是目前通過報文交換而得到的最佳路由。同時，報文交換僅限於相鄰的實體間，也就是說，實體共享同一個。當然，要定義路由是最佳的，就必須有衡量的辦法，這就用到前面所說的「metric」。RIP簡單的中，通常用可行路由所經的路由器數簡單地計算metric值。在復雜的中，metric一般代表該路由傳輸報的延遲或其它發送開銷。 令D代表從實體i到實體j的最佳路由的metric值，d（i，j）代表從i直接到j的開銷，因為開銷是可加的，演算法中最佳路由如此獲取表示： D（i，i）=0， 對所有的i D（i，j）=MIN[d（i，j）+D（k，j）， 當i不等於k時 實體i從相鄰路由器k收到k到j的開銷的估計D，i將D（i，j）加上i到k的開銷估計d（i，j），i比較從所有相鄰路由器得到的數值，取得最小數，就得到了它到j的最佳路由。

⑥ 路由協議的常用分析

路由分為靜態路由和動態路由，其相應的路由表稱為靜態路由表和動態路由表。靜態路由表由網路管理員在系統安裝時根據網路的配置情況預先設定，網路結構 發生變化後由網路管理員手工修改路由表。動態路由隨網路運行情況的變化而變化，路由器根據路由協議提供的功能自動計算數據傳輸的最佳路徑，由此得到動態路由表。
根據路由演算法，動態路由協議可分為距離向量路由協議（Distance Vector Routing Protocol）和鏈路狀態路由協議（Link State Routing Protocol）。距離向量路由協議基於Bellman-Ford演算法，主要有RIP、IGRP（IGRP為 Cisco公司的私有協議）；鏈路狀態路由協議基於圖論中非常著名的Dijkstra演算法，即最短優先路徑（Shortest Path First， SPF）演算法，如OSPF。在距離向量路由協議中，路由器將部分或全部的路由表傳遞給與其相鄰的路由器；而在鏈路狀態路由協議中，路由器將鏈路狀態信息傳 遞給在同一區域內的所有路由器。 根據路由器在自治系統（AS）中的位置，可將路由協議分為內部網關協議 （Interior Gateway Protocol，IGP）和外部網關協議（External Gateway Protocol，EGP，也叫域 間路由協議）。域間路由協議有兩種：外部網關協議（EGP）和邊界網關協議（BGP）。EGP是為一個簡單的樹型拓撲結構而設計的，在處理選路循環和設置 選路策略時，具有明顯的缺點，已被BGP代替。
EIGRP是Cisco公司的私有協議，是一種混合協議，它既有距離向量路由協議的特點，同時又繼承了鏈路狀態路由協議的優點。各種路由協議各有特點，適合不同類型的網路。下面分別加以闡述。 靜態路由表在開始選擇路由之前就被網路管理員建立，並且只能由網路管理員更改，所以只適於網路傳輸狀態比較簡單的環境。靜態路由具有以下特點：
· 靜態路由無需進行路由交換，因此節省網路的帶寬、CPU的利用率和路由器的內存。
· 靜態路由具有更高的安全性。在使用靜態路由的網路中，所有要連到網路上的路由器都需在鄰接路由器上設置其相應的路由。因此，在某種程度上提高了網路的安全性。
· 有的情況下必須使用靜態路由，如DDR、使用NAT技術的網路環境。
靜態路由具有以下缺點：
· 管理者必須真正理解網路的拓撲並正確配置路由。
· 網路的擴展性能差。如果要在網路上增加一個網路，管理者必須在所有路由器上加一條路由。
· 配置煩瑣，特別是當需要跨越幾台路由器通信時，其路由配置更為復雜。 動態路由協議內部網關協議IGP和外部網關協議EGP。而內部網關協議IGP可以分為距離矢量路由協議和鏈路狀態路由協議，兩種協議各有特點，分述如下：
1. 距離矢量（DV）協議
距離向量指協議使用跳數或向量來確定從一個設備到另一個設備的距離。不考慮每跳鏈路的速率。
距離向量路由協議不使用正常的鄰居關系，用兩種方法獲知拓撲的改變和路由的超時：
· 當路由器不能直接從連接的路由器收到路由更新時；
· 當路由器從鄰居收到一個更新，通知它網路的某個地方拓撲發生了變化。
在小型網路中（少於100個路由器，或需要更少的路由更新和計算環境），距離向量路由協議運行得相當好。當小型網路擴展到大型網路時，該演算法計算新路 由的收斂速度極慢，而且在它計算的過程中，網路處於一種過渡狀態，極可能發生循環並造成暫時的擁塞。再者，當網路底層鏈路技術多種多樣，帶寬各不相同時， 距離向量演算法對此視而不見。
距離向量路由協議的這種特性不僅造成了網路收斂的延時，而且消耗了帶寬。隨著路由表的增大，需要消耗更多的CPU資源，並消耗了內存。
2. 鏈路狀態（LS）路由協議
鏈路狀態路由協議沒有跳數的限制，使用「圖形理論」演算法或最短路徑優先演算法。
鏈路狀態路由協議有更短的收斂時間、支持VLSM（可變長子網掩碼）和CIDR。
鏈路狀態路由協議在直接相連的路由之間維護正常的鄰居關系。這允許路由更快收斂。鏈路狀態路由協議在會話期間通過交換Hello包（也叫鏈路狀態信息）創建對等關系，這種關系加速了路由的收斂。
3.鏈路狀態路由協議和距離向量路由協議的比較
不像距離向量路由協議那樣，更新時發送整個路由表。鏈路狀態路由協議只廣播更新的或改變的網路拓撲，這使得更新信息更小，節省了帶寬和CPU利用率。另外，如果網路不發生變化，更新包只在特定的時間內發出（通常為30min到2h）。
4 常用動態路由協議的分析
4.1 RIP（國際公有，最古老的路由協議，不過有很多缺陷）
RIP（路由信息協議）是路由器生產商之間使用的第一個開放標准，是最廣泛的路由協議，在所有IP路由平台上都可以得到。當使用RIP時，一台 Cisco路由器可以與其他廠商的路由器連接。RIP有兩個版本：RIPv1和RIPv2，它們均基於經典的距離向量路由演算法，最大跳數為15跳。
RIPv1是有類路由（Classful Routing）協議，因路由上不包括掩碼信息，所以網路上的所有設備必須使用相同的子網掩碼，不支持VLSM。RIPv2可發送子網掩碼信息，是無類路由（Classless Routing）協議，支持VLSM。
RIP使用UDP數據包更新路由信息。路由器每隔30s更新一次路由信息，如果在180s內沒有收到相鄰路由器的回應，則認為去往該路由器的路由不可用，該路由器不可到達。如果在240s後仍未收到該路由器的應答，則把有關該路由器的路由信息從路由表中刪除。
RIP具有以下特點：
· 不同廠商的路由器可以通過RIP互聯；
· 配置簡單； · 適用於小型網路（小於15跳）；
· RIPv1不支持VLSM；
· 需消耗廣域網帶寬；
· 需消耗CPU、內存資源。
RIP的演算法簡單，但在路徑較多時收斂速度慢，廣播路由信息時佔用的帶寬資源較多，它適用於網路拓撲結構相對簡單且數據鏈路故障率極低的小型網路中，在大型網路中，一般不使用RIP。
4.2 IGRP（已經退出歷史的舞台）
內部網關路由協議（Interior Gateway Routing Protocol，IGRP）是Cisco公司20世紀80年代開發的，是一 種動態的、長跨度（最大可支持255跳）的路由協議，使用度量（向量）來確定到達一個網路的最佳路由，由延時、帶寬、可靠性和負載等來計算最優路由，它在 同個自治系統內具有高跨度，適合復雜的網路。Cisco IOS允許路由器管理員對IGRP的網路帶寬、延時、可靠性和負載進行權重設置，以影響度量的計 算。
像RIP一樣，IGRP使用UDP發送路由表項。每個路由器每隔90s更新一次路由信息，如果270s內沒有收到某路由器的回應，則認為該路由器不可到達；如果630s內仍未收到應答，則IGRP進程將從路由表中刪除該路由。
與RIP相比，IGRP的收斂時間更長，但傳輸路由信息所需的帶寬減少，此外，IGRP的分組格式中無空白位元組，從而提高了IGRP的報文效率。但IGRP為Cisco公司專有，僅限於Cisco產品。
4.3 EIGRP（思科私有）
隨著網路規模的擴大和用戶需求的增長，原來的IGRP已顯得力不從心，於是，Cisco公司又開發了增強的IGRP，即EIGRP。EIGRP使用與IGRP相同的路由演算法，但它集成了鏈路狀態路由協議和距離向量路由協議的長處，同時加入散播更新演算法（DUAL）。
EIGRP具有如下特點：
· 快速收斂。快速收斂是因為使用了散播更新演算法，通過在路由表中備份路由而實現，也就是到達目的網路的最小開銷和次最小開銷（也叫適宜後繼， feasible successor）路由都被保存在路由表中，當最小開銷的路由不可用時，快速切換到次最小開銷路由上，從而達到快速收斂的目的。
· 減少了帶寬的消耗。EIGRP不像RIP和IGRP那樣，每隔一段時間就交換一次路由信息，它僅當某個目的網路的路由狀態改變或路由的度量發生變 化時，才向鄰接的EIGRP路由器發送路由更新，因此，其更新路由所需的帶寬比RIP和EIGRP小得多——這種方式叫觸發式（triggered）。
· 增大網路規模。對於RIP，其網路最大隻能是15跳（hop），而EIGRP最大可支持255跳（hop）。
· 減少路由器CPU的利用。路由更新僅被發送到需要知道狀態改變的鄰接路由器，由於使用了增量更新，EIGRP比IGRP使用更少的CPU。
· 支持可變長子網掩碼。
· IGRP和EIGRP可自動移植。IGRP路由可自動重新分發到EIGRP中，EIGRP也可將路由自動重新分發到IGRP中。如果願意，也可以關掉路由的重分發。
· EIGRP為模塊化設計，支持三種可路由的協議（IP、IPX、AppleTalk），更新版本支持IPv6。
· 支持非等值路徑的負載均衡。
· 因EIGIP是Cisco公司開發的專用協議，因此，當Cisco設備和其他廠商的設備互聯時，不能使用EIGRP
4.4 OSPF（國際公有）
開放式最短路徑優先（Open Shortest Path First，OSPF）協議是一種為IP網路開發的內部網關路由選擇協議，由IETF開 發並推薦使用。OSPF協議由三個子協議組成：Hello協議、交換協議和擴散協議。其中Hello協議負責檢查鏈路是否可用，並完成指定路由器及備份指 定路由器；交換協議完成「主」、「從」路由器的指定並交換各自的路由資料庫信息；擴散協議完成各路由器中路由資料庫的同步維護。
OSPF協議具有以下優點：
· OSPF能夠在自己的鏈路狀態資料庫內表示整個網路，這極大地減少了收斂時間，並且支持大型異構網路的互聯，提供了一個異構網路間通過同一種協議交換網路信息的途徑，並且不容易出現錯誤的路由信息。 · OSPF支持通往相同目的的多重路徑。
· OSPF使用路由標簽區分不同的外部路由。
· OSPF支持路由驗證，只有互相通過路由驗證的路由器之間才能交換路由信息；並且可以對不同的區域定義不同的驗證方式，從而提高了網路的安全性。
· OSPF支持費用相同的多條鏈路上的負載均衡。
· OSPF是一個無類路由協議，路由信息不受跳數的限制，減少了因分級路由帶來的子網分離問題。
· OSPF支持VLSM和無類路由查表，有利於網路地址的有效管理。
· OSPF使用AREA對網路進行分層，減少了協議對CPU處理時間和內存的需求。
4.5 BGP
BGP用於連接Internet。BGPv4是一種外部的路由協議。可認為是一種高級的距離向量路由協議。
在BGP網路中，可以將一個網路分成多個自治系統。自治系統間使用eBGP廣播路由，自治系統內使用iBGP在自己的網路內廣播路由。
Internet由多個互相連接的商業網路組成。每個企業網路或ISP必須定義一個自治系統號（ASN）。這些自治系統號由IANA （Internet Assigned Numbers Authority）分配。共有65535個可用的自治系統號，其中65512~65535為私 用保留。當共享路由信息時，這個號碼也允許以層的方式進行維護。
BGP使用可靠的會話管理，TCP中的179埠用於觸發Update和Keepalive信息到它的鄰居，以傳播和更新BGP路由表。
在BGP網路中，自治系統有： 1. Stub AS
只有一個入口和一個出口的網路。
2. 轉接AS（Transit AS）
當數據從一個AS到另一個AS時，必須經過Transit AS。
如果企業網路有多個AS，則在企業網路中可設置Transit AS。
IGP和BGP最大的不同之處在於運行協議的設備之間通過的附加信息的總數不同。IGP使用的路由更新包比BGP使用的路由更新包更小（因此BGP承載更多的路由屬性）。BGP可在給定的路由上附上很多屬性。
當運行BGP的兩個路由器開始通信以交換動態路由信息時，使用TCP埠179，他們依賴於面向連接的通信（會話）。
BGP必須依靠面向連接的TCP會話以提供連接狀態。因為BGP不能使用Keepalive信息（但在普通頭上存放有Keepalive信息，以允許 路由器校驗會話是否Active）。標準的Keepalive是在電路上從一個路由器送往另一個路由器的信息，而不使用TCP會話。路由器使用電路上的這 些信號來校驗電路沒有錯誤或沒有發現電路。 某些情況下，需要使用BGP：
· 當你需要從一個AS發送流量到另一個AS時；
· 當流出網路的數據流必須手工維護時；
· 當你連接兩個或多個ISP、NAP（網路訪問點）和交換點時。
以下三種情況不能使用BGP：
· 如果你的路由器不支持BGP所需的大型路由表時；
· 當Internet只有一個連接時，使用默認路由；
· 當你的網路沒有足夠的帶寬來傳送所需的數據時（包括BGP路由表）。

⑦ SPF 和 DUAL 兩種演算法有什麼區別

SPF演算法是OSPF路由協議的基礎;DUAL（擴散更新）演算法被EIGRP路由協議採用。
介紹下：
四種最常見路由協議是RIP、IGRP、OSPF和EIGRP。
1.RIP（Routing Information Protocol，路由信息協議）是使用最廣泛的距離向量協議，它是由施樂（Xerox）在20世紀70年代開發的。最大的特點是，其實現原理和配置方法都非常簡單。RIP基於跳數計算路由，並且定期向鄰居路由器發送更新消息。
2.IGRP是Cisco專有的協議，只在Cisco路由器中實現。它也屬於距離向量類協議，所以在很多地方與RIP有共同點，比如廣播更新等。它和RIP最大的區別表現在度量方法、負載均衡等幾方面。IGRP支持多路徑上的加權負載均衡，這樣，網路的帶寬可以得到更加合理的利用。另外，與RIP僅使用跳數作為度量依據不同，IGRP使用了多種參數，構成復合的度量值，這其中可以包含的因素有：帶寬、延遲、負載、可靠性和MTU（最大傳輸單元）等。

3.OSPF協議是20世紀80年代後期開發的，20世紀90年代初成為工業標准，是一種典型的鏈路狀態協議。OSPF的主要特性包括：支持VLSM（變長的子網掩碼）、收斂迅速、帶寬佔用率低等。等。OSPF協議在鄰居之間交換鏈路狀態信息，以便路由器建立鏈路狀態資料庫（LSD）之後，路由器根據資料庫中的信息利用SPF（Shortest Path First，最短路徑優先）演算法計算路由表，選擇路徑的主要依據是帶寬。
4.EIGRP是IGRP的增強版，它也是Cisco專有的路由協議。EIGRP採用了擴散更新（DUAL）演算法，在某種程度上，它和距離向量演算法相似，但具有更短的收斂時間和更好的可操作性。作為對IGRP的擴展，EIGRP支持多種可路由的協議，如IP、IPX和AppleTalk等。運行在IP環境時，EIGRP還可以與IGRP進行平滑的連接，因為它們的度量方法是一致的。

以上4種路由協議都是域內路由協議，它們通常使用在自治系統的內部。當進行自治系統間的連接時，往往採用諸如BGP（Border Gateway Protocols，邊界網關協議）和EGP（External Gateway Protocols，外部網關協議）這樣的域間路由協議。目前在Internet上使用的域間路由協議是BGP第四版。

⑧ 敘述路由器的工作原理及工作過程

傳統地，路由器工作於OSI七層協議中的第三層，其主要任務是接收來自一個網路介面的數據包，根據其中所含的目的地址，決定轉發到下一個目的地址。因此，路由器首先得在轉發路由表中查找它的目的地址，若找到了目的地址，就在數據包的幀格前添加下一個MAC地址，同時IP數據包頭的TTL（Time To Live）域也開始減數，並重新計算校驗和。當數據包被送到輸出埠時，它需要按順序等待，以便被傳送到輸出鏈路上。

路由器在工作時能夠按照某種路由通信協議查找設備中的路由表。如果到某一特定節點有一條以上的路徑，則基本預先確定的路由准則是選擇最優（或最經濟）的傳輸路徑。由於各種網路段和其相互連接情況可能會因環境變化而變化，因此路由情況的信息一般也按所使用的路由信息協議的規定而定時更新。

網路中，每個路由器的基本功能都是按照一定的規則來動態地更新它所保持的路由表，以便保持路由信息的有效性。為了便於在網路間傳送報文，路由器總是先按照預定的規則把較大的數據分解成適當大小的數據包，再將這些數據包分別通過相同或不同路徑發送出去。當這些數據包按先後秩序到達目的地後，再把分解的數據包按照一定順序包裝成原有的報文形式。路由器的分層定址功能是路由器的重要功能之一，該功能可以幫助具有很多節點站的網路來存儲定址信息，同時還能在網路間截獲發送到遠地網段的報文，起轉發作用；選擇最合理的路由，引導通信也是路由器基本功能；多協議路由器還可以連接使用不同通信協議的網路段，成為不同通信協議網路段之間的通信平台。

一般來說，路由器的主要工作是對數據包進行存儲轉發，具體過程如下：

第一步：當數據包到達路由器，根據網路物理介面的類型，路由器調用相應的鏈路層功能模塊，以解釋處理此數據包的鏈路層協議報頭。這一步處理比較簡單，主要是對數據的完整性進行驗證，如CRC校驗、幀長度檢查等。

第二步：在鏈路層完成對數據幀的完整性驗證後，路由器開始處理此數據幀的IP層。這一過程是路由器功能的核心。根據數據幀中IP包頭的目的IP地址，路由器在路由表中查找下一跳的IP地址；同時，IP數據包頭的TTL（Time To Live）域開始減數，並重新計算校驗和（Checksum）。

第三步：根據路由表中所查到的下一跳IP地址，將IP數據包送往相應的輸出鏈路層，被封裝上相應的鏈路層包頭，最後經輸出網路物理介面發送出去。

簡單地說，路由器的主要工作就是為經過路由器的每個數據包尋找一條最佳傳輸路徑，並將該數據包有效地傳送到目的站點。由此可見，選擇最佳路徑策略或叫選擇最佳路由演算法是路由器的關鍵所在。為了完成這項工作，在路由器中保存著各種傳輸路徑的相關數據——路由表（Routing Table），供路由選擇時使用。上述過程描述了路由器的主要而且關鍵的工作過程，但沒有說明其它附加性能，例如訪問控制、網路地址轉換、排隊優先順序等。

⑨ rip路由表更新演算法題

RIP是距離矢量，按照管理距離最短來尋路。
N1： 從A->D->N1 = 5, 從C->N1 = 3, A->C=2, 因此 N1的nexthop=C,或者D都可以，距離都是5
如果開啟備份路由，則加入FIB，作為備份
N2： 從A->C->N2 = 2, 從A->C = 2, 因此不變
N3：直連最優
N4：不變
N5：加入FIB，A->N5, 分為A-C->N5，因此距離=5，下一跳C

⑩ 什麼是路由啊 路由的組成 以及路由的演算法

路由：路由（routing）是指分組從源到目的地時，決定端到端路徑的網路范圍的進程。路由工作在OSI參考模型第三層——網路層的數據包轉發設備。路由器通過轉發數據包來實現網路互連。雖然路由器可以支持多種協議（如TCP/IP、IPX/SPX、AppleTalk等協議），但是在我國絕大多數路由器運行TCP/IP協議。路由器通常連接兩個或多個由IP子網或點到點協議標識的邏輯埠，至少擁有1個物理埠。路由器根據收到數據包中的網路層地址以及路由器內部維護的路由表決定輸出埠以及下一跳地址，並且重寫鏈路層數據包頭實現轉發數據包。路由器通過動態維護路由表來反映當前的網路拓撲，並通過網路上其他路由器交換路由和鏈路信息來維護路由表。

路由器的組成：

1. RAM（隨機存儲器）

   功能：存放路由表；存放ARP告訴緩存；存放快速交換緩存；存放分組交換緩沖；存放解壓後的IOS；路由器加電後，存放running配置文件；

   特點：重啟或者斷電後，RAM中的內容丟失。

2. NVRAM（非易失性RAM）

   功能：存儲路由器的startup配置文件；存儲路由器的備份。

   特點：重啟或者斷電後內容不丟失。

3. FLASH（快速快閃記憶體）

   功能：存放IOS和微代碼。

   特點：重啟或者斷電後內容不丟失；可存放多個IOS版本（在容量許可的前提下）；允許軟體升級不需替換CPU中的晶元。

4. ROM(只讀存儲器)

   功能：存放POST診斷所需的指令；存放mini-ios；存放ROM監控模式的代碼。

   特點：ROM中的軟體升級需要更換CPU的晶元（還好這種情況比較少遇到)

5. CPU（中央處理器）

   衡量路由器性能的重要指標，負責路由計算，路由選擇等。

6. 背板：

   背板能力是一個重要參數，尤其在交換機中。

路由演算法：又名選路演算法，可以根據多個特性來加以區分。演算法的目的是找到一條從源路由器到目的路由器的「好」路徑（即具有最低費用的路徑[1]）。演算法設計者的特定目標影響了該路由協議的操作；具體來說存在著多種路由演算法，每種演算法對網路和路由器資源的影響都不同；由於路由演算法使用多種度量標准（metric），從而影響到最佳路徑的計算。

演算法分類：主要有RIP、IGRP（IGRP為 Cisco公司的私有協議）；鏈路狀態路由協議基於圖論中非常著名的Dijkstra演算法，即最短優先路徑（Shortest Path First， SPF）演算法，如OSPF。在距離向量路由協議中，路由器將部分或全部的路由表傳遞給與其相鄰的路由器；而在鏈路狀態路由協議中，路由器將鏈路狀態信息傳 遞給在同一區域內的所有路由器。 根據路由器在自治系統（AS）中的位置，可將路由協議分為內部網關協議 （Interior Gateway Protocol，IGP）和外部網關協議（External Gateway Protocol，EGP，也叫域 間路由協議）。域間路由協議有兩種：外部網關協議（EGP）和邊界網關協議（BGP）。EGP是為一個簡單的樹型拓撲結構而設計的，在處理選路循環和設置 選路策略時，具有明顯的缺點，已被BGP代替。