臺灣博碩士論文加值系統

在光纖彙整網路中，需求連線對頻寬的要求不再是以波長為單位，而是可以要求較低的頻寬。而這些低頻寬的需求連線可以彙整在同一條波長上同時傳輸，然後再各自拆解至傳輸目的地，因此網路頻寬的使用率可以大幅提高，網路產量也因而增加。但是這些需求連線會因為其所要求頻寬的大小不同而使得其相對被阻塞的機率有所不同，因而產生所謂的容量不公平的情況。
允入控制可以用來改善容量不公平的問題。前人所提出的允入控制可以分為四類，分別是靜態頻寬保留、靜態臨界值保留、數學統計及馬可夫決策過程。
本研究的目的主要是針對光纖彙整網路的允入控制系統在公平性及網路產量的取捨間，提出可以使網路產量效能更加提昇，並且維持容量的公平性的馬可夫決策過程的方法。本研究所提的方法是基於動態臨界值設定的概念，並以暫存器來實作臨界值。允入控制系統中設置一個能儲存需求連線的連線暫存器(C-Buffer)，而網路拓樸中的每個單一連結皆關聯一個虛擬暫存器(V-Buffer)。當剩餘頻寬滿足新需求連線但所經過連結的虛擬暫存器有任一個不是空時，新的需求連線對於虛擬暫存器中的需求連線可依照可搶先(With Preemption, WP)、不可搶先(Without preemption, NP)二種模式操作。而NP的缺點與臨界值保留法一樣，會造成頻寬使用率降低。反之，WP的操作模式，則可以增加整體網路的產量，但系統卻又無法達到公平的狀態。而本研究整合暫存器於馬可夫決策過程，不同於以上二種的暫存器操作模式，提出一個基於最佳策略可搶先服務的動態操作模式，可以同時達到公平的機制又可以增加網路的產量。
最後模擬結果顯示本研究提出的方法可以達到較高的網路產量而且保持容量公平性。此外本研究所提方法的暫態時間為0.3單位時間明顯地比數學統計方法所需要10單位時間為佳。至於因使用具暫存器的公平允入控制所產生的平均等候時間，本研究所提動態搶先服務約為0.32單位時間介於可搶先服務與不可搶先服務之間。最後我們也比較本研究所提方法搭配不同的波長配置法或不同的網路拓樸下對容量公平性影響。

In optical grooming networks, requests with different bandwidth requirements can be multiplexed/demultiplexed into/from a wavelength to improve bandwidth utilization and network throughput accordingly. In such networks, capacity fairness becomes an important issue because requests of higher bandwidth requirements encounter higher blocking probabilities than those of lower bandwidth requirements.
Capacity fairness issue can be resolved by incorporating the call admission control mechanism. Previous studies on call admission control can be categorized in several types, including static bandwidth reservation (SBR), static threshold setting (STS), mathematical statistics (MS), and Markov decision process (MDP).
There exists a tradeoff between the fairness and the network throughput in the call admission control. This paper presents a dynamic preemption Markov decision process (DP-MDP) to further increase the network throughput without sacrificing the fairness. The proposed method is based on the concept of dynamic threshold setting which is implemented by a connection buffer (C-Buf) and a set of virtual buffer (V-Buf). If the residual bandwidth is sufficient to satisfy a new request and not all V-Bufs in the links passed by the new request are empty, the new request can be treated with two modes, i.e., with-preemption (WP) and without-preemption (NP). The NP mode similar to the STS method would result in the lower network throughput, while the WP mode could increase the network throughput but sacrifices the fairness. Instead of employing these two modes, this paper adopts a dynamic preemption Markov decision process to decide the proper timing to preempt according to the state of the system.
Simulation results show that the proposed DP-MDP improves the network throughput compared to the original MDP without sacrificing the fairness. Furthermore, the transient time of the proposed method is only 0.3 units obviously better than that of the MS method with the value of 10 units. Additionally, the average waiting time induced by the buffer is only 0.32 units. Finally, different wavelength assignment algorithms and different network topologies are also considered by the proposed method to evaluate the impact on the fairness.

