Branch and Bound 演算法在全光網路包含串音局限的限制條件之最佳化規劃效能分析

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：72

、訪客IP：18.117.81.240

姓名

郭承聰(Cheng-Chung Kuo) 查詢紙本館藏

畢業系所

通訊工程學系在職專班

論文名稱

Branch and Bound 演算法在全光網路包含串音局限的限制條件之最佳化規劃效能分析
(Optimised Design and Analysis of All-Optical Networks Incorporating crosstalk limited constraints using Branch and Bound Algorithm)

相關論文

★ 平行式最佳區塊碼解碼演算法	★ 數位廣播之視訊系統架構與信號估測
★ 粒子群優化演算法應用於電信業解決方案選商及專案排程之優化	★ 結合PSO及K-Means聚類分析演算法的圖像分割
★ 利用粒子群優化演算法改善分群演算法在訊號分群上之應用	★ 應用模糊聚類與粒子演算法之色彩分群研究
★ 粒子群優化演算法應用於企業更新數據網路採購之優化	★ 粒子群演算法應用於無線區域網路產品硬體開發成本優化
★ 粒子群演算法應用企業伺服器負載平衡之省電優化	★ 粒子群優化演算法應用於瓦斯業微電腦瓦斯表自動讀表之優化
★ 近場通訊之智慧倉儲管理	★ 在Android 平台上實現NFC 室內定位
★ 適用於訊號傳輸暨無線電力傳輸之設計	★ 結合PSO及圖像品質評估演算法識別頻譜訊號
★ 粒子群優化與二維Otsu演算法於影像二元化閥值選取研究	★ 利用A*解碼法應用到線性區塊碼的最大可能性解碼之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

光纖網路由於有許多技術仍處於發展初期，設備成本無法正確估計，而且對流量訊需求及新的應用發展具不確定性，導致無法正確量化網路頻寬的大小，加上網路設計規劃時，必須考量到之前發展的光纖設備和技術造成的限制作用。因此，網路最佳化問題在分波多工器WDM 全光網路中已日益獲得重視，線性規劃Integer Linear programming (ILP)是可以精確執行此任務的一種方式。
本論文中提及Routing and wavelength assignment(RWA)動態規劃多光纖、無波長轉換器的WDM 網路。給予一個流量矩陣，如每一個連結的光纖數量、每一條光纖所能支援的波長數量和每一個通訊需求所需的連線數量及連線時間等數據，建立線性規劃算式，運用Branch & Bound 演算法找出網路中所能建立連線的最大數量，分析及設計使得網路獲得最佳化。由於Branch and Bound 運算數量隨著變數的增加而呈指數增長，為使演算法在可接受的運算時間內分析更大量的變數，經由適當的上限(upper bound)設定或適當的設計網路模型達成此目的為網路最佳化的重要議題。另一方面，由於訊號在全光網路中會經過許多沒有光電轉換的交換器，在交換器中會產生串音來傷害訊號的品質，為此我們提出加入由串音因子計算BER，並在接收端設一個BER 可接受下限值的QoS 限制。

摘要(英)

Many optical technologies are relatively immature with respect to electronics, thus the cost of equipments can not be estimated correctly.
The unknown of future traffic demand and new applications development,it can not scale well with the network size. And network optimization must take currently and immaturity equipments functional constraints into account in the design. So, optimization problem of the WDM all-optical network is an important issue today. Integer Linear Programming is the most used exact method to perform this task.
In this thesis, we present dynamic routing and wavelength assignment in multifiber WDM networks without wavelength conversion. Give a traffic
matrix with parameters fiber amount, wavelength amount,connect lightpath request amount and connect period, to propose an ILP formulation. By using Branch and bound algorithm to find out the maximum lightpath that can be connected in the network, analysis and design to get network optimized.
The computation of Branch and bound algorithm is polynomially increase with variant amount. The appropriate upper bound or appropriate network
modeling can let the algorithm computes more variants in the acceptablecomputation time. Moreover, because a signal in all optial network passes through many switches without O-E-O converter, the crosstalk in the occurs in switches will impair the signal quality, thus we propose the BER counts with crosstalk factors, and set the QoS constraint of acceptable BER in
the receiver into the formulation.

關鍵字(中)

★ 全光網路

關鍵字(英)

★ All-Optical network

論文目次

