Practical scheduling algorithms in packet switches

Scheduling algorithms are used in switches and routers to provide a wide range of Quality of Services (QoS) for integrated services packet network. In switch designs, scheduling algorithms are directly related to the performance, the complexity of design, and the cost. This dissertation discusses the design, analysis, and performance of practical scheduling algorithms. Not only the QoS but also the scalability, complexity, and efficiency of switches are used as metrics.; For an output-queued switch, the main challenge is to build a large capacity switch because of the limitation of memory bandwidth. One common solution is to use scalable output-queued switches. Using the proposed scalable output-queued switch architectures and a sorted-priority scheduler design, we show that a practical implementation of a large capacity output-queued switch is to build a network of multiple smaller output-queued switches. We also discuss the performance and implementation tradeoffs of proposed scalable output-queued switch architectures.; In a combined input-output queued switch, the complexity of segmentation of packets at input ports and reassembly at output ports is a main concern. A combined input-output queued switch using crossbars can be designed to avoid the segmentation/reassembly process. However, the crossbar arbitration must be able to work with variable-length packets to maintain fairness among all Virtual Output Queues (VOQ). We propose a scheduling algorithm called Self-Optimized Latency that can be used in a crossbar arbitration to provide the fairness for all VOQs so that the segmentation/reassembly process can be eliminated.; Finally, we propose an efficient frame-based scheduling algorithm called Credit Round Robin. Performance analysis of Credit Round Robin shows that it provides a fine-granularity bandwidth with lower latency and better fairness compared to Deficit Round Robin [35] with the same complexity.