光核心及光擷取網路之網路效能最佳化

Abstract

在本論文中，主要研究三個最佳化問題分別應用於光核心、光都會，以及最後一哩的光存取分頻多工(wavelength division multiplexing; WDM)網路中。在第一部分的研究中，我們提出一高效能之最佳化逼近演算法，稱為Lagrangean放寬與探索式演算法(Lagrangean relaxation heuristics; LRH)。此方法主要用以解決光路徑與光波長之選擇(routing and wavelength assignment; RWA)於包含各式光交換元件(例如：全光纖交換、寬頻帶交換，窄頻帶交換)之光核心網路上。首先，我們將此光路徑與波長選擇問題有系統的公式化成整合性最佳化問題。此最佳化問題的目標為盡力降低最擁擠光纖路段之波長使用率。Lagrangean放寬與探索演算法執行限制放寬的動作並經由次坡度疊代法(subgradient-based iterations)產生一組Lagrangean乘法參數用以計算出原問題之下限解。同時，此演算法使用這些Lagrangean乘法參數再搭配內部的新式探索演算法以得到接近最佳解之上限解。根據所得的下限解與上限解，我們可量化Lagrangean放寬與探索演算法之精確度與收斂速度。對於不同網路環境設定，可達到對Lagrangean演算法效能之評估。依照相同之量化標準，我們對此一新式演算法與傳統上採用線性放寬演算法(linear programming relaxation; LPR)進行效能之比較。此效能比較實測於各種廣為大眾熟知的網路以及電腦隨機產生的網路中。模擬結果證明Lagrangean放寬與探索演算法在精確度與收斂速度上皆優於線性放寬演算法。此結果對於較大網路環境尤其明顯。 接著，在第二部分的都會型光纖網路研究上，我們設計一可提供服務品質差異之仿效Banyan光封包交換系統(QoS-enabled pseudo-Banyan optical packet switching system; QBOPSS)，以應用於分頻多工光都會網路中。此系統由一群適當尺寸之光仿效Banyan封包交換器和少量光纖暫存器組成，以期達到高系統擴展性、高成本效益、以及低封包遺失率之目標。在此新式光封包交換系統中，封包排程機制由一考量服務品質差異之平行遞增排程演算法(QoS parallel incremental scheduling; QPIS)完成。此排程演算法在滿足兩個系統資源限制：封包交換器能力限制和光暫存器數量限制之下，極力達成系統效能之最佳化並優先滿足高優先權封包遺失率。值得注意的，我們證明此新式排程演算法具有“運算結果隨時間最佳化”的特性。換言之，每回合運算中搜尋到交換路徑的封包數量將隨時間漸增。接著，我們為此平行遞增排程演算法設計一套硬體實現，以真正達成平行運算之目標。根據此硬體實現，我們經由模擬與分析進一步顯示出此演算法可達到逼近最佳化之結果，並同時具有低計算複雜度之特性。假設N是系統輸入埠數量，W和M分別表示外部與內部光波長數量，則此演算法的計算複雜度可表示為O(NW×log2(NMW))。最後，比較平行遞增排程演算法與其他演算法的模擬結果，我們可看出此新式排程演算法在封包遺失率、服務品質差異性提供、以及計算複雜度上皆優於其他演算法。 最後，論文的第三部分：最後一哩光存取分頻多工網路，我們提出一分散式控制之被動光纖網路(distributed control passive optical network; DCPON)架構。利用低速之額外控制頻道反射並廣播控制訊息的設計概念，分散式控制被動光纖網路可達到高系統頻寬使用率以及低資源要求/回應時間的目的。此新式架構中的動態資源分配(dynamic bandwidth allocation; DBA)由可調式封包串聯比例分配伺服演算法(adaptive packet-by-packet rate-proportional server; A-PRPS)完成。在新的分散式控制被動光纖網路中，我們依據使用者之流量需求變動程度和/或服務品質需求程度適當地調整可調式封包串聯比例分配伺服演算法內部之比重參數以及門檻參數。利用對應之參數調整，此新式動態資源分配演算法可有效率地降低具有高流量變動率和/或高服務品質需求之使用者的平均封包延遲和延遲誤差。模擬結果進一步顯示可調式封包串聯比例分配伺服演算法在平均封包延遲上遠低於常見的週期可變式交叉輪詢演算法(interleaved polling with adaptive cycle time; IPACT)以及其他週期性頻寬分配演算法。

In this thesis, three optimization problems are investigated separately in the optical core, metropolitan, and first-mile access wavelength division multiplexing (WDM) networks. Firstly, in the core network, we propose an efficient approximation approach, called Lagrangean relaxation with heuristics (LRH), aimed to resolve routing and wavelength assignment (RWA) problem for multi-granularity WDM core networks facilitating fiber, waveband, and lambda switching capabilities. The RWA problem is first formulated as a combinatorial optimization problem in which the bottleneck link utilization is to be minimized. The LRH approach performs constraint relaxation and derives a lower-bound solution index according to a set of Lagrangean multipliers generated through subgradient-based iterations. In parallel, using the generated Lagrangean multipliers, the LRH approach employs a new heuristic algorithm to arrive at a near-optimal upper-bound solution. With lower and upper bounds, we delineate the performance of LRH with respect to accuracy and convergence speed under different parameter settings. We further draw comparisons between LRH and a typical linear programming relaxation (LPR) approach via experiments over several well-known networks and randomly generated networks. Numerical results demonstrate that LRH outperforms the LPR approach in both accuracy and computational time complexity particularly for large size networks. In the second part of the thesis, we present the architecture of a QoS-enabled pseudo-Banyan optical packet switching system (QBOPSS) for WDM metro networks. The QBOPSS system consists of a group of downsized optical pseudo-Banyan space switches and a handful of fiber-delay-line-based optical buffers, achieving high system scalability, cost-effectiveness, and low packet loss probability. Packet scheduling in QBOPSS is performed by a QoS parallel incremental scheduling (QPIS) algorithm. The algorithm minimizes the loss probability for high-priority packets while maximizing system throughput and satisfying two constraints (switch-contention free, and buffer-contention free). Most notably, we prove that QPIS is incremental, i.e., the computed packet sets within each time slot are monotonically non-decreasing. We then present a hardware system architecture to demonstrate the parallel implementation of QPIS. As will be shown, QPIS achieves a near-optimal solution with an exceptionally low complexity, O(NW×log2(NMW)), where N is the number of input ports, and W and M the numbers of external and internal wavelengths, respectively. From simulation results that pit the QPIS algorithm against two other algorithms, we show that QPIS outperforms these algorithms on packet loss probability, QoS differentiation, and computational complexity. Finally, in the last part– first-mile access network, we propose a distributed control passive optical network (DCPON). By using low-speed out-of-band control channel to reflect and distributed control information, DCPON achieves high utilization and low request/response time. Dynamic bandwidth allocation (DBA) in DCPON is done by an adaptable packet-by-packet rate-proportional server (A-RPRS). In DCPON, by adjusting weight and threshold parameters of A-PRPS according to bursty degrees and/or QoS requirements of users, A-PRPS dramatically downgrades mean delay and delay jitter for high bursty and/or high QoS requiring users. Simulation results show that A-PRPS outperforms the interleaved polling with adaptive cycle time (IPACT) and other cycle-based DBAs on mean packet delay.