基于資源個性化需求感知的生存算法設計

林 國 勇

(廣西民族大學相思湖學院 廣西 南寧 530008)

0 引 言

為了應對云計算和大數據技術部署下光網絡載荷呈現指數級暴增的情形，在傳統光網絡鏈路層、網絡層、傳輸層的網元中植入多效控制件構建智能控制平面，使各層網元支持相同信令的構思應勢而生。在智能控制平面的介入下，光傳送網在實施基于不同SLA[1]波長業務的故障智能定位、智能檢測、智能自愈將成為可能。以ASON[2]為例，該網絡突破了傳統網絡受鏈路構建方式束縛而無法為不同SLA波長業務提供承載安全保障的瓶頸，通過改善光路資源管理效率、擴展局向協議來促進光傳送網上通路資源的調度，以降低SLA波長業務請求失效的風險，提升全網的生存性。同時ASON的部署克服了繁瑣的電路配置產生巨大的時間代價問題，使該網絡在響應不同SLA的波長業務對資源請求差異化服務提供了可能。正是這些優勢吸引了業界頻繁地在ASON上開展與波長業務承載算法相關的探討，但其中多以通路保護研究為主。甚至一些組織機構也從功能框架上對ASON的生存機制進行統一界定。以國際電聯制定的8080建議為例，該建議雖然規定了各類波長業務遭遇異常服務質量(QoS)時的自愈方法，但卻未明確自愈實施細則。作為該建議的補充，國際互聯網工程任務組為ASON在實施波長業務承載過程中可能面臨通路資源匱乏的風險定義了SRLG，以降低自愈過程中工作通路(WC)和保護通路(PC)同時失效的風險。

當前，與此SRLG相關的通路研究主要有ILP算法、APF算法、KSP算法。ILP算法思想[3-4]雖能規避通路對因共享的物理資源遭遇異常而同時失效的風險，但繁瑣的計算過程和高昂的時間成本均表明復雜度不占優勢。且計算復雜度與網絡規模呈正比的特征進一步局限了該算法只能部署在規模較小的網絡中，降低了實用性。APF算法機制[5-6]是通過參照鏈路途經SRLG的數量規模對鏈路權值進行定義，以便讓WC盡可能避開那些隸屬于多個SRLG的鏈路。雖然該機制在計算復雜度方面有所改善，卻忽略了鏈路帶寬利用率極小化以及SRLG陷阱等關鍵性問題。KSP算法策略[7]是從節點對中計算出K條最短WC用于規避波長業務請求失效的風險，然后參照權值排序鎖定基于SRLG分離的最佳通路對。雖然提升了實用性，但隨波長業務規模增加，算法復雜度也將上升。尤其在參數K較大的情形下表現出的時間代價依然較大。此外，雖存在另外一些復雜度和時間成本均較低的相關研究，比如基于業務區分的路由算法[8]，但事實證明這些研究極易遭遇通路對同時失效的風險。少數研究即便顧及到SRLG陷阱風險問題，也因缺乏考慮不同SLA波長業務對通路資源的客觀需求而限制了這些研究的可部署性。基于上述主流研究的單一性，本文從算法復雜度和時間成本代價角度出發，本著兼顧SRLG陷阱問題和SLA區分的原則，構思了一種基于不同SLA波長業務對通路資源客觀需求感知的自愈算法，旨在改善ASON在應對波長業務承載期間全網的生存性[9]。

1 基于分離原則的SLA可靠性分析

既有的生存算法研究雖是基于SRLG理念對波長通路展開保護，但只考慮2條以內鏈路出現故障的情形。這樣的保護思想從表面上看雖然使得WC和PC都保持了分離的狀態，但部署在復雜網絡中時兩者卻極有可能同屬于某一個SRLG。一旦該SRLG出現異常QoS事件，勢必導致WC和PC同步失效。可見，該情形下的鏈路分離、網元分離只能視為SRLG的一種特殊情況而不具備廣泛的適應性。因此要顯著改善復雜全局網絡的生存性，就不得不考慮在源宿網元對內部計算出不但不屬于同一個SRLG，還要滿足波長業務對通路資源可靠性需求的WC和PC。以此規避WC和PC因同一個SRLG出現異常QoS而引發的通路對同步失效風險，即遵循相對分離原則。基于該原則計算出的通路對可為不同SLA提供通路資源的可靠性保證。

假設五個網元構成了如圖1所示的布局圖，其對應的SRLG拓撲結構如圖2所示。此時由網元1向網元3發起一個波長業務的連接請求。根據KSP啟發式算法思想，將最短的e3直接定義為網元對[1,3]的WC。然而此舉決定了后續難以從全網中尋得與e3保持SRLG分離的PC。這是緣于網元對[1,3]間的其他組合路徑，如e5+e4，e6+e7+e4，e1+e2，和作為WC的e3同時歸屬于第3個、第8個SRLG。因此KSP算法的計算策略無法保證全網的生存性。

圖1 網元布局圖

圖2 共享風險鏈路組圖

