臺灣博碩士論文加值系統

在高密度波長多工技術蓬勃發展之下，Terabit/sec (Tbs)已逐漸形成，傳統電子式交換機交換速度將跟不上光纖的傳輸速度，全光學元件的交換機是解決的辦法之一，然而目前並無光的隨機存取記憶體，在解決資源競爭變得較為複雜，最常用的就是光纖延遲線，我們利用光學交換器與光纖延遲線結合起來以多階層方式來建構具有B個暫存器的光學時域多工器，每個暫存器可儲存一個固定長度的封包，暫存器的個數和交換器的個數成對數關係，使得具有多個暫存器的光學時域多工器較為可行，更重要的是我們整個多階層的交換器是採自我找路徑的方式，大大減低了控制交換器的複雜度，使得必須經由光轉電的控制模式能以很快的速度控制整個交換器交換的速度，在此篇論文裡，我們更進一步設計一個長度可變爆發性封包的全光學多工器。我們的架構包含了兩個區塊:一個是封包時序排程區塊，一個是固定長度封包的光學多工器，兩個區塊都是由交換機和延遲線構成。封包時序排程區塊目的是要將一個長度可變爆發性封包切成一個個固定長度的小封包，並在正確的時間傳送這些小封包到第二個區塊的正確的輸入埠，使在第二個區塊的輸出埠依據FIFO(先進入先出來)重新組合回原來相同的爆發性封包，經由此封包時序排程的最大延遲為一個常數，此常數只與輸入埠的個數和爆發性封胞裡最多的封包個數有關係，因此，封包時序排程區塊只需固定個數的交換機和光纖延遲線即可完成。
第一章 簡 介
製作高速網路交換機達到光纖傳輸速度的其中一個主要挑戰，即是解決要求相同資源的封包間競爭，有兩個常用的方法，一個是利用大量平行的電子式暫存器來加速交換的速度，另一個方法為光學交換器和光纖延遲線來模擬電子式暫存器，由於光纖延遲線不提供隨機存取功能，只提供預先決定的時序延遲，大大加深了解決封包間競爭的困難。在本篇論文我們提出了一個針對長度可變封包的光學多工器架構，由時序排程區塊和固定長度封包的光學多工器所構成，時序排程區塊只需要有限個光纖延遲線和光學交換器即可達成。
這篇論文的組織如下：第二章我們簡短介紹論文裡所用到的網路元件和先前我們所提出的固定長度封包的光學多工器。第三章提出了將長度可變封包灌到固定長度封包的光學多工器所產生的封包串列問題。第四章提出在固定長度封包的光學多工器前加一個封包時順排程區塊，並提出時序排程區塊的運作演算法，第五章為所提出來的架構作數學上的証明，最後為此架構作簡單的總結並且提出討論。
詳細的簡介請參閱附錄英文稿。
第二章 基本的網路元素與光學時域多工器
複習論文裡所用到的基本網路元件和先前我們所提出的固定長度封包的光學多工器。
詳細內容請參閱附錄英文稿。
第三章 封包串列問題
本章我們提出了將長度可變封包灌到固定長度封包的光學多工器所產生的封包串列問題，並提出簡單的想法來解決這個問題。
詳細的內容請參閱附錄英文稿。
第四章 所提出的多工器架構
本章我們延伸上章的想法建構一個完全可以解決封包串列問題的架構，並提出一個演算法來控製封包時序排程區塊。
詳細的結論請參閱附錄英文稿。
第五章 延遲邊界
本章証明封包時序排程真的可以用有限個光交換機和光纖延遲線組成，完全相同模擬了將長度可變封包灌入電子式多工器所產生的結果。
詳細的結論請參閱附錄英文稿。
第六章 結論
本章總結了具有處理長度可變爆發型封包的光學時域多工器的整體架構，並提出此多工器可用在建立一個全光學的Knockout Switch。
詳細的結論請參閱附錄英文稿。

It has been studied extensively in the literature how one achieves exact emulation of First In
First Out (FIFO) multiplexers for xed size cells (or packets) using optical crossbar Switches
and ber Delay Lines (SDL). In this thesis, we take a step further and propose a new
architecture that achieves exact emulation of FIFO multiplexers for variable length bursts.
Our architecture consists of two blocks: a cell scheduling block and an FIFO multiplexer
for xed size cells. Both blocks are made of SDL units. The objective of the cell scheduling
block is to schedule cells in a burst to the right input at the right time so that cells in the
same burst depart contiguously from the multiplexer for xed size cells. We show that cell
scheduling can be done eÆciently by keeping track of a single state variable, called the total
virtual waiting time in this thesis. Moreover, the delay through the cell scheduling block is
bounded above by a constant that only depends on the number of inputs and the maximum
number of cells in a burst. Such a delay bound provides a limit on the number of ber delay
lines needed in the cell scheduling block.

摘 要 …………………………………………………….. i
致 謝 ……………………………………………………... ii
目 錄 ………………………………………………………. iii
第一章 簡 介 ………………………………………. 1
第二章 基本的網路元件與光學時域多工器 ………. 2
第三章 封包串列問題 ……………….……………… 3
第四章 提出的多工器架構 …………………………. 4
第五章 延遲的邊界 …………………………………. 5
第六章 結論 ………………………………………. 6
附 錄 英文稿 ……………………………………… 7

