一種能有效降低波長路由光網絡阻塞率的波長緩存方法
2023-05-30 02:36:01
專利名稱：一種能有效降低波長路由光網絡阻塞率的波長緩存方法
技術領域：
本發明描述一種在波長路由光網絡中降低建路阻塞率，同時提高網絡資源利用率的方法，屬於光網絡通信技術領域。該方法特別適用於分布式波長路由的自動交換光網絡。
背景技術：
目前已有的光網絡擁塞控制方法主要可歸為兩大類。第一類方法通過對實際網絡業務的分布特性進行預測建立網絡模型，並根據該模型合理設計網絡拓撲並優化網絡資源的分配，以達到降低網絡阻塞率的目的。我們稱這類方法為網絡建模優化方法。第二類方法在網絡拓撲和網絡資源確定後，通過一定的策略或技術，在有限的資源條件下獲得最低的網絡阻塞率和最高的網絡資源利用率。我們稱這類方法為網絡策略優化方法。其中，第一類優化方法以靜態為主。由於該類方法在建模過程中需要考慮大量業務因素和限制條件，因此其計算複雜度非常高，不適合在網絡建成後的動態運營過程中採用。第二類優化方法可細分為三個子類路由與波長分配策略類(RWA)、波長變換類(WC)，以及重路由類。其中，RWA策略類通過算法上的設計進行優化路由選擇，從而儘可能的避免擁塞發生，充分利用網絡資源；WC類通過引入波長變換器，在光網絡擁塞發生前，將即將發生擁塞的業務轉移到空閒光波長，從而降低光網絡中由波長連續性限制帶來的負面影響，降低網絡阻塞率；重路由策略與前兩類策略不同，它是一種作用於擁塞發生之後的策略，軟搶佔(SP)是其一種典型方法。區別於硬搶佔方法，當網絡擁塞發生後，軟搶佔方法會為即將被搶佔的已有網絡業務計算一條新路由，若且唯若這條新路由被計算出來且該業務按新路由改路成功時，新的業務才能進行搶佔操作。因此從本質上說，重路由策略是一種網絡資源的實時再調整策略，並通過該調整使資源分布更合理，資源利用率更高。
然而就目前來說，第二類優化方法的三個子類均存在一個共同的局限性它們都只是通過降低網絡的空間不均衡性來達到更合理利用網絡資源的目的。網絡的空間不均衡性是由網絡拓撲結構的不均衡性以及網絡業務分布的空間不均衡性等因素所導致的，其直接導致了網絡實時可用資源在空間上的不均衡分布，這極大的限制了它們被充分利用。這種空間不均衡分布構成了第二類優化方法中各種策略或技術作用的基礎。
然而，除了空間不均衡性外，網絡中還存在著時間不均衡性，表現為網絡的瞬時業務強度並不是一個恆定的值，而是在一個範圍內波動。這種時間不均衡性主要由網絡的業務特性所導致。圖1描繪了電路交換光網絡的實時業務強度和阻塞分布(Poisson業務模型)。從圖中我們可以看到網絡的實時業務強度圍繞其均值(6.5Erlang)上下波動。對於分組交換網絡，數據業務具有更強的突發性和自相似性，因此在這種網絡中時間不均衡性同樣存在。可見網絡的時間不均衡性是普遍存在的。如果能有效利用這種時間不均衡性，網絡的資源利用率將存在進一步提升的空間。
發明內容
為有效利用網絡的時間不均衡性，本發明提出了這樣一種波長路由光網絡的波長緩存方法，它能有效提高網絡資源利用率並降低建路阻塞率。
從圖1中可以看到，在網絡負載較輕時，網絡擁塞集中出現在實時業務強度的峰值時段，而對於其他時段，擁塞很少或甚至不存在。圖2解釋了這個現象產生的原因。在圖2中，網絡的實時業務強度和其資源利用率存在明顯的相關性，表現為網絡的資源利用率會隨著實時業務強度的波動而正向波動。在實時業務強度的峰值時段，網絡的資源利用接近了飽和狀態，從而導致了業務擁塞的集中出現。而在其他時段，網絡的資源利用率處於一個相對較低的水平，此時網絡資源沒有得到充分利用。因此，如果能在網絡中設置一個資源緩存區，在非峰值時段將緩存區中的業務「清空」，即將閒置的網絡資源「集中」在該緩存區內，而在峰值時段集中「釋放」緩存區中的資源用於解決擁塞，那麼便可以達到在提高資源利用率的同時降低網絡阻塞率的作用。本發明就是基於這種思想提出的。
本發明的特徵在於1、該方法是在自動交換光網絡的控制平面伺服器上按以下步驟依次實現的步驟(1)初始化在所述伺服器中預設有開放最短路由優先協議OSPF的協議流程及其路由鏈路狀態資料庫Router LSDB；資源預留協議，便於光網絡節點能夠實時地得到網絡中所有業務的路由信息，並對其佔用的鏈路資源信息進行統計；步驟(2)在所述伺服器中預設一個資源緩存區，並按照設定比例把相應數量的光波長資源預留在該緩存區，剩餘的光波長資源構成非緩存區；然後再把所述的路由鏈路狀態資料庫也相應的劃分為緩存區鏈路狀態資料庫和非緩存區鏈路狀態資料庫，這些鏈路狀態資料庫是由所述伺服器按所述光網絡的鏈路狀態動態地改變的；步驟(3)所述伺服器分別對步驟(2)中所述的緩存區鏈路狀態資料庫和非緩存區鏈路狀態資料庫用迪克斯特拉Dijkstra最短路由算法生成其各自的路由表，分別稱為緩存區路由表和非緩存區路由表；步驟(4)在一個新的網絡業務到達時，在所述非緩存區路由表中，為該業務查詢最短路由步驟(4.1)若最短路由存在，表明沒有阻塞發生，便在該非緩存區中對新業務正常建路；步驟(4.2)若最短路由不存在，表明有阻塞發生，按步驟(5)處理；步驟(5)根據步驟(4)中所述的業務阻塞，根據事先設定的業務優先級等級，分別對阻塞業務採取不同的處理操作對於低優先級業務，按步驟(6)處理；對於高優先級業務，按步驟(7)處理；步驟(6)根據發生阻塞時的瞬時網絡業務強度以及緩存區鏈路資源利用率水平對步驟(5)中的低優先級阻塞業務採取不同的處理操作瞬時網絡業務強度I按下式進行計算I＝InsTrafNum/N，其中，InsTrafNum表示網絡中的瞬時業務數，N表示網絡節點的個數；緩存區鏈路資源利用率U按下式進行統計和計算U=|E|-1i=1|E|j=1keij/k,]]>其中，eij表示緩存區鏈路i在第j次採樣時的狀態1為佔用，0為空閒，|E|表示網絡緩存區的鏈路數，k表示在進行鏈路資源佔用率統計時的採樣次數；當網絡瞬時業務強度I大於其設定閾值Ith，且緩存區鏈路資源利用率U小於其設定閾值Uth時，按步驟(7)處理；當網絡瞬時業務強度I小於或等於其設定閾值Ith，或者緩存區鏈路資源利用率U大於或等於其設定閾值Uth時，所述伺服器返回該業務的阻塞信息，並結束其建路請求；步驟(7)開啟資源緩存區，並為步驟(5)中的高優先級阻塞業務，或步驟(6)中網絡瞬時業務強度大於其設定閾值Ith，且緩存區鏈路資源利用率小於其設定閾值Uth的低優先級阻塞業務查詢最短路由若最短路由存在，則在緩存區中為新業務建路；若最短路由不存在，則所述伺服器返回該業務的阻塞信息，並結束其建路請求。
2、在步驟(4.2)之後和步驟(5)之前，可先用路由與波長分配方法為所述阻塞業務尋找路由，若路由不存在，則阻塞發生，之後再用軟搶佔方法嘗試在非緩存區解決該阻塞，若找到搶佔業務對象，則把該被搶佔的業務改路，再用所述阻塞業務去佔用被搶佔業務的資源，在非緩存區建路，阻塞解決；若軟搶佔方法失敗，則執行步驟(5)。
3、對於所述預設的資源緩存區，對于波長路由網絡，其粒度為光波長量級。
4、對於非波長路由網絡，其資源緩存區的粒度為該非波長路由網絡所支持的最小交換粒度。
5、設定所有網絡業務為高優先級業務，在設定的業務負載強度下，將緩存區容量從零開始增加，每次增加量為其最小粒度值，直到所記錄的網絡阻塞率出現極小值時停止，此時即得到該業務負載強度下的最優緩存區容量值。
6、從零開始按照設定的步長不斷增加業務負載強度，對於每一個設定的業務負載強度，重複5中所述的操作，在網絡阻塞率出現極小值時記錄其所對應的最優緩存區容量值，該極小值超出網絡在正常業務負載區間運行時所設定的阻塞率上限值的20％時停止，此時即得到了正常業務負載區間內最優緩存區容量值隨業務負載強度變化的曲線。
本發明所述的波長路由光網絡的波長緩存方法的具體工作流程如圖3所示。
仿真結果(圖4)顯示，在採用波長緩存方法後，網絡的阻塞率指標得到了很大改善。從圖中我們看到，在網絡的正常業務負載區間(網絡阻塞率小於20％，節點載荷小於12Erlang)，波長緩存方法相比典型的已有網絡策略優化方法均能明顯的進一步降低網絡阻塞率。尤其對於輕負載網絡(節點載荷小於6Erlang)，網絡阻塞率更是大幅降低，特別當波長緩存方法與軟搶佔方法(SP)結合使用時，網絡阻塞率可降到普通LLR方法的1/20或單純SP方法的1/6。
圖1網絡實時業務強度和阻塞分布圖。
圖2網絡實時業務強度和其實時資源利用率關係圖。
圖3波長緩存方法工作流程圖。
圖4網絡阻塞率特性比較圖。
圖1說明這是一個電路交換光網絡的實時業務強度和阻塞分布圖，圖的上方為瞬時網絡業務強度，下方為每秒統計的阻塞業務數。其中，網絡拓撲採用19節點的EON拓撲模型，網絡業務採用Poisson模型。仿真業務數目為5000，阻塞業務數目為122，仿真業務負載強度為6.5Erlang，服務率μ＝0.1秒-1。
圖2說明這是一個電路交換光網絡的實時業務強度和其實時資源利用率的關係圖，圖的上方為瞬時網絡業務強度，下方為其資源利用率。該圖中的所有網絡仿真參數與圖1中相同。圖 瞬時網絡業務強度-★-網絡鏈路資源利用率圖3說明這是採用波長緩存方法的網絡節點的路由模塊工作流程圖。
-□-最小負載路由(LLR) 方法和採用已有典型網絡策略優化方法的網絡阻塞率比較圖。
稀疏波長變換(WC)其on過程，並平均分配在各個節點上。業務服務時間遵循負指-▽-軟搶佔策略(SP)數 波長緩存/WC(WB_WC)圖例如下-▼-波長緩存/SP(WB_SP)具體實施方式
為達到上述目的，以下通過具體的網絡實例說明本發明所提出的波長緩存方法的具體實施方式
，包括資源緩存區的設置、開啟以及路由計算等部分。在該網絡實例中，採用軟搶佔網絡策略優化方法(SP)輔助波長緩存方法的實施以達到最佳的網絡優化效果1.資源緩存區設置(1)緩存區的資源粒度及其資源預留設置對於最小交換粒度為波長的波長路由光網絡，資源緩存區的資源粒度應設置為波長級別。需要注意的是，在該網絡中所有光纖鏈路需要預留相同的波長資源至資源緩存區，使緩存區內的每個波長資源均能夠獨立構成一個擁有完整拓撲的子網絡。
對於其他最小交換粒度小于波長的網絡，資源緩存區的資源粒度應設置為該網絡的最小交換粒度。同樣，在該網絡中資源緩存區中的資源預留應遵守以下原則，即該預留需使緩存區內每個資源粒度的資源都能夠獨立構成一個擁有完整拓撲的子網絡。
(2)緩存區的容量大小設置資源緩存區的容量大小將直接影響到波長緩存方法對網絡的優化效果。如果緩存區設置過大，會大幅度降低高優先級業務的阻塞率。但是由於其佔用了過多網絡資源，會惡化低優先級業務的阻塞率指標，從而導致網絡的整體性能得不到改善。緩存區設置過小將限制波長緩存方法對網絡的優化效果。因此，在考慮整體網絡性能時，客觀存在一個最優的緩存區容量值，該最優值會隨著節點業務負載強度的變化而發生變化。在實際操作過程中，可以通過以下步驟得到最優緩存區容量值隨負載強度變化的具體數值步驟A設定所有網絡業務為高優先級業務。
步驟B對於設定的業務負載強度，將緩存區容量從零逐漸增加，每次增加量為其最小粒度。
步驟C當緩存區容量每增加到一個數值時，觀察整體網絡阻塞率的變化，直到其波動範圍小於其值的1％時，記錄其數值。之後繼續增加緩存區容量，並重複步驟C的操作，直到緩存區容量等於整個網絡容量，或所記錄的阻塞率出現極小值時停止。
步驟D找出所記錄的網絡阻塞率的極小值，其所對應的緩存區容量值即為該業務負載強度下的最優緩存區容量值。
步驟E按一定步長增加業務負載，重複步驟B-D的操作，直到網絡阻塞率指標超過網絡在正常業務負載區間運行時該指標的上限，在通常情況下，該上限可設為20％；至此，我們便得到了最優緩存區容量值隨負載強度的變化趨勢。
表1為通過以上方法得到的16波長EON網絡在不同負載強度下的最優緩存區容量值。在該網絡實例中，我們按照該表中的數據動態設置緩存區容量的大小。
表1最優緩存區容量設置(19節點EON網絡，16波長)
2.資源緩存區的開啟及路由計算在該網絡實例中，我們採用19節點的EON網絡拓撲模型，光波長數設定為16。其中，網絡業務到達遵循Poisson過程，並平均分配在各個節點上。業務服務時間遵循負指數分布，平均服務時間為1秒，節點業務強度的均值為6.5Erlang。同時，我們還設定開啟資源緩存區的瞬時網絡業務強度閾值Ith為節點業務強度的均值(Ith＝6.5Erlang)，緩存區鏈路資源利用率閾值Uth＝50％。
對某一時刻到達的A、B、C三個業務，我們根據所述波長緩存方法的工作流程(圖3)採取不同的緩存區開啟及路由操作。其中，業務B為高優先級業務，業務A、C為低優先級業務。該時刻的瞬時網絡業務強度I＝6Erlang，緩存區鏈路資源利用率U＝45％。
業務A在非緩存區用最短路由與波長分配策略為業務A尋找路由，該路由不存在，阻塞發生。之後啟用軟搶佔方法嘗試在非緩存區解決該阻塞，找到搶佔業務對象，並將該業務成功改路。而後業務A佔用該被搶佔業務的資源，並成功在非緩存區建路，阻塞解決。在此過程中，沒有開啟資源緩存區。
業務B在非緩存區用最短路由與波長分配策略為業務B尋找路由，該路由不存在，阻塞發生。之後啟用軟搶佔方法嘗試在非緩存區解決該阻塞，找不到搶佔對象，阻塞仍然無法解決。下一步準備開啟資源緩存區，嘗試在緩存區內為業務B尋找路由。由於業務B為高優先級業務，根據波長緩存方法的工作流程(圖3)，跳過閾值判斷過程直接開啟緩存區。而後在緩存區用最短路由與波長分配策略為業務B尋找路由，該路由存在。之後在緩存區中對業務B進行建路操作，阻塞解決。
業務C在非緩存區用最短路由與波長分配策略為業務C尋找路由，該路由不存在，阻塞發生。之後啟用軟搶佔方法嘗試在非緩存區解決該阻塞，找不到搶佔對象，阻塞仍然無法解決。下一步準備開啟資源緩存區，嘗試在緩存區內為業務C尋找路由。由於業務C為低優先級業務，根據波長緩存方法的工作流程(圖3)，需要在開啟緩存區前進行開啟閾值判斷。雖然此時的緩存區鏈路資源利用率U＜Uth，符合緩存區的開啟條件，但瞬時網絡業務強度I＜Ith，無法滿足緩存區的另外一個開啟條件。按工作流程，放棄開啟資源緩存區，並輸出阻塞信息。
本發明所述的在波長路由光網絡中降低建路阻塞率的方法，不僅僅限於說明書和實施方式中所列運用，它完全能被用於各種適合本發明之領域，熟悉本領域的人員可容易地實現本發明另外的優點和對其進行修改。因此在不背離權利要求及等同範圍所限定的一般概念的精神和範圍的情況下，本發明並不限於特定的細節和這裡示出與描述的圖示示例。
權利要求
1.一種能有效降低波長路由光網絡阻塞率的波長緩存方法，其特徵在於，該方法是在自動交換光網絡的網絡控制平面伺服器上按以下步驟依次實現的步驟(1)初始化在所述伺服器中預設有開放最短路由優先協議OSPF的協議流程及其路由鏈路狀態資料庫Router LSDB；資源預留協議，便於光網絡節點能夠實時地得到網絡中所有業務的路由信息，並對其佔用的鏈路資源信息進行統計；步驟(2)在所述伺服器中預設一個資源緩存區，並按照設定比例把相應數量的光波長資源預留在該緩存區，剩餘的光波長資源構成非緩存區；然後再把所述的路由鏈路狀態資料庫也相應的劃分為緩存區鏈路狀態資料庫和非緩存區鏈路狀態資料庫，這些鏈路狀態資料庫是由所述伺服器按所述光網絡的鏈路狀態動態地改變的；步驟(3)所述伺服器分別對步驟(2)中所述的緩存區鏈路狀態資料庫和非緩存區鏈路狀態資料庫用迪克斯特拉Dijkstra最短路由算法生成其各自的路由表，分別稱為緩存區路由表和非緩存區路由表；步驟(4)在一個新的網絡業務到達時，在所述非緩存區路由表中，為該業務查詢最短路由步驟(4.1)若最短路由存在，表明沒有阻塞發生，便在該非緩存區中對新業務正常建路；步驟(4.2)若最短路由不存在，表明有阻塞發生，按步驟(5)處理；步驟(5)根據步驟(4)中所述的業務阻塞，根據事先設定的業務優先級等級，分別對阻塞業務採取不同的處理操作對於低優先級業務，按步驟(6)處理；對於高優先級業務，按步驟(7)處理；步驟(6)根據發生阻塞時的瞬時網絡業務強度以及緩存區鏈路資源利用率水平對步驟(5)中的低優先級阻塞業務採取不同的處理操作瞬時網絡業務強度I按下式進行計算I＝InsTrafNum/N，其中，InsTrafNum表示網絡中的瞬時業務數，N表示網絡節點的個數；緩存區鏈路資源利用率U按下式進行統計和計算U=|E|-1i=1|E|j=1keij/k,]]>其中，eij表示緩存區鏈路i在第j次採樣時的狀態1為佔用，0為空閒，|E|表示網絡緩存區的鏈路數，k表示在進行鏈路資源佔用率統計時的採樣次數；當網絡瞬時業務強度I大於其設定閾值Ith，且緩存區鏈路資源利用率U小於其設定閾值Uth時，按步驟(7)處理；當網絡瞬時業務強度I小於或等於其設定閾值Ith，或者緩存區鏈路資源利用率U大於或等於其設定閾值Uth時，所述伺服器返回該業務的阻塞信息，並結束其建路請求；步驟(7)開啟資源緩存區，並為步驟(5)中的高優先級阻塞業務，或步驟(6)中網絡瞬時業務強度大於其設定閾值Ith，且緩存區鏈路資源利用率小於其設定閾值Uth的低優先級阻塞業務查詢最短路由若最短路由存在，則在緩存區中為新業務建路；若最短路由不存在，則所述伺服器返回該業務的阻塞信息，並結束其建路請求。
2.根據權利要求1所述的一種能有效降低波長路由光網絡阻塞率的波長緩存方法，其特徵在於，在步驟(4.2)之後和步驟(5)之前，可先用路由與波長分配方法為所述阻塞業務尋找路由，若路由不存在，則阻塞發生，之後再用軟搶佔方法嘗試在非緩存區解決該阻塞，若找到搶佔業務對象，則把該被搶佔的業務改路，再用所述阻塞業務去佔用被搶佔業務的資源，在非緩存區建路，阻塞解決；若軟搶佔方法失敗，則執行步驟(5)。
3.根據權利要求1所述的一種能有效降低波長路由光網絡阻塞率的波長緩存方法，其特徵在於，對於所述預設的資源緩存區，對于波長路由網絡，其粒度為光波長量級。
4.根據權利要求1所述的一種能有效降低波長路由光網絡阻塞率的波長緩存方法，其特徵在於，對於非波長路由網絡，其資源緩存區的粒度為該非波長路由網絡所支持的最小交換粒度。
5.根據權利要求1所述的一種能有效降低波長路由光網絡阻塞率的波長緩存方法，其特徵在於，設定所有網絡業務為高優先級業務，在設定的業務負載強度下，將緩存區容量從零開始增加，每次增加量為其最小粒度值，直到所記錄的網絡阻塞率出現極小值時停止，此時即得到該業務負載強度下的最優緩存區容量值。
6.根據權利要求1、5所述的一種能有效降低波長路由光網絡阻塞率的波長緩存方法，其特徵在於，從零開始按照設定的步長不斷增加業務負載強度，對於每一個設定的業務負載強度，重複權利要求5所述的操作，在網絡阻塞率出現極小值時記錄其所對應的最優緩存區容量值，該極小值超出網絡在正常業務負載區間運行時所設定的阻塞率上限值的20％時停止，此時即得到了正常業務負載區間內最優緩存區容量值隨業務負載強度變化的曲線。
全文摘要
一種能有效降低波長路由光網絡阻塞率的波長緩存方法屬於光通信網絡中降低建路阻塞率的技術領域，其特徵在於該發明所提出的波長緩存方法在網絡瞬時業務強度較低時，採用某種路由與波長分配方法在「非緩存波長」上正常計算路由並建立連接；而當網絡瞬時業務強度突增時，如果「非緩存波長」的網絡資源無法滿足新業務的建路請求，該方法將根據業務優先級以及網絡狀態等參數有選擇的在「緩存波長」上為新業務建立連接，從而利用網絡資源的時間不均衡分布有效提高其資源利用率，進而降低網絡中高優先級業務或整個網絡的阻塞率水平。
文檔編號H04L12/56GK101056475SQ20071009996
公開日2007年10月17日 申請日期2007年6月1日 優先權日2007年6月1日
發明者華楠, 鄭小平, 張漢一, 周炳琨 申請人:清華大學