臺灣博碩士論文加值系統

近幾年來，光佇列的建造在學術界吸引了很多注意，這樣的研究課題主要是導因於在全光網路中我們並沒有光封包的暫存器，為了達到暫存封包的目的，除了將光封包轉換成其它形式以外，目前已知的唯一方法是利用光的交換機將光封包導進光纖延遲線中，等到適當的時機再將它釋放到適當的地點，以模擬暫存器的效果。關於如何利用光的交換機與光纖延遲線建造各種光佇列，目前已經有一些理論研究成果被發表，包括輸出緩衝儲存交換機、先進先出光學多工器、先進先出光佇列，後進先出光佇列、優先權光佇列、光學線性壓縮器、光學不超越延遲線、以及可調變光纖延遲線等等。
在這篇論文裡，我們專注於尋找有繞行次數限制之雙輸入埠與單輸出埠之先進先出光學多工器的最佳建造方式 (亦即使其緩衝區容量為最大)。這樣的一個繞行次數限制是來自實作上可行性的考量。雙輸入埠與單輸出埠之先進先出光學多工器可以由一個 的光交換機以及 條光纖延遲線建造出來，在此架構以及繞行次數限制的條件下，鄭傑教授等研究人員已證明了一個最佳的建造方式必定屬於貪婪建造方式所成的集合 (a class of greedy constructions)。我們在這篇論文裡的主要貢獻，是證明出在貪婪建造方式所成之集合裡，我們可以在一個更小的子集合去尋找最佳建造方式，這樣一來，搜尋最佳建造方式的複雜度可以由O(M^(k-1))(多項式時間)減少到O(1)(常數時間)

Recently, constructing queues for optical packet switching has received a lot of attention in
the literature. Such a research interest mainly originates from the lack of optical buffers in optical packet switching networks. The only known way to "store" optical packets without converting them into other media is to use switched delay lines (SDL). Theoretical SDL constructions have been reported for various types of optical queues, including output-buffered switches, First-in-first-out (FIFO) multiplexers, FIFO queues, last-in-first-out (LIFO) queues, priority queues, linear compressors, non-overtaking delay lines, and flexible delay lines.

In this thesis, we focus on finding optimal constructions (in the sense of maximizing the buffer size) of optical 2-to-1 FIFO multiplexers by using a feedback system consisting of an (M + 2)x(M + 2) optical crossbar switch and M fiber delay lines under a simple packet routing policy and under the limitation that each optical packet can be recirculated through the M fibers at most k times. Such a limitation on the number of recirculations comes from
practical feasibility considerations. Under such a setting, it has been shown by Cheng et al. that an optimal construction belongs to a class of greedy constructions. Our contribution in this thesis is to show that an optimal construction could be found in a much smaller subset of the original class of greedy constructions. As a result, the complexity of searching for an
optimal construction could be reduced from O(M^(k-1)) (which grows with the switch size), to O(1)(which does not grow with the switch size).

Abstract i
Contents ii
1 Introduction 1
2 A Reduced Class of Greedy Constructions 7
3 Conclusion 34
Bibliography 35

[1] D. K. Hunter, D. Cotter, R. B. Ahmad, D. Cornwell, T. H. Gilfedder, P. J. Legg, and I. Andonovic, "2X2 buffered switch fabrics for tra±c routing, merging and shaping in
photonic cell networks," IEEE Journal of Lightwave Technology, vol. 15, pp. 86-101, January 1997.
[2] 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 Journal of Lightwave Technology, vol. 16, pp. 1725-1736, October 1998.
[3] J. T. Tsai, "COD: architectures for high speed time-based multiplexers and buffered packet switches," Ph.D. Dissertation, University of California, San Diego, La Jolla, CA, USA, 1995.
[4] 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, February 1996.
[5] C.-S. Chang, D.-S. Lee, and C.-K. Tu, "Recursive construction of FIFO optical multiplexers with switched delay lines," IEEE Transactions on Information Theory, vol. 50, pp. 3221-3233, December 2004.
[6] C.-S. Chang, D.-S. Lee, and C.-K. Tu, "Using switched delay lines for exact emulation of FIFO multiplexers with variable length bursts," IEEE Journal on Selected Areas in
Communications, vol. 24, pp. 108-117, April 2006.

