在全光波長分割多工存取網路上對多點傳輸技術的路徑繞送與波長分配演算法之研究

Routing and Wavelength Assignment Algorithms for Multicast Communication in All-optical WDM Access Networks

李勝楠(San-Nan Lee)

指導教授 ： 黃依賢

元智大學/資訊學院/資訊工程學系/博士(2006年)

https://doi.org/10.6838/YZU.2006.00288

摘要

由於光纖網路系統(Optical network)所擁有更多的頻寬，頻寬可擴充性以及適用於各種不同資料的傳輸，使得光纖網路系統將取代寬頻的網路系統，尤其在大都會型網路中(Metropolitan network 或 access network)的骨幹網路，以及光纖網路到家(Fiber to the Home, FTTH)，都將是未來的趨勢。在現階段的網路系統中，網際網路已經深入到每個家庭中，網際網路的技術日益更新，從早期的上網瀏覽資料，至今線上聊天，隨選視訊，多媒體傳輸以及線上會議等技術也都相繼發展研究中，也因此網路的頻寬也愈來愈不敷使用。由於波長分割多工系統擁有多個不同波長的頻道可供不同種類，或不同傳輸性質的資料在不同的波長頻道上傳輸，不但能提供更高的頻寬，也可以將傳輸的資料進行分類，以達到頻寬的有效利用、降低傳輸時間以及阻隔率(Call blocking probability)。
在波長分割多工系統下的路徑繞送和波長分配演算法主要分成以競賽為主(contention-based)和以保留頻寬為主(reservation-based)的方式應用於不同的網路拓樸，在環狀存取網路上我們發展出以競賽為主的排程與重新排程演算法，以更有效率的來分配頻道。另外我們也發展出以保留頻寬為主的演算法（ring-tree-based RWA algorithm）使用在網狀存取網路上。
首先使用類神經網路演算法的預測模組被提出應用於WDM ring access network，本研究著重在如何收集封包傳送的情形，判斷下一個封包應該要使用那個頻道來傳送相同目的端的封包並透過相同的頻道來傳送，以減少波長轉換的機率，並降低傳輸的時間。另外重新排程演算法也被提出應用於WDM ring access network上，利用重新排程的機制，能讓即時封包在時間的限制之下傳送到目的地，並且不會影響到非即時封包的傳送。這兩個議題的研究都是以ring為其網路的架構討論，也讓我們在多對多多點傳輸技術中，發展出以虛擬環的觀點來進行討論如何更有效率來節省鏈結數。尤其是在預測模組中，討論的方式是以目的端為主，和多對多多點傳輸技術的特性不謀而合。
模糊控制理論(Fuzzy control theory)用來控制網路負載平衡和跳躍次數(hop count)之間的交易(trade-off)，利用模糊控制不會因為跳躍次數過多而造成頻寬的浪費。此研究將應用於多對多多點傳輸技術上QoS的研究，因為QoS強調的是不同等級的服務有不同的服務品質，所以應用模糊控制理論，正好可以控制不同服務品質所需要的頻寬或減少頻寬的浪費。然後，提出ring-tree-based routing and wavelength assignment (RTRWA)演算法應用於多對多多點傳輸技術上，並且以先前ring的相關研究，發展出虛擬環的觀念，減少了鏈結數的使用。最後我們加入QoS來討論，發展出ring-tree-based routing and wavelength assignment with delay constraint (RTRWA-DC)演算法，使用模糊控制理論來控制負載平衡和跳躍數。
在多媒體傳輸、隨選視訊、QoS和線上會議等網際網路應用愈來愈廣泛的今天，波長分割多工的技術也廣泛的被討論中。這些相關的技術可分成一對一(One-to-one)、一對多(One-to-multipoint)和多對多(Multipoint-to-multipoint)的傳輸方式。一對多和多對多的傳輸可稱為多點傳輸技術(Multicast communication)，大部分的光纖系統研究都著重在一對一和一對多的研究上，至於多對多的相關研究甚少，但是多對多的網路傳輸應用，如線上會議等，將是未來網路的重要功能。如何讓這些應用更有效率的使用頻寬並增加使用者的人數，將大大的提高網路的效率，所以本論文提出使用ring拓樸為架構，發展出在WDM mesh access network中，混合式路徑繞送演算法(ring-tree-based routing and wavelength algorithm, RTRWA algorithm)，並運用模糊理論來達到QoS的要求。

關鍵字

路徑繞送 ； 波長分配 ； 多點傳輸 ； 波長分割多工

並列摘要

