Abstract
現今, 由於寬頻整合式服務如隨選視訊和多媒體通訊等應用的快速發展, 高效能的非同步傳輸模式封包交換技術已成為快速傳送資訊不可或缺的網 際網路之互連基礎架構。近年來有相當多的快速封包交換架構發表,諸如 Knockout交換網路, Banyan為主之交換網路, 或記憶體共享式交換網路等 皆是。在這些交換架構中, 本文將針對以空間區分為主的交換網路做進一 步的研究, 探討自設路徑式技術在設計時是否具有平行處理的可行性, 同時評估交換網路是否具有良好的擴充特性, 可用來設計大型的交換網路 系統。在本文中, 我們提出一個具有連線分享式設計與擴大連線數特性 之 Banyan網路架構為主之多級互連式網路; 在封包目的地為隨機分配和 全載輸入流量分析中, 新提出的交換架構在封包交換遺失機率和整體交換 網路封包流通量兩方面的表現皆相當趨近於Knockout網路的封包交換遺失 機率和流通量。本文同時針對新交換架構的設計與實作做深入的分析和探 討。更重要的是, 在使用大型積體電路技術的實作上, 更能實際驗証新交 換架構不但保有極短的自設路徑線路延遲特性, 而且在交換架構設計中具 有很好的模組化與擴充特性; 三種交換模組即可用來組合任一大小的交換 網路而不受硬體技術的限制。最後本文提出一新的集中器自設路徑平行處 理線路, 稱為緊密路徑設定方法, 採用此新方法可使整個交換網路的自設 路徑線路延遲與一個標準的Banyan網路完全相同。另外, 本文針對新交換 架構提出一容錯設計, 交換架構的連線分享式設計線路同時可被修改成提 供備用路徑的線路使用, 根據分析結果証明出修改後的容錯線路可提供單 一線路故障之容錯設計和發生多個線路故障時提供交換架構的健全特性。 Nowadays, because of the rapid development of high-bandwidth integrated services such as video on demand and multimedia communications, the high-performance cell switching technologies are becoming the internetworking infrastructure for transferring all kinds of information in high-speed. Recently, a great deal of researches have focused on constructing high-speed cell switching architectures such as Knockout switch, banyan-based switch, shared medium, or share memory switches. In these architectures, we will discuss the space division switches for exploring their self-routing mechanisms to design high-speed switching circuits in parallel and evaluating their scalable capability of switch architectures to design large switch systems. In this dissertation, a dilated banyan-based multistage interconnection network with shared link design is proposed. The cell switching loss probability and throughput performance of the new approach has the approximate results as those of Knockout switch under uniform traffic and full offered load. We also discuss and explore their design and implementation issues. Moreover, the whole switch fabric design is realized by VLSI technologies. It demonstrates that our approach not only has very short self- routing delay, but also has very good modularity and scalability on design switching systems. Three kinds of switch modules are enough to construct a large switch without any fundamental limitation by the hardware technology. Finally, a new fastest self-routing mechanism called compact routing scheme is used to design concentrators such that the self- routing delay of our switching architecture has the same as that of a regular banyan switch. In addition, a fault-tolerant design for our switching architecture is proposed. The shared link design is modified to provide redundant paths. The analytical results show that the fault-tolerant design provides fault tolerance for any single failure and robust in the presence of multiple faults.