Research On Scalable Multi-stage Multi-plane Switching Networks And Scheduling Algorithms

With the rapid development of the Internet, the data volumes and the Internet applications have exponentially grown. Thanks to the maturity of dense wavelength division multiplexing(DWDM) technologies, the transimission capacity of transimission systems has been constantly increased, however, switching technologies, including switching architectures and scheduling algorithms, have been relatively lagged behind and have gradually become a performance bottleneck in communication networks. The single-stage switching fabric plays a vital role in the backbone router/switch, meanwile abundant research studies have emerged in the field. Thus, Crossbar fabric, as a representative of single-stage switching fabrics, has a stimulative effect on the development of switching architecture, but due to its implementational cost is rising with the square of switching capacity N, i.e., its poor scalability is a fatal weakness to the current Internet environment such that it is difficult to implement a large capacity switching architecture with this structure.Log2N and Clos switches are two different multi-stage switching fabrics, and both in topologies and routing properties are very different except for their well scalability. Therefore, these two architectures can be easily used to build a high-speed large-capacity switch fabric. Therefore, multi-stage multi-plane switch architectures(including log2 N, multi-log2 N, Clos, and multi-Clos) are the research focuses in this dissertation, the main studies and research findings we are investigating are:Analyzing single-stage switch fabrics(crossbar) and their scheduling algorithmsSingle-stage structures cannot cope with the rapid expansion of information volumns and diversity of Internet applications due to their poor scalability, but they are basic components to establish the other scalable switching architectures both from topologies and scheduling algorithms. Hence we first investigate various single-stage switch fabrics, such as OQ, IQ, and CIOQ and so forth, and the corresponding classical scheduling algorithms, such as PIM and iSLIP algorithms.Analyzing multi-stage switching fabrics, log2 N and multi-log2 N, and thecorresponding scheduling algorithmsFrom the topology point of view, adjacent stages of a log2 N switch are connected with partial connection(PC), which gives rise to the unique routing path(simple uniqueness). Two results produced by the uniqueness are: self-routing and internal blocking. The self-routing simplifies the routing control, while internal blocking degrades the switching performance. To eliminate the internal blocking, several log2 N networks are used to construct a multi-log2 N network with HC(horizontal cascading) or VS(vertical stacking) connection model so as to destroy the uniqueness. The HC version of multi-log2 N increases the network diameter and violates performance requirements of optical switching, so the VS version of multi-log2 N is the most important research subject in this dissertation. A control algorithm based on conflict link sets(CA-CLS) is proposed in this thesis to completely remove the internal blocking problem. However, there exists some switching elements(SE) shared by two optical lights in the optical switching, so optical crosstalk will be produced between these two lights inside the shared SE, and then the switching performance will be degraded dramatically. Therefore, another control algorithm based on multiple decomposition of a full permutation(CA-MDP) is proposed again, and its performance and effectiveness is elaborately analyzed as well.Analyzing the Clos and multi-Clos swiches and the corresponding schedulingalgorithmsThe Clos network is a multi-path one because its adjacent stages are connected with full connection(FC) model. A direct consequence of multi-path is that the routing control of the Clos network is more difficult than that of the log2 N network, but nonblocking switching structures, such as strictly nonblocking(SNB) and rearrangeable nonblocking(RNB), can be constructed with a proper configuration. Since the number of routing paths in a Clos network is completely determined by the number of central modules(CM) at the central stage(CS), the assignment problem of routing paths is equivalent to the assignment of CMs in a Clos network. Thus, a parallel routing dispatching algorithm based on matrix decomposition(PRD-MD) is presented in this dissertation. The PRD-MD algorithm adopts a row-by-row decomposition method, which is different from the existing decomposition way, to decompose any traffic matrices. It can not only cope with the assignment problem of CM without difficulty, but also successfully resolve the incompleteness of existing decomposition algorithms. In addition, another dispatching algorithm called CRRD-AG is proposed to solve the defects of the CRRD algorithm. The intent of CRRD-AG algorithm proposed is twofold: reducing the amount of arbitral information and utilizing sufficiently the bandwidth of CS. It is shown by simulations that CRRD-AG algorithm achieves 100% throughput under uniform traffic and bursty traffic, and the average delay performance of the whole switching system is also improved significantly without reducing the throughput of the switching system.The multi-Clos architecture has so high scalability that it is easy to enlarge the switching capacity by adding switching plane. The dissertation has proposed some basic thoughts about the multi-Clos switch based on the TrueWay. Although no research findings is worthy of publication at present, it has become our goal in the future research.