Architecture And Scheduling Algorithm For Large-Scale Packet Switching

As one of the most important equipments in Internet, router is an active topic of research areas in industry and academia. Due to the limitation of access rate of storage chips, current high-performance routers usually adopt switch fabric as their switching module. This paper focuses on the design and analysis of switch fabric, and corresponding scheduling algorithms.Low-rate buffer can be employed in Parallel Packet Switching to construct switch fabric with high speed and good scalability, which becomes a valuable scheme for the next generation high speed routers and switches. In this paper, an existed generalized parallel packet switch fabric is studied, and the disadvantage of high blocking probability is analyzed. Moreover, an improved parallel packet switch fabric is proposed based on the idea of Balanced Incomplete Block Design (BIBD), and the constructing procedure of the connecting function for this improved switch fabric is introduced. According to calculation, improved switch fabric can avoid relevant cells passing in the same path, and can greatly reduce the blocking probability.Input Queued scheduling has been of wide application in high performance routers, but the algorithm they utilize should be elaborately designed in order to achieve better performance. Because of the high throughput and ready implementation, the iSLIP (iterative SLIP) algorithm has received lots of attention, but its performance is poor when nonuniform and bursty traffic arrive. In this paper, a frame-based scheduling algorithm named iFONA (iterative Frame Or Not Algrithm) is proposed. Besides, a prioritized algorithm named iADT (iterative Algorithm with Dual Thresholds) is presented. Based on the simulation result, it is shown that both iFONA and iADT can not only greatly reduce the average cell latency when the bursty load arrives, but also maintain the same performance under uniform i.i.d traffic as iSLIP.