[7] C.-C. Chou, C.-S. Chang, D.-S. Lee and J. Cheng, "A necessary and su±cient condition for the construction of 2-to-1 optical FIFO multiplexers by a single crossbar switch and fiber delay lines," IEEE Transactions on Information Theory, vol. 52, pp. 4519-4531, October 2006.
[8] Y.-T. Chen, C.-S. Chang, J. Cheng, and D.-S. Lee, "Feedforward SDL constructions of output-buffered multiplexers and switches with variable length bursts," in Proceedings IEEE International Conference on Computer Communications (INFOCOM'07), Anchorage, AK, USA, May 6-12, 2007.
[9] J. Cheng, "Constructions of fault tolerant optical 2-to-1 FIFO multiplexers," IEEE Transactions on Information Theory, vol. 53, November 2007.
[10] J. Cheng, "Constructions of optical 2-to-1 FIFO multiplexers with a limited number of recirculations," submitted to IEEE Transactions on Information Theory, 2007.
[11] C.-S. Chang, Y.-T. Chen, and D.-S. Lee, "Constructions of optical FIFO queues," IEEE Transactions on Information Theory, vol. 52, pp. 2838-2843, June 2006.
[12] A. Bouillard and C.-S. Chang, "An explicit control algorithm for optical FIFO queues," submitted to IEEE Transactions on Information Theory, 2007.
[13] P.-K. Huang, C.-S. Chang, J. Cheng, and D.-S. Lee, "Recursive constructions of parallel FIFO and LIFO queues with switched delay lines," IEEE Transactions on Information Theory, vol. 53, pp. 1778-1798, May 2007.
[14] A. D. Sarwate and V. Anantharam, "Exact emulation of a priority queue with a switch and delay lines," Queueing Systems: Theory and Applications, vol. 53, pp. 115-125,
July 2006.
[15] H.-C. Chiu, C.-S. Chang, J. Cheng, and D.-S. Lee, "A simple proof for the constructions of optical priority queues," Queueing Systems: Theory and Applications, vol. 56,
June 2007

[16] H.-C. Chiu, C.-S. Chang, J. Cheng, and D.-S. Lee, "Using a single switch with O(M) inputs/outputs for the construction of an optical priority queue with O(M^3) buffer," in Proceedings IEEE International Conference on Computer Communications (INFOCOM'07 Minisymposium), Anchorage, AK, USA, May 6-12, 2007.
[17] Y.-T. Chen, J. Cheng, and D.-S. Lee, "Multistage constructions of linear compressors, non-overtaking delay lines, and °exible delay lines," submitted to IEEE/ACM Transactions on Networking 2007. Conference version in Proceedings IEEE International Conference on Computer Communications (INFOCOM'06), Barcelona, Spain, April 23-29,
2006.
[18] C.-S. Chang, T.-H. Chao, J. Cheng, and D.-S. Lee, "Constructions of fault tolerant linear compressors and linear decompressors," in Proceedings IEEE International Conference on Computer Communications (INFOCOM'07), Anchorage, AK, USA, May 6-12, 2007.
[19] E. F. Burmeister and J. E. Bowers, "Integrated gate matrix switch for optical packet buffering," IEEE Photonics Technology Letters, vol. 18, pp. 103-105, January 2006.
[20] C. P. Larsen and M. Gustavsson, \Linear crosstalk in 4 X 4 semiconductor optical amplifier gate switch matrix," IEEE Journal of Lightwave Technology, vol. 15, pp. 1865-
1870, October 1997.
[21] R. Geldenhuys, Z. Wang, N. Chi, I. Tafur Monroy, A. M. J. Koonen, H. J. S. Dorren, F. W. Leuschner, G. D. Khoe, and S. Yu, "Multiple recirculations through Crosspoint
switch fabric for recirculating optical buffering," Electronics Letters, vol. 41, pp. 1136-1137, September 2005.
[22] 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 Proceedings IEEE Interna-
tional Conference on Computer Communications (INFOCOM'08), Phoenix, AZ, USA, April 13-18, 2008.