[1] F. Callegati, “Approximate modeling of optical buers for variable length packets,” Photonic Network Communications,
Vol. 3, pp. 383-390, 2001.
[2] C.S. Chang, D.S. Lee and C.M. Lien, “Load Balanced Birkho-von Neumann Switches, Part II: Multi-stage
Buering,” to appear in the special issue of Computer Communications on “Current Issues in Terabit Switching,”
2002.
[3] C.S. Chang, D.S. Lee and C.K. Tu, “Recursive construction of FIFO optical multiplexers with switched delay
lines,” preprint 2002.
[4] I. Chlamtac and A. Fumagalli, “QUADRO-star: High performane optical WDM star networks,” Proceedings of
IEEE GLOBAECOM’91, Phoenix, AZ, Dec. 1991.
[5] I. Chlamtac, A. Fumagalli, L.G. Kazovsky, P. Melman, W.H. Nelson, P. Poggiolini, M. Cerisola, A.N.M.M.
Choudhury, T.K. Fong, R.T. Hofmeister, C.L. Lu, A. Mekkittikul, D.J.M. Sabido IX, C.J. Suh and E.W.M.
Wong, “Cord: contention resolution by delay lines,” IEEE Journal on Selected Areas in Communications, Vol.
14, pp. 1014-1029, 1996.
[6] I. Chlamtac and A. Fumagalli, and C.-J. Suh, “Multibuer delay line architectures for ecient contention
resolution in optical switching nodes,” IEEE Transactions on Communications, Vol. 48, pp. 2089-2098, 2000.
[7] S.-T. Chuang, A. Goel, N. McKeown and B. Prabhkar, “Matching output queueing with a combined input
output queued switch,” IEEE INFOCOM’99, pp. 1169-1178, New York, 1999.
[8] R. L. Cruz and J. T. Tsai, “COD: alternative architectures for high speed packet switching,” IEEE/ACM
Transactions on Networking, Vol. 4, pp. 11-20, February 1996.
[9] D.K. Hunter and I. Andonovic, “Approaches to optical Internet packet switching,” IEEE Communication Magazine,
Vol. 38, pp. 116-122, 2000.
[10] D.K. Hunter, D. Cotter, R.B. Ahmad, D. Cornwell, T.H. Gilfedder, P.J. Legg and I. Andonovic, “2 ×2 buered
switch fabrics for trac routing, merging and shaping in photonic cell networks,” IEEE Journal of Lightwave
Technology, Vol. 15, pp. 86-101, 1997.
[11] D.K. Hunter, M.C. Chia and I. Andonovic, “Buering in optical packet switches,” IEEE Journal of Lightwave
Technology, Vol. 16, pp. 2081-2094, 1998.
[12] D.K. Hunter, W.D. Cornwell, T.H. Gilfedder, A. Franzen and I. Andonovic, “SLOB: a switch with large optical
buers for packet switching,” IEEE Journal of Lightwave Technology, Vol. 16, pp. 1725-1736, 1998.
[13] J. Hui, Switching and Trac Theory for Integrated Broadband Networks. Boston: Kluwer Academic Publishers,
1990.
[14] S. Iyer and N. McKeown, “Making parallel packet switches practical.” IEEE INFOCOM 2001.
[15] M. Karol, “Shared-memory optical packet (ATM) switch,” SPIE Vol. 2024 Multigigabit Fiber Communications
Systems, pp. 212-222, 1993.
[16] I. Keslassy and N. McKeown, “Maintaining packet order in two-stage switches,” preprint, 2001.
[17] M.R.N. Ribeiro and M.J. O’Mahony “Trac management in photonic packet switching nodes by priority assignment
and selective discarding,” Computer Communications, Vol 24, pp. 1689-1701, 2001.
[18] M. Schwartz, Broadband Integrated Networks. New Jersey: Prentice Hall, 1996.
[19] L. Tancevski, S. Yegnanarayanan, G. Castanon, et al. “Optical routing of asynchronous, variable length packets”
Journal on Selected Areas in Communications, Vol. 18, pp. 2084-2093, 2000.
[20] J.T. Tsai, “COD: architectures for high speed time-based multiplexers and buered packet switches,” Ph.D.
Dissertation, University of California, San Diego, 1995.
[21] Y.S. Yeh, M.G. Hluchyj, and A.S. Acampora, “The Knockout switch: a simple, modular architecture for highperformance
packet switching,” IEEE Journal of Selected Areas in Communications, Vol. SAC-5, pp. 1274-1283,
1987.
[22] S. Yao S, B. Mukherjee, and S. Dixit, “Advances in photonic packet switching: An overview,” IEEE Communication
Magazine, Vol. 38, pp. 84-94, 2000.
[23] M. Yoo, C. Qiao and S. Dixit, “QoS performance of optical burst switching in IP-over-ATM networks,” IEEE
Journal on Selected Areas in Communications, Vol. 18, pp. 2062-2071, 2000.
[24] K.Y. Yun, K.W. James, R.H. Fairlie-Cuninghame, S. Chakraborty, and R.L. Cruz, “A self-timed real-time sorting
network,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 8, pp. 356-363, 2000.