標題: 階層式交換器光纖網路上通道設置與保護之理論分析
Theoretical analysis of tunnel allocation in survivable MG-OXC networks
作者: 郭修嘉
Xiu-Jia Kuo
陳健
Chien Chen
資訊科學與工程研究所
關鍵字: 多單位光學交換器;通道;容量平衡通道配置法;權重通道配置法;通道式分段保護機制;整數線性規畫;Multi-granularity Optical Cross-Connect;tunnel;Capacity-Balanced Static Tunnel Allocation;Weighted Tunnel Allocation;Tunnel-based Segment Protection;Integer Linear Programming
公開日期: 2005
摘要: 在多單位交換器光纖網路中,數個綁成一束的連續波長形成一個通道(tunnel)並且像一個單獨波長一樣一起做交換。通道路徑上的交換器尺寸可因此而變小並降低成本。我們提供了一個 0/1 整數線性規畫(Integer Linear Programming)來解決多單位交換器光纖網路中長度固定的通道設置問題。先前的輔助圖模型被擴充成階層式的輔助圖模型來配合此整數線性規畫(ILP)。我們另外比較了其他種演算法,包括CBSTA,WTA和PCWTA。在數種光纖組合和網路拓樸下,模擬結果都顯示出PCWTA和WTA優於CBSTA,且他們都相當接近我們用整數線性規畫所求出的最佳解。接著在通道長度固定的假定下,我們分析各種通道長度對網路阻塞率的影響。這個假定出現在之前其他作者的論文中,但是該作者並沒有很仔細的解釋在該假定下,何種通道長度為最佳與其動機。一個利用Erlang Loss Formula來設計出的阻塞率模型在此被提出,並用來評估各種通道長度的優劣。在數個不同的網路拓樸下,此模型分析出的結果十分接近我們另外做的模擬結果,我們因而發現最佳的通道長度與網路拓樸是有相關的。最佳的通道長度應該要接近網路中節點之間的平均距離。 我們接著探討單一線路故障時的保護機制。一個名叫通道式分段保護的機制(TSP)已被發表來回復因線路故障所中斷的通訊。在通道已被設置好之後,我們再提出一新的整數線性規畫來解決靜態的路由與波長分配問題,並且將備份的頻寬分享機制考慮進來。模擬結果顯示出TSP能勝過另一種更直覺的保護機制(TPP)。
Multi-granularity Optical Cross-Connect (MG-OXC) has been proposed to provide a cost-efficient way to support the growing demand for bandwidth. In the MG-OXC networks, consecutive wavelengths are bundled to form a tunnel and then switched as a single unit. Network resources at the intermediate nodes on the route of a tunnel, including switching fabrics and multiplexers, can thus be reduced. We suggest a 0/1 Integer Linear Programming (ILP) formulation for RWA with tunnel allocation in MG-OXC networks under tunnel length constraint. The previous auxiliary graph model is extended to a layered auxiliary graph model to facilitate the formulation. We compare the performance of different heuristics, including CB-STA, WTA and PCWTA, to the ILP solution. The simulation results show that PC-WTA and WTA outperforms CB-STA in all switching type combinations and network topologies, and they are very close to the optimal value calculated from our ILP formulation. We further analyze the impact of tunnel length on blocking rate based on the hypothesis of fixed tunnel length constraint. This hypothesis occurred in previous work, but the authors didn’t explain its motivation clearly. A blocking probability model used Erlang loss formula is provided to estimate the performance of tunnel allocation with different tunnel length constraint. Based on the analytical results, which have proved to be very close to the simulation results, obtained from various kinds of networks, we find that the best performance on the length of a tunnel is related to the network topology. To put it plainly, the most suitable length of a tunnel should be the smallest integer greater than the average hop distance or the smallest integer greater than the average hop distance plus 1. Then we aim to provide an efficient fault-recovery protection scheme for the lightpaths. A segment-based protection scheme, called Tunnel Based Segment Protection (TSP) is proposed to recover the communications interrupted by a fiber cut in previous work. After tunnel has been allocated, we suggest another ILP formulation to solve the static RWA problem with concept of sharing backup capacity. Simulation results show that the network performance is improved comparing to adapt a straightforward path protection scheme (TPP) for the MG-OXC networks.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT009323556
http://hdl.handle.net/11536/79083
Appears in Collections:Thesis


Files in This Item:

  1. 355601.pdf