Quasi-output-buffered Switches

類輸出緩衝儲存交換機

吳其峰(Chi-Feng Wu)

指導教授 ： 張正尚

國立清華大學/電機資訊學院/通訊工程研究所/碩士(2008年)

https://doi.org/10.6843/NTHU.2008.00678

摘要

輸出緩衝儲存交換機(output-buffered switches)不但可以達到100%輸出率(throughput)，而且是目前所知在延遲效能表現上最好的交換機結構。然而，對於一個NxN的輸出緩衝儲存交換機，必須加速N倍才能達到如此好的效能。所以，在輸出與輸入的擴充方面，輸出緩衝儲存交換機具有惡名昭彰的問題：要直接建造一個大型的輸出緩衝儲存交換機是很困難的！在本論文中，我們探討如何去建造一個可擴充，且具有與輸出緩衝儲存交換機相當的延遲效能的交換機，並將這些觀念整合後提出一個新的概念：類輸出緩衝儲存交換機(quasi-output-buffered switches)。如同輸出緩衝儲存交換機一樣，類輸出緩衝儲存交換機是一種固定式(deterministic)交換機，所以只要對於一樣的輸入就一定會有一樣的輸出，且具有先進先出(first-in-first-out)的封包傳送能力和可以達到100%輸出率。此外，利用三級式克勞斯網路(Clos network)，我們可以用一組小型的類輸出緩衝儲存交換機遞迴建構(recursively construction)出大型的類輸出緩衝儲存交換機。甚至，如同班尼斯網路(Benes network)一樣，在N=2^n的情形下，我們可以僅利用2x2的門閂式交換機(crossbar switches)建構出NxN的類輸出緩衝儲存交換機；因為這樣建構出來的類輸出緩衝儲存交換機必須在封包成對後才能傳遞，所以我們特別稱之為封包配對交換機(packet-pair switch)。最後，藉由電腦模擬，我們發現相較於大多數的負載平衡交換機結構，在差不多的硬體複雜度下，封包配對交換機具有更好的延遲效能！

關鍵字

輸出緩衝儲存交換機 ； 負載平衡交換機 ； 封包配對交換機 ； 延遲效能

並列摘要

Output-buffered switches are known to have better performance than other switch architectures. However, output-buffered switches also suffer from the notorious scalability problem, and direct constructions of large output-buffered switches are difficult. In this thesis, we study the problem of constructing scalable switches that have comparable performance to output-buffered switches. For this, we propose a new concept, called quasi-output-buffered switch. Like an output-buffered switch, a quasi-output-buffered switch is a deterministic switch that delivers packets in the FIFO order and achieves 100% throughput.Using the three-stage Clos network, we show that one can recursively construct a larger quasi-output-buffered switch with a set of smaller quasi-output-buffered switches. By recursively expanding the three-stage Clos network, we obtain a quasi-output-buffered switch with only 2 × 2 switches. Such a switch is called a packet-pair switch as it always transmits packets in pairs. By computer simulations, we show that packet-pair switches have better delay performance than most load-balanced switches with comparable　construction complexity.

並列關鍵字

output-buffered switches ； load-balanced switches ； packet-pair switches ； delay performance

參考文獻

[1] H. Ahmadi and W. E. Denzel, “A survey of modern high-performance switching techniques,” IEEE Journal of Selected Areas in Communications, Vol 7. pp. 1091-1103, 1989.

[3] C.-S. Chang, “Stability, queue length and delay of deterministic and stochastic queueing networks,” IEEE Trans. on Automatic Control, Vol. 39, pp. 913-931, 1994.

[5] C.-S. Chang and D.-S. Lee, “Quasi-circuit switching and quasi-circuit Switches,” Proceedings of IEEE ITRE 2005.

[6] C.-S. Chang, D.-S. Lee and Y.-S. Jou, “Load balanced Birkhoff-von Neumann switches, part I: one-stage buffering,” Computer Communications, Vol. 25, pp. 611-622, 2002.40

[7] C.-S. Chang, D.-S. Lee, and Y.-J. Shih, “Mailbox switch: a scalable two-stage switch architecture for conflict resolution of ordered packets,” Proceedings of IEEE INFOCOM, Vol. 3, pp. 1995-2006, Hong Kong, 2004.