中文摘要.......................................I
Abstract....................................III
致謝(Acknowledgement).........................V
表格目錄.....................................VIII
圖目錄........................................IX
Chapter 1簡介..................................1
1.1光纖網路.....................................1
1.2公平允入機制..................................1
1.3章節簡介.....................................3
Chapter 2相關研究及動機..........................4
2.1靜態頻寬保留法與靜態臨界值設定法..................4
2.2數學統計法....................................5
2.3馬可夫決策過程.................................6
2.4研究動機......................................8
Chapter 3基於動態可搶先馬可夫決策過程之公平允入控制....10
3.1網路模型概觀..................................10
3.2建構馬可夫決策過程模組..........................11
3.3調整回饋方程式類別權重VS.最佳策略分布的情形.........18
3.4單一連結馬可夫決策延伸至多重連結...................24
3.5公平允入控制演算法..............................26
Chapter 4數據結果................................31
4.1模擬程式環境...................................31
4.2各方法公平率的比較..............................32
4.3需求連線被阻塞的機率.............................33
4.3.1各類別連線被阻塞的機率.........................34
4.3.2整體需求連線被阻塞的機率........................36
4.4網路產量的比較..................................37
4.5暫存器內連線被搶先的次數..........................38
4.6暫存器內連線平均等待時間..........................39
4.7MS CAC方法其類別連線被阻塞機率的變化................40
4.8不同的波長配置法對公平率造成的影響...................42
4.9不同的網路拓樸對公平率造成的影響....................43
Chapter 5結論與未來展望.............................48
參考文獻.......................................50
附錄一:...........................................52
附錄二:...........................................53
附錄三:...........................................54

[1] B. Mukherjee, et al., “Traffic grooming in mesh optical networks, Optical Fiber Communication Conference, OFC 2004 , vol. 2, no. 3, pp. 23-27, Feb. 2004.
[2] M. Sivakumar, K. M. Sivalingam, and S. Subramaniam, “On factors affecting the performance of dynamically groomed optical WDM mesh networks, Workshop on High Performance Switching and Routing, HPSR 2005, pp. 411- 415, May 2005.
[3] Keyao Zhu, Hui Zang, and B. Mukherjee, “A comprehensive study on next-generation optical grooming switches, IEEE Journal on Selected Areas in Communications, vol. 21, no. 7, pp. 1173-1186, Sept. 2003.
[4] K. Zhu, and B. Mukherjee, “A review of traffic grooming in WDM optical networks: architectures and challenges, Optical Networks Magazine, vol. 4, no. 2, pp. 55-64, Mar. 2003.
[5] A. K. Somani, “Survivability and traffic grooming in WDM optical networks, Cambridge University Press 2006.
[6] Keyao Zhu, Hongyue Zhu, and B. Mukherjee, “Traffic engineering in multigranularity heterogeneous optical WDM mesh networks through dynamic traffic grooming, IEEE Network, vol. 17, no. 2, pp. 8-15, Mar. 2003.
[7] Thiagarajan and A. K. Somani, “Performance analysis of WDM optical networks with grooming capabilities, Proc. SPIE Intl. Symp. on Voice, Video, and Data Comm.- Terabit Optical Networking : Arch., Control, and Management, Boston, MA, USA, vol. 4213, pp. 253-262, Nov. 2000.
[8] K. W. Ross, D. H. K. Tsang, “The stochastic knapsack problem, IEEE Transactions on Communications, vol. 37, no. 7, pp. 740-747, Jul. 1989.
[9] P. Tran-Gia and F. Hubner, “An analysis of trunk reservation and grade of service balancing mechanisms in multiservice broadband network, IFIP Workshop TC6, Modeling and Perfomance Evaluation of ATM Technology, pp. 2.1, La Martinique. 1993.
[10] S. Thiagarajan , A. K. Somani, “Capacity fairness of WDM networks with grooming capabilities, Optical Network Magazine, vol. 2, no. 3, pp. 24-32, May 2001.
[11] J. Choi, T. Kwon, Y. Choi, and M. Naghshineh, “Call admission control for multimedia services in mobile cellular networks: a Markov decision approach, IEEE Symposium on Computers and Communications, ISCC 2000, pp. 594-599, 2000.
[12] K. Mosharaf, J. Talim, and I. Lambadaris, “A call admission control for service differentiation and fairness management in WDM grooming networks, International Conference on Broadband Networks, BroadNets 2004, pp. 162-169, Oct. 2004.
[13] K. Mosharaf, J. Talim, and I. Lambadaris, “A call admission control for service differentiation and fairness management in WDM grooming networks, Optical Switching and Networking Journal, OSN 2005, vol. 2, no. 2, pp. 113-126, Sep. 2005.
[14] K. Mosharaf, J. Talim, and I. Lambadaris, “Optimal resource allocation and fairness control in all-optical WDM networks, IEEE Journal on Selected Areas in Communications, vol. 23, no. 8, pp. 1496-1507, Aug. 2005.
[15] M. L. Puterman, “Markov decision processes, Wiley Inter-Science, New York, 1994.
[16] R, A, Howard, “Dynamic Programming and Markov Process, M.I.T. Press, Cambridge, 1960.