| Given the rapid increase in traffic, greater demands have been put on research in high-speed switching systems. Such systems have to simultaneously meet several constraints, e.g., high throughput, low delay and low complexity. This makes it challenging to design an efficient scheduling algorithm, and has consequently drawn considerable research interest. However, previous results either cannot provide a 100% throughput guarantee without a speedup, or require a complex centralized scheduler.;In this dissertation, we first design a scheduling algorithm with as low as a O(1) computation complexity for an input-queued switch, which is the first scheduling algorithm that can guarantee a 100% throughput with a computation complexity that does not depend on the size of the switch.;We also design a distributed 100% throughput algorithm for crosspoint buffered switches, called DISQUO, and a distributed algorithm for an input-queued hybrid optoelectronic switch, called LIOS. We prove that both DISQUO and LIOS can achieve 100% throughput for any admissible Bernoulli traffic, with a low time complexity of O(1) per port. To the best of our knowledge, they are the first distributed algorithms that can provide a 100% throughput without speedup. Simulation results also show that DISQUO can provide a good delay performance as compared to an output-queued switch.;To scale up the capacity and reduce power consumption, optical packet routers with less buffering and a greater degree of optical transparency are actively being researched as a way to improve energy efficiency and capacity scaling over traditional electronic routers. Since it is difficult to buffer packets in the optical domain, in this dissertation, we also analyze the performance of a hybrid optoelectronic packet router. The router architecture has multiple optical switch planes and a shared electronic buffer to resolve output-port contention. We run extensive simulations to evaluate the performance of the router. We show that the router can provide good throughput, with realistic on-off bursty traffic and asynchronous packet arrivals. |
