Abstract
在非同步傳輸(ATM) 交換機系統中(Switching System), 已有許多多層廣 播(Multicast)方法被提出, 在這些方法中可以被分成兩大類的方法, 一 個是利用多階段內部連結網路(Multistage Interconnection Network)來 複製封包(Cell), 例如 Broadcast Banyan Network(BBN), 另一種則利用 共用緩衝區(Shared Buffer)來複製, 然而這兩種方法都有其缺點在, 前 者可接受的複製份數受限於交換機的大小,當複製的份數超過交換機大小 時, 即會發生溢載, 而使得封包遺失(Cell Loss)。 而後者則需要先進的 技術以滿足其快速之緩衝區存取需求, 受限於此因素, 這種設計的交換機 系統難以擴大。在本論文中,一個新而簡單的多層廣播交換機系統 (Multicast Switching System)被提出以達到高效能, 這個架構採用輸入 排隊(Input Queuing)方法, 立方編碼(Cube Addressing)關念被提出, 並 用來做為輸出位址(Out- put Address)編碼的方法。由於採用輸入排對設 計方式, 我們將面臨所謂的排頭問題(Head of Line Problem), 因此我們 提出兩種演算法(Algo- rithm)-貪婪法(Greedy Method)及交換向量法 (Switching Vector Method)-對封包進行排程(Schedule), 此兩種方法主 要是從單一傳輸 (Unicast)之排程方法改進而來,輸出衝突(Output Contention)能夠被排程方法解決, 但內部衝突(Internal Contention)卻 依然存在, 所以一個由Batcher-Banyan及BBN所組成, 叫做立方多層廣播 網路(Cube Multicast Network)被提出來, 在沒有輸出衝突情形下,解決 內部衝突的問題, 這個網路的設計是架構在立方位址編碼之無衝突特性上 。 評估一些模擬結果,交換向量法的表現比貪婪法要來的好, 本系統的最 大輸出量(Throughput)能達到 0.98。 There are several schemes proposed to provide multicast function in the ATM switching system. Those schemes can be classified into two main design approaches to duplicate cells. One employed multistage interconnection networks to duplicate cells, e.g. broadcast Banyan networks (BBN), while the other employed a shared buffer to duplicate cells. However, there are some disadvantages in the two design approaches. The requested copy number of the former design approach is con- strained by the switch size and the latter required advanced technique to speed up buffer access time. In this thesis, a new simple multicast switching architecture is proposed to achieve high performance. Our proposed architecture employs input queuing and the cube concept is introduced and used as the output address encoding scheme. We propose two algorithms, greedy and switching vector, to schedule cells. The output contention can be completely solved by our scheduling schemes, but the internal contention still exists. Hence, A tandem of a Batcher network, Banyan network and broadcast Banyan network, called cube multicast network, is also proposed to avoid in- ternal contention without any output contention. The design of cube multicast network is based on the blocking free property of the cube addressing scheme. Some simulations are evaluated and the throughput of the switch system can reach 0.98.