以可變動Delay Line建構之光緩衝器上的最佳管理及指定策略

Optimal Admission and Assignment Policies for Optical Buffers Constructed with Variable Delay Lines

楊淑惠(Shu-Huei Yang)

指導教授 ： 李端興

國立清華大學/電機資訊學院/資訊工程學系/碩士(2006年)

摘要

近年來，網際網路服務的多樣化刺激了使用者對於高頻寬網路的需求。由於光纖相較於其他傳輸媒介具有更高傳輸速率及可靠性，連帶使得光纖網路備受矚目。為了讓緩衝儲存裝置能負荷不斷提昇的傳輸速度，因此有人提出了光緩衝裝置的構想。傳統上，光纖上的光訊號必須在電子式的緩衝裝置做光電訊號轉換，而使用光緩衝器則可省去不必要的轉換時間。光緩衝裝置是由Optical Delay Line所構成，而Optical Delay Line依照其特性又可區分為固定延遲時間、可變動延遲時間〈Variable Optical Delay Line〉兩種類型。
在這篇論文中，我們試著找出以VODL所建構之光緩衝器上的最佳封包管理策略。我們考慮兩種型態的的VODL。這兩種VODL的共通點是它的延遲時間皆可調整，且每一個時槽都只能接受一個封包。不同點在於第一種VODL在舊的封包尚未離開前無法接收新的封包。而第二種VODL則沒有這項限制，但條件是新的封包必須和既有的封包有相同的延遲需求。對於第一種VODL，如果系統採用的是單純以封包類別作為判斷依據的管理策略，我們証明最佳的管控策略會符合一個Threshold Type。對於第二種VODL，我們提出兩種分析方式以簡化光緩衝器對應的 Markov chain。模擬結果說明我們的分析有相當的準確度。我們研究如何指定VODL以最小化封包的流失，並且提出一個簡單的貪婪演算法來找出最佳的設定方式。

關鍵字

光緩衝器 ； 可變動延遲元件 ； 流量管理 ； 最佳控制策略

並列摘要

In this paper we study optimal policies to maximize the throughput of optical buffers constructed with Variable Optical Delay Lines (VODLs). We consider two types of VODLs. Both VODLs can be tuned to provide delay of integral number of time slots to packets. The first type of VODLs can accept only one packet before the packet departs. However, the second type of VODLs can allow multiple packets
traversing in the delay lines. However, all packets in a type II VODLs are subject to the same delay. For the first type of VODLs, we show that the optimal state independent admission policy for the optical buffer to maximize throughput is a threshold type. For the second type of VODLs, we approximate the optical buffer by a Markov chain and derive an expression for the packet loss probability. We then propose a greedy algorithm to find the optimal number of dedicated VODLs in order to minimize the packet loss probability.

並列關鍵字

optical buffers ； variable optical delay lines ； admission control ； optimal policy

參考文獻

[1] C.-S. Chang, D.-S. Lee and C.-K. Tu, "Recursive construction of FIFO optical multiplexers with switched delay lines," IEEE Trans. on Information Theory, Vol. 50, No. 12, pp. 3221-3233, December 2004.

[2] Cheng-Shang Chang, Duan-Shin Lee, and Chao-Kei Tu, "Using Switched Delay Lines for Exact Emulation of FIFO Multiplexers with Variable Length Bursts," IEEE JSAC, April, 2006.

[3] Cheng-Shang Chang, Yi-Ting Chen, Duan-Shin Lee, "Construction of Optical FIFO Queues," IEEE Trans. on Info. Theory Vol. 52, No. 6, p. 2838-2843, June 2006.

[4] C.-S. Chang, Y.-T. Chen, Jay Cheng and Duan-Shin Lee, "Constructions of linear compressors, non-overtaking delay lines, and flexible delay lines for optical packet switching," accepted by IEEE Trans. on Networking.

[5] C.-C. Chou, C.-S. Chang, Duan-Shin Lee, J. Cheng, "A necessary and sufficient condition for the construction of 2-to-1 optical FIFO multiplexers by a single crossbar switch and fiber delay lines," accepted by IEEE Trans. on Info. Theory.