三級式 Clos 交換網路中的頻寬配置與多點放送聯結的尋徑

Abstract

在 ATM 網路的即時允入過程中，當由輸入埠到輸出埠之間存在著許多路 徑時，如何尋徑便成為一重要課題。在本論文中所探討的網路型態為三級 式 Clos 網路。選擇三級式 Clos 網路的原因是因為 Clos 網路是多種有 潛力的 ATM 交換機所選擇的網路結構，而且它的高連結性更提供了一嚴 格的尋徑測試。本篇論文包含兩大部分：第一部份是以頻寬配置的觀點來 對 Clos 網路中的單一放送聯結尋徑，而且探討的尋徑法共有六種，由文 中的結果顯示其中以循序搜尋法為最適合。除此之外，我們也設計了一個 簡單的系統控制機制以構成完整的設計。在第二部份中，我們以最低花費 為主要觀點設計並測試了三個在 Clos 網路上的多點放送聯結尋徑法，包 括一個最佳化方法與二個啟發式方法。最後並將上述的多點放送聯結尋徑 法應用於動態增加或減少放送目的點的尋徑上。 Routing is an issue if there are multiple paths from any input to any output in an ATM network that should perform connction admission control in real time. We focus on the 3-stage Clos network, not only because it is a candidate of large scale ATM switches, but also because its high connectivity poses a stringent test on routing algorithms. In this thesis, there are two parts: unicast routing and multicast routing in Clos networks. In the first part, we investigate six routing algorithms for unicast connections from the point of view of bandwidth allocation, and our results show that the sequential searching scheme is the one that spends least time and is easily implementable. Furthermore, we design an easy control scheme. In the second part, based on the measurement of minimum cost, we design and test three multicast routing algorithms including one optimum algorithm and two heuristic algorithms. Finally, we apply our proposed multicast routing algorithms to an environment where multicast connections are established via add-party/drop-party mechanism.