三階網路阻塞之研究

Abstract

三階寇露斯（Clos）網路已經廣泛三十年了，最早是將它應用在電話系 統上，而後人們亦把它應用在資料傳輸和多處理器（multiprocessor）的 架構上。在這些系統中，阻塞（blocking）是一定會存在且難以避免。在 這篇論文中，我們將探討在同步（synchronous）和非同步（ asynchronous）電路開關式的（circuit-switched）三階寇露斯網路上阻 塞之機率。 在同步電路開關式的三階寇露斯網路上，我們探討在均勻流 量模式（uniform traffic pattern model）上阻塞的機率，以及排列（ permutation）的問題。在排列問題上，我們提出分配（allocation）和 分割（division）兩種方法。 在非同步電路開關式的三階寇露斯網路上 ，我們分為無限（infinite）和有限（finite）服務時間（service time ）兩種模型。在無限服務時間的模型方面，我們提出窮舉（exhausted） 、樣本（sampling）和近似（approximation）等三種方法來計算阻塞機 率。在有限服務時間的模型方面，我們使用狀態圖（state diagram）法 來求得阻塞的機率。 我們知道要將所有造成阻塞狀態都皆列舉出來須耗 費大量的時間，故最後我們使用隨機樣本（random sampling）的技巧來 模擬阻塞的狀態，並算出阻塞之機率。並藉此模擬出來的阻塞機率來分析 三種路由（routing）演算法的效能。 Three-stage Clos networks have been the subject of extensive research over the last three decades. They were first introduced for use as telephone switching networks, but have since found applications in data communication and multiprocessor interconnection. In these systems, the blocking exists and is difficult to avoid. In this thesis, we study the blocking probability in synchronous and asynchronous, circuit- switched three-stage Clos networks. In synchronous circuit- switched three-stage Clos networks, we discuss the blocking probability in uniform traffic pattern model and the permutation problem. We propose allocation and division methods for the permutation problem. In asynchronous circuit-switched three- stage Clos networks, we divide theminto infinite and finite service time models. In infinite service time model, we propose exhausted, sampling and approximation methods to calculatethe blocking probability. In finite service time model, we use state diagram method to calculate the blocking probability. At last, we know the exhausted searches is not possible due to high time complexity. Therefore we use random sampling technique to choose partial admissible batches to do the simulation instead of mathematical calculation. According to the simulation we know the performance among the P, MI and STU routing algorithms.