Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19892
標題: 使用延遲緩衝器之光封包交換網路的效能增益
Performance Enhancement for All-Optical Packet Switching Networks with FDL Buffers
作者: 周冠宏
Chou, Kuan-Hung
關鍵字: 隨機分析
多節點封包排程
光緩衝器
光延遲線緩衝器
出版社: 資訊科學與工程學系所
引用: [1] X. Ma and G.-S. Kuo, “Optical switching technology comparison: optical mems vs. other technologies,” IEEE Communications Magazine, vol. 41, pp. S16-S23, nov. 2003. [2] D. J. Rabb and B. L. Anderson, “Optical cross-connect based on the spherical fourier cell,” Journal of Lightwave Technology, vol. 27, pp. 2737-2743, Jul 2009. [3] H. Wang, E. Aw, K. Williams, A. Wonfor, R. Penty, and I. White, “Lossless multistage soa switch fabric using high capacity monolithic 4 x 4 soa circuits,” in Optical Fiber Communication - incudes post deadline papers, 2009. OFC 2009. Conference on, pp. 1 -3, 22-26 2009. [4] S. Yuan and C. Lee, “Scaling optical switches to 100 tbs capacity,” in Photonics in Switching, p. PWB3, Optical Society of America, 2010. [5] N. Madamopoulos, V. Kaman, S. Yuan, O. Jerphagnon, R. Helkey, and J. Bowers, “Applications of large-scale optical 3d-mems switches in fiber-based broadbandaccess networks,” Photonic Network Communications, vol. 19, no. 1, pp. 62-73, 2010. [6] X. Li and M. Hamdi, “On scheduling optical packet switches with reconfiguration delay,” IEEE Journal on Selected Areas in Communications, vol. 21, no. 7, pp. 1156-1164, 2003. [7] B. Wu and K. Yeung, “On optimization of optical packet switches with reconfiguration overhead,” in 2005 Workshop on High Performance Switching and Routing, pp. 217 - 221, 12-14 2005. [8] B.Wu, K. L. Yeung,M. Hamdi, and X. Li, “Minimizing internal speedup for performance guaranteed switches with optical fabrics,” IEEE/ACM Transactions on Networking, vol. 17, no. 2, pp. 632-645, 2009. [9] V. Alaria, A. Bianco, P. Giaccone, E. Leonardi, and F. Neri, “Multihop control schemes in switches with reconfiguration latency,” IEEE/OSA Journal of Optical Communications and Networking, vol. 1, no. 3, pp. B40-B55, 2009. [10] G. Papadimitriou, C. Papazoglou, and A. Pomportsis, “Optical switching: switch fabrics, techniques, and architectures,” Journal of Lightwave Technology, vol. 21, pp. 384-405, feb. 2003. [11] J. Kim, C. Nuzman, B. Kumar, D. Lieuwen, J. Kraus, A. Weiss, C. Lichtenwalner, A. Papazian, R. Frahm, N. Basavanhally, D. Ramsey, V. Aksyuk, F. Pardo, M. Simon, V. Lifton, H. Chan, M. Haueis, A. Gasparyan, H. Shea, S. Arney, C. Bolle, P. Kolodner, R. Ryf, D. Neilson, and J. Gates, “1100 times; 1100 port mems-based optical crossconnect with 4-db maximum loss,” IEEE Photonics Technology Letters, vol. 15, pp. 1537-1539, nov. 2003. [12] A. Olkhovets, P. Phanaphat, C. Nuzman, D. Shin, C. Lichtenwalner, M. Kozhevnikov, and J. Kim, “Performance of an optical switch based on 3-d mems crossconnect,” IEEE Photonics Technology Letters, vol. 16, pp. 780-782, march 2004. [13] V. Li, C. Y. Li, and P. K. A. Wai, “Alternative structures for two-dimensional mems optical switches [invited],” Journal of Lightwave Technology, vol. 3, no. 10, pp. 742- 757, 2004. [14] B. Towles and W. Dally, “Guaranteed scheduling for switches with configuration overhead,” IEEE/ACM Transactions on Networking, vol. 11, pp. 835 - 847, oct. 2003. on Communications, vol. 55, no. 6, pp. 1212-1219, 2007. [16] B. Wu and U. of Hong Kong, Algorithm design in optical networking. University of Hong Kong, 2007. [17] B.Wu, K. L. Yeung, P.-H. Ho, and X. Jiang, “Minimum delay scheduling for performance guaranteed switches with optical fabrics,” Journal of Lightwave Technology, vol. 27, no. 16, pp. 3453-3465, 2009. [18] D. K. Hunter, M. C. Chia, and I. Andonovic, “Buffering in optical packet switches,” IEEE/OSA Journal of Lightwave Technology, vol. 16, pp. 2081-2094, Dec. 1998. [19] A. Als, Z. Ghassemlooy, G. Swift, P. Ball, and J. Chi, “Performance of the passive recirculating fiber loop buffer within an otdm transmission link,” Optics Communications, vol. 209, no. 1-3, pp. 137-147, 2002. [20] W. Vanderbauwhede and H. Novella, “A multiexit recirculating optical packet buffer,” IEEE Photonics Technology Letters, vol. 17, no. 8, pp. 1749-1751, 2005. [21] L. Xu, H. G. Perros, and G. Rouskas, “Techniques for optical packet switching and optical burst switching,” IEEE Communications Magazine, vol. 39, pp. 136-142, Jan. 2001. [22] W. A. Vanderbauwhede and D. A. Harle, “Architecture, design, and modeling of the opsnet asynchronous optical packet switching node,” Journal of Lightwave Technology, vol. 23, p. 2215, Jul 2005. [23] D. K. Hunter, W. D. Cornwell, T. H. Gilfedder, A. Franzen, and I. Andonovic, “Slob: a switch with large optical buffers for packet switching,” IEEE/OSA Journal of Lightwave Technology, vol. 16, pp. 1725-1736, Oct. 1998. Communications, vol. 48, pp. 2089-2098, Dec. 2000. [25] T. Zhang, K. Lu, and J. R. Jue, “Shared fiber delay line buffers in asynchronous optical packet switches,” IEEE Journal on Selected Areas in Communications, vol. 24, pp. 118-127, Part Supplement,&pr 2006. [26] H. Harai and M. Murata, “Optical fiber-delay-line buffer management in outputbuffered photonic packet switch to support service differentiation,” IEEE Journal on Selected Areas in Communications, vol. 24, pp. 108-116, Part Supplement,&ug 2006. [27] A. Lazzez, Y. Khlifi, S. Guemara El Fatmi, N. Boudriga, and M. Obaidat, “A novel node architecture for optical networks: Modeling, analysis and performance evaluation,” Computer Communications, vol. 30, no. 5, pp. 999-1014, 2007. [28] Y. Li, G. Xiao, and H. Ghafouri-Shiraz, “On the performance of different node configurations in multi-fiber optical packet-switched networks,” Photonic Network Communications, vol. 14, no. 1, pp. 11-22, 2007. [29] J. Mack, E. Burmeister, H. Poulsen, J. Bowers, and D. Blumenthal, “Synchronously loaded optical packet buffer,” IEEE Photonics Technology Letters, vol. 20, no. 21, pp. 1757-1759, 2008. [30] E. Burmeister, J. Mack, H. Poulsen, J. Klamkin, L. Coldren, D. Blumenthal, and J. Bowers, “Soa gate array recirculating buffer for optical packet switching,” in 2008 Optical Fiber communication/National Fiber Optic Engineers Conference, pp. 1-3, IEEE, 2008. [31] J.Mack, K. Nguyen, J. Garcia, E. Burmeister,M. Dummer, H. Poulsen, B. Stamenic, G. Kurczveil, K. Hollar, L. Coldren, et al., “Asynchronous 2 x 2 optical packet synchronization, buffering, and forwarding,” in 2010 Conference on (OFC/NFOEC) Optical Fiber Communication (OFC), collocated National Fiber Optic Engineers Conference, pp. 1-3, IEEE, 2010. [32] R. L. Cruz and J.-T. Tsai, “Cod: alternative architectures for high speed packet switching,” IEEE/ACM Transactions on Networking, vol. 4, pp. 11-21, Feb. 1996. [33] H. Harai and M. Murata, “High-speed buffer management for 40 gb/s-based photonic packet switches,” IEEE/ACM Transactions on Networking, vol. 14, pp. 191- 204, Feb. 2006. [34] J. Diao and P. L. Chu, “Analysis of partially shared buffering for wdm optical packet switching,” IEEE/OSA Journal of Lightwave Technology, vol. 17, pp. 2461-2469, Dec. 1999. [35] S. Debnath, S. Mahapatra, and R. Gangopadhyay, “Analysis of an optical packet switch with partially shared buffer and wavelength conversion,” IET Communications, vol. 1, pp. 810-818, August 2007. [36] C. Larsen and M. Gustavsson, “Linear crosstalk in 44 semiconductor optical amplifier gate switch matrix,” Journal of Lightwave Technology, vol. 15, pp. 1865-1870, Oct 1997. [37] R. Geldenhuys, N. Chi, I. T. Monroy, A. M. J. Koonen, H. J. S. Dorren, F. W. Leuschner, G. D. Khoe, S. Yu, and Z.Wang, “Multiple recirculations through crosspoint switch fabric for recirculating optical buffering,” Electronics Letters, vol. 41, pp. 1136-1138, Sept. 29, 2005. [38] E. F. Burmeister and J. E. Bowers, “Integrated gate matrix switch for optical packet buffering,” IEEE Photonics Technology Letters, vol. 18, pp. 103-105, Jan. 2006. [39] A. Uskov, F. Sedgwick, and C. Chang-Hasnain, “Delay limit of slow light in semiconductor optical amplifiers,” Photonics Technology Letters, IEEE, vol. 18, pp. 731- 733, 15, 2006. [40] E. Yamazaki, F. Inuzuka, K. Yonenaga, A. Takada, and M. Koga, “Compensation of interchannel crosstalk induced by optical fiber nonlinearity in carrier phase-locked wdm system,” IEEE Photonics Technology Letters, vol. 19, pp. 9-11, Jan.1, 2007. [41] K. Chou and W. Lin, “Performance analysis of a prioritization scheduling scheme for asynchronous optical packet switching networks,” in 2010 Second International Conference on Ubiquitous and Future Networks (ICUFN), pp. 187-192, IEEE, 2010. [42] J. Cheng, C.-S. Chang, T.-H. Chao, D.-S. Lee, and C.-M. Lien, “On constructions of optical queues with a limited number of recirculations,” in IEEE INFOCOM 2008, pp. 664-672, Apr. 13-18, 2008. [43] J. Cheng, “Constructions of optical 2-to-1 fifo multiplexers with a limited number of recirculations,” IEEE Transactions on Information Theory, vol. 54, pp. 4040-4052, Sept. 2008. [44] C. Chang, J. Cheng, T. Chao, and D. Lee, “Optimal constructions of fault tolerant optical linear compressors and linear decompressors,” IEEE Transactions on Communications, vol. 57, no. 4, pp. 1140-1150, 2009. [45] K. Leung and M. Eisenberg, “A single-server queue with vacations and gated timelimited service,” in IEEE INFOCOM '89, pp. 897 -906 vol.3, 23-27 1989. [46] K. K. Leung andM. Eisenberg, “A single-server queue with vacations and non-gated time-limited service,” Performance Evaluation, vol. 12, no. 2, pp. 115 - 125, 1991. [47] H. Bruneel and B. G. Kim, Discrete-Time Models for Communication Systems Including ATM. Norwell, MA, USA: Kluwer Academic Publishers, 1992. [48] H. Takagi, Queuing analysis: A foundation of performance evaluation. North- Holland, 1993. [49] V. Alaria, A. Bianco, P. Giaccone, E. Leonardi, F. Neri, and C. Syst, “Multi-hop scheduling algorithms in switches with reconfiguration latency,” in 2006 Workshop on High Performance Switching and Routing, p. 6, 2006. [50] B. Liang and M. Dong, “Packet prioritization in multihop latency aware scheduling for delay constrained communication,” IEEE Journal on Selected Areas in Communications, vol. 25, pp. 819-830, May 2007. [51] H. Ho and J. Liu, “Improvement of multi-hop packet transmission scheduling in wdm optical star networks,” Computer Communications, vol. 33, no. 6, pp. 706- 713, 2010. [52] K. Trivedi and R. Geist, “Decomposition in reliability analysis of fault-tolerant systems,” IEEE Transactions on Reliability, vol. 32, no. 5, pp. 463-468, 2009. [53] L. Garg, S.McClean, B.Meenan, and P.Millard, “A non-homogeneous discrete time markov model for admission scheduling and resource planning in a cost or capacity constrained healthcare system,” Health care management science, vol. 13, no. 2, pp. 155-169, 2010. [54] G. DAmico, J. Janssen, and R. Manca, “Initial and final backward and forward discrete time non-homogeneous semi-markov credit risk models,” Methodology and Computing in Applied Probability, vol. 12, no. 2, pp. 215-225, 2010. [55] I. Baldine, A. Bragg, G. Evans, M. Pratt, M. Singhai, D. Stevenson, and R. Uppalli, “Jumpstart deployments in ultra-high-performance optical networking testbeds,” IEEE Communications Magazine, vol. 43, pp. S18-S25, nov. 2005. [56] S. Yoo, H. J. Lee, Z. Pan, J. Cao, Z. Yanda, K. Okamoto, and S. Kamei, “Rapidly switching all-optical packet routing system with optical-label swapping incorporat- ing tunable wavelength conversion and a uniform-loss cyclic frequency awgr,” IEEE Photonics Technology Letters, vol. 14, pp. 1211-1213, aug 2002. [57] D. Klonidis, C. Politi, M. O'Mahony, and D. Simeonidou, “Fast and widely tunable optical packet switching scheme based on tunable laser and dual-pump four-wave mixing,” IEEE Photonics Technology Letters, vol. 16, pp. 1412-1414, may 2004. [58] D. Klonidis, C. Politi, R. Nejabati, M. O'Mahony, and D. Simeonidou, “Opsnet: design and demonstration of an asynchronous high-speed optical packet switch,” Journal of Lightwave Technology, vol. 23, pp. 2914-2925, oct. 2005. [59] D. W. Kim, A. Barkai, R. Jones, N. Elek, H. Nguyen, and A. Liu, “Silicon-oninsulator eight-channel optical multiplexer based on a cascade of asymmetric machzehnder interferometers,” Optics Letters, vol. 33, pp. 530-532, Mar 2008. [60] P. Louro, M. Vieira, M. Vieira, M. Fernandes, A. Fantoni, C. Francisco, and M. Barata, “Optical multiplexer for short range communications,” Physica E: Lowdimensional Systems and Nanostructures, vol. 41, no. 6, pp. 1082-1085, 2009. Proceedings of the E-MRS 2008 Symposium C: Frontiers in Silicon-Based Photonics. [61] Y.-D. Wu, T.-T. Shih, and M.-H. Chen, “New all-optical logic gates based on the local nonlinear mach-zehnder interferometer,” Optics Express, vol. 16, pp. 248-257, Jan 2008. [62] S. Danielsen, P. Hansen, and K. Stubkjaer, “Wavelength conversion in optical packet switching,” Journal of Lightwave Technology, vol. 16, pp. 2095-2108, dec 1998. [63] V. Eramo andM. Listanti, “Packet loss in a bufferless optical wdm switch employing shared tunable wavelength converters,” Journal of Lightwave Technology, vol. 18, pp. 1818-1833, dec 2000. [64] D. Hunter, M. Nizam, M. Chia, I. Andonovic, K. Guild, A. Tzanakaki, M. O'Mahony, L. Bainbridge, M. Stephens, R. Penty, and I. White, “Waspnet: a wavelength switched packet network,” IEEE Communications Magazine, vol. 37, pp. 120-129, mar 1999. [65] G. Castanon, L. Tancevski, S. Yegnanarayanan, and L. Tamil, “Asymmetric wdmalloptical packet switched routers,” in 2000 Optical Fiber Communication Conference, vol. 2, pp. 53 -55 vol.2, 2000. [66] F. Forghieri, A. Bononi, and P. Prucnal, “Analysis and comparison of hot-potato and single-buffer deflection routing in very high bit rate optical mesh networks,” IEEE Transactions on Communications, vol. 43, pp. 88 -98, jan 1995. [67] G. Castanon, L. Tancevski, and L. Tamil, “Routing in all-optical packet switched irregular mesh networks,” in IEEE GLOBECOM '99, vol. 1B, pp. 1017 -1022 vol. 1b, 1999. [68] F. Borgonovo, L. Fratta, and J. Bannister, “Unslotted deflection routing in all-optical networks,” in IEEE GLOBECOM '93, pp. 119 -125 vol.1, nov-2 dec 1993. [69] A. Acampora and S. Shah, “Multihop lightwave networks: a comparison of store-and-forward and hot-potato routing,” IEEE Transactions on Communications, vol. 40, pp. 1082-1090, jun 1992. [70] J. Feehrer, J. Sauer, and L. Ramfelt, “Design and implementation of a prototype optical deflection network,” in Proceedings of the conference on Communications architectures, protocols and applications, SIGCOMM '94, (New York, NY, USA), pp. 191-200, ACM, 1994. [71] S. Yao, B.Mukherjee, S. Yoo, and S. Dixit, “A unified study of contention-resolution schemes in optical packet-switched networks,” Journal of Lightwave Technology, vol. 21, no. 3, p. 672, 2003. [72] N. Beheshti, E. Burmeister, Y. Ganjali, J. E. Bowers, D. J. Blumenthal, and N.McKeown, “Optical packet buffers for backbone internet routers,” IEEE/ACM Transactions on Networking, vol. 18, pp. 1599-1609, October 2010. [73] S. Fuhrmann and R. Cooper, “Stochastic decompositions in the m/g/1 queue with generalized vacations,” Operations Research, vol. 33, no. 5, pp. 1117-1129, 1985. [74] Y. Tamir and G. Frazier, “High-performance multiqueue buffers for vlsi communication switches,” in 15th Annual International Symposium on Computer Architecture, pp. 343 -354, 30 1988. [75] D. Banovic and I. Radusinovic, “Scheduling algorithm for voq switches,” AEU - International Journal of Electronics and Communications, vol. 62, no. 6, pp. 455- 458, 2008. [76] L. Kleinrock and H. Levy, “The analysis of random polling systems,” OPERATIONS RESEARCH, vol. 36, no. 5, pp. 716-732, 1988. [77] O. Boxma and W. Groenendijk, “Waiting times in discrete-time cyclic-service systems,” IEEE Transactions on Communications, vol. 36, no. 2, pp. 164-170, 1988. [78] M. G. Hluchyj and M. J. Karol, “Queueing in high-performance packet switching,” IEEE Journal on Selected Areas in Communications, vol. 6, pp. 1587-1597, Dec. 1988. [79] N. McKeown, “The islip scheduling algorithm for input-queued switches,” IEEE/ACM Transactions on Networking, vol. 7, no. 2, pp. 188-201, 1999. [80] K. I. Kitayama and N. Wada, “Photonic ip routing,” IEEE Photonics Technology Letters, vol. 11, pp. 1689-1691, Dec. 1999. [81] M. Karol, M. Hluchyj, and S. Morgan, “Input versus output queueing on a spacedivision packet switch,” IEEE Transactions on Communications, vol. 35, pp. 1347- 1356, Dec 1987. [82] A. Papoulis and S. Pillai, Probability, random variables, and stochastic processes. McGraw-Hill, 2002.
摘要: 在本論文中我們專注與展示兩個重要的效能議題。第一個議題是關於在單一光封包交換器上,由於光學交換元件技術上的限制,週期更動內部交換線路設定所產生的時間耗費是不可忽略且對交換器效能具有嚴重影響性。更動線路的時間耗費增加了封包的平均等待時間且劣化了網路的輸出量。因此排程封包需要有額外的考量在更動內部交換線路設定的頻率上。第二個議題是在整體光封包交換網路上封包路由通過數個使用使用光延遲線(Fiber Delay Lines)緩衝器的光交換器產生的效能議題,由於光延遲線緩衝器是採用不斷繞行的方式來延遲與暫存封包,所以光延遲線緩衝器具有揮發性且會導致訊號遺失與雜訊累積。在路由路徑上,封包在光延遲線中過度繞行可能會因而被丟棄。所以封包的排程演算法變的比傳統電子式記憶體上的排程演算法更為複雜,更為需要額外考量來減少封包遺失。 在本論文中,我們希望找以數學分析的方式找出在單一光封包交換器上最佳的更動內部交換線路設定頻率,以達到最小化封包平均等待時間的目的。我們提出一個數學分析方法來實現更動內部交換線路設定頻率的分析與計算封包平均延遲時間,其適用於輸入端緩衝光交換器(Input-Buffer Optical Packet Switches)。此數學分析具有閉合型方程式可用來驗證更動線路設定頻率對於封包的平均等待時間之影響性。量化的實驗顯示,正確的調整更動設定頻率可顯著的降低封包的平均等待時間。在沉重負載流量下,使用基本的輪詢式(Round-Robin)排程法配合最佳的更動設定頻率可降低30\%的封包平均等待時間,相較於輪詢式排程法配合固定的更動設定頻率。 最後,在整體光封包交換網路上,我們提出一個延遲感知排程演算法與數學分析方法適用於整體光封包交換網路。此延遲感知排程演算法藉由調整封包延遲與剩餘距離間的權重來達到最小化封包遺失率的目的。而其數學分析方法則是基於非同構馬可夫分析(Non-Homogeneous Markovian Analysis)可用於研究各種排程演算法對於封包遺失與平均延遲的影響。數值結果顯示了各種網路參數如何影響最佳權重。我們量化的驗證了如何使用最佳的權重而可達到網路整體效能的顯著提升。例如在一給定的延遲限制與輕量網路流量下,我們排程法的封包遺失率較純粹使用延遲做為優先權的排程演算法低了71%。
In this dissertation, we address and explore two important performance issues of optical packet switching networks. The first issue we address is that an optical packet switch need to periodically reconfigure its switching fabric for moving packets through the switch. The reconfiguration overhead is not negligible with respect to the packet transmission time. And this has a significant impact on the switch performance. The overhead increases the average waiting time of packets and worsens throughput performance, so scheduling packets requires additional considerations on the reconfiguration frequency. The second issue is on the performance of routing packets through optical switches with Fiber Delay Lines (FDLs). Switch buffers that use FDLs have a volatile nature due to signal loss and noise accumulation, because the packets are recirculated in FDLs for storage. Packets suffer from excessive recirculation through FDLs, and they may be dropped eventually in their routing paths. Because of this, packet scheduling becomes more difficult in FDL buffers than in RAM buffers, and requires additional design considerations for reducing packet loss. In this dissertation, we firstly intend to find analytically the optimal reconfiguration frequency that minimizes the average waiting time of packets. We proposes an analytical model to facilitate our analysis on reconfiguration optimization for input-buffered optical packet switches with the reconfiguration overhead. The analytical model is based on a Markovian analysis and used to study the effects of various network parameters on the average waiting time of packets. Of particular interest is the derivation of closed-form equations that quantify the effects of the reconfiguration frequency on the average waiting time of packets. Quantitative examples are given to show that properly balancing the reconfiguration frequency can significantly reduce the average waiting time of packets. In the case of heavy traffic, the basic round-robin scheduling scheme with the optimal reconfiguration frequency can achieve as much as 30\% reduction in the average waiting time of packets, when compared with the basic round-robin scheduling scheme with a fixed reconfiguration frequency. Secondly, we propose a latency-aware scheduling scheme and an analytical model for all-optical packet switching networks with FDL buffers. The latency-aware scheduling scheme is intended to minimize the packet loss rate of the networks by ranking packets in the optimal balance between latency and residual distance. The analytical model is based on non-homogeneous Markovian analysis to study the effect of the proposed scheduling scheme on packet loss rate and average delay. Furthermore, our numerical results show how various network parameters affect the optimal balance. We demonstrate quantitatively how to achieve the proper balance between latency and residual distance so that the network performance can be improved significantly. For instance, we find that under a given latency limit and light traffic load our scheduling scheme achieves a packet loss rate 71% lower than a scheduling scheme that ranks packets simply based on latency.
URI: http://hdl.handle.net/11455/19892
Appears in Collections:資訊科學與工程學系所

文件中的檔案:

取得全文請前往華藝線上圖書館



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.