擴散更新演算法

Ⅰ 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第四版。

Ⅱ 路由演算法的類型有

靜態路由演算法

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，路由器便可以計算出延時。（路程往返時間是網路當前延遲的量度，通過一個分組數據包從遠程主機返回的時間來測量。）該時間包括了傳輸和處理兩部分的時間——也就是將分組數據包發送到目的地的時間以及接收方處理分組數據包和應答的時間。

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

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

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

Ⅲ eigrp依靠什麼機制防環

EIGRP是思科私有的路由協議，翻譯過來就是增強型內部網關路由協議，也是混合型距離矢量和鏈路狀態路由協議，用我自己話說就是「四不像」。

它的防環機制是採用擴散更新演算法（DUAL），在運行EIGRP的路由器上保存著三張表：鄰居表、拓撲表、路由表。當一台路由器剛剛啟動EIGRP進程時，通過發送hello包來進行建立鄰居關系，交換路由信息，通過執行擴散更新演算法，鄰居之間互相通告AD，最後將演算法執行的結果寫進拓撲表，拓撲表中最優的條目即寫進路由表。你可以自己做個實驗，敲一下sh ip eigrp topology命令，就可以看到EIGRP的拓撲表。

EIGRP計算度量值的方法為：10的7次方除以鏈路的帶寬，加上沿途各個介面出方向的延遲delay，再乘以256.
同時在EIGRP里還有這樣幾個概念要清楚：
AD：鄰居通過來的到達目的網路的度量值；
FD：自己到達鄰居的度量值+鄰居通告過來的鄰居自己到達目的網路的AD；
S：FD值為最小的下一跳路由，也叫後繼路由；
FS：FD值為次小的下一跳路由，也叫可行性路由。

擴散更新演算法的核心就是：鄰居通告過來的AD，要小於自己目前最優的FD，這樣才會寫進自己的路由表，具備成為S的條件。

由於FS為備用的下一跳路由，在執行完擴散更新演算法後，備用的路由也選好了，所以當網路發生狀況時，EIGRP的收斂速度也就是very high。

另外EIGRP有5種包：hello包、發送路由更新的updata包、對路由更新進行確認的updataack包、當路由發生變化，查找不到S時發送的查詢query包、對查詢進行響應的query replay包，交換這些包依靠的是RTP可靠信息傳輸協議機制。

注意的是：EIGRP不像OSPF建立鄰居關系時是hello去hello回，而是發送hello去，對端路由返回來的直接就是路由信息。

這就是EIGRP里我自己了解的，最主要的還是看完書後，自己搭個拓撲做一下EIGRP的實驗，做完後驗證一下，對整個協議的運行過程也就熟悉了，這樣才能真正的把所學的東西變成是自己的。

Ⅳ 路由協議的常用分析

路由分為靜態路由和動態路由，其相應的路由表稱為靜態路由表和動態路由表。靜態路由表由網路管理員在系統安裝時根據網路的配置情況預先設定，網路結構 發生變化後由網路管理員手工修改路由表。動態路由隨網路運行情況的變化而變化，路由器根據路由協議提供的功能自動計算數據傳輸的最佳路徑，由此得到動態路由表。
根據路由演算法，動態路由協議可分為距離向量路由協議（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路由表）。

Ⅳ 常見的路由選擇演算法有哪些

鏈路狀態演算法（也稱最短路徑演算法）發送路由信息到互聯網上所有的結點，然而對於每個路由器，僅發送它的路由表中描述了其自身鏈路狀態的那一部分。距離向量演算法（也稱為Bellman-Ford演算法）則要求每個路由器發送其路由表全部或部分信息，但僅發送到鄰近結點上。從本質上來說，鏈路狀態演算法將少量更新信息發送至網路各處，而距離向量演算法發送大量更新信息至鄰接路由器。 ——由於鏈路狀態演算法收斂更快，因此它在一定程度上比距離向量演算法更不易產生路由循環。但另一方面，鏈路狀態演算法要求比距離向量演算法有更強的CPU能力和更多的內存空間，因此鏈路狀態演算法將會在實現時顯得更昂貴一些。除了這些區別，兩種演算法在大多數環境下都能很好地運行。