一種多協議標籤交換網絡中的組播樹的優化方法
2023-11-06 04:04:47 2
專利名稱：一種多協議標籤交換網絡中的組播樹的優化方法
技術領域：
本發明屬於網絡通信技術領域，涉及一種多協議標籤交換網絡中組播 樹的優化方法。
背景技術：
組播是一點到多點的信息傳送方式。隨著網絡電視和視頻會議等網絡 多媒體應用日益廣泛，利用組播技術來支持點到多點、多點到多點通信是 減少帶寬消耗、提高服務質量的有效手段。在組播業務的實際應用中，組 播組成員經常隨時加入或退出組播組，網絡資源狀況也會因故障、恢復等 經常發生變化。TE ( Tra伍c Engineering流量工程)是一個強有力的工具。通過它可以 平衡網絡中不同的鏈路、路由器和交換機之間業務負荷，使所有這些設備 既不會過度使用，也不會未被充分使用。這樣就可以有效利用整個網絡的 資源，優化網絡流量。在MPLS (Multi-protocol Label Switching 多協議標 籤交換)網絡中，TE路徑的計算採用CSPF( Constraint Shortest Path First約 束最短路徑優先)算法。該算法需要綜合考慮路徑的cost (費用)、帶寬、鏈路屬性等因素，在源節點到目的節點之間選擇一條滿足約束條件的路徑。CSPF算法的計算步驟如下步驟一、裁減不滿足約束條件的鏈路；步驟二、選擇cost (費用)較低的路徑；步驟三、當存在多條COSt相同時路徑時，選擇各條路徑中最小可用帶寬是最大的路徑；步驟四、如果存在多條路徑，則選擇跳數最小的路徑；步驟五、如果仍然存在有多條路徑，根據配置的負載分擔策略選擇一 條路徑。通過CSPF算法選擇的路徑是最佳路徑，而非最短路徑，路徑上也不存 在負載分擔。下面結合附圖對MPLS網絡中組播的流量工程進行詳細描述。圖1所示 的是MPLS網絡中組播樹的示意圖。其中，S節點為源節點，即組播樹的根 節點，Rl為組播業務接收節點，即組播樹的葉子節點。假設圖中各條鏈路 的帶寬、費用、鏈路屬性等因素完全相同，在該組播樹上實現流量工程時， 通過CSPF算法可確定4艮節點S到葉子節點Rl的路徑是 S__〉A—>B—>C~>R1 ，此路徑共有4跳；當R2節點加入該組播樹成為葉子 節點後，通過CSPF算法可確定根節點到葉子節點R2的路徑是S—〉D—〉R2， 此路徑共有2跳；如果根節點S到葉子節點R1的路徑不變，則該組播數的總 跳數是6跳。如果S-R1的路由變為S-〉D->B-〉C->R1,則總跳數減少為5跳， 組播樹的整體費用有所降低。對於實時組播業務來說，需要儘可能的降低 組播樹傳輸延遲，降低傳輸開銷，因此這種優化是非常有意義的。現有技術中，當組播樹發生動態變化時，比如有新成員加入組播組， 而現有的組播的流量工程只能利用CSPF算法計算出根節點到新加入的葉子 節點之間的一條路徑，無法在組播組動態變化的情況下從整體上對組播樹 進行優化，建立連接源節點到目的節點的一棵整體費用最小的組播樹
發明內容
本發明提供了 一種多協議標籤交換網絡中的組播樹優化方法，用於解 決上述現有技術存在的無法在組播組動態變化的情況下從整體上對組播樹 進行優化，建立連接源節點到目的節點的一棵最小費用組播樹的問題。本發明的目的是通過以下技術方案實現的 一種多協議標籤交換網絡中的組播樹優化方法，包括 當組播樹變化時，計算組播樹的當前整體費用和組播樹的優化整體費用；判斷所述組播樹的優化整體費用是否小於所述當前整體費用，是則根 據所述組播樹的優化整體費用，切換所述組播樹的根節點到葉子節點之間 的路徑。其中，所述計算組播樹的優化整體費用具體包括計算從所述組播樹的根節點到所有葉子節點之間符合約束條件的全部 可選路徑以及相應的費用；對所述根節點到所有葉子節點符合約束條件的可選路徑進行組合；累加不同路徑組合對應的費用，對其路徑上重複的區段予以合併，得 出多個組播樹整體費用；比較所述多個組播樹整體費用，得出所述組播樹的優化整體費用以及 相應的路徑信息。其中，通過CSPF算法計算所述組播樹的根節點到所有葉子節點之間符 合約束條件的全部可選路徑。其中，所述計算組播樹的當前整體費用具體包括通過CSPF算法計算所述組播樹的根節點到發生變化的葉子節點之間的 一條滿足約束條件的最佳路徑以及相應的費用；累加從根節點到所有葉子節點的費用，對路徑上重複的區段予以合併， 得出所述組播樹的當前整體費用。其中，所述切換所述組播樹的根節點到葉子節點之間的路徑具體包括根據所述組播樹的優化整體費用對應的路徑信息，用針對流量工程擴 展的資源預留協議信令建立組播樹的根到葉子節點之間的路徑。其中，所述用針對流量工程擴展的資源預留協議信令建立組播樹的根 到葉子節點之間的路徑具體包括所述組播樹的根節點沿著對應於組播樹的優化整體費用的路徑逐跳向 下遊節點發送Path消息，直到葉子節點收到Path消息；所述葉子節點沿原路徑反向逐跳發送Resv消息，直到所述根節點收到 Resv消息。通過上述技術方案的描述可知，因新成員加入、老成員退出、網絡資源 故障、網絡資源故障恢復等各種情況導致組播樹變化時，本發明的技術方 案可以在滿足多QoS約束的條件下，對所有組播組成員的路由進行重新計 算，得出組播樹的優化整體費用，從而實現對組播樹整體優化。
圖1為在MPLS域中組播樹的葉子節點發生變化的示意圖； 圖2為本發明的實施例中實現組播樹優化方法的流程圖。
具體實施方式
為使本發明的目的、技術方案更加清楚明白，以下參照附圖並舉實 施例，對本發明做進一步的詳細說明。現有技術中，當組播樹發生動態變化時，只能針對發生變化的葉子節 點，採用CSPF算法計算出根節點到目的節點之間的一條路徑，無法在從整 體上計算組播樹的費用。本發明的技術方案提出一種組播樹的優化方法， 將CSPF算法擴展到用於計算從根節點到多個葉子節點的整體最優路徑，從
而能夠計算出組播樹的優化整體費用。如本發明提供的計算組播樹的優化整體費用的方法包括如下步驟步驟一、當組播樹發生變化時，比如有增加了葉子節點，採用CSPF算 法不再僅計算出從根節點到新增加的葉於節點的一條最佳路徑，而是保留 根節點到所有葉子節點的符合約束條件的全部可選路徑；步驟二、將從根節點到所有葉子節點的路徑費用進行累加，對其中重 復的區段予以合併，即重複的區段只計算一次，得出組播樹的整體費用；步驟三、替換步驟一中的可選路徑，重新計算組播樹整體費用；並將 計算出的結果與步驟二中計算出的組播樹成本進行比較，若小於步驟二中的組播樹整體費用，則用本步驟中的計算結果替換步驟二計算出的組播樹 整體費用，若大於步驟二中的組播樹整體費用，則丟棄該計算結果；步驟四、重複進行步驟二和步驟三，直到窮盡所有可選路徑的組合， 計算出最小值，即組播樹的優化整體費用。下面結合附圖1 ，用實例對計算組播樹整體費用的進行詳細說明。 當R2節點加入組^番樹成為葉子節點時，採用CSPF算法可以計算出根節 點到R2節點的路徑為S"^D—〉R2。組播樹的當前整體費用為6。為了實現 組播樹的優化，首先採用CSPF算法計算出根節點S到所有葉子節點的符合約 束條件的全部可選路徑。根節點S到葉子節點R1有2條可選路徑；路徑l為 S—〉A—〉B—〉C""〉R1 ，路徑1的費用為4;路徑2為S—〉D—〉B—〉C一〉R1, 路徑2的費用為4;根節點S到葉子節點R2隻有1條可選路徑，即路徑3，其費 用為S~~>D—>R2,該路徑費用為2。然後，將根節點S到所有葉節點R1、 R2的路徑費用進行累加，對其中 重複的區段予以合併，得出一個組播樹的整體費用。路徑1和路徑3的費用進行累加，由於路徑1和路徑3沒有重複的區段，故 此時組播樹的整體費用為6;路徑2和路徑3的費用進行累加，由於路徑2和路徑3在根節點S到中間節
點D之間的區段重合，則將此區段的費用予以合併，故此時組播樹的整體費用為5;最後，比較兩次的計算結果可以得出，該組播樹的優化整體費用為5。 計算出組播樹的優化整體費用後，可根據該計算結果對組播樹進行優化，即根據該優化整體費用對應的路徑信息建立組播樹中根節點到葉子節點的LSP。如圖2所示，本發明提供的多協議標籤交換網絡中組播樹的優化方法包 括如下步驟步驟201、當組播樹發生變化時，計算組播樹的整體費用，得出組播樹 的優化整體費用以及相對應的根節點到所有葉子節點的路徑； 具體地，也可以計算組播樹中的子樹的優化整體費用； 此步驟中，計算組播樹整體費用可以由組播樹(或者其子樹)的根節點完成，也可以由MPLS域的PCE (Path Computation Element路徑計算單元)節點完成；步驟202、判斷步驟201中計算出的組播樹的優化整體費用是否小於當 前的組播樹整體費用，是則執行步驟203，否則執行步驟204;優選地，為了減少組播樹切換的頻率，可根據網絡拓樸的實際情況和預 定的策略對切換做必要的限制。比如，可以對組播樹動態變化後的最小整 體費用和當前的整體費用的比值設定閾值，當所述比值小於預先設定的閾 值時，則切換，否則，保持原組播樹不變。步驟203 、根據計算得出的組播樹的優化整體費用及相對應的路徑信息， 用RSVP-TE ( Resource ReSerVation Protocol-Traffic Engineering針對流量工 程擴展的資源預留協議)信令來部署組播樹，完成組播樹的切換過程。具體過程為組播樹的根節點逐跳向下遊節點發送Path消息；中間節 點收到Path消息後繼續向下遊節點轉發，直到葉子節點收到Path消息；葉子 節點沿原路徑反向發送Resv消息，直到根節點收到Resv消息，則組播樹的 根節點到葉子節點的路徑成功建立。當組播樹的根節點到所有葉子節點之 間的路徑都建立成功，則完成組播樹的切換過程。步驟204、保持原有的組播樹不變。 上述組播樹優化過程，可以由組播樹的根節點或者MPLS域的PCE節點 周期性的(比如每天一次)進行，或者由網絡管理人員手工觸發。該優化 過程可以實時在線進行，也可以離線進行。若計算以後發現組播樹的整體 成本能夠有較大下降，則通過RSVP信令在刷新時重新進行部署。以上所述，僅為本發明較佳的具體實施方式
，但本發明的保護範圍並 不局限於此，任何熟悉該技術的人在本發明所揭露的技術範圍內，可輕易 想到的變化或替換，都應涵蓋在本發明的保護範圍之內。
權利要求
1、一種多協議標籤交換網絡中的組播樹優化方法，包括當組播樹變化時，計算組播樹的當前整體費用和組播樹的優化整體費用；判斷所述組播樹的優化整體費用是否小於所述當前整體費用，是則根據所述組播樹的優化整體費用，切換所述組播樹的根節點到葉子節點之間的路徑。
2、 如權利要求l所述的方法，其特徵在於，所述計算組播樹的優化整體 費用具體包括計算從所述組播樹的根節點到所有葉子節點之間符合約束條件的全部 可選路徑以及相應的費用；對所述根節點到所有葉子節點符合約束條件的可選路徑進行組合；累加不同路徑組合對應的費用，對其路徑上重複的區段予以合併，得出 多個組播樹整體費用；比較所述多個組播樹整體費用，得出所述組播樹的優化整體費用以及相 應的路徑信息。
3、 如權利要求2所述的方法，其特徵在於，通過CSPF算法計算所述組 播樹的根節點到所有葉子節點之間符合約束條件的全部可選路徑。
4、 如權利要求l所述的方法，其特徵在於，所述計算組播樹的當前整體 費用具體包括通過CSPF算法計算所述組播樹的根節點到發生變化的葉子節點之間的 一條滿足約束條件的最佳路徑以及相應的費用；累加從根節點到所有葉子節點的費用，對路徑上重複的區段予以合併， 得出所述組播樹的當前整體費用。
5、 如權利要求1至4中任一項所述的方法，其特徵在於，所述切換所述 組播樹的根節點到葉子節點之間的路徑具體包括 根據所述組播樹的優化整體費用對應的路徑信息，用針對流量工程擴展 的資源預留協議信令建立組播樹的根到葉子節點之間的路徑。
6、如權利要求5所述的方法，其特徵在於，所述用針對流量工程擴展的 資源預留協議信令建立組播樹的根到葉子節點之間的路徑具體包括所述組播樹的根節點沿著對應於組播樹的優化整體費用的路徑逐跳向 下遊節點發送Path消息，直到葉子節點收到Path消息；所述葉子節點沿原路徑反向逐跳發送Resv消息，直到所述根節點收到 Resv消息。
全文摘要
本發明公開了一種多協議標籤交換網絡中的組播樹優化方法，包括當組播樹變化時，計算組播樹的當前整體費用和組播樹的優化整體費用；判斷所述組播樹的優化整體費用是否小於所述當前整體費用，是則根據所述組播樹的優化整體費用，切換所述組播樹的根節點到葉子節點之間的路徑。本發明的技術方案可以在滿足多QoS約束的條件下，對所有組播組成員的路徑進行重新計算，實現對組播樹整體優化。
文檔編號H04L12/56GK101150491SQ20061006278
公開日2008年3月26日 申請日期2006年9月22日 優先權日2006年9月22日
發明者管紅光 申請人:華為技術有限公司