基於ospf協議的增量最短路徑樹計算方法
2023-09-14 11:46:35 1
專利名稱：基於ospf協議的增量最短路徑樹計算方法
技術領域：
本發明涉及網絡路由技術領域，特別涉及一種最短路徑樹計算方法。
背景技術：
對網際網路而言，故障是不可避免的。故障可導致連接中斷，危害網絡 服務，輕則導致分組丟失，重則使網絡癱瘓，因此網絡中的路由器應具備 對故障的自適應能力，當故障發生時能夠動態地調整路由，適應新的網絡 拓樸。隨著網際網路規模的迅速擴大，網絡故障數量明顯增加，並且隨著各 種應用的大量出現和廣泛使用，例如VoIP、在線^見頻等，人們對網絡端到 端性能的要求越來越高，現有的路由協議的自愈能力已不能夠滿足要求。
現有的路由協議的路由收斂時間較長，難以完全滿足用戶的需求。例 如，路由信息協議RIP (Routing Information Protocol)在故障發生後的自 愈時間在100秒的數量級，開放最短路徑優先協議OSPF( Open Shortest Path First)和ISIS (Intermediate System-Intermediate System)的3各由4欠症支時間 在幾秒到幾十秒之間。在收斂過程中，網絡路由可能是錯誤的，可導致分 組丟失，影響網絡應用。因此，需要一種方法解決上述問題。
發明內容
本發明的目的旨在至少解決上述技術缺陷之一，特別是解決路由收斂 慢的問題。
為了達到上述目的，本發明提出一種基於OSPF的增量最短路徑樹計 算方法，包括以下步驟路由器收到一條新的鏈路狀態通告，判斷變化鏈 路的權值是否增大；對所述權值增大或減小的變化鏈路，分別執行不同的 最短路徑樹更新操作，將更新元素保存在優先級隊列中；依次更新所述優 先級隊列中的隊首節點，搜索所述隊首節點的所有出邊，判斷能否為末節點提供更優的路徑。
作為本發明的一個實施例，所述根據變化鏈路的權值增大或減小，分
別執行不同的最短路徑樹更新操作，包括如果所述變化鏈路的權值增大 且不在所述最短路徑樹上，則保持所述最短路徑樹和路由表不變；如果所 述變化鏈路的權值增大且在所述最短路徑樹上，則搜索受到影響的以所述 變化鏈路的末節點為根的子樹中的節點的所有入邊，找到更優路徑，將更 新元素保存到優先級隊列中；如果所述變化鏈路的權值減小且不能為其末 節點提供更短路徑，則保持所述最短路徑樹和路由表不變；如果所述變化 鏈路的權值減小且能夠為其末節點提供更短路徑，則保持以所述末節點為 根節點的子樹的結構不變，更新所述子樹中各節點相應的最短路徑長度， 並搜索其他節點到所述子樹的所有入邊，找到更優路徑，然後將更新元素 保存到優先級隊列中。
作為本發明的一個實施例，所述更新元素包括受影響節點、新的父節 點和最短距離變化量。
本發明通過判斷變化鏈路權值增大或減小以及其是否在原最短路徑樹 上，找出受影響節點，採取增量方法更新原最短路徑樹，減少了最短路徑 樹重計算的時間，從而減少了故障收斂時間，同時，通過對路由表作出最 小的改變，提高了路由的穩定性。
本發明附加的方面和優點將在下面的描述中部分給出，部分將從下面 的描述中變得明顯，或通過本發明的實踐了解到。
本發明上述的和/或附加的方面和優點從下面結合附圖對實施例的描 述中將變得明顯和容易理解，其中
圖1為本發明實施例的基於OSPF協議的增量最短路徑樹計算方法的 流程圖2為本發明實施例的基於OSPF協議的增量最短路徑樹算法的實現 偽代碼。
具體實施例方式
下面詳細描述本發明的實施例，所述實施例的示例在附圖中示出，其
能的元件。下面通過參考附圖描述的實施例是示例性的，僅用於解釋本發 明，而不能解釋為對本發明的限制。
本發明主要在於當路由器收到新的鏈路狀態通告時，通過判斷變化鏈 路權值增大或減小以及其是否在原最短路徑樹上，找出受影響節點，採取 增量方法更新原最短路徑樹。
如圖1所示，為本發明實施例的基於OSPF的增量最短路徑樹計算方 法的流程圖。網絡路由器計算出正常路由後，保存以該路由器為根節點的 最短路徑樹。當路由器收到新的鏈路狀態通告時，首先判斷變化鏈路e的 權值是否增大，對於權值增大的鏈路和權值減小的鏈路，分別執行不同的 操作
對於權值增大的變化鏈路e，本發明提出的可能的計算方案如下，當然 本領域技術人員還能夠根據下述方案提出其他修改或變化，這些修改或變 化均應包含在本發明的包含範圍之內。
首先判斷變化鏈路e是否在最短路徑樹上。如果鏈路e不在最短路徑 樹上，則保持最短路徑樹和路由表不變；如果鏈路e在最短路徑樹上，則 以E(e)為根的子樹B(n)將受到影響，搜索受到影響的節點",的所有入邊，
找到一條可能的更優路徑，即路徑長度更短，然後將元素(受影響節點， 新的父節點，最短路徑變化量)保存到優先級隊列中。
對於權值減小的變化鏈路e,本發明提出的可能的計算方案如下，當然 本領域技術人員還能夠根據下屬方案提出其他修改或變化，這些修改或變 化均應包含在本發明的包含範圍之內。
首先判斷變換鏈路e能否為其末節點E(e)提供一條更短的路徑。如果 不能，則保持最短路徑樹和路由表不變；如果能，則以末節點E(e)為根節 點的子樹B(E(e))將受到影響，保持其結構不變，僅更新各節點相應的最短 路徑長度，而其他節點可能受到影響，搜索其所有到B(E(e))的入邊，以確 定能否找到一條更優的路徑。然後，將元素(受影響節點，新的父節點，最短距離變化量)保存到優先級隊列中。
然後，在優先級隊列不空的情況下，取出隊首元素，更新該隊首節點 的新的父節點及最短路徑長度。在本發明的實施例中，可以整體更新節點 及其子樹。更新完成後，搜索當前更新節點的所有出邊，判斷能否為末節 點提供一條更優的路徑。如果能，則將元素(受影響節點，新的父節點， 更新距離變化量)保存到優先級隊列中。
依次取出隊首元素進行上述更新操作，直至隊列為空，即對最短路徑 樹的增量更新完成，計算過程終止。
針對上述實施例，本發明的實現代碼如圖2所示。參考圖2中的增量 最短路徑樹算法的實現代碼，可以更清楚地了解本發明實施例的方面和優 點。
本發明通過判斷變化鏈路權值增大或減小以及其是否在原最短路徑樹 上，找出受影響節點，採取增量方法更新原最短路徑樹，減少了最短路徑 樹重計算的時間，從而減少了故障收斂時間，同時，通過對路由表作出最 小的改變，提高了路由的穩定性。
儘管已經示出和描述了本發明的實施例，對於本領域的普通技術人員 而言，可以理解在不脫離本發明的原理和精神的情況下可以對這些實施例 進行多種變化、修改、替換和變型，本發明的範圍由所附權利要求及其等 同限定。
權利要求
1、一種基於OSPF協議的增量最短路徑計算方法，其特徵在於，包括以下步驟路由器收到一條新的鏈路狀態通告，判斷變化鏈路的權值是否增大；根據所述變化鏈路的權值增大或減小，分別執行不同的最短路徑樹更新操作，將更新元素保存在優先級隊列中；依次更新所述優先級隊列中的隊首節點，搜索所述隊首節點的所有出邊，判斷能否為末節點提供更優的路徑。
2、 如權利要求1所述的基於OSPF協議的增量最短路徑計算方法，其 特徵在於，所述根據變化鏈路的權值增大或減小，分別執行不同的最短路 徑樹更新操作，包括如果所述變化鏈路的權值增大且不在所述最短路徑樹上，則保持所述 最短路徑樹和路由表不變；如果所述變化鏈路的權值增大且在所述最短路徑樹上，則搜索受到影 響的以所述變化鏈路的末節點為根的子樹中的節點的所有入邊，找到更優 路徑，將更新元素保存到優先級隊列中；如果所述變化鏈路的權值減小且不能為其末節點提供更短路徑，則保 持所述最短路徑樹和路由表不變；如果所述變化鏈路的權值減小且能夠為其末節點提供更短路徑，則保 持以所述末節點為根節點的子樹的結構不變，更新所述子樹中各節點相應 的最短路徑長度，並搜索其他節點到所述子樹的所有入邊，找到更優路徑， 然後將更新元素保存到優先級隊列中。
3、 如權利要求1所述的基於OSPF協議的增量最短路徑樹計算方法， 其特徵在於，所述更新元素包括受影響節點、新的父節點和最短距離變化 量。
4、 如權利要求1所述的基於OSPF協議的增量最短路徑樹計算方法， 其特徵在於，所述節點及其子樹可被整體地更新。
5、 如權利要求1所述的基於OSPF協議的增量最短路徑樹計算方法， 其特徵在於，所述計算過程的終止條件為所述優先級隊列為空。
全文摘要
本發明提出一種基於OSPF協議的增量最短路徑樹計算方法，包括以下步驟路由器收到一條新的鏈路狀態通告，判斷變化鏈路的權值是否增大；根據所述變化鏈路的權值增大或減小，分別執行不同的最短路徑樹更新操作，將更新元素保存在優先級隊列中；依次更新所述優先級隊列中的隊首節點，搜索所述隊首節點的所有出邊，判斷能否為末節點提供更優的路徑。本發明通過判斷變化鏈路權值增大或減小以及其是否在原最短路徑樹上，找出受影響節點，採取增量方法更新原最短路徑樹，減少了最短路徑樹重計算的時間，從而減少了故障收斂時間，同時，通過對路由表作出最小的改變，提高了路由的穩定性。
文檔編號H04L12/56GK101605096SQ20091008932
公開日2009年12月16日 申請日期2009年7月15日 優先權日2009年7月15日
發明者徐明偉, 琦 李, 芫 楊, 楊思傑 申請人:清華大學