Researches On & Implementation Of The Scheduling Policy In High-speed Routers

People bring forward more requirements on routers processing ability, switching capacity and throughput as the fast development of Internet to higher speed and broader band. On the one hand, routers must sustain the link rate which grows faster and faster, and on the other hand, they have to offer some kinds of Quality of Service. Switch architecture and scheduling algorithm are key points which limit the performance of router. This dissertation is devoted to the researches of the theory and implementation of high speed scheduling from the point of switching model's view according to the requirements of 863 Terabit router project. Based on the analysis and comparison of scheduling algorithm in existence, we emphasize on parallel packet switch architecture and analyze the sufficient and necessary conditions for its stable working, propose a two-stage distributed shared memories architecture and investigate the implementation of these two structures in Terabit router project. The main work of this dissertation is as follows:The problem of current scheduling scheme is pointed out and current scheduling algorithms are classified and compared from the point of switching model's view, and most studies in this field are summarized. We emphasize on the analysis of the emerging hotspot of the current research for the new direction and methods.Stable working for Parallel packet switch (PPS) is defined based upon reference switch and inventory theory. Then the necessary and sufficient conditions of stable working and algorithm for traffic dispatch for bufferless and buffered PPS are analyzed. Moreover, the minimum of layers and internal speedup of PPS for stable working are given. These results afford a good reference for engineering design.We proposes a two-stage distributed shared memory architecture (TSDSM) based on distributed shared memory architecture (DSM). The lower bound of it is also given. Scheduling algorithms for a TSDSM imitating a FCFS output-queued (OQ) switch and a FIFO OQ switch are given too. The feasibility of these algorithms is theoretically proved and an engineering simplified design of this algorithm is given. Without being speed up, the TSDSM can be used to realize high speed packet switch with commercially available memories.Based on the forementioned analysis and according to the requirements of 863 Terabit router project and other factors, we present a scheme of implementing the port switching module in terabit router system. It is implemented with six layer PPS architecture and every layer is implemented with the engineering simplified design of TSDSM. The throughput of this module is 160 Gbps.