[[alternative]]A Study of Virtual Topology Reconfiguration Problem in WDM Networks with Survivability Constraint

碩士資訊工程學系[[abstract]]分波多工（Wavelength Division Multiplexing, WDM）網路之組成包含了實體拓樸（physical topology）以及虛擬拓樸（virtual topology）。在實體拓樸當中的每一條鏈路代表著分波多工網路上的一條光纖，而虛擬拓樸當中的每一條鏈路則是代表著一條光路徑的存在。當中每筆傳輸需求均透過來源端點的發送器以及目的端點的接收器經由專屬的波長配置來進行傳送。伴隨著虛擬拓樸架構設計技術之成熟，在面對虛擬拓樸之設計時，網路的存活性（survivability）的考量也就相對的日趨重要。因為當中每一筆傳輸需求均挾帶著龐大的資料量，為了避免傳輸資料因光纖鏈路之損毀而發生遺失，於是便發展出保護機制（protection scheme）以解決該問題。除了分波多工網路的存活性，另一個值得去注意的議題就是虛擬拓樸的重組態（reconfiguration）。所謂的重組態，是指當舊有的虛擬拓樸變得不再適用時，僅需藉由虛擬拓樸當中部份鏈路的調整，即可改善整體網路之效能。相較於重新設計虛擬拓樸，重組態之應用可以在有限的時間以及成本下有效地提昇網路之效能。 本論文主要研究為探討存活性分波多工網路之虛擬拓樸重新組態問題。假設實體拓樸、現有的虛擬拓樸與新的交通流量為已知，根據新的交通流量來針對現有的虛擬拓樸來進行重組態之動作，在有限定調整次數（r）的情況下，期望進行完重組態動作後能夠降低虛擬拓樸之目標函數值，該目標函數值為平均權重傳遞時間。由於當重新調整的次數較大時，要在多項式時間內找出最佳解是不實際的。因此在本論文當中便提出了兩個啟發式演算法：積極調整啟發式演算法（positive reconfiguration heuristic algorithm, PRHA）、保守調整啟發式演算法（conservative reconfiguration heuristic algorithm, CRHA），而為了解決啟發式演算法僅能找出區域最佳解的問題，亦提出了一個基因演算法（Genetic Algorithm）以便求得更好的近似最佳解（sub-optimal solution）。 經由實驗，證實了所提出的啟發式演算法以及基因演算法的確可以有效地藉由虛擬拓樸之調整，進而降低目標函數值而且其改善效果與最佳解之差異仍在可接受的範圍之內。藉由實驗結果之分析，可以發現當網路剩餘資源較為有限的情況下，CRHA的改善效果會較PRHA來的好；反之，則PRHA會有著較好的表現。另外，從實驗的結果亦可以得知，藉由本論文中所提出的基因演算法將可彌補啟發式演算法往往只能找到區域最佳解的不足。 關鍵字：分波多工、存活性、重組態、基因演算法、專屬保護機制[[abstract]]Wavelength Division Multiplexing (WDM) network is composed of physical topology and virtual topology. Each link in the physical topology represents a fiber in the WDM network and each link in the virtual topology represents a lightpath. Communication requests are transmitted by sending packets on a dedicated wavelength of the lightpath between the source node’s transmitter and the destination node’s receiver. Following the development of virtual topology design technique is more mature, the consideration of survivability of WDM network is more important. Since huge data packet is transmitted in one connection. In order to avoid the data loss owing to fiber failure, protection scheme should be developed to tackle this problem. Another significant topic is virtual topology reconfiguration except survivability. For the reconfiguration, it can adjust parts of link in virtual topology so that upgrade the performance of virtual topology when the virtual topology isn’t suitable. To compare with virtual topology design again, reconfiguration could upgrade entire network performance effectively. this thesis is studied the virtual topology reconfiguration problem of WDM network with survivability and reconfiguration constraints. Given the physical topology, virtual topology and traffic demand matrix, the goal is to reconfigure virtual topology under the reconfiguration constraint r so as to minimize the objective value. The objective value is the average weighted propagation delay. Since finding a polynomial time algorithm to solve it is impractical when the reconfiguration constraint r is larger, two heuristic algorithms are proposed to solve it: positive reconfiguration heuristic algorithm (PRHA) and conservative reconfiguration heuristic algorithm (CRHA). Since the heuristic algorithm may trap into local optimal, in this thesis, a genetic algorithm (GA) is also proposed to search near optimal solution. Experiment results reveal that the objective value can be decreased effectively by using proposed heuristic algorithms and genetic algorithm. The difference in improvement ratio between optimal solution and the result found by proposed algorithm is acceptive. From the observate of experiment results, the CRHA is better than PRHA when the spare resource is poor, otherwise the performance of PRHA is better than CRHA. Furthermore, GA outperforms two heuristic algorithms and can get better solution. Keywords：WDM、survivability、reconfiguration、genetic algorithm、dedicated protectio