Switches and routers play important roles in providing high performance network service to end users. With the ever increasing demand for higher bandwidth and better service, it has become a more and more challenging task to design efficient scheduling algorithms for high performance switches. Based on the locations to buffer blocked packets, packet switches can be divided into several different categories: output queued (OQ) switches, input queued (IQ) switches, combined input-output queued (CIOQ) switches, and buffered crossbar switches.

In this dissertation, we design a series of efficient scheduling algorithms for different types of packet switches, analyze their performances, and discuss implementation issues. Firstly, for IQ switches, we propose a general method to convert traditional three step iterative matching algorithms to two step algorithms, which have implementation advantages and maintain identical performances. We theoretically prove the average convergence iteration number for iterative matching algorithms, and show by simulation that it is more accurate than the classical result. On the other hand, to efficiently buffer multicast packets in IQ switches, we present a novel queue structure by separately storing the address information and data information of a packet. In conjunction with the new multicast queue structure, we design a first-in-first-out based multicast scheduling algorithm called FIFO Multicast Scheduling (FIFOMS), which achieves low latency and high throughput for multicast traffic. Secondly, in order to apply two step algorithms to CIOQ switches, we propose a pipeline scheme called Second of Line (SOL) matching. It makes two scheduling decisions in every time slot without extra scheduling time or arbitration hardware. Any two step iterative matching algorithm can be efficiently pipelined with the proposed scheme, and furthermore achieves 100% throughput for any admissible traffic. Thirdly, for buffered crossbar switches, we propose the Localized Asynchronous Packet Scheduling (LAPS) algorithm that schedules variable length packets without segmentation-and-reassembly. It has the nice property to guarantee 100% throughput for any admissible traffic, as well as many implementation advantages. Finally, we consider how to fairly allocate bandwidth in packet switches to facilitate performance guarantees. We formulate the problem based on the max-min fairness principle, and present solution algorithms for unicast traffic and multicast traffic, respectively. The proposed algorithms are universally applicable to any type of switches and scheduling algorithms.