IP網路與分波多工網路之最佳化選徑與資源配置演算法

Abstract

本論文進行四項下世代網路最佳化選徑與資源配置的問題研究，提升網路的運作效能與存活度。包括WDM核心網路中光封包交換系統的設計以及光路預約許可(admission)與路徑的規劃；以及NG-SONET網路以及 IP網路，以最佳化的網路路徑規劃與資源配置來達成高網路服務存活度(survivability) 所衍生的路徑規劃配置的問題。本論文相關章節內容說明如下： 在第一章，先簡要介紹下世代網路，說明在 WDM 網路、SONET網路以及 IP Multicast 網路相關的技術進展，並指出在這些網路中有關網路資源規劃與配置最佳化的問題。 在第二章，介紹目前在 WDM 網路中重要的關鍵技術元件的功能與限制，並說明目前在多波長交換網路的光封包交換系統(OPS)所面臨的一些研究議題。同時提出克服相關問題的新式 OCPS 交換模式，以及相關的實驗網路- OPSINET。接著提出一個新的具有 buffer 能力的 OPS 系統架構設計，運用 WDM 多波長的性質、AWG的交換能力以及Cyclic Demux分單元的特性，設計出 non-blocking 的交換器，同時將其後所介接的 FDL 運用不同的波長擴充成為多個同樣時間長度的 FDL，大幅降低達成特定 packet loss probability 所需要使用的 FDL 的數量，並提出此一設計的效能分析。 在第三章，首先介紹光路預約問題的特性，目前在 WDM 網路中，靜態的光路規劃配置的問題，被稱為 RWA problem，其特性是沒有配置波長轉換功能的節點中，光路所經過的link 上都需要使用同一個頻率的光波。因為這個同一光路上光波連續的限制(Wavelength Continuality)，RWA problem 已經被證明為是一個 NP-Complete Problem。光路預約需要考量光路許可、路徑規劃以及光波配置，想要達到最佳化的配置，必須同時這三項因素，基本上光路預約問題也是一個NP-Complete Problem。我們運用網路最佳化方法來解決這一個網路資源配置的問題。 在第四章，先介紹 SONET 網路以及 NG-SONET 網路的新功能；並討論如何用用最少的網路資源來達成使用者對於網路存活度的期望的問題。依據數據資料傳送先天上可以因應網路頻寬變化調適的特性，提出一個在 NG-SONET 網路上的新的網路存活度需求的概念-網路存活度品質(Quality-of-Survivability)，讓使用者可以定義在網路正常運作模式以及面臨 link failure 或是 node failure 情況下所需要使用的傳輸頻寬。配合 NG-SONET VCAT點對點的大容量傳輸電路可以由數條容量較小的電路組成，但仍能維持資料的同步的特性，同時考量傳輸電路的路徑規劃與路徑的存活度需求，將相關的傳輸電路分散配置，降低所使用的電路因為 link failure 或是 node failure所造成的影響，同時達成運用最少的網路頻寬來達成使用者對於傳輸頻寬與存活度的需求。 在第五章，先簡要介紹網路編碼(Network Coding)技術，以及其在提升網路頻寬的使用效率與網路存活度上相關的研究成果，並介紹運用網路編碼技術來達成高存活度的網路群播(multicast)的研究基礎。我們分析了運用網路編碼以及樹狀結構(Tree-based)模式來進行網路群播服務所需要使用的網路頻寬，並探討其在疏密度不同的網路上的適用性。 在第六章，回顧本研究相關的研究成果，並提出未來可以再進一步探討的方向。

In this dissertation, four routing and resource provisioning problems in next generation networks are dealt with. The first two problems are related to transport functions of core networks in how to design a WDM OPS system and the Advance Lightpath Reservation problem in WDM Networks. The third one is about NG-SONET networks to find an optimal solution for Quality-of-Survivable multi-path routing and provisioning problem. The last one correlates to a survivable multicast IP network. This dissertation is organized as next described. In Chapter 1, we first give a brief introduction to NGN and make descriptions of some technology progresses in WDM, SONET, and IP multicast networks. We also point out several routing and resource provisioning problems in these networks. In Chapter 2, we first give a brief introduction to OPS enabling technologies, discuss the design issues of multi-wavelength optical packet switching networks and propose a new switching architecture to route packets and resolve contentions in both the wavelength and space dimensions together. In Chapter 3, we focus on the routing and resource allocation issues of prescheduled lightpath provisioning problems and give a Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks. The major challenge is that we need to determine request admission, as well as Routing and Wavelength Assignment jointly. In Chapter 4, we investigate the problems of how to meet the survivability requirements which users expect while lowering network resources consumed and propose a Quality-of-Survivability concept benefit by a phenomenon that data services are tolerant of bandwidth degraded gradually as the available bandwidth reduces. The goal of routing and resource provisioning is to satisfy bandwidth requirements of different states and minimize total bandwidth consumption at the same time. In Chapter 5 we briefly introduce the emerging network coding fundamentals first. Based on the observations, network coding has been proposed as a new technique to enhance network throughput and survivability in the literature, we study the problem of optimal routing and bandwidth provisioning for survivable multicast communications using network coding. Finally, concluding remarks and future work are made in Chapter 6.