首頁>Club>
16
回覆列表
  • 1 # 使用者5212068048941

    擴散更新演算法(Diffusing Update Algorithm,DUAL)DUAL是一個收斂演算法,它代替了用於其它距離向量協議的Belloman-ford 演算法。DUAL演算法的設計思想是,即使暫時的路由選擇環路也會對一個網路的效能造成損害,所以為了能隨時打破路由環路,使用擴散計算執行了一個分散式最短路徑路由選擇。為了能正確操作DUAL,較低層協議必須滿足下面的條件:

    一個節點需要在有限的時間內發現一個新鄰居的存在或連線鄰居的丟失。

    在已經執行的鏈路上傳送的所有訊息必須在有限的時間內正確接收,並且包含正確的序列號。

    所有的訊息,包括鏈路代價改變、鏈路失敗和發現新鄰居的通告,都應該在一個有限的時間內一次一個的處理,並且應該被有順序的檢測到。這些條件由鄰居發現和恢復部分以及RTP共同支援。DUAL演算法中的術語:

    鄰接——剛啟動時,路由器透過Hello資料包發現鄰居並標識自己給鄰居識別。當鄰居被發現時,EIGRP協議會使路由器嘗試和它的鄰居建立鄰接關係。鄰接是指兩臺相互交換路由資訊的鄰居之間形成的一條邏輯關聯關係。只有鄰接關係建立後,路由器才能從它的鄰居處接收路由更新訊息。這裡的更新訊息包括髮送路由器知道的所有路由和這些路由的度量值。對於每一條路由,路由器都會基於鄰居通告距離(annunciate distance ,AD)和它到鄰居鏈路的代價計算出一個距離。

    可行距離(feasible distance ,FD)——本地路由器到達每個目的網路的最小度量值就是該目的網路的可行距離。

    可行條件(feasible condition, FC)——到達一個目標網路的鄰居通告距離必須小於本地路由器到達同一網路的距離。

    可行後繼路由器(feasible successor ,FS)——本地路由器的鄰居路由器所通告的到達目的網路的距離滿足FC,那麼這個鄰居路由器就為該網路的一個可行後繼路由器。EIGRP協議中,路由器將可行後繼路由器的資訊儲存在拓撲結構表中。

    拓撲結構表的組成:

    目的網路

    目的網路的可行距離

    可行後繼路由器地址

    本地路由器到達目的網路的距離

    可行後繼路由器的通告距離

    連線可行後繼路由器的介面

    後繼路由器——對於拓撲表中列出的每個目的網路,將選用最小度量的路由放在路由表中,通告這條路由的鄰居路由器就是後繼路由器。

    如果一臺可行後繼路由器通告的一條路由在本地路由器上所計算的度量比當前後繼路由器的度量小,那麼這臺可行後繼路由器將成為後繼路由器。

    如果到達後繼路由器的鏈路失效了,或者鏈路的代價增加並超過了可行距離,那麼這臺路由器將在拓撲結構表中查詢可行後繼路由器,若存在這樣一個可行後繼路由器,就讓其成為後繼路由器,這種選擇通常發生在次秒級別範圍。若路由器找不到可行後繼路由器,路由器就進行擴散計算。可行後繼路由器減少了擴散計算的數量,並提高了網路的效能。同時可行後繼路由器也降低了網路重收斂的次數。

    DUAL的有限狀態機當一個EIGRP的路由器不執行擴散計算時,每一條路由都處於被動狀態(passive).在產生輸入事件的任何時候,路由器都會重新評估一條路由的可行後繼路由器列表,輸入事件包括:

    直連鏈路的代價發生變化

    直連鏈路的狀態(UP或DOWN)發生變化

    收到一個新的更新訊息

    收到一個查詢訊息

    收到一個答覆訊息路由器重新評估的第一步,在本地路由器上執行一個本地計算,也就是對所有可行後繼路由器重新計算到達目的地的距離。可能的結果如下:

    如果擁有最低度量的可行後繼路由器和已經存在的後繼路由器不同,那麼該可行後繼路由器成為新的後繼路由器。

    如果最低度量小於FD值,更新FD。

    如果新的度量距離和已經存在的度量距離不同,向所有的鄰居傳送更新。當路由器執行一個本地計算時,路由依然保持被動狀態。如果路由器發現了一臺可行後繼路由器,那麼將傳送一個更新訊息給它的所有鄰居,但不改變路由狀態。如果沒有在拓撲結構表中發現任意一臺可行後繼路由器,那麼路由器將執行擴散計算,而且路由器的狀態變為活動狀態(active).在擴散計算完成和路由狀態變為被動狀態之前,路由器不能:

    改變路由的後繼路由器

    改變正在通告的路由的距離

    改變路由的FD值

    開始進行路由的另一個擴散計算路由器是透過向它的鄰居傳送查詢資料包,開始擴散計算的。查詢資料包包中包含新的本地路由器計算的到目的地的距離。收到查詢的路由器執行自己的本地計算:

    若該鄰居路由器上有到達目的網路的一個或多個可行後繼路由器,該鄰居就傳送一個答覆資料包給傳送查詢的源路由器,答覆資料包中將包含鄰居路由器計算的到達目的網路的最小距離。

    若該鄰居路由器上沒有到達目的地的可行後繼路由器,它將把這條路由的狀態置為活動狀態,並開始擴散計算。對於每一臺接收查詢的鄰居路由器,本地路由器會設定一個答覆狀態標記(reply status)來不斷的跟蹤所有未處理的查詢。當路由器收到所有傳送給鄰居路由器的查詢答覆時,擴散計算完成。當擴散計算開始時,一個活動計時器被初始化為3min,如果活動計時器超時後還沒有收到答覆資料包。那麼這條路由就被宣告為“卡”在活動狀態(stuck in active ,SIA).這些沒有答覆的鄰居將從鄰居表中刪除。並且擴散計算預設該鄰居答覆的為無窮大度量。

    #timer active-time %修改活動計時器時間 11

    在擴散計算完成時,路由器會將FD值置為無窮大,這樣可確保所有鄰居答覆中達到目的地的有限距離都能滿足FC,並且成為一臺可行後繼路由器。而後路由器會基於這些答覆訊息中的距離和傳送答覆的鄰居路由器的鏈路代價計算出到達目的網路的距離。並選出度量值最低的路由器成為後繼路由器,並把最低度量值設為FD。並且將不滿足FC的可行後繼路由器刪除。注意,在收到所有答覆之前不會選擇後繼路由器。

  • 中秋節和大豐收的關聯?
  • 南宋怎麼滅的金國?