Research On High Speed Switching Technology Based On Load Balanced Switch Architecture

The background of this PhD thesis is the activities towards NGI (Next Generation Internet) and the work presented in this thesis is based on the research projects of SUPA (Single-layer User-data switching Platform Architecture) sponsored by NSFC. In the past, Internet has been facing with ever-growing challenges from application requirements, deteriorated operation environment, as well as from technique advances such as in wired and wireless communications. It has been gradually recognized by network communities since2005that the paramount task of NGI is to develop clean slate network architecture, which involves new conceptual model, functional organization, and new technologies. This thesis is devoted to new switching techniques and switch fabric, which are capable of dealing with high transmission capacity per port/lambda and modern network traffic patterns in backbone switches.Having analyzed existing switching techniques and switch fabric, the author has devoted his efforts to a special type of switching technique called LB (Load-Balancing) switching for its low average delay in heavy load and bursty traffic. LB-BvN (Load Balanced Birkhoff-von Neumann switch architecture), which consists of two stage crossbars, has shown potentials in meeting requirements of high-speed switching in future NGI environments and thus drawn much attention. Due to the deterministic and periodic connection patterns of the two crossbars, LB-BvN switch can ruled out the effects of scheduling algorithm on the length of timeslot. With respect to a fixed-length packet, the length of time slot is only concerned with the port rate, and it means that the switching rate can be increased to be the utmost limits of the microelectronics technology, even the limits of the optical communication technology. Obviously, it provides the possibility for the high-speed switching. On the other hand, packets from the same flow can be distributed to the central buffers in a uniform manner by its first-stage crossbar, therefore the LB-BvN switch can well adapted to the bursty traffic.Although the load balanced switch architectures can well meet the requirements of the future switching, they has a fatal flaw that packets from the same flow may be out-of-sequence. Several schemes have been proposed to solve this problem; however, the existing schemes are far from ideal, they have an extravagant complexity or a poor performance. If the computation complexity for scheme to solve the out-of-sequence problem is higher than O(1), the whole switching process must be sluggish and the high-speed switching capacity of LB-BvN must be damaged. On the other hand, the lopsided stress on the O(1) complexity over the whole switching process is also advisable.In order to solve the problems in the load balanced switch architectures, this dissertation proposed a series of schemes.O(1) complexity throughout the whole switching process and better performance are the primary restraint of all the research. The main contents and the conclusions in this dissertation are as flows:(1) This dissertation proposed a load balanced switch architecture named SLBA (Smart Load Balanced switch Architecture), which has O(1) complexity throughout the whole switching process. The SLBA switch consists of two stages and the input of the second stage calculates an MWT-WTP (Minimal Waiting Time Without Taking over the previous Packets of the same flow), which will be used by the SOM (Smart Order Maintenance) mechanism to enable packets to be delivered out of switch in an earliest time without disordering. Consequently, the computational complexity and out-of-sequence problems are thus solved. Both theoretical analysis and simulation results show that the SLBA switch is stable under any traffic conditions and has a better performance in light loaded condition compared with the Byte-Focal switch.(2) To futher improve SLBA switch to avoid extra communication between the switch fabric and the linecards, this dissertation proposed CFSB (Combine Flow Splitter with Byte-Focal), which can fully take the advantages of flow splitter and the VCQ (Virtual Central Queuing). Both theoretical analysis and simulation results show that the CFSB switch is stable under any traffic conditions with better performance compared with the Byte-Focal switch.(3) There is a miner drawback of CFSB switch, that sequence of cells arrive at the first-stage crossbar may not be maintained when entering the buffers at second-stage crossbar. To solve this problem, this dissertation proposed a novel switch fabric with LB-IFS (Load Balanced switch architecture based on Implicit Flow Splitter), which enable the packets of the same flow to be forwarded without disordering by a combination of IFS(Implicit Flow Splitter) with the DBM (Double-Buffering Mode). The LB-IFS switch has a better performance than CFSB while remaining the same processing complexity.(4) FTSA (Feedback-based Two-stage Switch Architecture) switch has complexity problem and imposes restrictions for the scheduling algorithms in practice, although some simulation results have shown excellent performance. This dissertation tries to solve its probles by extending the time space of the algorithm usable for the FTSA switch and to reduce the complexity and processing time. Author's DFTS (Double-Feedback-based Two-stage Switch architecture) enables scheduleing time being extended to approach a full timeslot by introduction of DFM (Double Feedback Mode). (5) The author's PB-EDF (Priority Bitmap-based Earliest Departure First), on the other hand, reduces complexity of existing scheduling algorithm to O(1) by combination of the PBA (Priority Bitmap Algorithm) of the with EDF (Earliest Departure First) algorithm for FTSA switch.(6) DFTS and PB-EDF cannot be combined into one switch although each of them has partially solved some of problems. The author has found an alternative approach to them by introduction of FFTS (Front-Feedback-based Two-stage Switch architecture) although its performance is a little bit lower than FFTS. Finally, the author has further extended the processing time for scheduling by FTSA-2-SS (FTSA using2-Staggered Symmetry connection pattern) with a new connection mode called2-SS (2-Staggered Symmetry connection pattern). Theoretical analysis has shown that delay of FTSA-2-SS is equivalent to FFTS under the same switching environment.The work presented in this thesis provides a comprehensive study to LB-based switching techniques and switch fabrics and the author's improvements to existing techniques have been shown superiority over existing ones through both theoretical proof and simulation results.