光同步數字傳送網資源分配中子網間業務規整的實現方法
2023-11-01 14:31:47
專利名稱：光同步數字傳送網資源分配中子網間業務規整的實現方法
技術領域：
本發明涉及網絡多業務優化技術，尤其涉及一種光同步數字(SDH)傳送網資源分配中子網間業務規整的實現方法。
背景技術：
網絡的多業務優化問題，考慮到其複雜性，通常被劃分為相關聯的兩個子問題路由分配和資源分配。其中，該路由分配優化是在給定網絡拓撲，即節點和鏈路的結構，以及業務矩陣表的條件下，為每個業務分配路由，使其滿足在網絡中每條鏈路上承載的業務不超過網絡資源總和的約束條件，同時還要達到佔用網絡資源最少和網絡負載平衡的優化目標；而資源分配可以歸結為一個整數線性規劃(ILP)問題，這一問題是非多項式困難(NP-hard)的，眾所周知，在網絡規模較大的情況下，求解這樣問題的全局最優解幾乎是不可能的。具體到SDH傳送網中，傳送網的時隙資源主要分為高階和低階兩類，高階一般指虛容器4(VC4)，低階一般指VC12。那麼，SDH傳送網中的資源分配問題可以定性描述為在給定包括節點與鏈路結構的網絡拓撲、業務需求表和業務路由的條件下，為每個業務分配資源，要在滿足每條鏈路上使用的資源不超過其資源總和、節點交叉資源容量和節點時分交叉能力約束條件的同時，使網絡中的剩餘資源能夠滿足將來更多業務增長和使用低階交叉資源最少的優化目標。
因此，本發明人在另一專利申請中提出了一種多業務的優化方法，該方法是根據SDH傳送網絡的特點，將整個SDH傳送網絡劃分為環形子網，先對每個業務進行最佳路由分配；在路由分配優化的基礎上，再通過在各子網內進行相對獨立的資源分配，以提高進行資源分配的計算效率；然後在各子網中將業務需求映射到不同幾何體，通過對幾何體的合理堆積和組合，以及對業務路由相似性的分析，不斷進行資源的優化分配。如此，不僅較好地解決了低階交叉資源限制的問題，而且很好地反映了在具有時隙連續性約束條件下，如何度量資源分配結果的優劣情況，從而完成優化目標。
在上述多業務優化方法中，根據業務路由相似性分析對業務資源分配進行優化的過程，稱為業務規整，業務規整按其應用範圍又可分為子網內業務規整和子網間業務規整。所謂子網內業務規整就是指在一個環形子網內部根據業務路由相似性優化業務資源分配的過程；同樣，子網間業務規整就是指在不同環形子網之間根據業務路由相似性完成業務資源分配優化的過程。可見，業務規整對SDH傳送網絡中的多業務優化來說是十分重要的，合適的規整方法能夠簡化和完善多業務優化的過程，提高業務優化程度。但是，現有技術中尚未提出合適的子網間業務規整處理方法。
發明內容
有鑑於此，本發明的主要目的在於提供一種SDH傳送網資源分配中子網間業務規整的實現方法，該方法使跨子網業務佔用儘可能少的低階交叉資源，同時可提高SDH傳送網中不同時進行各節點低階交叉資源分配的有效性，進而提高資源分配的優化水平。
為達到上述目的，本發明的技術方案是這樣實現的一種光同步數字傳送網資源分配中業務規整的實現方法，該方法包括以下步驟A、將光同步數字傳送網劃分為一個以上環形子網，並將該傳送網中的每個業務按路由分配到不同環形子網中；B、從步驟A所劃分的環形子網中取出一個子網，根據子網間業務所經過的子網和每個業務路由所經過的出入子網節點對子網間業務進行分組；C、從步驟B所劃分的業務組中取出一個業務組，根據子網間業務的數量和每個業務路由所經過節點的交叉屬性對當前業務組中的所有業務進行規整；這裡，所述的規整是將所有經過子網和經過出入子網節點都相同的子網間業務所佔的低階時隙資源合併到同一個高階時隙資源中；D、判斷是否規整完當前所選子網中的所有業務分組，如果未規整完當前所選子網中的所有業務分組，則返回步驟C；否則，判斷是否規整完所有的環形子網，如果是，則結束過程，否則返回步驟B。
其中，步驟A進一步包括按每個環形子網中節點連接度的大小和子網內的業務量對所劃分的子網進行排序；步驟B進一步包括從經過排序的環形子網中由大到小順序選取一個子網。
步驟B進一步包括按每條業務路由所經過的子網數目對每個業務分組中的所有業務進行排序；步驟C進一步包括從當前子網所有業務分組中按由大到小的順序依次取出一個分組。
步驟C進一步包括對已規整的業務組進行標記；步驟D進一步包括系統根據業務組的已規整標記來判斷是否規整完當前所選子網中的所有業務分組和子網間業務。
步驟D還進一步包括規整完當前所選子網中的所有業務分組後，對當前已規整的子網進行標記；系統根據子網的已規整標記來判斷是否規整完所有子網的業務。
步驟C中對一個業務組中所有業務進行規整後，進一步包括判斷是否還有未規整業務，如果是，則重新對所有未規整業務按路由次相似性進行分組，然後依次對每個分組進行規整處理；否則，執行步驟D。其中，所述按路由次相似性重新對未規整業務分組為將未規整的業務加入到其子路由的分組中。所述的子路由為業務路由的最大子集。
因此，本發明所提供的SDH傳送網資源分配中子網間業務規整的實現方法，具有以下的特點和優點1)本發明通過將全網劃分為環形子網，按照子網及業務路由中出入子網的節點對業務進行比較，進而建立路由相似業務的分組，之後，再按照業務路由的相似性對分組業務進行規整，從而避免低階交叉資源的佔用。
2)通過將未規整的業務轉移到業務路由最大子集的分組中進行規整處理，進一步提高業務規整的機會，進而提高了在SDH傳送網中不同時進行各節點低階交叉資源分配的有效性，同時可以達到使用低階交叉資源最少的優化目標。
3)本發明經過了模擬測試，能在很短的時間內，得到很好的優化結果，這說明本發明可以很好地應用於工程中。
圖1為業務分布的具體實例示意圖；圖2為本發明子網間業務規整的實現流程圖。
具體實施例方式
下面結合附圖和具體實施例對本發明作進一步說明。
本發明主要是解決在SDH傳送網各節點低階交叉資源不同的情況下，減少使用子網間業務低階交叉資源的問題，為此，引入了業務規整的概念。所謂規整，在本發明的應用環境下就是指將一組低階交叉資源合併為一個高階交叉資源，此處，低階指VC12，高階指VC4。換句話說，規整就是將一組VC12時隙分配到同一個VC4時隙中，從而避免低階交叉資源的佔用。從端到端業務的角度來看，進行業務規整的前提是不同業務經過一個節點前後的鏈路要一致，即選定一個節點，兩個或兩個以上業務經過該選定節點的前後路由完全相同。
圖1為業務分布的一具體應用實例示意圖，圖1中，三條曲線從上至下代表A、B、C三個業務，N1～N4為SDH傳送網上的四個節點。從圖中可以看出，業務A和業務B的路由都是從節點N1經節點N2到節點N3的鏈路，兩個業務在節點N2處前後的路由相同，即相對於節點N2來說，在節點N2之前，業務A和業務B都是從節點N1到節點N2；在節點N2之後，業務A和業務B都是從節點N2到節點N3。那麼，業務A和業務B即可在節點N2處進行業務規整。而業務C的路由是從節點N4經節點N2到節點N3的鏈路，這樣業務A和業務C或是業務B和業務C在節點N2處前後的鏈路不一致，所以，業務A和業務B均無法在節點N2處與業務C進行規整。可見，通過比較不同業務的路由，相似性越大的業務之間，其綁定的效果就越好，並且可以在更多的節點進行綁定。
本發明的基本思想就是先根據SDH傳送網的特點，將SDH傳送網劃分為一個或一個以上環形子網；當一條業務路由經過某個環形子網時，由於其在環形子網內的部分可以按環的兩個方向進行切換，不會影響該業務路由的其它部分，而該業務路由在子網間的規整是跨子網業務低階交叉資源優化的關鍵，因此，在環形子網劃分後，本發明按不同子網逐一對每條經過當前子網的業務路由進行處理，比較經過該節點所有業務路由的相似性，並將具有相似性的業務路由劃分成組；然後，逐組進行業務規整。為滿足效率的要求，本發明可採用匹配優先(First-fit)的方法。
圖2為本發明實現子網間業務規整的流程示意圖，如圖2所示，本發明的具體實現流程包括以下的步驟步驟201根據SDH傳送網的特點，將SDH傳送網劃分為一個或一個以上環形子網，並將每個業務根據其路由，劃分到其經過的各個環形子網中。
步驟202～203由於業務規整的前提是業務經過一個節點前後的鏈路一致，所以節點間的連接度越大，其規整的壓力就越大。另外，通過節點的業務流量，也影響到業務規整的需求。因此，先按照子網節點間連接度的大小和子網業務量對所有環形子網進行排序，確定規整的次序。子網排序完畢後，按照連接度和業務量排列順序由大到小依次取其中的每個子網逐一進行處理。
步驟204對於當前要處理的環形子網，先確定該子網中的所有出入子網節點，然後對每條業務路由，根據該業務路由所經過的子網及其經過當前子網的出入子網節點來比較路由的相似性，將路由完全相同的業務放到同一組中。
步驟205～206對經過當前子網的所有業務路由分組完畢後，依次取出其中的每個分組進行規整處理。具體做法是按照業務路由所經過子網的數目對所有分組進行排序，然後對每個分組逐一進行處理。較佳的是先處理路由經過子網數目大的分組業務，根據分組中業務的數量和業務路由所經過節點的交叉屬性，對業務進行規整，即將一組VC12時隙合併到同一個VC4時隙中，然後再對已規整過的業務組進行標記，以避免重複處理。在對分組的處理過程中，可根據需要按照不同的條件對分組進行排序，不僅限於以經過子網的數目為條件。
步驟207判斷是否有未規整的業務，如果有，則對未規整的業務按路由次相似性進行分組，比如將未規整的業務加入到其子路由的分組中，這裡所述的子路由為業務路由的一個最大子集。然後，對這些分組重複步驟205～206的相關操作，進一步提高業務規整的機會。
步驟208～209根據分組的已規整標記判斷是否還有業務分組未被處理，如果有，則返回步驟205取下一業務分組進行處理；否則，對當前規整的子網做出已規整標記，然後，根據子網的已規整標記判斷是否還有子網間的業務未被處理，如果是，則返回步驟203取下一子網進行處理；否則，結束子網間業務規整過程。
以上僅通過列舉較佳實施例，對本發明的目的、技術方案和優點進行進一步的說明，所應理解的是，其並不用以限定本發明的保護範圍。
權利要求
1.一種光同步數字傳送網資源分配中子網間業務規整的實現方法，其特徵在於該方法包括以下步驟A、將光同步數字傳送網劃分為一個以上環形子網，並將該傳送網中的每個業務按路由分配到不同環形子網中；B、從步驟A所劃分的環形子網中取出一個子網，根據子網間業務所經過的子網和每個業務路由所經過的出入子網節點對子網間業務進行分組；C、從步驟B所劃分的業務組中取出一個業務組，根據子網間業務的數量和每個業務路由所經過節點的交叉屬性對當前業務組中的所有業務進行規整；D、判斷是否規整完當前所選子網中的所有業務分組，如果未規整完當前所選子網中的所有業務分組，則返回步驟C；否則，判斷是否規整完所有的環形子網，如果是，則結束過程，否則返回步驟B。
2.根據權利要求1所述的方法，其特徵在於步驟A進一步包括按每個環形子網中節點連接度的大小和子網內的業務量對所劃分的子網進行排序；步驟B進一步包括從經過排序的環形子網中由大到小順序選取一個子網。
3.根據權利要求1所述的方法，其特徵在於步驟B進一步包括按每條業務路由所經過的子網數目對每個業務分組中的所有業務進行排序；步驟C進一步包括從當前子網所有業務分組中按由大到小的順序依次取出一個分組。
4.根據權利要求1所述的方法，其特徵在於步驟C進一步包括對已規整的業務組進行標記；步驟D進一步包括系統根據業務組的已規整標記來判斷是否規整完當前所選子網中的所有業務分組和子網間業務。
5.根據權利要求1所述的方法，其特徵在於步驟D進一步包括規整完當前所選子網中的所有業務分組後，對當前已規整的子網進行標記；系統根據子網的已規整標記來判斷是否規整完所有子網的業務。
6.根據權利要求1所述的方法，其特徵在於所述規整是將所有經過子網和經過出入子網節點都相同的子網間業務所佔的低階時隙資源合併到同一個高階時隙資源中。
7.根據權利要求1所述的方法，其特徵在於步驟C中對一個業務組中所有業務進行規整後，進一步包括判斷是否還有未規整業務，如果是，則重新對所有未規整業務按路由次相似性進行分組，然後依次對每個分組進行規整處理；否則，執行步驟D。
8.根據權利要求7所述的方法，其特徵在於所述按路由次相似性重新對未規整業務分組為將未規整的業務加入到其子路由的分組中。
9.根據權利要求8所述的方法，其特徵在於所述的子路由為業務路由的最大子集。
全文摘要
本發明公開了一種光同步數字傳送網資源分配中子網間業務規整的實現方法，包括將光同步數字傳送網劃分為一個以上環形子網，並將該網中的每個業務按路由分配到不同環形子網中；對每個子網，根據子網間業務所經過的子網和每個業務路由所經過的出入子網節點對子網間業務進行分組；對每個業務組，根據子網間業務的數量和每個業務路由所經過節點的交叉屬性對當前業務組中的所有業務進行規整；然後，判斷是否規整完所有業務分組或所有子網，如果沒有，則選取下一個業務分組或子網進行規整；否則結束流程。本發明使子網間業務儘可能少的佔用低階交叉資源，提高在各節點低階交叉資源不同時進行資源分配的有效性。
文檔編號H04L12/24GK1540922SQ0312792
公開日2004年10月27日 申請日期2003年4月24日 優先權日2003年4月24日
發明者敖奇, 劉亮, 敖 奇 申請人:華為技術有限公司