但是，相對分離原則下的生存算法在感知e3與e5+e4、e6+e7+e4、e1+e2隸屬于相同SRLG后，將重新計算出路徑組合e1+e2用于取代e3，定義為網元對[1,3]之間波長業務的WC，同時將路徑組合e6+e7+e4定義為該波長業務下基于SRLG相對分離的PC。可見，相對分離原則下的生存算法在滿足波長業務對帶寬資源需求的前提下，可為波長業務的承載與保護提供良好的保障。同時，根據SLA協議規定，在通路對中承載不同層級的波長業務時，可通過測試該波長業務在一定周期內實施路由[10]局向的穩定程度來定義不同層級波長業務的可靠等級。因此，在全局網絡中為不同SLA波長業務提供一個基于不同等級可靠性的資源需求為前提，尋找一個基于SRLG相對分離的通路對方案是可行的。

2 算法設計

2.1 失效風險模型

定義一個共享了光纖/纜、通道和路徑等物理資源的通路對對應于某編號的共享風險鏈路組(S-No.)。一旦上述四個層次的物理[11]資源出現異常，則源宿網元對之間所有鏈路上的各等級SLA波長業務都將面臨失效風險。若這些鏈路在不同程度上共享了不同的物理資源，那么鏈路上各等級SLA波長業務面臨的失效風險程度也將有所不同。因此鏈路對物理資源的共享程度與相同S-No.內的鏈路出現失效風險的概率息息相關。假設某一個S-No.內有n條鏈路，且定義m

L(srlg)=P(m失效|n失效) (m,n)∈srlg

由于在實際應用中，該失效率的參數可通過鏈路所共享的四個層次物理資源來量化，故此處假設該失效率為給定的賦值。

2.2 基于SLA資源需求模型

實際應用中由于并非所有的波長業務均要求提供1∶1的帶寬資源保護，也就是無需在基于SRLG絕對分離的情形下為所有不同SLA的波長業務尋找通路對。于是，本次研究的思路調整為只要通路對的資源能夠滿足不同SLA波長業務的可靠性需求即可，無需遵循SRLG絕對分離的原則。因此，為使鏈路滿足某一個波長業務對帶寬資源的可靠需求，要求波長業務對鏈路帶寬資源的可靠率R必須超過通路對同時失效的可能性，即：1-R≥L(WC,PC)。

式中，S-m和S-n分別為鏈路m和鏈路n所對應的S-No.集合。由此可得：

將通路對中對應于同一個S-No.的鏈路定義為風險鏈路，同時令srlg-i為某一個S-No.。當定義每條鏈路僅對應于唯一的S-No.，那么在風險鏈路僅一條時，上述公式演化為：

(S-m)∩(S-n)=srlg-i,m∈WC,n∈PC

當存在多個風險鏈路的情形時，上述公式進一步演化為：

(1-Am)]

在遵循相對分離原則的前提下，若存在多個風險鏈路，只要其滿足該式即可視為該鏈路是符合不同SLA的波長業務對帶寬通路資源的可靠性需求[13]。

為了評估每個鏈路作為通路對的可行性，算法將為每一個鏈路定義兩個權值評估函數分別展開計算。通過該函數的動態考量，將搜索出SRLG中的風險鏈路用于實施不同SLA的波長業務對帶寬通路資源的可靠性需求分析。令某個通路對的權值為σwc-l和σpc-l，當源節點發起波長業務請求時，為通路對的鏈路分別賦予權值函數。該權值函數分別記作：

若假設全局網絡的鏈路帶寬資源均衡[14]分布，則鏈路總帶寬Ball為一個恒數。同時鏈路的閑置帶寬表征為Bidle。定義C為一個數值較大的恒數。如果途徑WC的鏈路和l同屬于某一個S-No.，則要參照公式

(1-Am)]

進一步分析這樣的風險鏈路能否符合不同SLA的波長業務對帶寬通路資源的可靠性需求。

3 算法實施

步驟1初始化全網，將迭代計算參量置零。若未收到建立鏈接的請求指令，根據全網鏈路初始權值等狀態參量動態[15]更新鏈路的權值；若收到建立鏈接的請求指令，進入下一步驟。

步驟2若迭代計算參量為零，經由σwc-l函數更新所有鏈路的權值，并根據Dijsktra算法規劃出WC。如果未能尋得WC，則返回步驟1；反之進入下一步驟。若此時迭代計算參量不為零，則參照前一次迭代計算過程計算出來的WC權值，根據Dijsktra算法規劃出WC。如果依舊不能尋得WC，說明建立鏈接的請求指令被中斷，此時需重返步驟1；反之進入下一個步驟。

[L(srlg-i)·(1-Am)]之間的關系來判斷當前通路對能否符合不同SLA的波長業務對帶寬通路資源的可靠性需求。若前者小于后者，表明通路對未能符合不同SLA的波長業務對帶寬通路資源的可靠性需求。此時隨機定義一條風險鏈路的工作權值并賦值∞，同時對迭代計算參量執行一次加法計數后返至第二個步驟。

