WDM網路中多點傳輸與波長指派問題研究

Abstract

在可見的未來，WDM 網路將被用來建置主幹網路，因此，建置多點傳輸功能，以提供多變的網路應用需求是必要的。在本篇論文中，我們擴展路由與波長指派問題（routing and wavelength assignment problem, RWA）的研究，重新定義在WDM網路具傳輸延遲限制的多點傳輸與波長指派的新問題，簡稱MRWAP-DC。在此問題中，多點傳輸需求具傳輸延遲限制且網路節點具不同的分光能力或波長轉換能力，多點傳輸代價定義為傳輸代價與所需光波長數的線性加權，其目的為對每一個需求尋找一個光樹狀傳輸路由集合（light-forest），在最小的多點傳輸代價下，使得這些多點傳輸需求可以在傳輸延遲限制內，成功的將資料傳輸至所有的目的節點。在本篇論文中，MRWAP-DC將被完整定義與描述，提出一個整數線性規劃（ILP）方法，使得MRWAP-DC問題可被轉換成條件定義最佳化問題，利用CPLEX 線性規劃工具以找出問題的最佳解。雖然ILP方法可用來找出滿足條件的最佳解，但只適合解決小規模的網路路由與波長指派問題，因此，我們提出兩個啟發式演算法（meta-heuristic）：螞蟻演算法（Ant Colony Optimization）與基因遺傳演算法（Genetic Algorithm）以解決兩個簡化的問題－URWAP-DC-SR和MRP-DC-WWC-SR。此外，針對動態網路路由與波長指派問題，執行時間為重要的考慮因素，因此，我們提出兩個直覺演算法：k-最短路徑近似演算法（Near-k-Shortest-Path-based Heuristic，NKSPH）與反覆尋解模型（Iterative Solution Model，ISM），以處理大規模網路的動態路由與波長指派問題。由實驗的數據結果，這兩個直覺演算法可以找到接近最佳解的近似解。 在本篇論文中，不僅利用ILP方法來定義MRWAP-DC問題，同時提出四種不同解決這類簡化問題的方法，透過利用ILP方法所得到的最佳解比較，這些方法可以找到接近最佳解的近似解，但花費的執行時間卻遠比ILP方法少。

Because optical wavelength division multiplexing (WDM) networks are expected to be realized for building up backbone in the near future, multicasting in WDM networks needs to be addressed for various network applications. This dissertation studies an extended routing and wavelength assignment (RWA) problem called multicast routing and wavelength assignment problem with delay constraint (MRWAP-DC) that incorporates delay constraints in WDM networks having heterogeneous light splitting capabilities. The objective is to find a light-forest for a multicast whose multicast cost, defined as a weighted combination of communication cost and wavelength consumption, is minimal. An integer linear programming (ILP) formulation is proposed to formulate and solve the special problem of MRWAP-DC, MRWAP-DC-WWC. Experimental results show that using CPLEX to solve the ILP formulation can optimally deal with small-scale networks. Therefore, we develop two heuristics, Near-k-Shortest-Path-based Heuristic (NKSPH) and Iterative Solution Model (ISM), to solve the problem in large-scale networks. Numerical results indicate that the proposed heuristic algorithms can produce approximate solutions of good quality in an acceptable time. This dissertation also investigates two special problems, URWAP-DC-SR and MRP-DC-WWC-SR by two meta-heuristics ant colony optimization (ACO) and genetic algorithm (GA). We compare the performance of the proposed algorithms with the ILP formulations. Solutions found by these meta-heuristics are approximately equal to those found by the ILP formulations, and the elapsed execution times are far less than that demanded by the ILP formulations.