大型進入排隊式交換機之次序保證與最大配對

Abstract

大型進入排隊式交換機的探討目前仍是一個重要的課題，在這篇 論文中，我們對於次序保證與最大配對提出了解決的辦法。 首先 ，對於以一些先進先出的排隊來模擬跳耀式排隊，我們提出了一個容易實 作和保證次序的架構。在進入排隊式交換機中，跳耀式排隊是一種有效降 低前頭阻礙的方式。但是，跳耀式排隊的實作一直是個困難的問題。早期 ，尚馬和皮努曾提出了一個類似的作法，但是他們的方法無法保證次序。 我們提出的新方法，非但可以保證次序，而且還有容易實作和硬體負荷少 的特性。 再者，我們也提出一個新的方法來處理大型進入排隊 式交換機的配對問題。從我們早先的觀察發現，進入排隊式交換機的效能 不單受限于前頭阻礙，配對方式的無效率同樣有著相當的影響。在新提出 的配對方法中，若是將中間溝通用的網路以四倍的速度運作，可以有效地 將配對的成功率從傳統的百分之六十三點二提升到百分之九十八點一。 How to build efficient large scale ATM switches is still a problem nowadays. Two methods are proposed in this thesis to address two problems, cell sequence integrity and maximum pairing, in input queues ATM switches. A simple and orderly implementation for the bypass queue, by FIFO queues, is presented first. Sharma and Pinnu suggested a smart implementation of the bypass queue, used to reduce the effect of head of line (HOL) blocking, by many FIFO queues; unfortunately, the detailed procedure was married by a mistake of losing cell sequence integrity which is an important feature in ATM network. In this thesis, we propose an improved architecture to correct the mistake and describe the related operating procedures. Second, we propose a novel maximum pairing method for input- queued switches, and the algorithm for this pairing. Motivated by the observation that throughput is mainly limited by the maximum matching or pairing, instead of the HOL effect, our method tries to maximize the number of pairing. The achieved maximum pairing throughput is proved to be 1 - e-k, where k is the number of FIFO queues in each input port.