Study On Some Key Technologies Of High Speed Multi-stage Packet Switching Fabrics

With the explosive growth of Internet traffic and the rapid development of broadband optical transmission technologies, network nodes have gradually become a bottleneck in Internet development. Switch fabric, as the core component of a node, has been becoming one of hotspots in network research . Single-stage crossbar, as the dominating switch fabric in core routers, is quite abundant in its research achievements.However, because of engineering constraints (rack power supply, chip size, etc.), it is not easy to achieve a large switch capacity. To build large-capacity packet switching networks, multi-stage switch fabric is a commonly used means. Direct interconnection network and indirect interconnection network are two main topologies of space-division multi-stage switch fabric. Although direct interconnection networks possess good scalability, their unpredictable performance limits them only available in the early days of large-capacity router research. Indirect interconnection networks are becoming the research focus. The current research methods for indirect interconnection networks (such as three-stage clos networks, parallel packet switch (PPS), two-stage switch network, etc) in literatures are simple extension from those for single-stage crossbar, which are centralized control methods in essentce. These methods have problems of their own, such as difficulty in realization, unpredictable performance, and not full availability of predominance in topology of multi-stage switch fabric, etc. In this thesis we investigate the key technologies of high-speed packet switching multi-stage indirect interconnection networks to try to resolve the problems mentioned above. The main work and contributions are as follows.1. Distributed scheduling scheme in multi-stage switch faric is proposed.According to different roles of switch units in multi-stage switch fabrics, they are divided into load balancing stage of units and scheduling stage of units within which the control on switch is achieved through load balancing strategy and scheduling strategy respectively. Therefore, the scheduling problem of multi-stage indirect interconnection networks is decomposed into two subproblems of load balancing and scheduling within switch units, thus it has the following advantages: (1) the realization of a fully distributed algorithm makes it convenient for multi-rack implementation. The control information exchange between stages of switch units and between ones within each stage of switch unit is avoided because the traffic load within scheduling stage of switch units is coordinated through the load balancing stage of switch units in distributed scheduling scheme. (2) This scheme has a good inheritance. In our distributed scheduling scheme proposed, the scheduling within scheduling stage of switch units is similar to the one within single-crossbar switch fabrics, and therefore the research results of single-crossbar switch fabric available can be directly used for reference. (3)This scheme is simple in implementation and convenient for algorithm performance analyses and control. . 2. The resource requirements of guaranteeing performance in the distributed scheduling in three-stage Clos networks are analyzed. It is shown that they are the least resource demand. The out-of-sequence of cells is one of primary problems that distributed scheduling in three-stage Clos networks may be confronted with. A new distributed scheduling algorithm called LDVSA (Load Dispatched and Volleyed Scheduling Algorithm) is proposed. Further analysis shows that the algorithm can keep cells in sequence and also possess good performance.3. Based on a simple distributed scheduling algorithm called RRBSA(Round-Robin Balanced Scheduling Algorithm), switching mechanisms of distributed scheduling in three-stage Clos networks have been studied. The research results show that both fixed length cell switching mechanism and variable length packet switching mechanism have their own limitations. So we propose a new mixed switching mechanism which combines the advantages of the two switching mechanisms mentioned above. The mixed mechanism achieves load balancing on a granularity of variable length packet thus keeping cells in sequence, on the basis of which a new token scheme is adopted to guarantee the fairness of load balancing. In addition, fixed length cell is employed in the later two stages of Clos networks to accommodate various types of traffic. Final results indicate that the mixed switching mechanism is proper for the distributed scheduling in three-stage Clos networks.4. After the analysis of various faults of three-stage Clos networks, a fault model suitable for distributed scheduling in three-stage Clos networks is presented. Also, according to the affects of network faults on different input queues in input stages, a new distributed fault tolerance scheduling algorithm is put forward. At the same time, its method and capability of fault tolerance are analyzed. Results indicate that the algorithm has good fault-tolerance performance.5.Distributed scheduling scheme is introduced into two kinds of multi-stage switch fabrics having been received many studies, including PPS(Parallel Packet Switching) and two-stage switch fabric, and thus their research deficiencies are overcome. The distributed scheduling algorithms in three-stage Clos networks are further simplified due to the unification of two-stage networks and three-stage Clos networks under distributed scheduling scheme. Using the study achievements in this thesis to build switch networks with ultra-large capacity (over 100Tb/s) can realize a switch fabric whose maximum capacity reaches up to 655.36Tb/s, much higher than the level of existing research results.6. A new type of switch fabric called MR (Magic Ring) is proposed. The fabric is a new three-stage indirect interconnection network with good scalability. With the introduction of ring network having the characteristics of direct interconnection networks in middle stage of switch network and of subtle connection relations between stages of switch networks, the new fabric overcomes the weakness in scalability of traditional indirect interconnection networks.