The rise of the Internet has caused enormous variations in network applications, especially for multimedia. On the WDM system, the routing and wavelength assignment problem can be solved by the contention-based scheme or the reservation-based scheme. Several important multimedia applications, such as video on demand, video conferencing, and distribution networks, share this characteristic that is suitably transmitted by the multicast scheme. In this dissertation, the contention-based schemes, stochastic model and PEM algorithm, are proposed to aggregate packets and reschedule real-time packets in the WDM ring access network. The reservation-based scheme, RTRWA-DC, is proposed in the WDM mesh access network. It uses the virtual ring to connect all multicast session member and improve the performance in terms of the call blocking probability, channel utilization and user capacity.
At first, this dissertation discusses the scheduling/rescheduling algorithms for ring topology. The Self-Organized Map (SOM) neural network is used to generate a stochastic generative model to assign a proper channel to a packet and achieve packet aggregation on a cost-effective OADM. Finding a way to decrease the transmission time can increase the performance of a WDM access network. In general, the applications for packet transmission between several nodes, such as multicast communication, voice, and video, share a property: same destination. This is why a heuristic algorithm is proposed to aggregate packets. Secondly, a novel real-time packet rescheduling algorithm, called the PEM (PDS-EAC-MTD) algorithm, is proposed. This algorithm uses a token-passing protocol to achieve QoS on a WDM Ring Access Network. The PDS (Priority-Differentiated Scheduling) algorithm deals with real-time packets, allowing them to be transmitted first so that the front line of the prescheduled nonreal-time packets can be inserted into the queue. The EAC (Earliest Available Channel) algorithm selects the earliest available data channel independently of the availability of the destination. The MTD (Minimum Time Difference) algorithm selects the minimum-time-to-wait channel to transmit the nonreal-time packet and quickly establishes the path of real-time packets. The discussion of the ring algorithm leads to a virtual ring using the ring-tree-based routing and wavelength assignment (RTRWA) algorithm.
Multicast session communications in WDM mesh networks require the development of efficient multipoint-to-multipoint multicast algorithms. Several heuristics have approximate solutions using lightpath or light-tree for one-to-multipoint multicast communications and few papers discuss the multipoint-to-multipoint multicast problems in WDM mesh networks. We propose a ring-tree-based routing and wavelength assignment (RTRWA) algorithm to enhance the network performance for multipoint-to-multipoint multicast communications. The RTRWA algorithm can find an optimal ring that covers all multicast group members to establish a connection. The simulation results show that the proposed algorithm outperforms the light tree-based algorithm in terms of blocking probability, user capacity, and mean maximum transmission time for various numbers of wavelengths, request rates, and session sizes, especially those featuring larger session sizes and lower request rates.
How to ensure that a packet is transmitted given the limited transmission time is very crucial. A ring-tree-based routing and wavelength assignment with delay constraint (RTRWA-DC) reduces the number of searching ring paths to achieve low complexity and sufficient number of links to increase the chance of successful connections. The fuzzy logic control (FLC) in FLC LLR algorithm is based on the traffic load and hop counts to determine whether or not the lightpath can be established. The fuzzy logic theory enhances the ring-tree-based routing and wavelength assignment with delay constraint (RTRWA-DC) algorithm. Simulation results show that the RTRWA-DC is more effective for resource utilization than the tree scheme in terms of lower call blocking probability and link utilization even in strict delay constraint. It is suitable for big group size and long holding time of multipoint-to-multipoint multicast communication.

並列關鍵字

RWA ； multicast ； WDM ； multipoint-to-multipoint

參考文獻

[Hwang05] I.S. Hwang, S. N. Lee and I.C. Chang, “Performance assessment of fuzzy logic control routing algorithm with different wavelength assignments in DWDM networks,” Journal of Information Science and Engineering, Vol. 22, No. 2, pp. 461-473, Mar. 2006.

[Hwang06a] I.S. Hwang, S.N. Lee and Y.P. Kuo, “Packet rescheduling in real-time using token-passing protocol in WDM ring access networks”, Tamkang Journal of Science and Engineering, Vol. 9, No. 2, pp. 107-114, June 2006.

[Aisawa97] S. Aisawa, K. Noguchi, and H. Miyao, “Learning method for neural network using weight perturbation of orthogonal bit sequence and its application to adaptive WDM demultiplexer”, IEEE Journal of Lightwave Technology, Vol. 15, No. 11, pp. 1997-2003, Nov. 1997.

[Bengi01] K. Bengi and H.R. Van, “CONRAD a novel medium access control protocol for WDM local lightwave networks enabling efficient convergence of real-time and data services,” Proceedings on Local Computer Networks, pp. 468-476, Nov. 2001.

[Cao05] Y. Cao and O. Yu, “QoS-guaranteed routing and wavelength assignment for group multicast in optical WDM networks”, Conference on Optical Network Design and Modeling, pp.175-184, 7-9 Feb. 2005.