4 算法成效

對生存算法成效的評估主要在NSFNET網絡上開展，其結構如圖3所示，可見整個網絡共有21個鏈路和14個網元。假設每個鏈路僅分配唯一的S-No.，該鏈路平均最大可承載16個波長業務，鏈路的平均可靠率在區間[0.97，0.99]內。同時假設14個具有全光波變換[16]功能的網元中可隨機生成源宿網元對，且每一次所發起的業務連接建立請求均被定義為是一個波長業務的帶寬，該波長業務也在此源宿網元對之間隨機產生。該波長業務對鏈路資源的可靠性要求在區間[0.97，1]內。假設算法開展三次迭代計算，且為單個SRLG的失效率參數賦值0.5、0.3、0.2。

圖3 NSFNET網絡拓撲圖

為了考察生存算法在篩選通路方面的相對優勢，在通路資源配置上選擇專用保護算法(SPA)與生存算法做對比分析。對于SPA算法，其思想是為每一個WC配置一個專用的PC，且要求網中其他的光通路不能分享該PC上的光波帶寬資源。算法對ASON全網波長業務的保護成效可通過分析阻塞率、資源占用率和PC跳數等指標[17]來確定。

圖4描述了兩種算法下的不同SLA波長業務請求鏈接的通暢程度。正如前文所述，并非所有波長業務均要求提供1∶1[18]的通路資源保護，即無需在基于SRLG絕對分離情形下為所有不同的SLA波長業務尋找通路對。本文構思的生存算法正是基于此實際情況而設計，因此算法依據不同波長業務對通路資源可靠性要求的不同，在不存在SRLG絕對分離的通路對情形下，依然可搜索出合適的PC用于為不同SLA的波長業務提供鏈接請求保障。但SPA算法卻無法針對此情形響應出有效的選路策略，進而導致該波長業務的鏈接請求無法獲得保證。同時，生存算法主張的循環迭代計算機制在應對PC無法符合SRLG相對分離要求的情形時，可自動將風險鏈路刪除并重新實施路徑的計算與分析，從而避免陷入無解的境況。相比之下，SPA算法在面對此情形時卻無法搜索到和WC保持分離的PC。正是由于上述原因才導致生存算法在應對不同SLA波長業務請求時能保證較好鏈接率。

圖4 不同算法下SLA波長業務通暢程度

圖5所示曲線描述了不同算法下PC跳數大小情況。該指標體現了不同SLA波長業務的自愈時長，是衡量ASON生存能力的重要指標之一。其自愈時間和PC的段數呈正比。觀察圖中曲線可知，生存算法在本項測試中表現出的PC段數相對較少，因此該算法的自愈時長較短，于是實施該算法的ASON將具有更好的生存性。導致生存算法曲線走勢總體較低的原因是該算法在搜索PC時將那些和WC同屬于某一個編號S-No.的鏈路也考慮在內，展開選路的計算。但SPA算法思想與此截然相反，其選路機制主張放棄那些與WC同屬于某一個編號S-No.的鏈路。這就決定了SPA算法的計算對象銳減，需繞行更遠的鏈路方可獲得PC。這顯著增加了PC的段數，進而使得SPA算法下的跳值曲線走勢總體偏高。

圖5 不同算法下PC跳值

圖6所示為不同算法下的PC資源被占用的程度。該指標主要用于描述為一個SLA的波長業務鏈接請求需要的WC資源，所提供的預留PC資源的規模，可定義為WC和PC跳數的比值。從圖中曲線走勢不難看出，生存算法下的ASON保護帶寬資源被占用的程度較低。緣于生存算法的思想主張，在保持通路相對分離的前提下若WC可滿足不同SLA波長業務對其資源[19]的可靠性需求，就不再額外地去占用PC資源，因此可最大程度降低波長業務的請求對ASON全網開銷資源的消耗。故生存算法在節約全網通路資源方面表現出了SPA算法所不具備的優勢。

圖6 不同算法下PC資源占用程度

根據表1數據顯示，對于相同業務量的SLA波長業務請求，隨著迭代計算頻次的增加，業務通暢程度逐步好轉。但縱觀三組測試[20]數據可見，好轉幅度最為顯著的是在賦值2和3期間，在隨后的表現中這種變化趨勢較為微弱。因此在本次定義的ASON網絡環境中，三次以內的迭代頻次對生存算法效能度的影響最佳。

表1 迭代計算頻次對波長業務通暢度的影響力

5 結 語

助力大數據技術在ASON中的融合應用發展，首要解決的問題是網絡生存性。本文從生存性指標出發提出了一種基于不同SLA波長業務對通路對資源不同需求的生存性算法。算法本著相對分離原則從SRLG中規劃出科學的通路對用于實施SLA波長業務的承載。評估數據表明所構思的生存算法能夠較好地改善ASON在應對SLA多波長業務承載請求時的生存能力。相對于傳統的算法方案，本文算法具有更優的全局性和適應性。