Routing in All-Optical WDM Networks

全光式光纖網路上繞徑之研究

王聲葦(Sheng-Wei Wang)

指導教授 ： 林華君

國立清華大學/電機資訊學院/通訊工程研究所/博士(2008年)

摘要

隨著大量多媒體資訊在網路上傳送，使用者對於頻寬的需求也愈來愈高。
使用光波分割多工技術的全光式光纖網路能夠提供相當大量的頻寬以符合此急速增加的需求。
在全光式光纖網路中，繞徑的方法在整體網路效能中扮演了一個很重要的角色。
本博士論文主要分成三個部分研究在全光式光纖網路上繞徑的相關議題。

在本論文的第一部分，我們提出了一個新的替用式繞徑設計概念，我們的目標為降低連線阻斷率。
我們的主要概念為，我們要設計出新的替用式繞徑方法，可以將每一個來源目地配對的流量，以最佳化的流量分配分散在網路上。
若是有一種新的替用式繞徑方法，可以使網路上呈現最佳化流量分配時的流量型態，這個替用式繞徑方法應該可以最小化連線阻斷率。
我們將如何得到網路上最佳化分配數學化為一個非線性的流量最佳化問題，並使用標準的最佳化方法得到最佳化流量分配。
我們以此概念設計了兩種不同的替用式繞徑方法，一種為固定替用式繞徑，而另一種為動態替用式繞徑。
經過模擬的結果，我們發現我們提出的替用式繞徑方法都能大量降低連線阻斷率。

在第二部分，我們考量到替用式繞徑方法所使用的路徑問題。
在替用式繞徑中，每一個來源目的配對都事先決定多條路徑。
在以往的研究中，替用式繞徑多使用最短且不共用光纖的多條路徑。
然而，根據網路拓璞及每一來源目的配對的流量，這並不是一個好的選擇。
我們在這一部分提出了新的找尋不共用光纖的多條路徑的方法，目的為這些路徑在給替用式繞徑使用時，能夠有最低的連線阻斷率。
這個方法的主要概念為從被網路上最佳化流量分配所使用的路徑中尋找最好而且不共用光纖的多條路徑。
經過模擬的結果，我們發現我們提出的尋找路徑方法，在兩種不同的替用式繞徑方法使用下，都能有效地降低連線阻斷率。

在最後一個部分，我們考量在全光式光纖網路上的群播問題。
在光纖網路上，一個群播樹由一棵光樹來傳送，而在這一棵光樹上的每一個分光點，都必需為擁有分光能力的交換器。
然而，擁有分光能力的交換器比起一般交換器的成本大很多，因此並非每一個點都是擁有分光能力的交換器。
在如此的網路上做群播的繞徑，被稱做疏離分光群播繞徑。
疏離分光群播繞徑的效能，除了取決於繞徑方法外，具有分光能力的交換器在網路上的位置也很重要。
在這一部分，我們即研究在網路上決定具有分光能力交換器所擺設位置方法。
我們提出了兩個方法決定如何擺設這種交換器。
經過模擬之後，我們發現其中一種方法和最佳化的方法有很近的效能。
而我們的擺設方法和已知的疏離分光繞徑方法亦可以一起考慮，更進一步提升效能。

關鍵字

繞徑 ； 光波分割多工 ； 群播

並列摘要

In all-optical WDM networks, routing algorithms play an important role in the performance of the networks.
In this thesis, we consider some research topics related to routing algorithms in all-optical WDM networks.

Among the three categories of unicast routing algorithms for all-optical WDM networks, alternate routing algorithms are computationally efficient and able to yield low connection blocking probability.
In the first part, we propose a new approach to designing alternate routing algorithms for all-optical WDM networks in order to reduce the connection blocking probability.
The key idea is to try to route traffic in approximately the optimal way of splitting the traffic among the multiple routing paths between each source-destination pair.
Two alternate routing algorithms are proposed based on this approach.
Our simulation results show that the alternate routing algorithms designed according to the optimal way of splitting the traffic can effectively reduce the connection blocking probability.

In the second part, we consider the routing paths for alternate routing algorithms.
Depending on the traffic requirements of all source-destination pairs, hop-count based mbox{$k$-shortest} link-disjoint paths used in previous works may not be the best choice for the predetermined routing paths.
We propose a method to find a set of link-disjoint routing paths between each source-destination pair to be used by an alternate routing algorithm in order to reduce the connection blocking probability.
The key idea is to find a set of link-disjoint routing paths based on the routing paths that are utilized by the optimal traffic pattern in the network.
Our simulation results show that using the link-disjoint routing paths found by the proposed method yields significantly lower connection blocking probability than employing the hop-count based mbox{$k$-shortest} link-disjoint paths and using the routing paths found by the capacity-balanced alternate routing method~cite{ho02}.

In the third part, multicast routing is taken into account.
To reduce the cost, splitters which are used to realize multicast trees can be placed at a subset of nodes.
The problem of selecting a subset of nodes to place the splitters such that certain performance measure is optimized is called the splitter placement problem.
The goal is to place a given number of splitters in the network such that the average per link wavelength resource usage of multicast connections is minimized.
Two splitter placement methods are proposed.
The two proposed splitter methods are shown to yield significant lower average wavelength resource usage than the random placement method.
One of the methods is shown to produce near minimum average wavelength resource usage.

並列關鍵字

Routing ； WDM ； Multicast ； Splitter Placement

參考文獻

[1] M. Ali and J. Deogun, “Allocation ofMulticast Nodes inWavelength-Routed Networks,” ICC 2000, vol.2, pp. 614-618.

[2] M. Ali, “Optimization of Splitting Node Placement inWavelength-Routed Optical Networks,” IEEE Journal on Selected Area in Communications, vol. 20, no. 8, pp. 1571-1579, October 2002.

[3] R. Bhandari, “Optimal Diverse Routing in Telecommunication Fiber Networks,” in Proceedings of IEEE INFOCOM 1994.

[4] R. Bhandari, Survivable Networks: Algorithms for Diverse Routing, Kluwer Academic Publishers, Norwell, MA, USA, 1999.

[5] A. Birman and A. Kershenbaum, “Routing and Wavelength Assignment Methods in Singlehop All-optical Networks with Blocking,” Proceedings of IEEE INFOCOM, vol. 2, pp. 431-438, April 1995.