都會擷取環形光網路之低運算複雜度動態訊務彙集機制

Abstract

在近幾年裡，同步光纖(SONET)環狀網路被大幅應用在光纖基礎建設上。而且隨著時間經過，光纖網路的發展已經有了很大的進步，不只如此訊務的流量也大幅激增。此外由於分波多工(WDM)的技術的成熟並且被大幅應用下，光纖網路的傳輸容量大幅的提升。然而相對於一個波長提供的頻寬，訊務的流量仍是相當的小。所以為了有效的利用資源，可以利用訊務彙集的技術，把需求頻寬小的訊務彙集到頻寬大的波長上。 在本篇論文中，我們考慮動態訊務彙集的問題。而且我們的目標是讓波長頻寬的使用率達到最高，同時降低新連線呼叫拒絕率。根據要達成的目標，我們把這個問題公式化成整數線性規劃(ILP)的問題，並且為了解這個問題，我們從模擬退火演算法的精神，提出一個STGA演算法來求的最佳解。但是因為計算複雜度的關係，我們另外提出計算法雜度較低的HTGA的演算法。在HTGA演算法裡面主要有三個步驟：訊務彙集的動作、波長指派的動作、訊務重新被安排的動作。這些動作的主要目的是在儘可能不要改變光通道的情況下讓系統的使用率更好。 從模擬裡我們可以得到幾個結果，HTGA在系統使用效率方面只比STGA差10%左右，而在計算複雜度方面HTGA卻是比STGA低很多；除此之外，HTGA在光通道被重新安排的數目也是比STGA少很多。從這些結果顯示，我們可以指出HTGA是個有可行性且吸引人的演算法。

In recent years, synchronous optical network (SONET) ring networks have been widely deployed for the optical network infrastructure. The progresses of optical networks evolve with time; meanwhile, the carried traffic streams surge. The transmission capacity of an optical network largely increases because of the development and application of wavelength division multiplexing (WDM) technologies. However the required bandwidth of a traffic stream is also much smaller than the bandwidth capacity of a wavelength. Thus, in order to efficiently utilize the network resources, many lower-speed traffic streams can be multiplexed onto a high-speed wavelength by traffic-grooming technique. In the thesis, we consider the traffic grooming problem, which the property of the traffic is dynamic and nonuniform traffic. Our objective is to effectively reduce the new call blocking rate and maximize the utilization efficiency of the wavelengths which are used by the system. Integer linear problem (ILP) methodology is applied to formulate for this problem. And, in order to solve the ILP, we first propose a simulated annealing-based traffic grooming (STGA) algorithm to obtain the optimal solution. However, the STGA algorithm is infeasible due to its computation complexity. Alternatively, we propose a heuristic algorithm, called a heuristic-based traffic grooming (HTGA) algorithm. There are the three main operations in HTGA algorithm: operation of traffic grooming, operation of wavelength assignments, operation of traffic rearrangement. The main purpose of these operations is to achieve the better system utilization without changing the lightpath topology as could as possible. From the simulation evaluation, network performance measures are observed. For system utilization, the HTGA algorithm is only 10% less than the STGA algorithm, whereas the computation complexity of the STGA algorithm is much larger than that of the HTGA algorithm. In addition, the number of rearranged lightpaths by the HTGA algorithm is fewer than the ones by the STGA algorithm. From these results, we can conclude that the HTGA algorithm is a feasible and attractive algorithm.