[發明專利]實現多下一跳路由的方法、裝置及系統

有效

• 申請號: 200910246316.8
• 申請日: 2009-11-25
• 公開（公告）號: CN101702686A
• 公開（公告）日: 2010-05-05
• 發明（設計）人: 朱宣勇;陳庶樵;羅偉;蘭巨龍;黃健美;田銘;關禮安
• 申請（專利權）人: 中國人民解放軍信息工程大學
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 逯長明;王寶筠

技術領域

本發明涉及計算機網絡及通訊技術領域，尤其涉及一種實現多下一跳路 由的方法、裝置及系統。

背景技術

路由問題是通訊網絡研究中的一個核心問題，路由算法的優劣直接影響 著網絡通訊的性能。當前因特網路由普遍應用的是基于最短路徑優先 （Shortest?Path?First，SPF）原則的單下一跳路由算法，無論是采用距離矢 量機制（例如路由信息協議RIP），還是鏈路狀態機制（例如開放式最短路徑 優先OSPF），都是由網絡節點計算自身到目的地的最短路徑，選取唯一的下 一跳進行傳輸。在實際中，這種路由算法總是傾向于選取處理能力強的節點 和鏈路，難以充分利用網絡資源，往往造成傳輸路徑的集中，引發傳輸擁塞。

參見圖1，圖1中所示網絡中的網絡節點有A、B1～B3、C1～C3、D?1～D3， 以節點A作為網絡出口節點。

以節點A為出口，采用SPF算法計算得到的單下一跳路由，其中各節點 之間標注的數值代表拓撲代價值（花費），代價值越低表明所耗資源越低，優 選由代價值低構成的鏈路。如圖1中帶有箭頭的最粗直線所示：帶有箭頭的 最粗直線代表參與路由的鏈路，箭頭表示數據流向，其他直線代表的鏈路未 參與路由?？梢钥闯觯W絡中的流量集中到D1→C1→B1→A這條路徑上， 而此時還有大量可行鏈路處于閑置狀態。

為了彌補單下一跳路由的不足，提出了多徑路由的概念，意在找出到目 的地的數條傳輸路徑同時參與傳輸，從而達到均衡網絡流量，更充分地利用 網絡資源的目的。

當前的多徑路由算法主要分為兩大類，一類是采用集中式計算的源路由 算法，此類算法往往是面向連接的，針對源點到目的地間計算并維護多條完 整的傳輸路徑，大多數基于服務質量（Quality?of?Service，QoS）需求和基于 多協議標簽交換（Multi-protocol?Label?Switching，MPLS）技術的多徑路由 算法都屬此類。這些算法往往針對特定問題，有較大的計算和維護花費，實 現復雜，需要特殊技術支持。另一類是對當前分布式計算的單下一跳路由算 法進行擴展，通過放寬最短路徑限制，允許各點選取到目的地距離比自身近 的鄰居作為可用的下一跳，從而產生多條傳輸路徑。此類算法對現行的路由 機制改變較小，相對于源路由更易于實現，可以采用距離矢量機制（例如多 路徑距離矢量算法MDVA），也可以采用鏈路狀態機制（例如多路徑算法 MPA）。但此類算法選路的策略還不夠靈活，難以更加充分有效的利用網絡資 源，合理的規劃網絡流向，可挖掘的潛力有限。

發明內容

本發明提供一種實現多下一跳路由的方法、裝置及系統，以解決現有路 由方案由于單下一跳路由造成的網絡流量不均衡、網絡資源利用率不高的問 題。

為此，本發明實施例采用如下技術方案：

一種實現多下一跳路由的方法，在網絡中各節點獲得全網的拓撲信息后， 執行以下步驟：網絡節點定序過程：各網絡出口節點以自身為根運行支撐樹 搜索算法，分別給網絡中所有節點定序，從而確定網絡中各個節點的序號， 所述各個節點的序號值不相等，以使得所述網絡中各個節點形成按序號從小 到大的嚴格隊列；多下一跳路由過程：執行從高序號節點向任意一個相鄰低 序號節點的數據轉發。

所述各網絡出口節點以自身為根運行支撐樹搜索算法，分別給網絡中所 有節點定序，從而確定網絡中各個節點的序號包括：網絡出口節點執行支撐 樹搜索算法，分別給網絡中所有節點定序，獲得網絡中各節點序號值；網絡 出口節點向全網節點泛洪包含所述各節點序號值的序號表。所述執行從高序 號節點向任意一個相鄰低序號節點的數據轉發包括：各節點根據收到的序號 表，獲得自身和所有鄰居的序號值；各節點針對不同的網絡出口，執行序號 值比較過程；確定所有序號值小于本節點序號值的鄰居節點都是所對應網絡 出口節點的下一跳節點，選擇一個下一跳節點進行數據轉發。

所述支撐樹搜索算法包括寬度優先搜索算法、深度優先搜索算法、最短 路徑樹搜索算法或最小支撐樹搜索算法。

一種實現多下一跳路由的網絡出口節點裝置，包括用于獲得網絡拓撲信 息的拓撲信息獲取單元，還包括：網絡節點定序單元，用于運行以所述網絡 出口節點為根的支撐樹搜索算法，分別給網絡中所有節點定序，從而確定對 網絡中各個節點的序號，所述各個節點的序號值不相等，以使得所述網絡中 各個節點形成按序號從小到大的嚴格隊列。