第一章緒論…………………………………………………………………………..1
1.1 研究動機……………………………………………………………………1
1.2 論文架構……………………………………………………………………2
第二章 WDM 波長多工系統架構……………………………………………...………3
2.1 多工…………………………………………………………………………3
2.2 傳輸…………………………………………………………………………5
2.2.1 WDM傳輸系統……………………………………………………….13
2.3 交換………………………………………………………..………………15
2.3.1 不可穿透光和可穿透光交換……………………………………..15
2.3.2 光封包、連發和電路交換………………………………………..16
2.3.3 MPLS，MPλS 和GMPLS……………………………………………18
2.4 波長路由光纖網路(WRON)………………………………………………..19
2.5 光纖網路的標準………………………………….………..……………...20
2.5.1 ITU-T OTN 和ASON/ASTN 標準……………………………………20
2.5.2 IETF GMPLS 協定………………………………..………….…..….23
2.5.3 OIF………………………………………………………....………24
第三章光纖網路最佳化問題分類及定義…………………………….….………..25
3.1 問題分類……………………………………………………….………….25
3.1.1 時間水平軸分類…………………………………….…………….25
3.1.2 功能分類……………………………………………….………….26
3.2 網路設計…………………………………………………………………27
3.2.1 多層網路設計……………………………………………………27
3.2.2 保護與復原………………………………………………………27
3.2.3 動態流量的阻塞機率……………………………………………30
3.2.4 重新配置問題……………………………………………………31
3.2.5 矩陣………………………………………………………………32
3.2.6 WDM 網路的最佳化問題………………………………………….32
3.2.7 連線成本的網路最佳化…………………………………………33
3.3 最短、分解和備用路徑…………………………………………………34
3.4 虛擬波長路徑和波長路徑………………………………………………35
第四章 RWA 問題的ILP 公式……………………………………………………...37
4.1 多光纖網路的承載流量最大化…………………………………………38
4.2 波長最小化規劃…………………………………………………………40
4.3 串音元件和QoS 限制條件………………………………………………41
第五章模擬結果與討論…………………………………………………………..46
5.1 串音因子影響BER 的QoS 門檻限制…………………………………….46
5.2 環狀網路模擬…………………………………………………………….47
5.2.1 單一光纖，多個波長模擬…………………………….…………47
5.2.2 多條光纖，單一波長模擬……………………………………….48
5.3 實際網路模擬……………………………………………………….……50
5.3.1 14 條光纖，4 個波長…………………………………………….51
5.3.2 14 條光纖，3 個波長…………………………………………….53
5.4 阻塞機率(Blocking probability)評估……………….………………55
5.5 Branch and Bound 演算法……………………………………………….56
第六章結論…………………………………………………………………………59
參考文獻……………………………………………………………………………..60

參考文獻

