以輸入輸出佇列交換系統來仿效輸出佇列交換系統

Abstract

輸入輸出佇列交換系統，例如內部加速的縱橫式交換系統，被認為是提供大型交換系統於寬頻整合服務網路的解決方案。內部加速兩倍的輸入輸出佇列交換系統搭配maximal配對演算法已被證明傳輸率可達到百分之一百，然而百分之一百的傳輸率並不能保證每條連線的服務品質。另一方面，內部加速兩倍的輸入輸出佇列交換系統搭配stable配對演算法被證明可正確地仿效輸出佇列交換系統；不幸地，已知的stable配對演算法的複雜度太高，而對高速交換系統不可行。在此論文中我們提出一個新的配對演算法叫做the least cushion first/most urgent first (LCF/MUF)，並且證明內部加速兩倍的輸入輸出佇列交換系統搭配此演算法可仿效一個採用任意排程演算法的輸出佇列交換系統。最後我們還提出一個交換系統的架構，利用我們提出的演算法來實現嚴格排程的服務機制。

Combined input output queued (CIOQ) architecture such as crossbar with speedup has recently been proposed to build a large capacity switch for broadband integrated services networks. It was shown that, for a speedup factor of 2, a CIOQ switch can achieve 100% throughput with a simple maximal matching algorithm [1]. Achieving 100% throughput, however, is not sufficient for per-connection quality of service (QoS) guarantee. In [2],[3], it is proved that a CIOQ switch with a speedup factor of 2 can exactly emulate an output queued (OQ) switch if stable matching is adopted. Unfortunately, the complexity of currently known algorithms makes stable matching impractical for high-speed switches. In this thesis, we propose a new matching algorithm called the least cushion first/most urgent first (LCF/MUF) algorithm and formally prove that a CIOQ switch with a speedup factor of 2 can exactly emulate an OQ switch which adopts any service discipline for cell transmission. A potential implementation of our proposed matching algorithm for strict priority service discipline is also presented.