Research On High Performance Network Switch Fabrics And Scheduling Algorithms

With Internet traffic explosively increasing in the recent decades, the internet nodes, routers or switches for instance, are becoming the main restraining factors of developing high speed internet. As the physical core of a network node, Switch Fabric is required to be more flexible, better Quality of Service supporting and larger capacity. Therefore the research on new switch fabric structure and its scheduling algorithm with higher speed and better performance turn out to be the hotspots of network infrastructure. In this work, four key aspects of the research, which are "new type of high performance switch structure","low jitter scheduling algorithm","network coding for multistage switch" and "efficient contention scheduling scheme on optical switch ", have been studied and elaborately illustrated in the dissertation.So far output-queued switch is the fabric switch that meets most various QoS demands, although it is suffered from N times internal speedup issue, which can be avoided by using crossbar and buffered queue based switches. However, in such switches, only one packet can pass through the crossbar from input port to output port, which constrains the switch performance and further more limits the complexity of QoS demands. On the other hand, crosspoint-queued switch is the fabric switch that has the best performance. However since its crosspoint buffer is not as large as input buffer, the performance of crosspoint-queued switch under non-uniform traffic is much lower than that under uniform traffic. To solve this problem, a new load-balance crosspoint-queued switch is proposed. By adding a load-balance stage in front of crosspoint queued stage, it turns non-uniform traffic at input ports into uniform traffic at internal ports of crosspoint-queued stage. By this means the issue of non-uniform traffic is well settled while the high performance of crosspoint-queued switch is still kept. Nevertheless, adopting this new switch structure may cause another problem on out of order. Therefore an improved load-balance crosspoint-queued switch with virtual input queues is also proposed. It can keep the sequence of input packet using virtual queues at the crosspoint buffers.The most remarkable features of partial connected multistage switch structure are flexibility and internal simple routing, which make it very suitable for construction of modern optical switching network. However, due to the inherent internal switch path collision, its performance is suffered from packet loss. By the modern network coding method, this internal switch path collision problem can be emulated as a binary erasure channel on coding theory. Meanwhile bit errors on binary erasure channel can be corrected by a channel coding method. We proposed a redundant correcting coding scheme to improving the packet loss without disturbing the internal structure of partial connected multistage switch. Analysis and simulation both show that coding method can reduce the packet loss of partial connected multistage switch structure.Rapidly growing multimedia applications on Internet require more QoSs than the traditional Internet applications. Thus in the research work, not only quality of throughput, delay and packet loss but also transmitting jitter, which has import influence on network voice and video application, have to be concerned. The low jitter scheduling algorithm for combined input and crosspoint-queued switch needs to be improved as well as the nowaday frame and matrix decomposition based low jitter scheduling algorithms are far too complex for online scehduling. In this work, a hybrid lower jitter scheduling algorithm that can achieve low jitter performance with low complexity is proposed for combined input and crosspoint-queued switch. Then another optimization based algorithm with good jitter performance is also proposed for frame based scheduling.Based on Wavelength Division Multiplex (WDM), Modern Optical Packet Switch(OPS) system provides large switch capacity as well as saves costs. Thus it is very suitable for building the infrastructure of modern backbone switch network. Nevertheless, without optical buffers inside, traditional all-optical switch sufferes from packet loss due to the output wave length blocking, which can be avoided by applying a more efficient contention resolving algorithm. Current contention scheduling algorithms only give precedence to output wavelength distribution phrase, while it is unable to efficiently exploit the available wavelength as well as limited range converter. To improve this, a new wavelength-adjustable contention scheduling algorithm with better packet loss performance and throughput is proposed in this dissertation. It adjusts the pre-allocated output wavelengthes during wavelength converter scheduling phrase as well as effeciently consumes switch resources, output wavelengthes or wavelength converters for instance.