參考文獻
[1] Zhengbing Bian,”Wavelength Assignment Algorithms For WDM Optical
Network,” A Thesis Submitted In Partial Fulfillment Of The Requirements For The
Degree Of Master of Science in the School of Computing Science,SIMON FRASER
UNIVERSITY,August 2003.
[2] Ioannis P.Androulakis And Christodoulos A. Floudas”Distributed Branch And
Bound Algorithms For Global Optimization,” 1998.
[3] Arne John Glenstrup,”Optimised Design and Analysis of All-Optical Networks,”Technical University of Denmark PhD Thesis, Summer 2002.
[4] Gurvan Huiban and Geraldo Robson Mateus,”Opticmzation Aspect of The
Reconfiguration Problem In WDM Networks,” Computer Science Department,
Federal University of Minas Gerais,October 2005.
[5] Mohamed Saad And Zhi-Quan Luo,”On the Routing and Wavelength Assignment
in Multifiber WDM Networks,” 2003.
[6]Josue Kuri,”Optimization Problems in WDM Optical Transport Networks with
Scheduled Lightpath Demands,” Telecommunication at ENST PhD Thesis,September
2003.
[7] Jeffery L.Kennington, Mark W.Lewis,”The Path Restoration Version of the Spare Capacity Allocation Problem with Modularity estrictions:Modes,Algorithms, and an Empirical Analysis,” INFORMS Journal on Computing 13(3):181-190, 2001.
[8] N.R. Mahapatra and S. Dutt, “Sequential and Parallel Branch-and-Bound Search Under Loimited-Memory Constraints,” The IMA Volumes in Mathmatics and its Applications-Parallel Processing of Discrete Problems, P. Pardalos (ed.), Vol. 106.139-158, Springer-Verlag New York, Inc., 1999.
[9] Y. Pointurier and M. Brandt-Pearce, “Routing and wavelength assignment
incorporating the effects of crosstalk enhancement by fiber nonlinearity,” Prodeedings of the 39th Annual Conferece on Information Sciences and Systems, pp. 212-216, March 2005.
[10] Huifang Kong and Chris Phillips, “A Fast Two-Stage Routing and Wavelength
Assignment(RWA) Mechanism for Optimal Max-RWA Problem in Wavelength
Constrained WDM Networks”, accepted by the 10th European Conference on
Networks & Optical Communications (NOC 2005), London UK, July, 2005.
[11] G. Maier, A. Pattavina, M. Tornatore. ” WDM network optimization by ILP based on source formulation,” In Proceedings, IEEE INFOCOM 2002, New York (NY) USA,June 23-27, 2002.
[12] T. Gyselings, G. Morthier, R. Baets, “Crosstalk analysis of multiwavelength optical cross connects,”,IEEE Journal of Lightwave Technology, p 1273-1283,1999.
[13] Teck Yoong Chai, Tee Hiang Cheng, Sanjay K. Bose, Chao Lu, Gangxiang Shen,
“Crosstalk Analysis for Limited-Wavelength-Interchanging Cross Connects,” IEEE
Photonics Technology Letter, VOL.14,No.5, May 2002.
[14] Y. Xin, G. Rouskas and H. Perros, “On the physical and logical design of
large-scale optical network", Journal of Lightwave Technology, Vol. 21 (2003), pp:904-915.
[15] Tim Granger, “ Reconfigurable wavelength-switched optical networks for the
Internet core,” University of Cambridge Computer Laboratory PhD Thesis, Nov.
2003.
[16] Rajiv Ramaswami, Kumar N. Sivarajan, “Routing and wavelength assignment in
all-optical networks,” IEEE/ACM Trans. Netw. 3(5): 489-500 (1995)
[17] Rajesh M. Krishnaswamyh and Kumar N. Sivarajan, “Algorithms for Routing
and Wavelength Assignment Based on Solutions of LP-Relaxations,” IEEE
Communications Letters, VOL.5, No.10, Oct. 2001.
[18] Dhritiman Banerjee and Biswanath Mukherjee, “Wavelength-Routed Optical
Networks: Linear Formulation, Resource Budgeting Tradeoffs, and a Reconfiguration Study,” IEEE/ACM Transcations on Netowrking, VOL.8, No.5,Oct. 2000.
[19] Yurong huang,Jonathan P. Heritage and Biswanath Mukherjee, “ Connection
Provisioning With Transmission Impairment Consideration in Optical WDM
Networks With High-Speed Channels,” Journal of Lightwave Technology, VOL.
23,No.3, Mar. 2005.
[20] Poompat Saengudomlert, Eytan H. Modiano and Robert G. Gallager, “Dynamic
Wavelength Assignment for WDM All-Optical Tree Networks,” IEEE/ACM Transcations on Networking, VOL.13, No.4, Aug. 2005.
[21] Yongbing Zhang, Koji Taira, Hideaki Takagi and Sajal K. Das,”Adaptive
wavelength routing and assignment in optical WDM networks,” Optical Networks
Magazine September/October 2003.
[22] Y. Pointurier, M. Brandt-Pearce, T. Deng, and S. Subramaniam, “Fair QoS-Aware Adaptive Routing and Wavelength Assignment in All-Optical Networks," Proceedings of the IEEE International Conference on Communications (ICC), Istanbul, Turkey, June 2006.
[23] Y. Pointurier and M. Brandt-Pearce "Analytical Study of Crosstalk Propagation in All-Optical Networks Using Perturbation Theory," IEEE Journal of Lightwave Technology, December 2005, pp. 4074-4083.
[24] Iguatemi E. Fonseca, Raul C. Almeida Jr., Helio Waldman, Moisés R. N. Ribeiro:“Meeting Optical QoS Requirements with Reduced Complexity in Dynamic
Wavelength Assignment,” BROADNETS 2004: 331-333
[25] Y. Huang, W. Wen, J. P. Heritage, and B. Mukherjee, "Signal-quality
consideration for dynamic connection provisioning in all-optical
wavelength-routed networks," Proc., OptiComm, Oct. 2003.
[26] Y. Huang, A. Gencata, J. P. Heritage, and B. Mukherjee, "Routing and
wavelength assignment with quality-of-signal constraints in WDM networks,"
Proc., ECOC, paper no. P4.16, Sept. 2002.
[27] Yvan Pointurier, , Maïté Brandt-Pearce, “Analytical Study of Crosstalk
Propagation in All-Optical Networks Using Perturbation Theory,” JOURNAL OF
LIGHTWAVE TECHNOLOGY, VOL. 23, NO. 12, DECEMBER 2005.
[28] E. Salvadori, R. Battiti, " Quality of Service in IP over WDM: Considering Both
Service Differentiation and Transmission Quality ", Proc. IEEE "ICC 2004", Paris -
France, June 2004.
[29] Ioannis Tomkos, Dimitrios Vogiatzis, Carmen Mas Machuca, Ioannis
Zacharopoulos, Anna Tzanakaki, E. Varvarigos “Performance Engineering of
Metropolitan Area Optical Networks thuough Impairment Constraint Routing,” IEEE
Communications Magazine, Optical Supplement, August 2004.
[30] S. Shen, G. Xiao, and T. H. Cheng, "Evaluating link-state update triggers in wavelength-routed networks," in Proc. Asia-Pacific Optical Communications
Conference and Exhibition (APOC) 2004, 7–11 November 2004, Beijing, China.
[31] E. Kozlovski, M. Dueser, I. de Miguel and P. Bayvel "Analysis of Burst
Scheduling for Dynamic Wavelength Assignment in Optical Burst-Switched
Networks" 14th Annual Meeting of the IEEE Lasers & Electro-Optics Society, LEOS
2001. San Diego, California. 11-15 November 2001. paper TuD2.
[32] Rocco Cardillo, Vittorio Curri, Marco Mellia, Considering transmission
impairments in configuring wavelength routed optical networks, OFC 2006, Anaheim,CA, 5-10 March 2006
[33] Ashwin Sridharan, Kumar N. Sivarajan "Blocking in All-Optical
Networks",INFOCOM 2000, Tel Aviv Israel.

指導教授

賀嘉律(Chia-Lu Ho)

審核日期

2006-7-18

推文