使用光交換機和光纖延遲線遞迴建構平行先進先出光佇列和後進先出光佇列

使用光交換機和光纖延遲線建構光封包交換機的緩衝儲存器是一種非常普遍的方法。最近的研究顯示這種方法存在系統化的理論來建構多種不同的光緩衝儲存器，包括先進先出多工器，先進先出光佇列，優先權光佇列，線性壓縮器，非超前延遲線和彈性延遲線。由於平行的先進先出光佇列使用共同的緩衝儲存器被廣泛的用在很多交換機的架構上，如輸入緩衝儲存交換機和負載均衡伯克霍夫-馮紐曼交換機，在這篇論文我們對這種佇列提出了一個新的建造方式。而它的中心概念是兩層的快取。第一層是一個兩埠的隨機要求光佇列(當作一個快速的儲存元件)而第二層是一個比率放大平行先進先出光佇列(當作一個慢速的儲存元件)。靠著決定適當的轉儲門檻值跟取回門檻值，我們證明這個兩層的快取架構可以作為一個平行的先進先出光佇列且使用共同的緩衝儲存器。此外這個兩層的架構可以被遞迴的延展成n層的架構，而當緩衝儲存器大小是B，佇列的數目N>>1，總共所需的2x2光交換機數目是O(N log N log(B/N log N))。當佇列的數目為1，即一個單一的光佇列且緩衝儲存器大小是B，總共所需的2x2光交換機數目是O(log(B))。這個複雜度是跟張正尚教授等研究人員所提出的架構相同。我們也指出這個兩層的遞迴架構可以被推廣來建造平行後進先出光佇列且使用共同的緩衝儲存器，同時使用的2x2光交換機數目和平行先進先出光佇列相同。最後這個架構一個重要的優點是它容錯的能力。我們可以在每一層增加額外的光學記憶體單元(在我們架構下一個基本的元件)來提昇它的可靠度，即確保當某些光學記憶體單元不能正常運作時我們的架構還能正常的運作。

關鍵字

快取；先進先出光佇列；後進先出光佇列；光緩衝儲存器；光交換機和光纖延遲線

並列摘要

One of the most popular approaches for the constructions of optical buffers needed for optical packet switching is to use Switched Delay Lines (SDL). Recent advances in the literature have shown that there exist systematic SDL construction theories for various types of optical buffers, including First In First Out (FIFO) multiplexers, FIFO queues, priority queues, linear compressors, non-overtaking delay lines, and flexible delay lines. As parallel FIFO queues with a shared buffer are widely used in many switch architectures, e.g., input-buffered switches and load-balanced Birkhoff-von Neumann switches, in this paper we propose a new SDL construction for such queues. The key idea of our construction for parallel FIFO queues with a shared buffer is {em two-level caching}, where we construct a dual-port random request queue in the upper level (as a high speed storage device) and a system of scaled parallel FIFO queues in the lower level (as a low speed storage device). By determining appropriate dumping thresholds and retrieving thresholds, we prove that the two-level cache can be operated as a system of parallel FIFO queues with a shared buffer. Moreover, such a two-level construction can be recursively expanded to an $n$-level construction, where we show that the number of $2 imes 2$ switches needed to construct a system of $N$ parallel FIFO queues with a shared buffer $B$ is $O(N log N log (B/Nlog N))$ for $N >>1$. For the case with $N=1$, i.e., a single FIFO queue with buffer $B$, the number of $2 imes 2$ switches needed is $O(log B)$. This is of the same order as that previously obtained by Chang emph{et al}. We also show that our two-level recursive construction can be extended to construct a system of $N$ parallel Last In First Out (LIFO) queues with a shared buffer by using the same number of $2 imes 2$ switches, i.e., $O(N log N log (B/Nlog N))$ for $N>>1$ and $O(log B)$ for $N=1$. Finally, we show that a great advantage of our construction is its fault tolerant capability. The reliability of our construction can be increased by simply adding extra optical memory cells (the basic elements in our construction) in each level so that our construction still works even when some of the optical memory cells do not function properly.

並列關鍵字

Caches ； FIFO queues ； LIFO queues ； optical buffers ； switched delay lines

參考文獻

[1] M. J. Karol, "Shared-memory optical packet (ATM) switch," in Proceedings SPIE vol. 2024: Multigigabit Fiber Communication Systems (1993), October 1993, pp. 212-222.

[2] 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.

[3] I. Chlamtac, A. Fumagalli, and C.-J. Suh, "Multibu®er delay line architectures for efficient contention resolution in optical switching nodes," IEEE Transactions on Communications, vol. 48, pp. 2089-2098, December 2000.

[5] 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.

[6] D. K. Hunter, D. Cotter, R. B. Ahmad, D. Cornwell, T. H. Gilfedder, P. J. Legg, and

國際替代計量

使用光交換機和光纖延遲線遞迴建構平行先進先出光佇列和後進先出光佇列

主題瀏覽