With the recent emergence of optical technology, the line capacity has increased to an extremely high speed. As a result, switches and routers are becoming bottlenecks of the Internet since the speed of scheduling algorithms of switches and routers does not keep pace with the high line rate. On the other hand the number of users of the Internet increases exponentially. Input queued switches with crossbar switch fabrics require only a memory bandwidth of two times the line speed. Thus they are suitable for the design of high performance switches and routers. However the design of scheduling algorithms for input queued switches is still a challenging issue. With regard to the design of an appropriate scheduling algorithm for high performance switches and routers, we have to consider vario...[ Read more ]

With the recent emergence of optical technology, the line capacity has increased to an extremely high speed. As a result, switches and routers are becoming bottlenecks of the Internet since the speed of scheduling algorithms of switches and routers does not keep pace with the high line rate. On the other hand the number of users of the Internet increases exponentially. Input queued switches with crossbar switch fabrics require only a memory bandwidth of two times the line speed. Thus they are suitable for the design of high performance switches and routers. However the design of scheduling algorithms for input queued switches is still a challenging issue. With regard to the design of an appropriate scheduling algorithm for high performance switches and routers, we have to consider various measures such as packet delay, throughput, stability and scalability, etc.

In this thesis, we investigate various scheduling algorithms for input queued crossbar-based switches, including maximum weight matching scheduling algorithms, maximal size matching scheduling algorithms and randomized matching algorithms. Both advantages and disadvantages of those algorithms are explored. We then propose a wide class of stable scheduling algorithms which achieve a good delay performance and simple hardware implementation. After that, we study more practical scheduling algorithms which are appropriate for switches with large port numbers (> 64). Since our goal is to design scalable switches and routers in terms of both line speed and port size to meet the trend of today's Internet development, we propose a novel scalable scheduling architecture which considers both efficiency and the cost of implementation. Distributed parallel arbitration algorithms are proposed for this scheduling architecture, which both achieve a good performance and are practical. The novel scalable scheduling architecture is suitable for multicast scheduling as well as unicast scheduling. Considering that real traffic is composed of both unicast and multicast traffic, we also propose an integrated scheduling algorithm to combine unicast scheduling with multicast scheduling for this scalable scheduling architecture.