評估式基因演算法應用於高存活性網路之頻寬分配問題

本研究在現有的路徑繞送機制下，運用建立備份路徑的方式，來保護主要路徑的繞送，當網路拓樸產生共用風險鏈路群組(SRLG; Shared Risk Link Groups)時，網路繞送依然可以100%恢復運作，且能有效解決備份路徑頻寬分配問題(SCA; Spare Capacity Allocation)，預期能有效降低備份路徑所使用之單位頻寬與Redundancy值。而本研究也根據網路產生SRLG，將SCA問題定成為單一連線失敗問題，允許網路連線產生單一連線中斷。在找尋主要路徑與備份路徑主要參考SSR(Successive Survivable Routing)演算法，而SSR演算法會因網路拓樸與流量需求的影響，造成解不穩定與不佳的情況，因此本研究將提出一個評估式基因演算法，改良傳統基因演算法隨機挑選要進行交配的染色體，並與SSR演算法相互配合，近而改善SSR演算之缺點，以求得更佳的解。在實驗方面，將進行兩組的實驗設計，而此兩組的實驗所著重的重點有些許差異，但在問題定義上，皆期望有效解決SCA問題，使整體備份路徑使用之單位頻寬能達到最小化，而第一組實驗設計的重點在於，(1) 流量無限制條件下，探索出最佳解，(2) 找出合適的參數設定方式，第二組的實驗設計重點在於，(1) 每組O-D pair所需之單位頻寬不一致，較符合現實狀況，(2) 備份路徑將採用分流的功能，每組O-D pair將平均分攤所要求之單位頻寬，(3) 所有連線將增加權重值，使網路每條連線的成本不盡相同，(4) 測試第四章所提出之參數設定方式。網路的拓樸與流量需求明顯會影響SCA問題的解果，而本研究所提出之評估式基因演算法在無限制條件的SCA問題有較佳的表演，且有效改善流量需求不同所造成的影響，而備份路徑加入分流的機制，更可以有效降低整體備份路徑所使用的單位頻寬。

關鍵字

共用風險鏈路群組；評估式基因演算法；備份路徑頻寬分配問題；高存活性網路

並列摘要

This thesis uses one backup path to protect each primary path to against single link failure in communication networks. This study proposes an MEGA to cooperate with SSR algorithm to improve the stability and effectiveness of solve the SCA (Spare Capacity Allocation) problems for SRLG (Shared Risk Link Groups) especially for randomized traffic requirements. The objective of SCA problem is to minimize the total spare capacity when all traffic demands require a 100% survivability or restoration level on different network topologies. Two kinds of experiments are performed in this thesis, the experiment I focus on a non-constrained situation and concentrates on finding the optimal solution. Furthermore, several experimental analyses of operational parameters are executed in this first experiment. The second experiment focus on: (1) nonuniform demands of origin-destination pairs are allowed; (2) “Spilt Flow” scheme is adopted to set up multiple backup paths for protecting one working path; (3) Given network topology and each link cost, the value of redundancy value is significantly influenced by different flow pattern. The experimental results of the first experiment show that MEGA can efficiently approach the best solution. The results of the non-constrained SCA problems also compares with several existing SCA algorithms and reveals that MEGA can enhance the performance of SSR algorithm to prevent the randomized defect of initial route ordering from influencing the result of SCA problem.. The results of the experiment II show that backup path with “Spilt Flow” scheme can effectively reduce total spare capacity required.

並列關鍵字

SRLG ； MEGA ； Survivable Network ； SCA

參考文獻

[1] H. Kerivin, D. Nace, and T-TL. Pham, “Design of capacitated survivable networks with a single facility,” IEEE/ACM Trans. Networking, vol. 13, no. 2, pp. 248-261, Apr. 2005.

[2] J. H. Holland, Adaptation in Natural and Artificial Systems, MIT Press, 1975.

[3] J. Mccall, “Genetic algorithms for modeling and optimization,” Journal of Computational and Applied Mathematics, vol. 184, pp. 205-222, 2005.

[4] J. A. Vasconcelos, J. A. Ramirez, R. H. C. Takahashi, and R. R. Ssldanha, “Improvements in genetic algorithm,” IEEE Trans. Mag., vol. 37, no. 5, Sep. 2001.

[5] C. N. Bendtsen, and T. Dkrink, “Dynamic memory model for non-stationary optimization,” in Proc. Congress On Evolutionary Computation (CEC’02), 2002, PP. 145-150.

國際替代計量

評估式基因演算法應用於高存活性網路之頻寬分配問題

全文下載

主題瀏覽